History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms

Abstract

Variance-reduced algorithms, although achieve great theoretical performance, can run slowly in practice due to the periodic gradient estimation with a large batch of data. Batch-size adaptation thus arises as a promising approach to accelerate such algorithms. However, existing schemes either apply prescribed batch-size adaption rule or exploit the information along optimization path via additional backtracking and condition verification steps. In this paper, we propose a novel scheme, which eliminates backtracking line search but still exploits the information along optimization path by adapting the batch size via history stochastic gradients. We further theoretically show that such a scheme substantially reduces the overall complexity for popular variance-reduced algorithms SVRG and SARAH/SPIDER for both conventional nonconvex optimization and reinforcement learning problems. To this end, we develop a new convergence analysis framework to handle the dependence of the batch size on history stochastic gradients. Extensive experiments validate the effectiveness of the proposed batch-size adaptation scheme.

46 pages, 23 figures; Published in ICML 2020

References in corpus (17)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Don't Decay the Learning Rate, Increase the Batch Size
• 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
• The Optimal Reward Baseline for Gradient-Based Reinforcement Learning
• Recovery Guarantees for One-hidden-layer Neural Networks
• AdaBatch: Adaptive Batch Sizes for Training Deep Neural Networks
• Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines
• Stop Wasting My Gradients: Practical SVRG
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Big Batch SGD: Automated Inference using Adaptive Batch Sizes
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient
• Improving the convergence of SGD through adaptive batch sizes

Cited by in corpus (4)

• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Variance reduction for Riemannian non-convex optimization with batch size adaptation
• Improving the convergence of SGD through adaptive batch sizes