A Stochastic Line Search Method with Convergence Rate Analysis
arXiv:1807.07994
Abstract
For deterministic optimization, line-search methods augment algorithms by providing stability and improved efficiency. We adapt a classical backtracking Armijo line-search to the stochastic optimization setting. While traditional line-search relies on exact computations of the gradient and values of the objective function, our method assumes that these values are available up to some dynamically adjusted accuracy which holds with some sufficiently large, but fixed, probability. We show the expected number of iterations to reach a near stationary point matches the worst-case efficiency of typical first-order methods, while for convex and strongly convex objective, it achieves rates of deterministic gradient descent in function values.
Cited by in corpus (17)
- Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces
- Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
- Gradient-only line searches: An Alternative to Probabilistic Line Searches
- Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
- Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
- Adaptive Stochastic Optimization
- A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems
- Adaptive Regularization for Nonconvex Optimization Using Inexact Function Values and Randomly Perturbed Derivatives
- Optimization of noisy blackboxes with adaptive precision
- StoMADS: Stochastic blackbox optimization using probabilistic estimates
- Gradient-only line searches to automatically determine learning rates for a variety of stochastic training algorithms
- Bounding the expected run-time of nonconvex optimization with early stopping
- Traversing the noise of dynamic mini-batch sub-sampled loss functions: A visual guide
- Parabolic Approximation Line Search for DNNs
- Analysis of the BFGS Method with Errors
- Direct-Search for a Class of Stochastic Min-Max Problems
- Approximately Exact Line Search