Better Mini-Batch Algorithms via Accelerated Gradient Methods

By Andrew Cotter, Ohad Shamir, Nati Srebro, Karthik Sridharan. 2011

330 citations recorded by the source corpus.

Mini-batch algorithms have been proposed as a way to speed-up stochastic convex optimization problems. We study how such algorithms can be improved using accelerated gradient methods. We provide a novel analysis, which shows how standard gradient methods may sometimes be insufficient to obtain a significant speed-up and propose a novel accelerated gradient algorithm, which deals with this deficiency, enjoys a uniformly superior guarantee and works well in practice.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

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 Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “for convex objectives [256, 119, 132].”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “We note that minibatch SGD can also be accelerated (Cotter et al., 2011), leading to a bound with better dependence on R , but this is again outmatched by the bound for the (accelerated) local-AC-SA algorithm above.”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “Comparing (18) and (22), we see that SVRG also improves over A-MB-SGD as soon as K > T log(TKM/L), that is if the number of points we are processing on each machine each round is slightly more then the total number of rounds, which is also a realistic scenario.”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “, 2017), which uses codes to speed up synchronous distributed first-order methods (Raviv et al., 2017; Charles et al., 2017; Cotter et al., 2011).”
Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “For the derivation of C ( n, q ) see for instance Lemma B.2 in Cotter et al. (2011).”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, methodology): “A similar dependence occurs with other recently-proposed algorithms for distributed optimization (e.g. Yang, 2013; Mahajan et al., 2013; Dekel et al., 2012; Cotter et al., 2011; Duchi et al., 2012).”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “This is a well-known fact in optimization, and most convergence bounds for stochastic-gradient based methods, including minibatch, involve upper bounds on E[‖ĝ(wk)‖](2)2, in a multiplicative form, for both convex and nonconvex setups [39, 40, 41, 42, 42, 43, 44, 45, 46, 47].”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “data [19, 7, 10, 8], or settings where the computing architecture is different, e.”
An asynchronous parallel stochastic coordinate descent algorithm (2013, methodology): “Parallel stochastic gradient approaches have received broad attention; see Agarwal and Duchi [2012] for an approach that allows delays between evaluation and update, and [Cotter et al., 2011] for a minibatch stochastic gradient approach with Nesterov acceleration.”
Mini-Batch Primal and Dual Methods for SVMs (2013, background): “Several recent papers consider the use of mini-batches in stochastic gradient descent, as well as stochastic dual averaging and stochastic mirror descent, when minimizing a smooth loss function (Dekel et al., 2012; Agarwal & Duchi, 2011; Cotter et al., 2011).”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, methodology): “In that case, Following previous work (e.g. [15]), we even assume that E [ x 2 i ] = 1 for all i , in which case the sparse PCA problem reduces to detecting a coordinate pair ( i ∗ , j ∗ ) , i ∗ j ∗ for which x i ∗ , x j ∗ are maximally correlated.”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “See for example [10, 9, 4] and the references therein.”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “Following Cotter et al. (2011), we assume that ℓ(w, ξ) is β-smooth: ∥∥∇ℓ(w, ξ)−∇ℓ(w′, ξ) ∥∥ ≤ β ∥∥w −w′ ∥∥ , ∀w,w′ ∈ Ω. Assume that the domain Ω is bounded with radius B = sup w∈Ω ‖w‖.”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “In ord e to enable parallelism, the idea of mini-batching—using estim a ing the gradient using multiple random i in each iteration—is often employed [21], [22], [23], [24], [18], [25].”
Inference Compilation and Universal Probabilistic Programming (2016, methodology): “The source code for our framework and for reproducing the experiments in this paper can be found on our project page.”
Adaptive Sampling for SGD by Exploiting Side Information (2016, background): “An alternative is to average over a mini batch of instances, which can be implemented efficiently and also improves the convergence for certain mini batch sizes(Li et al., 2014; Cotter et al., 2011).”
Backdoor Embedding in Convolutional Neural Network Models via Invisible Perturbation (2018, methodology): “ in a sequential order, and used to update all the parameters of the CNN model. 1 3.2.3 Poisoned Training. Typically, a CNN model is trained and updated using mini-batch gradient descent optimization [6, 10] and backpropagation [30]. The training procedure is essentially a process of finding the opt”