mlsanityData to 14 Oct 2026

Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions

arXiv 2502.06443 ↗First posted 10 Feb 2025cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

The problem of learning single index and multi index models has gained significant interest as a fundamental task in high-dimensional statistics. Many recent works have analysed gradient-based methods, particularly in the setting of isotropic data distributions, often in the context of neural network training. Such studies have uncovered precise characterisations of algorithmic sample complexity in terms of certain analytic properties of the target function, such as the leap, information, and generative exponents. These properties establish a quantitative separation between low and high complexity learning tasks. In this work, we show that high complexity cases are rare. Specifically, we prove that introducing a small random perturbation to the data distribution--via a random shift in the first moment--renders any Gaussian single index model as easy to learn as a linear function. We further extend this result to a class of multi index models, namely sparse Boolean functions, also known as Juntas.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 28 of its 45 references that are in the map. First posted on arXiv 10 Feb 2025.

Builds on

28 of 45 references.

References · 28

  1. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  2. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  3. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  4. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  5. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  6. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  7. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 70
  8. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  9. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  10. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  11. 2023Learning time-scales in two-layers neural networkscited by 57
  12. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
16 more
  1. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52
  2. 2020Learning a Single Neuron with Gradient Methodscited by 50
  3. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  4. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  5. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
  6. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  7. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 37
  8. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  9. 2016Distribution-Specific Hardness of Learning Neural Networkscited by 27
  10. 2023Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputscited by 22
  11. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  12. 2023A Mathematical Model for Curriculum Learning for Paritiescited by 19
  13. 2023On Single Index Models beyond Gaussian Datacited by 17
  14. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 15
  15. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  16. 2022Learning a Single Neuron for Non-monotonic Activation Functionscited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 6.

8 papers.

  1. 2025Online Learning of Neural Networkscited by 5
  2. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  3. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  4. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 2
  5. 2026The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficientlycited by 1
  6. 2026Learning with Shallow Neural Networks on Cluster-Structured Featurescited by 1
  7. 2026The Power of Power Law: Asymmetry Enables Compositional Reasoningcited by 0
  8. 2026Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biasescited by 0