Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
Abstract
This paper studies time-varying composite optimization problems with convex but not necessarily strongly convex objective functions, on compact domains and with bounded temporal variability. As a baseline, we first analyze the time-varying proximal gradient (TV-PG) method. We show that its asymptotic function value gap is bounded by O(δ1/2) as δ→0, where δ measures the temporal variability of the objective function. This dependence on δ is tight in the worst case for TV-PG. Our main contribution is a time-varying accelerated proximal gradient method that improves the asymptotic upper bound on the function value gap to O(δ2/3). The method builds on a novel acceleration scheme whose momentum parameter is determined by the current iterates, with no explicit dependence on the iteration index. We establish the bounds for both the baseline and accelerated methods through a unified analysis based on potential functions. Numerical experiments on a synthetic problem and autoregression problems with real-world datasets demonstrate the tracking performance of the proposed algorithm.
Related
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
- The Convergence Rate of Accelerated Proximal Gradient Methods with General Inertia Term for Convex Composite Multiobjective Optimization
- Wasserstein accelerated proximal gradient algorithms
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
BibTeX
@misc{kamijima2026accelerated,
title = {{Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization}},
author = {Tomoya Kamijima and Naoki Marumo and Akiko Takeda},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11425},
eprint = {2610.11425},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11425},
}
RIS
TY - UNPB
TI - Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
AU - Tomoya Kamijima
AU - Naoki Marumo
AU - Akiko Takeda
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11425
UR - https://arxiv.org/abs/2610.11425
AB - This paper studies time-varying composite optimization problems with convex but not necessarily strongly convex objective functions, on compact domains and with bounded temporal variability. As a baseline, we first analyze the time-varying proximal gradient (TV-PG) method. We show that its asymptotic function value gap is bounded by O(δ^1/2) as δ→0, where δ measures the temporal variability of the objective function. This dependence on δ is tight in the worst case for TV-PG. Our main contribution is a time-varying accelerated proximal gradient method that improves the asymptotic upper bound on the function value gap to O(δ^2/3). The method builds on a novel acceleration scheme whose momentum parameter is determined by the current iterates, with no explicit dependence on the iteration index. We establish the bounds for both the baseline and accelerated methods through a unified analysis based on potential functions. Numerical experiments on a synthetic problem and autoregression problems with real-world datasets demonstrate the tracking performance of the proposed algorithm.
ER -