On the Adaptivity of Stochastic Gradient-Based Optimization

Abstract

Stochastic-gradient-based optimization has been a core enabling methodology in applications to large-scale problems in machine learning and related areas. Despite the progress, the gap between theory and practice remains significant, with theoreticians pursuing mathematical optimality at a cost of obtaining specialized procedures in different regimes (e.g., modulus of strong convexity, magnitude of target accuracy, signal-to-noise ratio), and with practitioners not readily able to know which regime is appropriate to their problem, and seeking broadly applicable algorithms that are reasonably close to optimality. To bridge these perspectives it is necessary to study algorithms that are adaptive to different regimes. We present the stochastically controlled stochastic gradient (SCSG) method for composite convex finite-sum optimization problems and show that SCSG is adaptive to both strong convexity and target accuracy. The adaptivity is achieved by batch variance reduction with adaptive batch sizes and a novel technique, which we referred to as geometrization, which sets the length of each epoch as a geometric random variable. The algorithm achieves strictly better theoretical complexity than other existing adaptive algorithms, while the tuning parameters of the algorithm only depend on the smoothness parameter of the objective.

arXiv commentAccepted by SIAM Journal on Optimization; 54 pages

References in corpus (17)

• 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
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Variance Reduction for Nonconvex Optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• A Universal Catalyst for First-Order Optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Proximal Stochastic Dual Coordinate Ascent
• On the Universality of Online Mirror Descent
• Optimal Black-Box Reductions Between Optimization Objectives
• Tight Complexity Bounds for Optimizing Composite Objectives
• A Lower Bound for the Optimization of Finite Sums
• A unified variance-reduced accelerated gradient method for convex optimization
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• An optimal algorithm for stochastic strongly-convex optimization
• Revisiting the Polyak step size

Cited by in corpus (6)

• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• Enhanced Bilevel Optimization via Bregman Distance
• On the Convergence of SARAH and Beyond
• Variance Reduction with Sparse Gradients
• Variance Reduction on General Adaptive Stochastic Mirror Descent
• Stochastic ADMM with batch size adaptation for nonconvex nonsmooth optimization