Barzilai-Borwein Step Size for Stochastic Gradient Descent
arXiv:1605.04131
Abstract
One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step size by hand, which can be time consuming in practice. In this paper, we propose to use the Barzilai-Borwein (BB) method to automatically compute step sizes for SGD and its variant: stochastic variance reduced gradient (SVRG) method, which leads to two algorithms: SGD-BB and SVRG-BB. We prove that SVRG-BB converges linearly for strongly convex objective functions. As a by-product, we prove the linear convergence result of SVRG with Option I proposed in [10], whose convergence result is missing in the literature. Numerical experiments on standard data sets show that the performance of SGD-BB and SVRG-BB is comparable to and sometimes even better than SGD and SVRG with best-tuned step sizes, and is superior to some advanced SGD variants.
References in corpus (3)
Cited by in corpus (34)
- Optimization for deep learning: theory and algorithms
- Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
- Big Batch SGD: Automated Inference using Adaptive Batch Sizes
- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
- Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers
- Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
- Distributed and Scalable Optimization for Robust Proton Treatment Planning
- Second-order step-size tuning of SGD for non-convex optimization
- The Barzilai-Borwein Method for Distributed Optimization over Unbalanced Directed Networks
- Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
- Bold Diagrammatic Monte Carlo in the Lens of Stochastic Iterative Methods
- Stochastic Subspace Descent
- Training Neural Networks for and by Interpolation
- A stochastic gradient descent approach with partitioned-truncated singular value decomposition for large-scale inverse problems of magnetic modulus data
- On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
- Adaptive Step Sizes in Variance Reduction via Regularization
- AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
- A variable metric mini-batch proximal stochastic recursive gradient algorithm with diagonal Barzilai-Borwein stepsize
- Geometric Convergence for Distributed Optimization with Barzilai-Borwein Step Sizes
- On the Convergence of SARAH and Beyond
- Neuro-Optimization: Learning Objective Functions Using Neural Networks
- SGDLibrary: A MATLAB library for stochastic gradient descent algorithms
- A family of spectral gradient methods for optimization
- Accelerating Mini-batch SARAH by Step Size Rules
- Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
- On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization
- On a Faster -Linear Convergence Rate of the Barzilai-Borwein Method
- On the acceleration of the Barzilai-Borwein method
- Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
- Data-driven Algorithm Selection and Parameter Tuning: Two Case studies in Optimization and Signal Processing
- TATi-Thermodynamic Analytics ToolkIt: TensorFlow-based software for posterior sampling in machine learning applications
- A Semismooth Newton Method for Support Vector Classification and Regression
- Compositional Stochastic Average Gradient for Machine Learning and Related Applications
- Automatic and Simultaneous Adjustment of Learning Rate and Momentum for Stochastic Gradient Descent