mlsanityData to 7 Oct 2026

Recovery Guarantees for One-hidden-layer Neural Networks

arXiv 1706.03175 ↗First posted 10 Jun 2017cs.LG cs.DS stat.MLcited by 94

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to mathitlocal~strong~convexity in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show mathitlocal~linear~convergence guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity d · log(1/ε) · poly(k,λ ) and computational complexity n· d · poly(k,λ) for smooth homogeneous activations with high probability, where d is the dimension of the input, k (k≤ d) is the number of hidden nodes, λ is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, ε is the targeted precision and n is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity mathitlinear in the input dimension and mathitlogarithmic in the precision.

Key facts. Cited by 94 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Jun 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 0; 2021: 18; 2022: 26; 2023: 24; 2024: 14; 2025: 9; 2026: 2.

94 papers.

Sort:

By area:

  1. 2021Decentralized Federated Averagingcited by 114
  2. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  3. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  4. 2021Continual Learning in the Teacher-Student Setup: Impact of Task Similaritycited by 86
  5. 2022Self-Training: A Surveycited by 85
  6. 2023DiffFit: Unlocking Transferability of Large Diffusion Models via Simple Parameter-Efficient Fine-Tuningcited by 82
  7. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  8. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  9. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  10. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  11. 2022The Mechanism of Prediction Head in Non-contrastive Self-supervised Learningcited by 38
  12. 2023Test-Time Training on Video Streamscited by 37
38 more
  1. 2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35
  2. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  3. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 29
  4. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  5. 2023Generalization Ability of Wide Neural Networks on ℝcited by 28
  6. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  7. 2022Reconstructing Training Data from Model Gradient, Provablycited by 27
  8. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  9. 2021Parameter identifiability of a deep feedforward ReLU neural networkcited by 24
  10. 2021Single Layer Predictive Normalized Maximum Likelihood for Out-of-Distribution Detectioncited by 23
  11. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  12. 2021Exponentially Many Local Minima in Quantum Neural Networkscited by 22
  13. 2024Provably learning a multi-head attention layercited by 21
  14. 2024A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Expertscited by 21
  15. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  16. 2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
  17. 2022How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysiscited by 18
  18. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  19. 2021On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Settingcited by 16
  20. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
  21. 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysiscited by 15
  22. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  23. 2021Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networkscited by 14
  24. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  25. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  26. 2018Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithmscited by 13
  27. 2022Local Identifiability of Deep ReLU Neural Networks: the Theorycited by 12
  28. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  29. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  30. 2021Local SGD Optimizes Overparameterized Neural Networks in Polynomial Timecited by 10
  31. 2022Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methodscited by 10
  32. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  33. 2024Towards Robust Out-of-Distribution Generalization Bounds via Sharpnesscited by 10
  34. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  35. 2022Annihilation of Spurious Minima in Two-Layer ReLU Networkscited by 9
  36. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  37. 2021Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samplescited by 8
  38. 2022Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian datacited by 8

50 most cited of 94 All 94 (JSON)