Research map / Learning theory and algorithms / Sample complexity
Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a unified gradient-based algorithm (label transformation plus random weight perturbation) training a two-layer network to learn Gaussian single-index models with sample complexity matching the SQ lower bound for any generative exponent, and a sparsity-aware perturbation for k-sparse signals.
Problem
Whether neural networks trained with gradient-based methods can achieve the optimal computational-statistical tradeoff for learning Gaussian single-index models with generative exponent s* >= 3, where prior gradient methods have a gap to the SQ lower bound.
Approach
Combines a general gradient oracle (label transformation / modified loss, batch reusing as special case) with random weight perturbation on the sphere (exploration with polarization gamma) to raise gradient SNR, and for sparse signals perturbs weights using a polynomial-size cover of sparse supports with top-k projection and gradient sharing.
Key results
- Algorithm achieves sample complexity Õ(d^{s*/2} ∨ d) for uniform prior, matching the SQ lower bound up to polylog factors for all s* >= 1.
- For k-sparse signals with k=o(sqrt d), sample complexity Õ(k^{s*}) with a matching SQ lower bound Ω̃(k^{s*}) up to polylog factors.
- Simulations for s*=4 show fitted log-log slopes of about 1.82 to 1.97 (close to s*/2 = 2), consistent with n ∝ d^2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add weight perturbation and gradient aggregation to gradient-based training | Two-layer neural network for the Gaussian single-index model · Uniform prior, s^\star>2 | sample complexity: d^{s^\star -1} -> \tilde O(d^{s^\star/2} \lor d) | Helped |
| Use prior-cover perturbations instead of perturbations sampled from the sparse prior | Sparse gradient-based feature learning · k-sparse prior, k=o(\sqrt d) | sample complexity: \tilde{O}(k^{s^\star} \cdot d / k^2) -> \tilde O(k^{s^\star}) | Helped |
| Use prior-matched sparse perturbations rather than a polynomial-size cover of the sparse prior (ablation) | Sparse gradient-based feature learning · k-sparse prior | sample complexity: \tilde{O}(k^{s^\star} \cdot d / k^2) | Hurt |
| Use batch-reusing | Gradient-based feature learning for polynomial links · Polynomial link, s^\star\leq 2 | sample complexity: \widetilde{\Theta}(d) | Helped |
| Use batch-reusing instead of a high-pass oracle designed for general generative exponents (ablation) | Gradient-based feature learning · s^\star\geq 3 | sample complexity | Hurt |
| Use sparse-aware perturbation and top-k support projection | Two-layer neural network for the sparse Gaussian single-index model · k-sparse prior with k=o(\sqrt d) | sample complexity: \tilde O(d^{s^\star/2} \lor d) -> \tilde O(k^{s^\star}) | Helped |
| Use the proposed method with s^\star=4 and vary sample size and dimension | Gradient-based feature learning · Gaussian single-index model, uniform prior | log n slope: 1.9058; 1.8201; 1.9103; 1.9343; 1.9640; 1.9653 | Helped |
Surprising findings
- Vanilla online minibatch SGD requires about d^{s*-1} samples, far from the SQ bound, even though the SQ bound is d^{s*/2}.
Limitations
- Requires fresh weight perturbations each step, with L perturbations per neuron (overparameterized effective width d^{(s*+1)/2}), not standard training practice.
- Sparse algorithm requires a polynomial-size cover over supports and width M=d; conjecture for s*=1 is unproven.
- Analysis relies on Gaussian design and Hermite expansion.
Experimental setup
Datasets: synthetic Gaussian single-index model data
Benchmarks: synthetic Gaussian single-index model (phi(x)=x^2 exp(-x^2), s*=4)
Metrics: average alignment |<theta_m, theta*>| top-8 alignment
Baselines: online SGD batch reusing partial trace estimator pruning
Builds on: batch reusing landscape smoothing generative exponent label transformation
Closest papers by meaning
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.88)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.87)
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.86)
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.86)
- From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD (NeurIPS 2025 · similarity 0.86)
- Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.