Published on Mon Nov 05 2018

Non-ergodic Convergence Analysis of Heavy-Ball Algorithms

Tao Sun, Penghang Yin, Dongsheng Li, Chun Huang, Lei Guan, Hao Jiang

In this paper, we revisit the convergence of the Heavy-ball method, and present improved convergence complexity results in the convex setting. We extend our results to multi-block version of the algorithm with both the cyclic and stochastic update rules.

0
0
0
Abstract

In this paper, we revisit the convergence of the Heavy-ball method, and present improved convergence complexity results in the convex setting. We provide the first non-ergodic O(1/k) rate result of the Heavy-ball algorithm with constant step size for coercive objective functions. For objective functions satisfying a relaxed strongly convex condition, the linear convergence is established under weaker assumptions on the step size and inertial parameter than made in the existing literature. We extend our results to multi-block version of the algorithm with both the cyclic and stochastic update rules. In addition, our results can also be extended to decentralized optimization, where the ergodic analysis is not applicable.

Wed Sep 14 2016
Machine Learning
Stochastic Heavy Ball
The Heavy-ball method differential equation was introduced by Polyak in the 1960s. The family of second-order methods recently received a large amount of attention. We describe some almost sure convergence results in the case of general non-convex coercive functions.
0
0
0
Mon Aug 10 2020
Machine Learning
An improved convergence analysis for decentralized online stochastic non-convex optimization
In this paper, we study decentralized online stochastic non-convex optimization over a network of nodes. We show that the resulting algorithm, GT-DSGD, enjoys certain desirable characteristics. In contrast, the existing results suggest that GT- DSGD is always network-dependent.
0
0
0
Sat Nov 07 2020
Machine Learning
A fast randomized incremental gradient method for decentralized non-convex optimization
We study decentralized non-convex finite-sum minimization problems. In this context, we analyze a single-timescale randomized incremental gradient method. GT-SAGA is computationally efficient as it evaluates one component gradient per node per iteration.
1
0
0
Thu Nov 22 2018
Machine Learning
Markov Chain Block Coordinate Descent
The method of block coordinate gradient descent (BCD) has been a powerful method for large-scale optimization. This paper considers the BCD method that progressively updates a series of blocks selected according to a Markov chain.
0
0
0
Sun Jun 14 2020
Machine Learning
Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
We study stochastic gradient descent (SGD) and the Stochastic heavy ball method (SHB) We show that the convergence rate of the functionValues is arbitrarily close to in the overparametrized case.
1
0
0
Thu Feb 13 2020
Machine Learning
Nonasymptotic analysis of Stochastic Gradient Hamiltonian Monte Carlo under local conditions for nonconvex optimization
We provide a nonasymptotic analysis of the convergence of the stochastic gradient Hamiltonian Monte Carlo (SGHMC) to a target measure in Wasserstein-2distance. Our analysis quantifies key theoretical properties of the SGHMC as a sampler under local conditions.
0
0
0