Can speed up the convergence rate of stochastic gradient methods to $\mathcal{O}(1/k^2)$ by a gradient averaging strategy?

• URL: http://arxiv.org/abs/2002.10769v1
• Date: Tue, 25 Feb 2020 09:58:23 GMT
• Title: Can speed up the convergence rate of stochastic gradient methods to $\mathcal{O}(1/k^2)$ by a gradient averaging strategy?
• Authors: Xin Xu and Xiaopeng Luo
• Abstract summary: We show that if the iterative variance we defined is always dominant even a little bit in the gradient iterations, the proposed gradient averaging strategy can increase the convergence rate. This conclusion suggests how we should control the gradient iterations to improve the rate of convergence.
• Score: 8.663453034925363
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we consider the question of whether it is possible to apply a gradient averaging strategy to improve on the sublinear convergence rates without any increase in storage. Our analysis reveals that a positive answer requires an appropriate averaging strategy and iterations that satisfy the variance dominant condition. As an interesting fact, we show that if the iterative variance we defined is always dominant even a little bit in the stochastic gradient iterations, the proposed gradient averaging strategy can increase the convergence rate $\mathcal{O}(1/k)$ to $\mathcal{O}(1/k^2)$ in probability for the strongly convex objectives with Lipschitz gradients. This conclusion suggests how we should control the stochastic gradient iterations to improve the rate of convergence.

Related papers

• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• On Almost Sure Convergence Rates of Stochastic Gradient Methods [11.367487348673793]
  We show for the first time that the almost sure convergence rates obtained for gradient methods are arbitrarily close to their optimal convergence rates possible. For non- objective functions, we only show that a weighted average of squared gradient norms converges not almost surely, but also lasts to zero almost surely.
  arXiv  Detail & Related papers  (2022-02-09T06:05:30Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization [0.0]
  We propose a new technique, em variance controlled gradient (VCSG), to improve the performance of the reduced gradient (SVRG) $lambda$ is introduced in VCSG to avoid over-reducing a variance by SVRG. $mathcalO(min1/epsilon3/2,n1/4/epsilon)$ number of gradient evaluations, which improves the leading gradient complexity.
  arXiv  Detail & Related papers  (2021-02-19T12:22:56Z)
• Convergence of Gradient Algorithms for Nonconvex $C^{1+\alpha}$ Cost Functions [2.538209532048867]
  We show a byproduct that a gradient converges and provide an explicit upper bound on the convergence rate. This allows us to prove the almost sure convergence by Doobmartin's supergale convergence theorem.
  arXiv  Detail & Related papers  (2020-12-01T16:48:59Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball [17.33867778750777]
  We study gradient descent (SGD) and the heavy ball method (SHB) for the general approximation problem. For SGD, in the convex and smooth setting, we provide the first emphalmost sure convergence emphrates for a weighted average of the iterates.
  arXiv  Detail & Related papers  (2020-06-14T11:12:05Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  We show a proof of convergence between the Adam Adagrad and $O(d(N)/st)$ algorithms. Adam converges with the same convergence $O(d(N)/st)$ when used with the default parameters.
  arXiv  Detail & Related papers  (2020-03-05T01:56:17Z)
• Stochastic gradient-free descents [8.663453034925363]
  We propose gradient-free methods and accelerated gradients with momentum for solving optimization problems. We analyze the convergence behavior of these methods under the mean-variance framework.
  arXiv  Detail & Related papers  (2019-12-31T13:56:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.