Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods

By Jascha Narain Sohl-Dickstein, Ben Poole, Surya Ganguli. 2013

130 citations recorded by the source corpus.

We present an algorithm for minimizing a sum of functions that combines the computational efficiency of stochastic gradient descent (SGD) with the second order curvature information leveraged by quasi-Newton methods. We unify these disparate approaches by maintaining an independent Hessian approximation for each contributing function in the sum. We maintain computational tractability and limit memory requirements even for high dimensional optimization problems by storing and manipulating these quadratic approximations in a shared, time evolving, low dimensional subspace. This algorithm contrasts with earlier stochastic second order techniques that treat the Hessian of each contributing function as a noisy approximation to the full Hessian, rather than as a target for direct estimation. Each update step requires only a single contributing function or minibatch evaluation (as in SGD), and each step is scaled using an approximate inverse Hessian and little to no adjustment of hyperparameters is required (as is typical for quasi-Newton methods). We experimentally demonstrate improved convergence on seven diverse optimization problems. The algorithm is released as open source Python and MATLAB packages.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Optimization & Training

Citations in the corpus

Adam: A Method for Stochastic Optimization (2014, methodology): “The sum-of-functions (SFO) method (Sohl-Dickstein et al., 2014) is a recently proposed quasi-Newton method that works with minibatches of data and has shown good performance on optimization of multi-layer neural networks.”
Deep Unsupervised Learning using Nonequilibrium Thermodynamics (2015, methodology): “In all cases the objective function and gradient were computed using Theano [4], and model training was with SFO [37].”
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization (2014, methodology): “The first direction is to explore methods beyond Kyrylov subspaces, such as one in (Sohl-Dickstein et al., 2014), that allow the saddlefree Newton method to scale to high dimensional problems, where we cannot easily compute the entire Hessian matrix.”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “An extensive list of convex loss functions used in a statistical data-fitting context is given by Teo et al. [2007], and non-smooth loss functions (or regularizers) can also be put in this framework by using smooth approximations (for example, see Nesterov [2005]).”
Discovering Hidden Factors of Variation in Deep Networks (2014, methodology): “, 2013b) and different training algorithms such as SGD with momentum, SFO (Sohl-Dickstein et al., 2014), or Dropout (Srivastava et al.”
A Kronecker-factored approximate Fisher matrix for convolution layers (2016, methodology): “This can be used in any number of ways in the context of optimization, most simply by using ∇̂h = [F̂(γ)]−1∇h as an approximation to the natural gradient F−1∇h. Alternatively, we could use it in the context of the full K-FAC algorithm, or as a preconditioner for iterative second-order methods (Marte”
A Progressive Batching L-BFGS Method for Machine Learning (2018, methodology): “Stochastic second-order methods have been explored within the context of convex and non-convex optimization; see (Schraudolph et al., 2007; Sohl-Dickstein et al., 2014; Mokhtari & Ribeiro, 2015; Berahas et al., 2016; Byrd et al., 2016; Keskar & Berahas, 2016; Curtis, 2016; Berahas & Tak´aˇc, 2017;…”
DAWNBench : An End-to-End Deep Learning Benchmark and Competition (2017, unknown): “Researchers have proposed new software systems [29, 1, 8, 12, 9, 46], training algorithms [33, 48, 45, 28, 44, 18, 27, 50, 42, 43, 14], communication methods [39, 49, 11, 9, 12, 22] and hardware [20, 30, 37, 19, 7, 21] to decrease this cost.”
SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization (2015, methodology): “, 2014) and (Sohl-Dickstein et al., 2014) in their stochastic quasi-Newton methods.”
Accelerating SVRG via second-order information (2015, background): “Note that [16] suffers from a high memory requirement and expensive per-iteration complexity.”
Regularization for Deep Learning: A Taxonomy (2017, methodology): “, 2011), Hessianfree methods (Martens, 2010), Sum-of-functions optimizer (Sohl-Dickstein et al., 2014), ProxProp (Frerix et al.”
A Linearly-Convergent Stochastic L-BFGS Algorithm (2015, methodology): “The inverse Hessian approximation H r is deﬁned from the pairs ( s j , y j ) for r − M + 1 ≤ j ≤ r using the standard L-BFGS update rule, which is described in Section 2.1.”
A modified Adam algorithm for deep neural network optimization (2023, methodology): “Second-order optimization methods are not widely used because they require more computations to obtain secondorder derivatives [49].”