Universal Adaptive Proximal Gradient Methods via Gradient Mapping Accumulation
Abstract
We propose an adaptive proximal gradient method for minimizing the sum of two functions, where one is a simple convex function, and the other belongs to one of the three classes: nonconvex smooth, convex nonsmooth, or convex smooth. The key feature of the method is an adaptive step size that accumulates historical gradient mapping norms in the denominator. Without any modification or knowledge of problem parameters, the method converges across all three problem classes under mild bounded-iterates and bounded-variance assumptions, with rates matching those of the proximal gradient method up to logarithmic factors, in both deterministic and stochastic settings. For the convex setting, we further propose an accelerated variant. It retains a similar near-optimal convergence rate for the nonsmooth case and achieves an improved rate of order Õ(1/t2 + σ/√t) for the smooth case, which is optimal up to logarithmic factors. Notably, we develop new techniques for controlling the effect of stochastic noise, which are applicable across all three problem classes in the stochastic setting and enable a simplified analysis.
Related
- EQUIVARIANCE VERSUS FIRM NON-EXPANSIVENESS IN INCREMENTAL PROXIMAL GRADIENT METHODS FOR PLUG-AND-PLAY DENOISING
- On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression
- Composite and Stochastic Smoothed Decentralized Bregman Proximal-Gradient Methods
- Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives
- Tight Stationarity Transfer and Repeatability for Inexact Proximal-Gradient Methods
BibTeX
@misc{wang2026universal,
title = {{Universal Adaptive Proximal Gradient Methods via Gradient Mapping Accumulation}},
author = {Zimeng Wang and Alp Yurtsever},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.05944},
eprint = {2605.05944},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.05944},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Universal Adaptive Proximal Gradient Methods via Gradient Mapping Accumulation
AU - Zimeng Wang
AU - Alp Yurtsever
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2605.05944
UR - https://arxiv.org/abs/2605.05944
AB - We propose an adaptive proximal gradient method for minimizing the sum of two functions, where one is a simple convex function, and the other belongs to one of the three classes: nonconvex smooth, convex nonsmooth, or convex smooth. The key feature of the method is an adaptive step size that accumulates historical gradient mapping norms in the denominator. Without any modification or knowledge of problem parameters, the method converges across all three problem classes under mild bounded-iterates and bounded-variance assumptions, with rates matching those of the proximal gradient method up to logarithmic factors, in both deterministic and stochastic settings. For the convex setting, we further propose an accelerated variant. It retains a similar near-optimal convergence rate for the nonsmooth case and achieves an improved rate of order Õ(1/t^2 + σ/√t) for the smooth case, which is optimal up to logarithmic factors. Notably, we develop new techniques for controlling the effect of stochastic noise, which are applicable across all three problem classes in the stochastic setting and enable a simplified analysis.
ER -