TL;DR
This paper introduces adaAGC, a novel adaptive accelerated gradient method that achieves faster convergence for a wide range of machine learning problems without requiring users to guess hidden "growth constants." By combining adaptive regularization with a conditional restarting scheme based on the magnitude of the gradient, the authors extend the benefits of accelerated methods to problems satisfying the general Hölderian Error Bound (HEB) condition.
Introduction & Problem Statement
In optimization for machine learning, Proximal Gradient (PG) and Accelerated Proximal Gradient (APG/FISTA) methods are standard workhorses. While APG is theoretically faster, achieving its best performance—specifically, linear convergence—typically requires the objective function to be "strongly convex."
However, many real-world problems (such as Lasso or Support Vector Machines) are not strongly convex. Fortunately, they often satisfy a "Quadratic Growth Condition" (QGC). Researchers can force APG to run very fast on QGC problems by periodically "restarting" the algorithm. The catch is that knowing when to restart requires knowing a specific, often hidden, constant related to the function's growth. In practice, this constant is unknown, forcing practitioners to tune it manually.
Furthermore, some problems do not even satisfy QGC; instead, they follow a broader geometric rule called the Hölderian Error Bound (HEB). This paper aims to create an algorithm that is both adaptive (bypassing the need for the unknown constant) and accelerated under this more general HEB condition.
Proposed Methodology: adaAGC
The authors propose the Adaptive Accelerated Gradient Converging (adaAGC) method. Its core innovation relies on a two-pronged strategy:
- Adaptive Regularization: The algorithm solves a sequence of subproblems where a small quadratic term (regularization) is added to the objective. This term is adjusted dynamically based on the algorithm's current "guess" of the error bound parameters.
- Conditional Restarting: Instead of restarting at fixed, predetermined intervals, adaAGC monitors the magnitude of the proximal gradient. If the gradient fails to decrease sufficiently within a calculated timeframe, the algorithm deduces that its internal estimate of the growth constant is too small. It then increases the estimate and restarts the process.
This mechanism allows the algorithm to "search" for the correct parameters of the function's landscape while it optimizes, making it effectively parameter-free regarding the error bound constant $c$.
Key Theoretical & Empirical Results
Theoretical Superiority
The authors prove that adaAGC achieves a superior iteration complexity for the gradient norm compared to standard PG, without requiring the growth constant $c$ that restarted APG (rAPG) relies on.
Specifically, adaAGC achieves an iteration complexity of $\tilde{O}(1/\epsilon^{\frac{1-2\theta}{2(1-\theta)}})$ for the gradient norm. For the common case of $\theta=1/2$ (which includes Lasso and SVMs), this results in global linear convergence with a square-root dependence on the condition number. Unlike many previous results that only guaranteed fast convergence near the optimum (local convergence), the linear convergence results provided for piecewise quadratic problems here are global.
Empirical Performance
The authors evaluated their method on standard benchmarks from the LibSVM repository (splice, cpusmall, and bodyfat) across various regularization schemes ($\ell_1$, $\ell_\infty$, and $\ell_p$ norms).
In these experiments, adaAGC consistently outperformed standard Proximal Gradient and FISTA.
- On the
bodyfatdataset with $\ell_1$ constrained $\ell_p$ regression, adaAGC was significantly faster than PG, with the performance gap widening as the problem became more complex (higher $p$). - In square loss regression on
cpusmall, adaAGC reached the target precision in roughly 10% of the iterations required by standard PG.
Key Insights
- Broadening the Scope: Most prior work focused strictly on the Quadratic Growth Condition (where $\theta = 1/2$). This paper demonstrates that many ML objectives (like piecewise quadratic losses with $\ell_1$ or $\ell_\infty$ norms) satisfy the broader HEB, and provides a unified framework to handle different values of the exponent $\theta$.
- Gradient as a Compass: A key insight is using the proximal gradient's magnitude as the criterion for both termination and restarting. It serves as a reliable, computable proxy for how far the current solution is from the optimal set.
Limitations and Future Work
- Knowledge of $\theta$: While the algorithm is adaptive to the constant $c$, it still requires the user to know (or guess) the exponent $\theta$ in the HEB condition. While $\theta=1/2$ is common for many ML problems, it is not universal.
- Convexity Constraint: The current analysis is strictly for convex problems. Extending these adaptive accelerated techniques to non-convex landscapes (where Kurdyka-Łojasiewicz inequalities apply) remains an open challenge.
- Smoothness Parameter: The algorithm assumes the Lipschitz constant $L$ of the gradient is known, though the authors suggest standard backtracking techniques can be used to mitigate this requirement in practice.
Summary updated