Proves SQ lower bounds for learning two-hidden-layer neural networks.
problem Learning two-hidden-layer ReLU networks with Gaussian inputs.
method Refined lifting procedure to reduce Boolean PAC learning to Gaussian.
result Superpolynomial SQ lower bounds for Gaussian inputs.
Optimal SQ bounds for learning binary product distributions and Ising models.
problem Learning binary product distributions and Ising models robustly.
method Statistical Query (SQ) lower bounds for robust learning.
result Optimal SQ lower bounds match known algorithm error guarantees.
New SQ lower bounds for NGCA without requiring chi-squared condition.
problem Proving SQ hardness for NGCA under moment-matching conditions.
method General SQ lower bound methodology applied to NGCA under moment-matching conditions.
result Proved near-optimal SQ lower bounds for NGCA without chi-squared condition.
New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.
problem Learning mixtures of Gaussians with bounded covariance matrices is hard.
method Statistical Query (SQ) lower bounds.
result Any SQ algorithm requires complexity at least d Ω ( 1 / ε ) d^{Ω(1/ε)} d Ω ( 1/ ε ) for learning mixtures of bounded covariance Gaussians. The study sets limits on how well halfspaces can be learned when labels are corrupted.
problem Learning halfspaces in the presence of Massart noise.
method Statistical query (SQ) lower bounds.
result No SQ algorithm can achieve misclassification error better than the corruption rate η η η with superpolynomial accuracy or a superpolynomial number of queries. Optimized Franz-Parisi criterion matches SQ lower bounds for various statistical models.
problem Understanding computational hardness in statistical inference.
method Proposed and refined Franz-Parisi criterion, established equivalence with SQ lower bounds.
result Optimized Franz-Parisi criterion is equivalent to Statistical Query (SQ) lower bounds.
Statistical Query lower bound shows difficulty in list-decodable linear regression.
problem List-decodable linear regression with adversarial corruption.
method Statistical Query (SQ) lower bound analysis.
result Lower bound of d p o l y ( 1 / α ) d^{\mathrm{poly}(1/α)} d poly ( 1/ α ) for list-decodable linear regression. New bounds show complex neural networks need many queries to learn.
problem Learning non-polynomial activation functions with Gaussian marginals.
method Gradient boosting procedure to amplify lower bounds on SQ dimension of neural networks.
result Statistical-query lower bounds for ReLU regression with 2 n c ε 2^{n^c} ε 2 n c ε queries. Study shows SQ lower bounds for learning ReLUs with Massart noise.
problem Learning a single neuron in the presence of Massart noise.
method Statistical Query (SQ) lower bounds for efficient learning algorithms.
result No efficient SQ algorithm can approximate the optimal error within any constant factor.
Lower bound shows super-polynomial gap for estimating truncated Gaussian means.
problem Estimating mean of truncated Gaussian distribution with limited samples.
method Statistical Query (SQ) lower bounds for learning.
result Super-polynomial information-computation gap for the task.
Paper solves k-sparse parity problem with sign SGD, matching SQ lower bound.
problem Solving k-sparse parity problems efficiently.
method Sign stochastic gradient descent on neural networks.
result Matches Statistical Query lower bound for solving k-sparse parity problems.
The study establishes SQ lower bounds for learning halfspaces and ReLUs under Gaussian marginals.
problem Agnostically learning halfspaces and ReLUs under Gaussian marginals.
method Statistical Query (SQ) lower bounds analysis.
result Proves SQ lower bounds of d p o l y ( 1 / ε ) d^{\mathrm{poly}(1/ε)} d poly ( 1/ ε ) for both problems. Tensor PCA problem analyzed with statistical query lower bounds.
problem Estimating the expected value of a rank-1 tensor from Gaussian samples.
method Sharp analysis of optimal sample complexity in the Statistical Query model.
result SQ algorithms with polynomial query complexity fail in the conjectured hard phase and have sub-optimal sample complexity.
New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.
problem Smoothed agnostic learning of halfspaces under subgaussian distributions.
method Statistical Query (SQ) lower bound using moment-matching hard distribution and linear programming duality.
result First non-trivial lower bound on complexity nearly matches known upper bound.
Lower bounds show learning mixtures of linear classifiers is nearly impossible.
problem Learning mixtures of linear classifiers under Gaussian covariates.
method Statistical Query (SQ) lower bounds and new spherical designs.
result Complexity of any SQ algorithm is \( n^{\mathrm{poly}(1/Δ) \log(r)} \), where Δ is the pairwise \(\ell_2\)-separation.
Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is O ( d / ε + d / ( max { p , ε } ) 2 ) O(d/ε + d/(\max\{p, ε\})^2) O ( d / ε + d / ( max { p , ε } ) 2 ) , SQ lower bound is Ω ( d 1 / 2 / ( max { p , ε } ) 2 ) Ω(d^{1/2}/(\max\{p, ε\})^2) Ω ( d 1/2 / ( max { p , ε } ) 2 ) . Study shows SQ hardness for multiclass linear classification with random noise.
problem Complexity of multiclass linear classification with random noise.
method Proves super-polynomial SQ lower bounds for MLC with RCN.
result Super-polynomial SQ lower bounds for MLC with RCN.
Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning with statistical queries, and Littlestone dimension characterizes online learning. In this paper we aim to develop combinatorial dimensions th…
Unified approach for quantum and classical learning from evaluation oracles.
problem Learning from evaluation oracles in quantum and classical settings.
method Inspired by Kearns' SQ and Valiant's weak evaluation oracle, a unified framework is established.
result Characterizes query complexity for learning linear function classes and extends learnability results for quantum circuits.
Improved efficient robust regression with near-linear time and subquadratic samples.
problem Robust linear regression with unknown covariance matrix under Gaussian covariates.
method Near-linear time algorithm using subquadratic samples, complemented by SQ and polynomial lower bounds.
result Achieves prediction error O ( ε κ ) O(\sqrt{εκ}) O ( ε κ ) for ε κ ≲ 1 εκ\lesssim 1 ε κ ≲ 1 , improving over prior works. Near-optimal SQ hardness shows learning halfspaces with Massart noise is hard.
problem Learning halfspaces with Massart noise in the presence of label corruption.
method Statistical Query (SQ) model analysis.
result No efficient SQ algorithm can achieve better than Ω ( η ) Ω(η) Ω ( η ) error, even for optimal noise levels. Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
Gradient descent fails to learn simple neural networks efficiently.
problem Learning one-layer neural networks efficiently using gradient descent.
method Gradient descent and statistical query algorithms.
result Superpolynomial lower bounds for learning one-layer neural networks.
We study the complexity of training neural network models with one hidden nonlinear activation layer and an output weighted sum layer. We analyze Gradient Descent applied to learning a bounded target function on n n n real-valued inputs. We give an agnostic learning guarantee for GD: starting from a randomly initialized …
New algorithm for learning mixtures with mostly uniform weights, improving on previous bounds.
problem Learning mixtures of Gaussians with uniform weights and mostly uniform component weights.
method Statistical Query (SQ) lower bound and quasi-polynomial upper bound for testing.
result Quasi-polynomial upper bound for testing mixtures with mostly uniform weights.
New algorithms learn multi-index models via harmonic analysis, achieving statistical and computational trade-offs.
problem Learning multi-index models with unknown projections of input data.
method Exploiting the equivariance of the problem under the orthogonal group, we derive lower bounds and construct spectral algorithms based on harmonic tensor unfolding.
result Achieve statistical and computational trade-offs between sample and runtime complexity.
Gradient descent can efficiently learn a target function with diverse and near-orthogonal features.
problem Learning a target function with additive structure and diverse features.
method Gradient descent training of a two-layer neural network.
result A large subset of polynomial target functions can be efficiently learned.
New algorithm learns disjunctions faster than previous methods.
problem Learning Boolean disjunctions in the agnostic PAC model.
method Developed an agnostic learner with complexity 2 i l d e O ( n 1 / 3 ) 2^{ ilde{O}(n^{1/3})} 2 i l d e O ( n 1/3 ) . result First separation between SQ and CSQ models in distribution-free agnostic learning.
New algorithm for learning ReLU networks with Gaussian noise, improving previous results.
problem PAC learning one-hidden-layer ReLU networks with Gaussian marginals and label noise.
method First polynomial-time algorithm for k k k up to i l d e O ( log d ) ilde{O}(\sqrt{\log d}) i l d e O ( log d ) for positive coefficients, no assumptions on rank or condition number. result Proves a Statistical Query lower bound of d Ω ( k ) d^{Ω(k)} d Ω ( k ) for arbitrary real coefficients, separating learnability classes. Study learning halfspaces with Massart noise under Gaussian distribution, improving previous results.
problem Learning halfspaces with Massart noise under Gaussian distribution, especially when the parameter is 1/2.
method Developed algorithms for general and homogeneous halfspaces with sample and computational complexities.
result Established qualitatively matching lower bounds for the complexities of learning algorithms.
Statistical query (SQ) algorithms are algorithms that have access to an {\em SQ oracle} for the input distribution D D D instead of i.i.d.~ samples from D D D . Given a query function φ : X → [ − 1 , 1 ] φ:X \rightarrow [-1,1] φ : X → [ − 1 , 1 ] , the oracle returns an estimate of E x ∼ D [ φ ( x ) ] {\bf E}_{ x\sim D}[φ(x)] E x ∼ D [ φ ( x )] within some tolerance τ φ τ_φ τ φ that roughly corresponds t…
New framework limits SGD for multi-index models, addressing SQ framework shortcomings.
problem Limitations of SGD for multi-index models beyond SQ framework.
method Developed a new non-SQ framework to study SGD limitations for single-index and multi-index models.
result Applies to broad settings and architectures, including neural networks.
Hard problem of learning simple generative models from i.i.d. samples.
problem Learning simple neural network distributions from samples.
method Statistical query model, ODE-based construction of piecewise-linear functions.
result No polynomial-time algorithm can solve this problem even with one-hidden-layer ReLU networks.
Framework for robust decision making in changing environments with privacy constraints.
problem Interactive decision making in changing environments with constraints.
method Hybrid Decision Making with Structured Observations (hybrid DMSO) framework, local differentially private decision making, query-based learning, robust and smooth decision making.
result Strong connections and bounds derived for DEC, SQ dimension, local minimax complexity, learnability, and joint differential privacy.
Neural networks can achieve optimal sample complexity for learning single-index models.
problem Achieving optimal computational-statistical tradeoff in learning Gaussian single-index models.
method Unified gradient-based algorithm for training a two-layer neural network, adaptable to various loss and activation functions.
result Sample complexity of d s ⋆ / 2 ∨ d d^{s^\star/2} \lor d d s ⋆ /2 ∨ d matches the SQ lower bound up to a polylogarithmic factor. New lower bounds show learning intersections of halfspaces is hard even for a few halfspaces.
problem Learning intersections of halfspaces in polynomial time under standard assumptions.
method Unified connection to parallel pancakes distribution for proving hardness.
result Learning ω ( log log N ) ω(\log \log N) ω ( log log N ) halfspaces in dimension N N N requires super-polynomial time under standard assumptions. Study shows computational and statistical gaps in Gaussian Single-Index Models.
problem Statistical and computational trade-offs in high-dimensional regression problems.
method Analysis of SQ and LDP frameworks, partial-trace algorithm.
result Computational algorithms require significantly more samples than information-theoretic limits.
Study on estimating Gaussian mean with missing data in high dimensions.
problem Estimating Gaussian mean in high dimensions with missing data due to realizable contamination.
method Statistical Query model, Low-Degree Polynomials, PTF tests, and algorithms.
result Established information-computation gap and developed efficient algorithms.
We study the problem of high-dimensional linear regression in a robust model where an ε ε ε -fraction of the samples can be adversarially corrupted. We focus on the fundamental setting where the covariates of the uncorrupted samples are drawn from a Gaussian distribution N ( 0 , Σ ) \mathcal{N}(0, Σ) N ( 0 , Σ ) on R d \mathbb{R}^d R d . We give near…
Differentiable learning via SGD and GD can simulate various learning problems, depending on precision and minibatch size.
problem Understanding the power of differentiable learning via SGD and GD compared to statistical query (SQ) learning.
method Comparing the learning power of SGD and GD on population and empirical losses with statistical query learning.
result The learning power of SGD and GD depends on the precision of gradient calculations relative to the minibatch size or sample size.
We give algorithms for estimating the expectation of a given real-valued function φ : X → R φ:X\to {\bf R} φ : X → R on a sample drawn randomly from some unknown distribution D D D over domain X X X , namely E x ∼ D [ φ ( x ) ] {\bf E}_{{\bf x}\sim D}[φ({\bf x})] E x ∼ D [ φ ( x )] . Our algorithms work in two well-studied models of restricted access to data samples. The first o…
The study optimizes polynomial regression for learning under Gaussian distributions.
problem Agnostic learning of Boolean and real-valued functions under Gaussian distributions.
method LP duality and polynomial degree analysis for L 1 L^1 L 1 -regression. result Optimal SQ lower bounds for various function classes.
Algorithm learns arbitrary ReLU neurons under Gaussian inputs.
problem Learn an arbitrary ReLU activation over Gaussian marginals.
method Statistical Query (SQ) algorithm that outputs a ReLU activation achieving O ( O P T ) + ε O(\mathrm{OPT}) + \varepsilon O ( OPT ) + ε loss. result First constant factor approximation for arbitrary bias in polynomial time.
Robust learner finds subspace for MIMs with label noise.
problem Learning Multi-Index Models with label noise under Gaussian distribution.
method Iterative subspace approximation using conditional moments.
result Qualitatively optimal robust learner in SQ model.
Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.
problem High-dimensional hypothesis testing and information-computation gaps.
method Analysis of statistical query framework and low-degree polynomials.
result Statistical query algorithms and low-degree polynomials are almost equivalent in power under mild conditions.
Lower bounds show density estimation requires linear samples or query time.
problem Statistical-computational trade-offs in density estimation.
method Lower bound analysis on data structures.
result Lower bounds demonstrate statistical-computational trade-offs for density estimation.
Study private query release with public data, reducing sample sizes.
problem Answering a wide range of statistical queries while maintaining privacy.
method Combines public and private samples to answer queries with differential privacy.
result Private and public sample complexities for different query classes.
New insights on robust learning under strong noise models.
problem Challenging label-noise models in robust learning.
method Extending statistical query framework to more general noise models and using evolutionary algorithms.
result First polynomial time algorithm for learning linear threshold functions with arbitrarily small excess error in presence of Tsybakov noise.