On Convergence of Incremental Gradient for Non-Convex Smooth Functions
Preprint
Abstract
In machine learning and neural network optimization, algorithms like incremental gradient, and shuffle SGD are popular due to minimizing the number of cache misses and good practical convergence behavior. However, their optimization properties in theory, especially for non-convex smooth functions, remain incompletely explored. This paper delves into the convergence properties of SGD algorithms with arbitrary data ordering, within a broad framework for non-convex smooth functions. Our findings show enhanced convergence guarantees for incremental gradient and single shuffle SGD. Particularly if $n$ is the training set size, we improve $n$ times the optimization term of convergence guarantee to reach accuracy $\varepsilon$ from $O(n / \varepsilon)$ to $O(1 / \varepsilon)$.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- First-order and Stochastic Optimization Methods for Machine Learning2020
- Why random reshuffling beats stochastic gradient descentMathematical Programming, 2019
- Perturbed Iterate Analysis for Asynchronous Stochastic OptimizationSIAM Journal on Optimization, 2017
- Parallel stochastic gradient algorithms for large-scale matrix completionMathematical Programming Computation, 2013
- Ergodic mirror descent2011
- An optimal method for stochastic composite optimizationMathematical Programming, 2011
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- A Randomized Incremental Subgradient Method for Distributed Optimization in Networked SystemsSIAM Journal on Optimization, 2010
- A class of unconstrained minimization methods for neural network trainingOptimization Methods and Software, 1994
- An Adaptive Associative Memory PrincipleIEEE Transactions on Computers, 1974