Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives
Abstract
We study Bregman proximal gradient (BPG) algorithms under relative smoothness for convex, relatively strongly convex, and nonconvex objectives. Existing accelerated BPG algorithms for convex objectives typically require additional assumptions on Bregman divergences, most notably triangle-scaling conditions, which can lead to slower convergence rates. We propose a family of geometry-accelerated BPG algorithms that exploit Bregman geometry in both proximal-gradient and mirror-space updates, without imposing additional geometric conditions such as triangle-scaling conditions. Our methods adapt the stepsizes and mirror-space updates through local backtracking and computable acceptance criteria, without a global relative-smoothness constant as input. We derive convergence bounds in terms of the parameters accepted during the iterations. These bounds yield an Ø(k−2) rate for convex objectives and a linear rate for relatively strongly convex objectives when the geometry-acceleration parameters remain uniformly bounded. For nonconvex objectives, we establish an Ø(k−1) rate for a stationarity measure without requiring a lower Bregman bound or a full-domain Bregman divergence. Numerical experiments on inverse problems, entropy-regularized least squares, D-optimal design, and nonnegative matrix factorization demonstrate faster practical convergence than established Bregman baselines.
Related
- On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression
- Right Bregman proximal gradient with application to Poisson inverse problems
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Composite and Stochastic Smoothed Decentralized Bregman Proximal-Gradient Methods
- Wasserstein accelerated proximal gradient algorithms
BibTeX
@misc{yamashita2026accelerated,
title = {{Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives}},
author = {Yuya Yamashita and Shota Takahashi and Akiko Takeda},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34773},
eprint = {2609.34773},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34773},
}
RIS
TY - UNPB
TI - Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives
AU - Yuya Yamashita
AU - Shota Takahashi
AU - Akiko Takeda
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34773
UR - https://arxiv.org/abs/2609.34773
AB - We study Bregman proximal gradient (BPG) algorithms under relative smoothness for convex, relatively strongly convex, and nonconvex objectives. Existing accelerated BPG algorithms for convex objectives typically require additional assumptions on Bregman divergences, most notably triangle-scaling conditions, which can lead to slower convergence rates. We propose a family of geometry-accelerated BPG algorithms that exploit Bregman geometry in both proximal-gradient and mirror-space updates, without imposing additional geometric conditions such as triangle-scaling conditions. Our methods adapt the stepsizes and mirror-space updates through local backtracking and computable acceptance criteria, without a global relative-smoothness constant as input. We derive convergence bounds in terms of the parameters accepted during the iterations. These bounds yield an Ø(k^−2) rate for convex objectives and a linear rate for relatively strongly convex objectives when the geometry-acceleration parameters remain uniformly bounded. For nonconvex objectives, we establish an Ø(k^−1) rate for a stationarity measure without requiring a lower Bregman bound or a full-domain Bregman divergence. Numerical experiments on inverse problems, entropy-regularized least squares, D-optimal design, and nonnegative matrix factorization demonstrate faster practical convergence than established Bregman baselines.
ER -