Research map / Optimization / Nonconvex and smooth optimization
Adaptive Proximal Gradient Methods Are Universal Without Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that a linesearch-free adaptive proximal gradient method (AdaPG) converges for convex problems with locally Hölder continuous gradients of unknown order, with an O(1/K^nu) rate and no approximation oracle, and validates it numerically against NUPG, F-NUPG and AC-FGM.
Problem
Composite convex minimization where the smooth part has only locally Hölder continuous gradient of unknown order, where standard Lipschitz-based adaptive methods and approximation-based universal methods are either unsupported or require linesearch/ε-oracles.
Approach
Analyzes the adaptive stepsize rule of AdaPG^{q,r} under local Hölder continuity with q in [1,2], using scaled stepsizes lambda_k that are shown to be lower bounded on steps where the second stepsize term is active, yielding exact (non-approximate) linesearch-free convergence without knowing the Hölder order.
Key results
- AdaPG outperforms NUPG consistently on p-norm Lasso in calls to A and A^T
- AdaPG consistently outperforms NUPG on Hölder-smooth SVMs, and in many cases beats F-NUPG and AC-FGM
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use linesearch-free AdaPG without prior knowledge of the local Hölder order or modulus | Convex composite problems with locally Hölder-continuous gradients · Locally Hölder-smooth convex composite problems | best-iterate objective gap: O(1/(K+1)^ν) | Helped |
| Use AdaPG instead of NUPG | p-norm Lasso · p-norm Lasso | calls to A and Aᵀ | Helped |
| Use AdaPG instead of F-NUPG or AC-FGM | p-norm Lasso · p-norm Lasso | calls to A and Aᵀ | Helped |
| Use AdaPG instead of NUPG | Hölder-smooth SVM with ℓ1 regularization · LibSVM binary classification datasets | calls to A and Aᵀ | Helped |
| Use AdaPG instead of NUPG | Hölder-smooth convex optimization problems · Diverse locally and globally Hölder-smooth problems | performance | Helped |
| Use AdaPG instead of F-NUPG or AC-FGM | Hölder-smooth convex optimization problems · Diverse experimental problems | performance | Mixed |
Limitations
- Worst-case rate O(1/K^nu) is worse than NUPG's rate
- Analysis restricted to convex problems
- Convergence for q=0 (subgradient case) left open
Experimental setup
Datasets: LibSVM binary classification datasets
Benchmarks: LibSVM
Metrics: objective gap versus calls to A and A^T
Baselines: NUPG F-NUPG AC-FGM
Builds on: AdaPG Nesterov universal primal gradient method AC-FGM
Closest papers by meaning
- Adaptive Proximal Gradient Method for Convex Optimization (NeurIPS 2024 · similarity 0.90)
- Stochastic Weakly Convex Optimization beyond Lipschitz Continuity (ICML 2024 · similarity 0.88)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.88)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.88)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.