Convergence rates of stochastic gradient method with independent sequences of step-size and momentum weight
In large-scale learning algorithms, the momentum term is usually included in the stochastic sub-gradient method to improve the learning speed because it can navigate ravines efficiently to reach a local minimum. However, step-size and momentum weight hyper-parameters must be appropriately tuned to optimize convergence. We thus analyze the convergence rate using stochastic programming with Polyak's acceleration of two commonly used step-size learning rates: `diminishing-to-zero" and `constant-and-drop" (where the sequence is divided into stages and a constant step-size is applied at each stage) under strongly convex functions over a compact convex set with bounded sub-gradients. For the former, we show that the convergence rate can be written as a product of exponential in step-size and polynomial in momentum weight. Our analysis justifies the convergence of using the default momentum weight setting and the diminishing-to-zero step-size sequence in large-scale machine learning software. For the latter, we present the condition for the momentum weight sequence to converge at each stage.
Code (0)
등록된 구현이 없습니다.
Tasks
NavigateMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT
We provide non-asymptotic convergence rates of the Polyak-Ruppert averaged stochastic gradient descent (SGD) to a normal random vector for a class of twice-differentiable test functions. A crucial intermediate step is pr…
parameter estimationvalidTight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
We study the convergence of Stochastic Gradient Descent (SGD) for strongly convex objective functions. We prove for all $t$ a lower bound on the expected convergence rate after the $t$-th SGD iteration; the lower bound i…
Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
Stochastic gradient algorithms estimate the gradient based on only one or a few samples and enjoy low computational cost per iteration. They have been widely used in large-scale optimization problems. However, stochastic…
The Power of Factorial Powers: New Parameter settings for (Stochastic) Optimization
The convergence rates for convex and non-convex optimization methods depend on the choice of a host of constants, including step sizes, Lyapunov function constants and momentum constants. In this work we propose the use …
Stochastic OptimizationFinite-Time Analysis of Stochastic Gradient Descent under Markov Randomness
Motivated by broad applications in reinforcement learning and machine learning, this paper considers the popular stochastic gradient descent (SGD) when the gradients of the underlying objective function are sampled from …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)