mlsanityData to 14 Oct 2026

Learning with Gradient Descent and Weakly Convex Losses

arXiv 2101.04968 ↗First posted 13 Jan 2021stat.ML cs.LG math.STcited by 16

Not on the map. Why?

Abstract (arXiv)

We study the learning performance of gradient descent when the empirical risk is weakly convex, namely, the smallest negative eigenvalue of the empirical risk's Hessian is bounded in magnitude. By showing that this eigenvalue can control the stability of gradient descent, generalisation error bounds are proven that hold under a wider range of step sizes compared to previous work. Out of sample guarantees are then achieved by decomposing the test error into generalisation, optimisation and approximation errors, each of which can be bounded and traded off with respect to algorithmic parameters, sample size and magnitude of this eigenvalue. In the case of a two layer neural network, we demonstrate that the empirical risk can satisfy a notion of local weak convexity, specifically, the Hessian's smallest eigenvalue during training can be controlled by the normalisation of the layers, i.e., network scaling. This allows test error guarantees to then be achieved when the population risk minimiser satisfies a complexity assumption. By trading off the network complexity and scaling, insights are gained into the implicit bias of neural network scaling, which are further supported by experimental findings.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 37 of its 59 references that are in the map. First posted on arXiv 13 Jan 2021.

Builds on

37 of 59 references.

References · 37

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  3. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  5. 2018On Lazy Training in Differentiable Programmingcited by 675
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  8. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  9. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  10. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  11. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  12. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
25 more
  1. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  2. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  3. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  4. 2019An Investigation into Neural Net Optimization via Hessian Eigenvalue Densitycited by 292
  5. 2017Empirical Analysis of the Hessian of Over-Parametrized Neural Networkscited by 290
  6. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  7. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
  8. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  9. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  10. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 159
  11. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  12. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  13. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  14. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
  15. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  16. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  17. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  18. 2018Hessian-based Analysis of Large Batch Training and Robustness to Adversariescited by 87
  19. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  20. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  21. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  22. 2019The asymptotic spectrum of the Hessian of DNN throughout trainingcited by 19
  23. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  24. 2019Implicit Regularization of Accelerated Methods in Hilbert Spacescited by 14
  25. 2015Iterative Regularization for Learning with Convex Loss Functionscited by 9

Built on by

Cited by year (2026 to 14 Oct)

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

16 papers.

Sort:

By area:

  1. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  2. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  3. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 26
  4. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  5. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  6. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  7. 2025Wasserstein Convergence of Score-based Generative Models under Semiconvexity and Discontinuous Gradientscited by 15
  8. 2023Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networkscited by 9
  9. 2024Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methodscited by 7
  10. 2023Asynchronous Multi-Model Dynamic Federated Learning over Wireless Networks: Theory, Modeling, and Optimizationcited by 3
  11. 2025Stability and Generalization of Quantum Neural Networkscited by 3
  12. 2025On the Theory of Continual Learning with Gradient Descent for Neural Networkscited by 3
4 more
  1. 2025Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processescited by 2
  2. 2025WEEP: A Differentiable Nonconvex Sparse Regularizer via Weakly-Convex Envelopecited by 1
  3. 2026Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networkscited by 1
  4. 2024Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimizationcited by 0