Almost Tune-Free Variance Reduction
arXiv:1908.09345
Abstract
The variance reduction class of algorithms including the representative ones, SVRG and SARAH, have well documented merits for empirical risk minimization problems. However, they require grid search to tune parameters (step size and the number of iterations per inner loop) for optimal performance. This work introduces `almost tune-free' SVRG and SARAH schemes equipped with i) Barzilai-Borwein (BB) step sizes; ii) averaging; and, iii) the inner loop length adjusted to the BB step sizes. In particular, SVRG, SARAH, and their BB variants are first reexamined through an `estimate sequence' lens to enable new averaging methods that tighten their convergence rates theoretically, and improve their performance empirically when the step size or the inner loop length is chosen large. Then a simple yet effective means to adjust the number of iterations per inner loop is developed to enhance the merits of the proposed averaging schemes and BB step sizes. Numerical tests corroborate the proposed methods.
References in corpus (11)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
- Stochastic Variance Reduction for Nonconvex Optimization
- Non-convex Finite-Sum Optimization Via SCSG Methods
- Variance Reduction for Faster Non-Convex Optimization
- Momentum-Based Variance Reduction in Non-Convex SGD
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
- Adaptive Step Sizes in Variance Reduction via Regularization
- On the Convergence of SARAH and Beyond
- Accelerating Mini-batch SARAH by Step Size Rules