ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
Abstract
We propose ABrA-GD (Adaptive Bregman Accelerated Gradient Descent), an adaptive algorithm for relatively smooth convex optimization. The algorithm is derived from a computable primal--dual certificate that guarantees progress by comparing the objective value with a lower bound on the minimum of a regularized objective. This certificate enables adaptation to both smoothness and geometry, using only the relative strong convexity constant as a problem-dependent input. We introduce the dual Bregman Length Distortion Factor (BLDF), which measures how dual Bregman lengths change under an anchor shift or rescaling. Under bounded local dual BLDF, ABrA-GD achieves an accelerated O(1/k2) rate for convex objectives and an accelerated linear rate for relatively strongly convex objectives.
Related
- Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
- Accelerated Concatenation of Stepsize Schedules for Smooth Strongly Convex Gradient Descent
- Region-Preserving Accelerated Gradient Methods for Geodesically Convex Optimization
- TIGER: Tunable-Geometry Accelerated Gradient Sliding with Adaptive Safeguards under Similarity
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{scieur2026abragd,
title = {{ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization}},
author = {Damien Scieur},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38741},
eprint = {2609.38741},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38741},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
AU - Damien Scieur
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38741
UR - https://arxiv.org/abs/2609.38741
AB - We propose ABrA-GD (Adaptive Bregman Accelerated Gradient Descent), an adaptive algorithm for relatively smooth convex optimization. The algorithm is derived from a computable primal--dual certificate that guarantees progress by comparing the objective value with a lower bound on the minimum of a regularized objective. This certificate enables adaptation to both smoothness and geometry, using only the relative strong convexity constant as a problem-dependent input. We introduce the dual Bregman Length Distortion Factor (BLDF), which measures how dual Bregman lengths change under an anchor shift or rescaling. Under bounded local dual BLDF, ABrA-GD achieves an accelerated O(1/k^2) rate for convex objectives and an accelerated linear rate for relatively strongly convex objectives.
ER -