Gradient Descent
LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning
Tianyi Chen, Georgios Giannakis, Tao Sun, Wotao Yin
This paper presents a new class of gradient methods for distributed machine learning that adaptively skip the gradient calculations to learn with reduced communication and computation. Simple rules are designed to detect slowly-varying gradients and, therefore, trigger the reuse of outdated gradients. The resultant gradient-based algorithms are termed Lazily A ggregated G radient -- justifying our acronym LAG used henceforth. Theoretically, the merits of this contribution are: i) the convergence rate is the same as batch gradient descent in strongly-convex, convex, and nonconvex cases; and, ii) if the distributed datasets are heterogeneous (quantified by certain measurable constants), the communication rounds needed to achieve a targeted accuracy are reduced thanks to the adaptive reuse of lagged gradients. Numerical experiments on both synthetic and real data corroborate a significant communication reduction compared to alternatives.
Efficient Stochastic Gradient Hard Thresholding
Pan Zhou, Xiaotong Yuan, Jiashi Feng
The results of AHSG-HT are established for quadratic loss functions.
The Effect of Network Width on the Performance of Large-batch Training
Lingjiao Chen, Hongyi Wang, Jinman Zhao, Dimitris Papailiopoulos, Paraschos Koutris
Distributed implementations of mini-batch stochastic gradient descent (SGD) suffer from communication overheads, attributed to the high frequency of gradient updates inherent in small-batch training.
A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
In particular, ProxSVRG+ generalizes the best results given by the SCSG algorithm, recently proposed by [Lei et al.,
On the Local Minima of the Empirical Risk
Chi Jin, Lydia T. Liu, Rong Ge, Michael I. Jordan
Even for applications with nonconvex nonsmooth losses (such as modern deep networks), the population risk is generally significantly more well-behaved from an optimization point of view than the empirical risk.
Variance-Reduced Stochastic Gradient Descent on Streaming Data
Ellango Jothimurugesan, Ashraf Tahmasbi, Phillip Gibbons, Srikanta Tirthapura
Such a model is never "complete" but instead needs to be continuously updated as newer training data points arrive.
Sample Efficient Stochastic Gradient Iterative Hard Thresholding Method for Stochastic Sparse Linear Regression with Limited Attribute Observation
In real-world sequential prediction scenarios, the features (or attributes) of examples are typically high-dimensional and construction of the all features for each example may be expensive or impossible.
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport
This is an idealization of the usual way to train neural networks with a large hidden layer.
Stochastic Chebyshev Gradient Descent for Spectral Optimization
Insu Han, Haim Avron, Jinwoo Shin
Unfortunately, computing the gradient of a spectral function is generally of cubic complexity, as such gradient descent methods are rather expensive for optimizing objectives involving the spectral function.
Bayesian Distributed Stochastic Gradient Descent
Neural Information Processing Systems http://nips.cc/