Probabilistic Line Searches for Stochastic Optimization

By Maren Mahsereci, Philipp Hennig. 2015

133 citations recorded by the source corpus.

In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a probabilistic line search by combining the structure of existing deterministic methods with notions from Bayesian optimization. Our method retains a Gaussian process surrogate of the univariate optimization objective, and uses a probabilistic belief over the Wolfe conditions to monitor the descent. The algorithm has very low computational cost, and no user-controlled parameters. Experiments show that it effectively removes the need to define a learning rate for stochastic gradient descent.

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

Citations in the corpus

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “For these experiments we also compare against a standard VR method (SVRG) [36] and probabilistic line-search (PLS) [55].”
Early Stopping without a Validation Set (2017, neutral): “Here the variance estimator of the gradient distribution is denoted as Σ̂(w) ≈ varx∼p(x) [∇`(w, x)] with Σ̂(w) = 1/(|S|−1) ∑ x∈S (∇`(w, x)−∇LS(w)) 2, where 2 denotes the elementwise square and S is either the full dataset D or a mini-batch B.”
Automatic Differentiation Variational Inference (2016, background): “Optimization using line search could also improve convergence speed and robustness (Mahsereci and Hennig, 2015), as well as natural gradient approaches for nonconjugate models (Khan et al.”
An empirical analysis of the optimization of deep network loss surfaces (2016, background): “Some have characterized the critical points of deep linear neural networks [2, 28] and high-dimensional, random Gaussian error functions [4, 9, 11, 24].”
Coupling Adaptive Batch Sizes with Learning Rates (2016, background): “More generally, our work ﬁts into a recent effort to auto-mate or simplify the tuning of parameters in stochastic optimization algorithms, most notably the learning rate [23, 17].”
L4: Practical loss-based stepsize adaptation for deep learning (2018, background): “Also, an interesting Bayesian approach for probabilistic line search has been proposed in [13].”
An Empirical Analysis of Deep Network Loss Surfaces (2016, methodology): “One approach is to analogize the states of neurons as the magnetics dipoles used in spherical spinglass Ising models from statistical physics (Parisi, 2016; Fyodorov & Williams, 2007; Bray & Dean, 2007).”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, background): “However, line search techniques have a high computational cost in general, which limits their applicability to stochastic optimization [29].”
Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients (2017, methodology): “Several recent papers (Mahsereci & Hennig, 2015; Balles et al., 2017b) have used this variance estimate for other aspects of stochastic optimization.”
Follow the Signs for Robust Stochastic Optimization (2017, background): “Several recent papers [11, 2, 12] have pointed out that an explicit, local estimate of the gradient variance r(θ) can be obtained from a single mini-batch evaluation via r̂(θ) = 1 |B| − 1 (”
A Subsampling Line-Search Method with Second-Order Results (2018, methodology): “ewton and negative curvature procedure using each iteration’s chosen mini-batch as the source of function evaluation sample in the line search. A more mature approach for line search was presented in [35], where extensive experiments matching performance to pre-tuned SGD were presented. An innovatin”
A Unifying Framework for Gaussian Process Pseudo-Point Approximations using Power Expectation Propagation (2016, background): “…(Rasmussen and Williams, 2005), representation learning (Lawrence, 2005), state space modelling (Wang et al., 2005), active learning (Houlsby et al., 2011), reinforcement learning (Deisenroth, 2010), black-box optimisation (Snoek et al., 2012), and numerical methods (Mahsereci and Hennig, 2015).”
Backtracking gradient descent method for general $C^1$ functions, with applications to Deep Learning (2018, methodology): “This phenomenon has been observed in practice, and the method of rescaling of learning rates has been proposed to prevent it, in both Standard GD [29] and Wolfe’s method [30].”
Barzilai-Borwein Step Size for Stochastic Gradient Descent (2016, background): “[12] suggests performing line search for an estimated function, which is evaluated by a Gaussian process with samples fit(xt).”
Bayesian Probabilistic Numerical Methods (2017, background): “[2016] Optimiser arg minx(t) {x(ti)}i=1 Bayesian Optimisation [Mockus, 1989](6) {∇x(ti)}i=1 Hennig and Kiefel [2013] {(x(ti),∇x(ti)}i=1 Probabilistic Line Search [Mahsereci and Hennig, 2015] {I[tmin < ti]}i=1 Probabilistic Bisection Algorithm [Horstein, 1963](5) {I[tmin < ti] + error}i=1 Waeber et a”
A Unifying Framework for Sparse Gaussian Process Approximation using Power Expectation Propagation (2016, background): “005), state space modelling (Wang et al., 2005), active learning (Houlsby et al., 2011), reinforcement learning (Deisenroth, 2010), black-box optimisation (Snoek et al., 2012), and numerical methods (Mahsereci and Hennig, 2015). GPs have many elegant theoretical properties, but their use is greatly ”
Big Batch SGD: Automated Inference using Adaptive Batch Sizes (2016, methodology): “While there has been some work on adaptive stepsize methods for stochastic optimization (Mahsereci and Hennig, 2015; Schaul et al., 2013; Tan et al., 2016; Kingma and Ba, 2014; Zeiler, 2012), the methods are largely heuristic without any kind of theoretical guarantees or convergence rates.”
Automated Inference with Adaptive Batches (2017, methodology): “While there has been some work on adaptive stepsize methods for stochastic optimization (Mahsereci and Hennig, 2015; Schaul et al., 2013; Tan et al., 2016; Kingma and Ba, 2014; Zeiler, 2012), the methods are largely heuristic without any kind of theoretical guarantees or convergence rates.”
DeepOBS: A Deep Learning Optimizer Benchmark Suite (2019, background): “…Hutter, 2017; Reddi et al., 2018), incorporation of second-order information (Martens, 2010; Martens & Grosse, 2015; Botev et al., 2017; Zhang et al., 2017; Chen et al., 2018), and automating optimization (Schaul et al., 2013b; Mahsereci & Hennig, 2017; Rolinek & Martius, 2018), to name just a few.”
BackPACK: Packing more into backprop (2019, methodology): “…of the gradients within the batch has been found to be theoretically and practically useful for adapting hyperparameters like learning rates (Mahsereci & Hennig, 2017) and batch sizes (Balles et al., 2017), or regularize ﬁrst-order optimization (Le Roux et al., 2007; Balles & Hennig, 2018;…”