New Convergence Aspects of Stochastic Gradient Algorithms

Abstract

The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is violated for cases where the objective function is strongly convex. In Bottou et al. (2018), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. We show that for stochastic problems arising in machine learning such bound always holds; and we also propose an alternative convergence analysis of SGD with diminishing learning rate regime. We then move on to the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime in the case of diminished learning rate. It is well-known that SGD converges if a sequence of learning rates $\{{\eta }_t\}$ satisfies ${\sum }_{t=0}^{\infty }{\eta }_t\to \infty$ and ${\sum }_{t=0}^{\infty }{\eta }_t^2<\infty$. We show the convergence of SGD for strongly convex objective function without using bounded gradient assumption when $\{{\eta }_t\}$ is a diminishing sequence and ${\sum }_{t=0}^{\infty }{\eta }_t\to \infty$. In other words, we extend the current state-of-the-art class of learning rates satisfying the convergence of SGD.

arXiv commentJournal of Machine Learning Research. arXiv admin note: substantial text overlap with arXiv:1802.03801

References in corpus (5)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Improved asynchronous parallel optimization analysis for stochastic incremental methods

Cited by in corpus (4)

• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD