A Few Accelerated Algorithms for Convex Optimization under $(H_0,H_1)$-Smoothness

Breaking the Smoothness Barrier

In large-scale machine learning, we spend most of our time optimizing objectives that are "locally bumpy." While we often assume a global smoothness constant to make the math tractable, real-world landscapes change their curvature as we approach a solution. The "bumpiness" or curvature typically decreases as the optimality gap (the difference between the current loss and the minimum possible loss) shrinks. This means the problem actually becomes easier to navigate the closer you get to the answer.

Current state-of-the-art algorithms struggle to capitalize on this. Most accelerated methods rely on a single, pessimistic global Lipschitz constant (a single value describing the maximum possible curvature). This constant stays fixed even when the local landscape has flattened out. This leaves a critical question on the table: Can we design an optimizer that explicitly recognizes and exploits this decreasing curvature to achieve faster convergence?

The pursuit of gap-dependent acceleration

The authors of this paper investigate whether we can achieve acceleration by moving away from global smoothness to a model called $(H_0, H_1)$-smoothness. In this framework, the Hessian (the matrix of second-order derivatives that describes local curvature) is bounded by a baseline constant $H_0$ plus a term $H_1$ that scales with the current optimality gap.

The core tension is that traditional Nesterov-style acceleration is optimized for a static curvature. If you use a fixed, large curvature constant to ensure stability, you lose the speedup that comes from the landscape flattening. Conversely, if you adapt your step size too aggressively without a formal framework, you risk divergence. The paper seeks to bridge this gap by providing the first accelerated guarantees for this broader class of functions. These guarantees cover both full-gradient and coordinate-based optimization.

Cracks in the global smoothness model

Until now, the field has largely relied on $(L_0, L_1)$-smoothness, where curvature is tied to the gradient norm. While useful, this is a subset of the $(H_0, H_1)$ model. The authors note that there are functions that satisfy $(H_0, H_1)$-smoothness but fail to meet $(L_0, L_1)$ requirements. These functions have curvature spikes that are not captured by the gradient alone.

Standard accelerated methods essentially "freeze" the curvature at the start of training. As seen in the comparative analysis of existing literature, this leads to a heavy penalty. If you treat a gap-dependent problem as a standard smooth one, you incur a $\sqrt{F_0/\epsilon}$ penalty, where $F_0$ is the initial gap. This means as you demand higher precision ($\epsilon$), the computational cost explodes linearly with the initial error. Previous attempts to fix this, like the "Frozen-FGM" approach, fail to decouple the baseline curvature from the gap-dependent component. This leads to inefficient trajectories in the late stages of optimization.

Exploiting the shrinking gap

The authors' investigation centers on a "Restart Meta-Algorithm." Instead of one long, continuous optimization run, they break the process into discrete phases. Each phase aims to halve the current optimality gap. By resetting the algorithm at the start of each phase, they can use a curvature estimate tuned to the current gap level.

To make this work in practice, they combine Nesterov-type acceleration with "small-dimensional relaxation." This technique solves a simplified one-dimensional problem to find an optimal coupling point. They tested this on a synthetic "chain-cosh" objective designed to mimic high-curvature peaks. The results in are telling.

For a desired gap of $10^{-8}$, the proposed restarted method requires roughly 105 iterations. In contrast, the non-accelerated "GD-Warmup" requires over 2,000. Furthermore, the authors demonstrate that this method is remarkably robust to the $H_1$ parameter. As shown in [Figure 1b], the iteration count remains relatively stable even as the gap-dependent curvature increases significantly.

Separating baseline from gap-dependent costs

The primary finding is that the proposed algorithms successfully separate the influence of $H_0$ and $H_1$. The reported iteration complexity for the full-gradient method is $\tilde{O}(\sqrt{H_0 \tilde{R}^2/\epsilon} + \sqrt{H_1 \tilde{R}^2} \log(F_0/\epsilon))$. This is a significant theoretical and practical win. The $H_1$ term—the part that causes trouble in high-curvature regimes—now only contributes logarithmically to the accuracy requirement.

The authors also extend this to coordinate descent. This is vital for high-dimensional problems where computing a full gradient is too expensive. They show that by using non-uniform sampling (picking coordinates based on their individual smoothness constants), you can drastically reduce the number of required oracle calls. In their experiments on anisotropic objectives, the non-uniform method achieved a 5.1x reduction in coordinate-gradient calls compared to uniform sampling, as illustrated in .

They also addressed the "messy" reality of implementation by testing "inexact segment relaxation." reveals a clear U-shaped tradeoff.

If your line-search tolerance is too loose, convergence stalls. If it is too tight, you waste cycles on unnecessary precision. The sweet spot appears to be around a residual tolerance of $10^{-6}$.

Implications for the production path

If these results hold in more complex, non-convex settings, they could fundamentally change how adaptive optimizers are tuned. The ability to mathematically decouple baseline curvature from the optimization gap suggests that builders can create more aggressive acceleration schedules without sacrificing stability.

Specifically, this work implies two things for practitioners. First, for problems where the landscape flattens (typical in overparameterized models), implementing a restart-based scheme with gap-adaptive step sizes is likely to yield significant speedups over vanilla momentum or Adam. Second, in high-dimensional sparse settings, investing in non-uniform coordinate sampling is a direct way to slash the total number of gradient computations.

The research suggests that if the "effective curvature" truly drops as the loss stabilizes, a phase-restart strategy might offer a more principled alternative to the heuristic learning-rate decay and warmup schedules currently used in the industry.

Figures from the paper