mlsanityData to 7 Oct 2026

Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs

arXiv 1702.07966 ↗First posted 26 Feb 2017cs.LG math.OC stat.MLcited by 61

Not on the map. Why?

Abstract (arXiv)

Deep learning models are often successfully trained using gradient descent, despite the worst case hardness of the underlying non-convex optimization problem. The key question is then under what conditions can one prove that optimization will succeed. Here we provide a strong result of this kind. We consider a neural net with one hidden layer and a convolutional structure with no overlap and a ReLU activation function. For this architecture we show that learning is NP-complete in the general case, but that when the input distribution is Gaussian, gradient descent converges to the global optimum in polynomial time. To the best of our knowledge, this is the first global optimality guarantee of gradient descent on a convolutional neural network with ReLU activations.

Key facts. Cited by 61 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Feb 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 24; 2022: 16; 2023: 11; 2024: 5; 2025: 4; 2026: 1.

61 papers.

Sort:

  1. 2021Understanding self-supervised Learning Dynamics without Contrastive Pairscited by 254
  2. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  3. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 101
  4. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  5. 2021Separation of Scales and a Thermodynamic Description of Feature Learning in Some CNNscited by 53
  6. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  7. 2021Constrained Learning with Non-Convex Lossescited by 42
  8. 2021Adversarial Robustness with Semi-Infinite Constrained Learningcited by 39
  9. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  10. 2022The Mechanism of Prediction Head in Non-contrastive Self-supervised Learningcited by 38
  11. 2023Scaling MLPs: A Tale of Inductive Biascited by 37
  12. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
38 more
  1. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  2. 2022Implicit Full Waveform Inversion with Deep Neural Representationcited by 26
  3. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  4. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  5. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  6. 2021Parameter identifiability of a deep feedforward ReLU neural networkcited by 24
  7. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  8. 2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
  9. 2021GradSign: Model Performance Inference with Theoretical Insightscited by 18
  10. 2022How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysiscited by 18
  11. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
  12. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  13. 2021Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry IIcited by 16
  14. 2022Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Trainingcited by 15
  15. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  16. 2023Resilient Constrained Learningcited by 15
  17. 2021Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networkscited by 14
  18. 2021Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscited by 14
  19. 2024On the hardness of learning under symmetriescited by 13
  20. 2022Local Identifiability of Deep ReLU Neural Networks: the Theorycited by 12
  21. 2022Towards Theoretically Inspired Neural Initialization Optimizationcited by 11
  22. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  23. 2021Local SGD Optimizes Overparameterized Neural Networks in Polynomial Timecited by 10
  24. 2022Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methodscited by 10
  25. 2023Global Optimality in Bivariate Gradient-based DAG Learningcited by 10
  26. 2022Annihilation of Spurious Minima in Two-Layer ReLU Networkscited by 9
  27. 2024Near-Optimal Solutions of Constrained Learning Problemscited by 9
  28. 2025Generative quantum advantage for classical and quantum problemscited by 9
  29. 2021Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samplescited by 8
  30. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  31. 2022Magnitude and Angle Dynamics in Training Single ReLU Neuronscited by 5
  32. 2022Finite Sample Identification of Wide Shallow Neural Networks with Biasescited by 5
  33. 2021A Convergence Theory Towards Practical Over-parameterized Deep Neural Networkscited by 4
  34. 2021Practical Convex Formulation of Robust One-hidden-layer Neural Network Trainingcited by 4
  35. 2023What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglementcited by 4
  36. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  37. 2021Achieving Small Test Error in Mildly Overparameterized Neural Networkscited by 3
  38. 2025Quantum advantage for learning shallow neural networks with natural data distributionscited by 3

50 most cited of 61 All 61 (JSON)