Hybrid Deterministic-Stochastic Methods for Data Fitting

By Michael P. Friedlander, Mark W. Schmidt. 2011

414 citations recorded by the source corpus.

Many structured data-fitting applications require the solution of an optimization problem involving a sum over a potentially large number of measurements. Incremental gradient algorithms offer inexpensive iterations by sampling a subset of the terms in the sum. These methods can make great progress initially, but often slow as they approach a solution. In contrast, full-gradient methods achieve steady convergence at the expense of evaluating the full objective and gradient on each iteration. We explore hybrid methods that exhibit the benefits of both approaches. Rate-of-convergence analysis shows that by controlling the sample size in an incremental gradient algorithm, it is possible to maintain the steady convergence rates of full-gradient methods. We detail a practical quasi-Newton implementation based on this approach. Numerical experiments illustrate its potential benefits.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Don't Decay the Learning Rate, Increase the Batch Size (2017, background): “We note that a number of recent works have discussed increasing the batch size during training (Friedlander & Schmidt, 2012; Byrd et al., 2012; Balles et al., 2016; Bottou et al., 2016; De et al., 2017), but to our knowledge no paper has shown empirically that increasing the batch size and decaying…”
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “In particular, a bound on the variance with vanishing constants is needed, which, as far as we know, can only be satisﬁed by running SGDA with growing mini-batch size [Friedlander and Schmidt, 2012] (see also App.”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “The required geometric growth rate for G k is the same as that of SGD to obtain linear convergence without variance-reduction or interpolation (De et al., 2016; Friedlander and Schmidt, 2012).”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Other authors [23, 13, 18, 64, 43] use a line-search termination criteria that requires function/gradient evaluations averaged over multiple samples.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “ing sample sizes. 43 One approach is to follow the theoretical results described above and tie the rate of growth in the sample size n k= jS kjto the rate of convergence of the optimization iteration [59,74]. Such an approach, which presets the sampling rate before running the optimization algorithm”
Minimizing finite sums with the stochastic average gradient (2013, background): “Friedlander and Schmidt [17] give conditions under which this strategy achieves the O(1/k) and O(ρk) convergence rates of FG methods.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “References [10, 6] show, for strongly convex stochastic minimization, that SGD with exponentially increasing batch sizes can achieve linear convergence rate on a single machine.”
Hyperparameter optimization with approximate gradient (2016, methodology): “The analysis of this al-gorithm is inspired by the work of d’Aspremont (2008); Schmidt et al. (2011); Friedlander and Schmidt (2012) on inexact-gradient algorithms for convex optimization.”
A Bayesian Perspective on Generalization and Stochastic Gradient Descent (2017, neutral): “We can then exploit increased parallelism across multiple GPUs, reducing model training times (Goyal et al., 2017). A similar scaling rule was independently proposed by Jastrzebski et al. (2017) and Chaudhari & Soatto (2017), although neither work identifies the existence of an optimal noise scale.”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, background): “, [11, 6, 10]) have explored this idea by using mini-batches with exponentially growing sizes, but their overall computational cost is still on the same order as full gradient methods.”
Semi-Stochastic Gradient Descent Methods (2013, methodology): “Earlier works of Friedlander and Schmidt [15], Deng and Ferris [16], and Bastin et al.”
Demystifying Parallel and Distributed Deep Learning (2018, methodology): “Also, large-batch methods only converge and generalize when: (a) learning rates are adjusted statically [84, 141] or adaptively [259]; (b) using a “warmup” phase [84]; (c) using the batch size to control gradient variance [78]; (d) adaptively increasing minibatch size during training [226]; or (e) w”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “Our comparisons also included a deterministic L-BFGS algorithm and the Hybrid L-BFGS/stochastic algorithm of [6].”
Online Batch Selection for Faster Training of Neural Networks (2015, background): “The detailed theoretical analysis of advantages of batch size scheduling can be found in (Friedlander & Schmidt, 2012; Babanezhad et al., 2015).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Earlier works of [62], [48] and [10] attempt to interpolate between GD and SGD and decrease variance by varying the sample size.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “In the area of deterministic algorithms, the inexact variant of the full gradient descent method, xk+1 = xk−ωk[∇f(xk)+ k], has received a lot of attention [49, 11, 51, 16, 32].”
On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization (2019, methodology): “For strongly convex stochastic minimization, it is proven in (Friedlander & Schmidt, 2012; Bottou et al., 2For general non-convex functions, the convergence rate is usually measured in terms of ‖∇f(x)‖2 which in some sense can be considered as the counterpart of f(x)− f(x∗) in convex case…”