TL;DR
This paper introduces AdaPG$^{q,r}$, a unified, linesearch-free adaptive proximal gradient framework that eliminates the need for expensive backtracking by calculating stepsizes purely from past iterations. The authors prove convergence under local Lipschitz conditions, establish larger stepsize policies with guaranteed lower bounds, and successfully extend this adaptive mechanism to create a novel alternating minimization algorithm (AdaAMA$^{q,r}$) in the dual setting.
What Problem Does This Paper Address?
Proximal gradient (PG) methods are the workhorses for solving optimization problems that can be split into a smooth component ($f$) and a nonsmooth component ($g$). However, their performance hinges heavily on selecting an appropriate stepsize.
Traditional "look-forward" linesearch methods rely on trial-and-error backtracking to find a valid stepsize, which requires multiple expensive function evaluations per iteration. On the flip side, existing adaptive "look-backward" methods often suffer from diminishing stepsizes that slow down convergence, or they rely on restrictive global Lipschitz continuity assumptions that rarely hold in practice.
The authors tackle this dilemma by designing an adaptive framework that safely allows larger stepsizes, guarantees that stepsizes do not vanish (shrink to zero), and operates under realistic local Lipschitz continuity assumptions.
Methods
The paper introduces AdaPG$^{q,r}$, a two-parameter adaptive framework that estimates the local geometry of the objective function using only the gradients of the two previous iterates ($\ell_k$ and $L_k$).
The key innovation lies in its stepsize update rule: $$\gamma_{k+1} = \gamma_k \min \left\{ \sqrt{\frac{1}{q} + \frac{\gamma_k}{\gamma_{k-1}}}, \sqrt{\frac{1-\frac{r}{q}}{[\gamma_k^2 L_k^2 + 2\gamma_k \ell_k(r-1) - (2r-1)]_+}} \right\}$$
Here, $q$ and $r$ are hyperparameters that control the aggressiveness of the stepsize updates. The first term in the minimum allows the algorithm to rapidly recover from a small stepsize by increasing it linearly once a local geometric threshold is cleared.
The authors analyze different combinations of $q$ and $r$ to strike a balance between aggressive stepsize growth and safe theoretical lower bounds:
Extension to Alternating Minimization (AMA)
By exploring the dual optimization setting, the authors extend this adaptive framework to composite problems of the form $\min \psi_1(x) + \psi_2(Ax)$. This yields AdaAMA$^{q,r}$, which relaxes the standard requirement of global strong convexity down to mere local strong convexity:
Datasets
The authors evaluated their methods using standard datasets from the LIBSVM library for logistic regression and cubic regularization problems:
- a5a: $m = 6414, n = 123$, density = 0.11
- mushroom: $m = 8124, n = 112$, density = 0.19
- phishing: $m = 11055, n = 68$, density = 0.44
For regularized least squares (Lasso), synthetic datasets were generated following standard benchmarks in optimization literature.
Key Insights and Ideas
- True Look-Backward Adaptivity: Unlike traditional linesearch methods that guess a stepsize and backtrack if it fails, AdaPG$^{q,r}$ looks backward at past data to indirectly guarantee a sufficient descent condition for the next step.
- The Power of $q$ and $r$: The parameter $q$ dictates how aggressively the stepsize can grow after encountering a tight local bottleneck, while $r$ ensures the stepsize remains safely bounded away from zero.
- Local Realism: By proving convergence under local Lipschitz continuity and local strong convexity, the theoretical guarantees align perfectly with real-world problems where global constants are unknown or infinite.
Key Results
- Non-Vanishing Stepsizes: Theorem 1.1 mathematically proves that the stepsize $\gamma_k$ is strictly bounded below by a positive constant ($\gamma_{min}$). It will never continuously shrink to zero.
- Empirical Speedups: In numerical simulations across regularized least squares, $\ell_1$-regularized logistic regression, and cubic regularization, variants of AdaPG$^{q,r}$ consistently matched or outperformed traditional backtracking linesearch (
PG-lsb) and older adaptive frameworks (adaPG,adaPG-MM). Crucially, they achieved this using significantly fewer calls to linear operators, translating directly to reduced computational overhead.
Limitations and Future Work
While the framework provides robust theoretical and empirical advantages, the current convergence analysis is strictly limited to convex optimization problems.
The authors point out several promising avenues for future research:
- Extending the adaptive framework to nonconvex problems.
- Adapting the methods for variational inequalities and simple bilevel optimization.
- Investigating the practical efficacy of fully time-varying parameters ($q_k, r_k$) to further optimize worst-case convergence rates.
Summary updated