Can speed up the convergence rate of stochastic gradient methods to $\mathcal{O}(1/k^2)$ by a gradient averaging strategy?
This provides a method to accelerate convergence in optimization for machine learning, but it is incremental as it builds on existing stochastic gradient approaches.
The paper tackles the problem of improving the convergence rate of stochastic gradient methods for strongly convex objectives with Lipschitz gradients, showing that a gradient averaging strategy can increase the rate from O(1/k) to O(1/k^2) in probability under a variance dominant condition.
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.