Finite-Sum Optimization: A New Perspective for Convergence to a Global Solution
Not on the map. Why?
Abstract (arXiv)
Deep neural networks (DNNs) have shown great success in many machine learning tasks. Their training is challenging since the loss surface of the network architecture is generally non-convex, or even non-smooth. How and under what assumptions is guaranteed convergence to a textitglobal minimum possible? We propose a reformulation of the minimization problem allowing for a new recursive algorithmic framework. By using bounded style assumptions, we prove convergence to an varepsilon-(global) minimum using mathcaltildeO(1/varepsilon3) gradient computations. Our theoretical foundation motivates further study, implementation, and optimization of the new algorithmic framework and further investigation of its non-standard bounded style assumptions. This new direction broadens our understanding of why and under what circumstances training of a DNN converges to a global minimum.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 28 of its 36 references that are in the map. First posted on arXiv 7 Feb 2022.
Builds on
28 of 36 references.
References · 28
- 2014Adam: A Method for Stochastic Optimizationcited by 36,960
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
- 2019On the Convergence of Adam and Beyondcited by 834
- 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
- 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
- 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
16 more
- 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
- 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
- 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
- 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
- 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 94
- 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
- 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
- 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
- 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
- 2018Online Adaptive Methods, Universality and Accelerationcited by 51
- 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
- 2019Multi-Level Composite Stochastic Optimization via Nested Variance Reductioncited by 28
- 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 26
- 2019A Stochastic Composite Gradient Method with Incremental Variance Reductioncited by 26
- 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
- 2020Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimizationcited by 10
Built on by
Citing papers per year: 2022: 1; 2023: 1.
2 papers.