87 citations · 305 across the 39 of their papers we have counts for
12 papers · 1 filter
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of \emph{testable learning}, where the goal is to replace hard-to-verify distributional assumptions (…
Memory-Sample Lower Bounds for Learning Parity with Noise
Sumegha Garg, Pravesh K. Kothari, Pengda Liu +1
In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn from a stream of random linear…
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov +1
We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being…
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes
Pravesh K. Kothari, Roi Livni
We study the expressive power of kernel methods and the algorithmic feasibility of multiple kernel learning for a special rich class of kernels. Specifically, we define \emph{Eucli…
Efficient Algorithms for Outlier-Robust Regression
Adam Klivans, Pravesh K. Kothari, Raghu Meka
We give the first polynomial-time algorithm for performing linear or polynomial regression resilient to adversarial corruptions in both examples and labels. Given a sufficiently la…
An Analysis of the t-SNE Algorithm for Data Visualization
Sanjeev Arora, Wei Hu, Pravesh K. Kothari
A first line of attack in exploratory data analysis is data visualization, i.e., generating a 2-dimensional representation of data that makes clusters of similar points visually id…