# Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization

arXiv: https://arxiv.org/abs/1808.03045 · HTML: https://mlsanity.com/paper/1808.03045/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2018.

## Built on by (most cited first, 20 of 20)

- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning](https://mlsanity.com/paper/2306.14522/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient](https://mlsanity.com/paper/2206.01209/) (2022)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements](https://mlsanity.com/paper/2107.08011/) (2021)
- [Bregman Douglas-Rachford Splitting Method](https://mlsanity.com/paper/2509.08739/) (2025)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [Multilevel Geometric Optimization for Regularised Constrained Linear Inverse Problems](https://mlsanity.com/paper/2207.04934/) (2022)
- [An inexact Bregman proximal point method and its acceleration version for unbalanced optimal transport](https://mlsanity.com/paper/2402.16978/) (2024)
- [Efficient algorithms for regularized Poisson Non-negative Matrix Factorization](https://mlsanity.com/paper/2404.16505/) (2024)
- [Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimization](https://mlsanity.com/paper/2411.15795/) (2024)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)
- [Entropy-Smooth Convex Optimization Cannot Be Accelerated](https://mlsanity.com/paper/2607.27476/) (2026)
- [Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size](https://mlsanity.com/paper/2608.12009/) (2026)

## Abstract (arXiv)

We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. We investigate a triangle scaling property of the Bregman distance generated by the reference convex function and present accelerated Bregman proximal gradient (ABPG) methods that attain an O(k-γ) convergence rate, where γ∈(0,2] is the triangle scaling exponent (TSE) of the Bregman distance. For the Euclidean distance, we have γ=2 and recover the convergence rate of Nesterov's accelerated gradient methods. For non-Euclidean Bregman distances, the TSE can be much smaller (say γ≤ 1), but we show that a relaxed definition of intrinsic TSE is always equal to 2. We exploit the intrinsic TSE to develop adaptive ABPG methods that converge much faster in practice. Although theoretical guarantees on a fast convergence rate seem to be out of reach in general, our methods obtain empirical O(k-2) rates in numerical experiments on several applications and provide posterior numerical certificates for the fast rates.