Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization

By Quoc Tran-Dinh, Nhan H. Pham, Dzung T. Phan, Lam M. Nguyen. 2019

60 citations recorded by the source corpus.

We introduce a hybrid stochastic estimator to design stochastic gradient algorithms for solving stochastic optimization problems. Such a hybrid estimator is a convex combination of two existing biased and unbiased estimators and leads to some useful property on its variance. We limit our consideration to a hybrid SARAH-SGD for nonconvex expectation problems. However, our idea can be extended to handle a broader class of estimators in both convex and nonconvex settings. We propose a new single-loop stochastic gradient descent algorithm that can achieve $O(\max\{\sigma^3\varepsilon^{-1},\sigma\varepsilon^{-3}\})$-complexity bound to obtain an $\varepsilon$-stationary point under smoothness and $\sigma^2$-bounded variance assumptions. This complexity is better than $O(\sigma^2\varepsilon^{-4})$ often obtained in state-of-the-art SGDs when $\sigma < O(\varepsilon^{-3})$. We also consider different extensions of our method, including constant and adaptive step-size with single-loop, double-loop, and mini-batch variants. We compare our algorithms with existing methods on several datasets using two nonconvex models.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “• We prove that incorporating momentum based variance reduction [4, 33] into each local client update reduces client drift and obtains the optimal statistical rates.”
Better Theory for SGD in the Nonconvex World (2020, unknown): “We now consider the regularized logistic regression problem from (Tran-Dinh et al., 2019) with the aim of testing the ﬁt of our Assumption 2 compared to other assumptions.”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “Recently, [39] demonstrated in that the convex combination of SGD and SARAH [27] performs very well on non-convex problems.”
Momentum-Based Variance Reduction in Non-Convex SGD (2019, background): “Independently and simultaneously with this work, [24] have proposed a new algorithm that does improve over SGD to match our same convergence rate, although it does still require one checkpoint gradient.”