New Convergence Aspects of Stochastic Gradient Algorithms

MaRDI QIDQ5214284zbMATH OpenFDO

Authors Lam M. Nguyen, Phuong Ha Nguyen, Peter Richtárik, Katya Scheinberg, M. Takáč, Marten van Dijk

Publication date 7 February 2020

Full work available at URL https://arxiv.org/abs/1811.12403, http://jmlr.csail.mit.edu/papers/v20/18-759.html

zbMATH Keywords

stochastic gradient algorithm (SGA)stochastic gradient descent (SGD)

Mathematics Subject Classification ID

Applications of stochastic analysis (to PDEs, etc.) (60H30) Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Learning and adaptive systems in artificial intelligence (68T05)

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 $et{a}_t$ satisfies $su{m}_{t=0}^{i}nftyet{a}_{t}ightarrowinfty$ and $su{m}_{t=0}^{i}nftyet{a}_t^2<infty$. We show the convergence of SGD for strongly convex objective function without using bounded gradient assumption when $et{a}_t$ is a diminishing sequence and $su{m}_{t=0}^{i}nftyet{a}_{t}ightarrowinfty$. In other words, we extend the current state-of-the-art class of learning rates satisfying the convergence of SGD.

Recommendations

• scientific article; zbMATH DE number 1322672
• scientific article; zbMATH DE number 1341059
• Convergence analysis of gradient descent stochastic algorithms
• Convergence of stochastic proximal gradient algorithm
• On stochastic accelerated gradient with convergence rate
• Convergence rates for the stochastic gradient descent method for non-convex objective functions
• On the Convergence of Algorithms with Implications for Stochastic and Nondifferentiable Optimization
• On convergence of quasi-gradient stochastic methods of optimization

Cited in

(18)

• Stochastic gradient descent with Polyak's learning rate
• Convergence of stochastic proximal gradient algorithm
• A sharp convergence rate for a model equation of the asynchronous stochastic gradient descent
• Finite-sum smooth optimization with SARAH
• On the linear convergence of the stochastic gradient method with constant step-size
• Strong error analysis for stochastic gradient descent optimization algorithms
• Generalization performance of multi-pass stochastic gradient descent with convex loss functions
• Sign stochastic gradient descents without bounded gradient assumption for the finite sum minimization
• A Convergence Study of SGD-Type Methods for Stochastic Optimization
• scientific article; zbMATH DE number 7733450 (Why is no real title available?)
• Random-reshuffled SARAH does not need full gradient computations
• Last-iterate convergence of shuffling momentum gradient method under the Kurdyka-Lojasiewicz inequality
• Convergence of Adam for non-convex objectives: relaxed hyperparameters and non-ergodic case
• Improving the stochastically controlled stochastic gradient method by the bandwidth-based stepsize
• Statistical inference for decentralized federated learning
• A unified theoretical framework for the last-iterate convergence of stochastic adaptive optimization
• A stochastic conjugate gradient method with restart procedure for machine learning
• Performance analysis of stochastic gradient algorithms under weak conditions

This page was built for publication: New Convergence Aspects of Stochastic Gradient Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5214284)