Abstract
We consider the problem of minimizing a convex function over a closed convex set, with Projected Gradient Descent (PGD). We propose a fully parameter-free version of AdaGrad, which is adaptive to the distance between the initialization and the optimum, and to the sum of the square norm of the subgradients. Our algorithm is able to handle projection steps, does not involve restarts, reweighing along the trajectory or additional gradient evaluations compared to the classical PGD. It also fulfills optimal rates of convergence for cumulative regret up to logarithmic factors. We provide an extension of our approach to stochastic optimization and conduct numerical experiments supporting the developed theory.
Introduction
In convex optimization, achieving optimal performance typically requires precise tuning of hyperparameters. Standard algorithms like Projected Gradient Descent (PGD) and AdaGrad often necessitate prior knowledge of the distance to the optimum ($||x_1 - x_*||$), the Lipschitz constant ($L$), and the optimization horizon ($T$). Incorrect estimation of these parameters can lead to slow convergence or failure. While techniques like the "doubling trick" or "coin betting" exist, they often rely on "cold restarts"—discarding progress and restarting from the initial point—or struggle with projection steps on constrained sets.
This paper introduces FREE ADAGRAD, a fully parameter-free optimization algorithm that adapts to these unknowns automatically. It achieves near-optimal convergence rates without the overhead of restarts or additional gradient evaluations, even when operating on unbounded sets.
Methodology: The FREE ADAGRAD Algorithm
The core innovation of FREE ADAGRAD is an automatically tuned sequence $k_t$ that governs the step size $\eta_t$. The algorithm operates through a series of "probing" steps and a distance-based doubling condition.
At each iteration, the algorithm performs a projection step and checks if the distance from the current iterate to the initialization exceeds a specific threshold $B_{t+1}(k)$. If this threshold is breached, it indicates that the current step size parameter $k$ is underestimating the distance to the optimum. In response, the algorithm doubles the parameter $k$ and continues. Unlike traditional doubling tricks, FREE ADAGRAD does not perform cold restarts; it maintains its current position $x_t$, preserving the progress made in previous iterations.
This mechanism allows for implicit distance tracking, where the algorithm "learns" the distance to $x_*$ by monitoring its displacement from $x_1$. Furthermore, the algorithm is scale-invariant: multiplying the objective function by a constant scales the regret bound proportionally without requiring manual retuning.
Theoretical and Empirical Results
Theoretical Guarantees
The authors establish a cumulative regret bound for FREE ADAGRAD of approximately: $$R_T \leq \tilde{O}(||x_1 - x_*|| \sqrt{\sum ||g_t||^2})$$ where $\tilde{O}$ hides logarithmic factors. This rate matches the theoretical lower bounds for adaptive optimization. Through online-to-batch conversion, the average of the iterates $\bar{x}_T$ is shown to converge to the optimum at a rate of $1/\sqrt{T}$ (up to log factors).
Empirical Performance
The algorithm was evaluated using synthetic numerical experiments on various convex functions, including $L_1$ and $L_2$ norms and absolute linear forms ($f(x) = \frac{1}{n} \sum | \langle a_i, x \rangle |$). These tests demonstrated that FREE ADAGRAD consistently tracks or outperforms standard AdaGrad and even "Oracle" PGD (which knows the exact Lipschitz constant). The advantage over the Oracle stems from FREE ADAGRAD's ability to adapt to the local norms of subgradients encountered along the trajectory, rather than relying on a global worst-case constant.
Discussion and Limitations
While FREE ADAGRAD represents a significant step toward truly parameter-free optimization, several areas for future work remain:
- Online Convex Optimization (OCO): Extending these specific bounds to settings where the objective function changes at every step is non-trivial.
- Stochastic Optimization: The current extension to Stochastic Gradient Descent (SGD) still requires knowledge of the Lipschitz constant $L$ to set the step size correctly.
- Logarithmic Overhead: There is a minor theoretical cost in the form of extra logarithmic factors compared to perfectly tuned algorithms.
- Last-Iterate Convergence: The tightest convergence bounds currently apply to the average iterate ($\bar{x}_T$); achieving similar results for the last iterate without additional assumptions remains an open challenge.
Summary updated