mlsanityData to 7 Oct 2026

Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent

arXiv 2106.13792 ↗First posted 25 Jun 2021cs.LG math.OC stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

Although the optimization objectives for learning neural networks are highly non-convex, gradient-based methods have been wildly successful at learning neural networks in practice. This juxtaposition has led to a number of recent studies on provable guarantees for neural networks trained by gradient descent. Unfortunately, the techniques in these works are often highly specific to the particular setup in each problem, making it difficult to generalize across different settings. To address this drawback in the literature, we propose a unified non-convex optimization framework for the analysis of neural network training. We introduce the notions of proxy convexity and proxy Polyak-Lojasiewicz (PL) inequalities, which are satisfied if the original objective function induces a proxy objective function that is implicitly minimized when using gradient methods. We show that gradient descent on objectives satisfying proxy convexity or the proxy PL inequality leads to efficient guarantees for proxy objective functions. We further show that many existing guarantees for neural networks trained by gradient descent can be unified through proxy convexity and proxy PL inequalities.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 33 of its 49 references that are in the map. First posted on arXiv 25 Jun 2021.

Builds on

33 of 49 references.

References · 33

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  3. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  4. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  5. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  7. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  8. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  9. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  10. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  11. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  12. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
21 more
  1. 2016Identity Matters in Deep Learningcited by 107
  2. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  3. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  4. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  5. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  6. 2019Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networkscited by 60
  7. 2020Learning a Single Neuron with Gradient Methodscited by 50
  8. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  9. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  10. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  11. 2016Diverse Neural Network Learns True Target Functionscited by 33
  12. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  13. 2013An Asynchronous Parallel Stochastic Coordinate Descent Algorithmcited by 26
  14. 2018Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networkscited by 22
  15. 2013Gradient methods for convex minimization: better rates under weaker conditionscited by 21
  16. 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20
  17. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  18. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  19. 2019Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networkscited by 16
  20. 2020Agnostic Learning of Halfspaces with Gradient Descent via Soft Marginscited by 14
  21. 2017Characterization of Gradient Dominance and Regularity Conditions for Neural Networkscited by 8

Built on by

Cited by year

Citing papers per year: 2022: 6; 2023: 9; 2024: 3; 2025: 3.

21 papers.

Sort:

  1. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  2. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  3. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 50
  4. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  5. 2023Benign Overfitting for Two-layer ReLU Convolutional Neural Networkscited by 34
  6. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  7. 2023On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Levelcited by 14
  8. 2023Provable Guarantees for Neural Networks via Gradient Feature Learningcited by 13
  9. 2022On Feature Learning in Neural Networks with Global Convergence Guaranteescited by 12
  10. 2024Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimizationcited by 10
  11. 2025LDC-MTL: Balancing Multi-Task Learning through Scalable Loss Discrepancy Controlcited by 7
  12. 2023Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimizationcited by 6
9 more
  1. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  2. 2023On the Convergence of the Gradient Descent Method with Stochastic Fixed-point Rounding Errors under the Polyak-Lojasiewicz Inequalitycited by 4
  3. 2023Adaptive Mirror Descent Bilevel Optimizationcited by 2
  4. 2023Implicit Regularization in Feedback Alignment Learning Mechanisms for Neural Networkscited by 1
  5. 2025Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networkscited by 1
  6. 2025Pointwise confidence estimation in the non-linear ℓ2-regularized least squarescited by 1
  7. 2022From Optimization Dynamics to Generalization Bounds via Lojasiewicz Gradient Inequalitycited by 0
  8. 2022Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast Evasion of Non-Degenerate Saddle Pointscited by 0
  9. 2023A Linearly Convergent GAN Inversion-based Algorithm for Reverse Engineering of Deceptionscited by 0