73 citations · 347 across the 51 of their papers we have counts for
16 papers · 1 filter
Sparse Linear Regression is Easy on Random Supports
Gautam Chandrasekaran, Raghu Meka, Konstantinos Stavropoulos
Sparse linear regression is one of the most basic questions in machine learning and statistics. Here, we are given as input a design matrix and meas…
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis +2
In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on -- is to output a hypoth…
Simple Mechanisms for Representing, Indexing and Manipulating Concepts
Yuanzhi Li, Raghu Meka, Rina Panigrahy +1
Supervised and unsupervised learning using deep neural networks typically aims to exploit the underlying structure in the training data; this structure is often explained using a l…
On User-Level Private Convex Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
We introduce a new mechanism for stochastic convex optimization (SCO) with user-level differential privacy guarantees. The convergence rates of this mechanism are similar to those…
Learning Narrow One-Hidden-Layer ReLU Networks
Sitan Chen, Zehao Dou, Surbhi Goel +2
We consider the well-studied problem of learning a linear combination of ReLU activations with respect to a Gaussian distribution on inputs in dimensions. We give the first…
Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
Sitan Chen, Aravind Gollakota, Adam R. Klivans +1
We give superpolynomial statistical query (SQ) lower bounds for learning two-hidden-layer ReLU networks with respect to Gaussian inputs in the standard (noise-free) model. No gener…