53 citations · 420 across the 50 of their papers we have counts for
32 papers · 1 filter
Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Recent work has shown the surprising power of low-degree sandwiching polynomial approximators in the context of challenging learning settings such as learning with distribution shi…
Learning Juntas under Markov Random Fields
Gautam Chandrasekaran, Adam Klivans
We give an algorithm for learning juntas in polynomial-time with respect to Markov Random Fields (MRFs) in a smoothed analysis framework where only the external field h…
The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
Adam R. Klivans, Konstantinos Stavropoulos, Kevin Tian +1
Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial filtering and show a number of striking applica…
Does Generation Require Memorization? Creative Diffusion Models using Ambient Diffusion
Kulin Shah, Alkis Kalavasis, Adam R. Klivans +1
There is strong empirical evidence that the state-of-the-art diffusion modeling paradigm leads to models that memorize the training set, especially when the training set is small.…
Testing Noise Assumptions of Learning Algorithms
Surbhi Goel, Adam R. Klivans, Konstantinos Stavropoulos +1
We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has…
Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
Gautam Chandrasekaran, Adam Klivans
We consider the fundamental problem of learning the parameters of an undirected graphical model or Markov Random Field (MRF) in the setting where the edge weights are chosen at ran…
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…
Agnostically Learning Single-Index Models using Omnipredictors
Aravind Gollakota, Parikshit Gopalan, Adam R. Klivans +1
We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All prior work either held only in the realizable s…
One-Dimensional Deep Image Prior for Curve Fitting of S-Parameters from Electromagnetic Solvers
Sriram Ravula, Varun Gorti, Bo Deng +7
A key problem when modeling signal integrity for passive filters and interconnects in IC packages is the need for multiple S-parameter measurements within a desired frequency band…
Ambient Diffusion: Learning Clean Distributions from Corrupted Data
Giannis Daras, Kulin Shah, Yuval Dagan +3
We present the first diffusion-based framework that can learn an unknown distribution using only highly-corrupted samples. This problem arises in scientific applications where acce…
Tester-Learners for Halfspaces: Universal Algorithms
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time…
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…
An Efficient Tester-Learner for Halfspaces
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023). In this model, a learner certifies t…
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 (…
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…
Efficiently Learning Any One Hidden Layer ReLU Network From Queries
Sitan Chen, Adam R Klivans, Raghu Meka
Model extraction attacks have renewed interest in the classic problem of learning neural networks from queries. In this work we give the first polynomial-time algorithm for learnin…
Tight Hardness Results for Training Depth-2 ReLU Networks
Surbhi Goel, Adam Klivans, Pasin Manurangsi +1
We prove several hardness results for training depth-2 neural networks with the ReLU activation function; these networks are simply weighted sums (that may include negative coeffic…
Learning Deep ReLU Networks Is Fixed-Parameter Tractable
Sitan Chen, Adam R. Klivans, Raghu Meka
We consider the problem of learning an unknown ReLU network with respect to Gaussian inputs and obtain the first nontrivial results for networks of depth more than two. We give an…
From Boltzmann Machines to Neural Networks and Back Again
Surbhi Goel, Adam Klivans, Frederic Koehler
Graphical models are powerful tools for modeling high-dimensional data, but learning graphical models in the presence of latent variables is well-known to be difficult. In this wor…
Statistical-Query Lower Bounds via Functional Gradients
Surbhi Goel, Aravind Gollakota, Adam Klivans
We give the first statistical-query lower bounds for agnostically learning any non-polynomial activation with respect to Gaussian marginals (e.g., ReLU, sigmoid, sign). For the spe…
Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
Surbhi Goel, Aravind Gollakota, Zhihan Jin +2
We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent. We show that any classifier…
Approximation Schemes for ReLU Regression
Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar +2
We consider the fundamental problem of ReLU regression, where the goal is to output the best fitting ReLU with respect to square loss given access to draws from some unknown distri…
Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
Mao Ye, Chengyue Gong, Lizhen Nie +3
Recent empirical works show that large deep neural networks are often highly redundant and one can find much smaller subnetworks without a significant drop of accuracy. However, mo…
Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
Surbhi Goel, Sushrut Karmalkar, Adam Klivans
We consider the problem of computing the best-fitting ReLU with respect to square-loss on a training set when the examples have been drawn according to a spherical Gaussian distrib…