On the Adaptivity of Stochastic Gradient-Based Optimization

Stochastic gradient-based optimization has been a core enabling methodology in applications to large-scale problems in machine learning and related areas. Despite this progress, the gap between theory and practice remains significant, with theoreticians pursuing mathematical optimality at the 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 it 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 refer to as geometrization, and 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 depend only on the smoothness parameter of the objective.