Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting

By Jakub Konecný, Jie Liu, Peter Richtárik, Martin Takác. 2015

279 citations recorded by the source corpus.

We propose mS2GD: a method incorporating a mini-batching scheme for improving the theoretical complexity and practical performance of semi-stochastic gradient descent (S2GD). We consider the problem of minimizing a strongly convex function represented as the sum of an average of a large number of smooth convex functions, and a simple nonsmooth convex regularizer. Our method first performs a deterministic step (computation of the gradient of the objective function at the starting point), followed by a large number of stochastic steps. The process is repeated a few times with the last iterate becoming the new starting point. The novelty of our method is in introduction of mini-batching into the computation of stochastic steps. In each step, instead of choosing a single function, we sample b functions, compute their gradients, and compute the direction based on this. We analyze the complexity of the method and show that it benefits from two speedup effects. First, we prove that as long as b is below a certain threshold, we can reach any predefined accuracy with less overall work than without mini-batching. Second, our mini-batching scheme admits a simple parallel implementation, and hence is suitable for further acceleration by parallelization.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Mathematical Optimization

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 Optimization & Training

In Mathematical Optimization

Citations in the corpus

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The SVRG algorithm runs in two nested loops.”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, background): “Finally, the recent work [10] generalizes S2GD to the mini-batch setting, thereby also permitting parallel processing, albeit with more synchronization and allowing only small mini-batches.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, background): “In other words, when naively equipped with momentum, stochastic gradient methods are “very prune to error accumulation” [22] and do not yield accelerated convergence rates in general.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “Another algorithm from the SGD class of methods is Stochastic Variance Reduced Gradient(1) (SVRG) [80] and [89, 187, 81].”
Stochastic Recursive Gradient Algorithm for Nonconvex Optimization (2017, background): “Recently, a large number of improved variants of stochastic gradient algorithms have emerged, including SAG/SAGA [22, 4], MISO/FINITO [13, 5], SDCA [24], SVRG/S2GD [9, 10], SARAH [16] 1.”
Efficient Distributed SGD with Variance Reduction (2015, methodology): “Variance reduction (VR) methods [13, 14, 15, 16, 17, 18, 19, 20, 21, 22] have recently gained popularity as an alternative to classical SGD.”
StopWasting My Gradients: Practical SVRG (2015, methodology): “[18] have also recently considered using batches of data within SVRG.”
Stochastic Block BFGS: Squeezing More Curvature out of Data (2016, methodology): “rmly at random. Using the subsampled gradient rf S(x) as a proxy for the gradient is the basis for (minibatch) stochastic gradient descent (SGD), but also for many successful variance-reduced methods [32, 36, 18, 19, 5, 35, 20] that make use of the subsampled gradient in calculating g t: Recently, t”