Abstract
In modern machine learning, adaptive optimization is essential for handling diverse objective landscapes without exhaustive hyperparameter tuning. While online adaptive algorithms like AdaGrad have seen significant success, their application to offline and stochastic settings often requires specific adjustments to maintain optimality. This paper presents a novel conversion scheme that transforms online adaptive algorithms into offline methods. These derived methods, such as AdaNGD, provide favorable guarantees based on the harmonic sum of queried gradients and implicitly adapt to the objective's structure. Specifically, they achieve fast convergence in smooth settings without prior knowledge of smoothness parameters while remaining robust in non-smooth cases. Furthermore, we extend this approach to stochastic optimization via "Lazy-SGD," where minibatch sizes are chosen adaptively based on gradient magnitude, offering a principled framework for variance reduction.
Introduction
The pursuit of "adaptiveness" is a central theme in optimization research. Ideally, an algorithm should automatically determine its own step size or learning rate by observing the geometry of the objective function. While algorithms like AdaGrad and Adam have revolutionized online learning—where data arrives sequentially and may be adversarial—their performance in offline or stochastic settings can be suboptimal compared to specialized methods.
This research bridges the gap between online adaptivity and offline efficiency. By introducing a novel online-to-offline conversion scheme, we develop a family of "universal" algorithms. These methods automatically adapt to the smoothness of a problem and provide a theoretically grounded approach to selecting minibatch sizes in stochastic gradient descent (SGD).
The Challenge of Universality
Optimization problems generally fall into two categories: smooth and non-smooth.
- Smooth Problems: If an objective is known to be smooth, algorithms like Gradient Descent with a constant step size can achieve a fast $O(1/T)$ convergence rate.
- Non-smooth Problems: For non-smooth objectives, practitioners typically rely on Subgradient Descent, which yields a slower $O(1/\sqrt{T})$ rate.
A "universal" algorithm is one that achieves the optimal rate for both scenarios without being explicitly told the smoothness parameter ($\beta$). While existing universal methods often utilize expensive line-search procedures, this work proposes a more direct, adaptive approach derived from online learning principles.
Online-to-Offline Conversion and AdaNGD
The core contribution of this work is a conversion scheme that leverages the strengths of online adaptive algorithms for offline optimization.
AdaNGD (Adaptive Normalized Gradient Descent)
The authors introduce AdaNGD, which applies the logic of AdaGrad to a sequence of normalized gradients. Unlike standard averaging techniques, AdaNGD employs a "hindsight weighting" scheme. In this scheme, points associated with smaller gradients are assigned higher weights in the final output. This allows the algorithm to focus its attention on regions near the optimum where the gradient norm vanishes.
The performance of AdaNGD is characterized by the harmonic sum of the queried gradients. Because the harmonic mean is dominated by small values, the algorithm naturally accelerates when it encounters regions of low curvature or approaches the global minimum.
SC-AdaNGD
For objectives that are strongly convex, the authors propose SC-AdaNGD. This variant implicitly interpolates between the decaying learning rates required for general convex functions and the constant learning rates optimal for smooth, strongly convex functions. This interpolation is driven by the observed decay of gradient norms, allowing for exponential (linear) convergence rates, $O(\exp(-\gamma T))$, in smooth settings.
Principled Minibatching: Lazy-SGD
In stochastic optimization, minibatches are used to reduce the variance of gradient estimates. While theory often suggests a minibatch size of 1, empirical evidence favors larger batches. However, choosing the "right" size has historically been a matter of trial and error.
This paper introduces Lazy-SGD, a stochastic extension of the adaptive framework. Lazy-SGD utilizes an "Adaptive Estimate" (AE) procedure to determine the number of samples drawn from a noisy gradient oracle. The key insight is that the optimal minibatch size should be inversely proportional to the square of the gradient norm:
$$\text{Minibatch Size} \propto \frac{1}{\|g\|^2}$$
When the gradient is large, the algorithm takes small batches and moves quickly. As the gradient becomes smaller (indicating the algorithm is nearing the optimum), the algorithm becomes "lazy," spending more time at the current point to draw a larger minibatch. This provides a high-precision estimate exactly when the signal-to-noise ratio is lowest, effectively reducing variance where it matters most.
Experimental Validation
The theoretical claims were validated through controlled experiments on synthetic problems:
- Smooth Quadratic Minimization: Testing convergence on smooth, strongly convex objectives.
- Non-smooth Strongly Convex Problems: Utilizing a quadratic objective with an $\ell_1$ norm term to test robustness against non-smoothness.
In these tests, SC-AdaNGD variants outperformed standard Gradient Descent and traditional line-search methods. Specifically, a variant with a growth parameter $k=1.1$ demonstrated significantly faster convergence than standard GD, confirming the practical utility of the harmonic sum-based guarantees.
Conclusion and Future Directions
This work provides a principled bridge between online adaptivity and offline optimization. By focusing on the harmonic sum of gradients and hindsight weighting, the proposed algorithms achieve universality across smooth and non-smooth landscapes. The Lazy-SGD framework further offers a theoretical justification for adaptive minibatching, a long-standing question in stochastic optimization.
Future research may address the current dependence of SC-AdaNGD on the strong-convexity parameter ($H$) and explore the application of these techniques to non-convex landscapes, such as those found in deep neural networks. Additionally, investigating the behavior of these algorithms when the global minimum lies on the boundary of the constraint set remains an open area for exploration.
Summary updated