Adaptive Accelerated Gradient Converging Method under H\"{o}lderian Error Bound Condition

Mingrui Liu, Tianbao YangNeurIPS 2017 · OpenReview

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:

  1. 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.
  2. 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.

Algorithm Comparison Table

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 bodyfat dataset 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

Abstract

Recent studies have shown that proximal gradient (PG) method and accelerated gradient method (APG) with restarting can enjoy a linear convergence under a weaker condition than strong convexity, namely a quadratic growth condition (QGC). However, the faster convergence of restarting APG method relies on the potentially unknown constant in QGC to appropriately restart APG, which restricts its applicability. We address this issue by developing a novel adaptive gradient converging methods, i.e., leveraging the magnitude of proximal gradient as a criterion for restart and termination. Our analysis extends to a much more general condition beyond the QGC, namely the H\"{o}lderian error bound (HEB) condition. {\it The key technique} for our development is a novel synthesis of {\it adaptive regularization and a conditional restarting scheme}, which extends previous work focusing on strongly convex problems to a much broader family of problems. Furthermore, we demonstrate that our results have important implication and applications in machine learning: (i) if the objective function is coercive and semi-algebraic, PG's convergence speed is essentially $o(\frac{1}{t})$, where $t$ is the total number of iterations; (ii) if the objective function consists of an $\ell_1$, $\ell_\infty$, $\ell_{1,\infty}$, or huber norm regularization and a convex smooth piecewise quadratic loss (e.g., square loss, squared hinge loss and huber loss), the proposed algorithm is parameter-free and enjoys a {\it faster linear convergence} than PG without any other assumptions (e.g., restricted eigen-value condition). It is notable that our linear convergence results for the aforementioned problems are global instead of local. To the best of our knowledge, these improved results are first shown in this work.
BibTeX
@inproceedings{liu2017adaptive,
  author = {Mingrui Liu and Tianbao Yang},
  title = {{Adaptive Accelerated Gradient Converging Method under H\textbackslash\{\}"\{o\}lderian Error Bound Condition}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=rJZrbYWO-S},
}
Figure