# Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 49 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Builds on (most cited first, 29 of 29)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems](https://mlsanity.com/paper/1706.06461/) (2017)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Hyperspectral Unmixing: Ground Truth Labeling, Datasets, Benchmark Performances and Survey](https://mlsanity.com/paper/1708.05125/) (2017)
- [A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise](https://mlsanity.com/paper/1902.01637/) (2019)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization](https://mlsanity.com/paper/1808.03045/) (2018)
- [Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration](https://mlsanity.com/paper/2011.06572/) (2020)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Stabilized Barzilai-Borwein method](https://mlsanity.com/paper/1907.06409/) (2019)
- [Direct Acceleration of SAGA using Sampled Negative Momentum](https://mlsanity.com/paper/1806.11048/) (2018)
- [Forward-Backward Splitting with Bregman Distances](https://mlsanity.com/paper/1505.05198/) (2015)
- [AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization](https://mlsanity.com/paper/2401.08024/) (2024)
- [Bregman Forward-Backward Operator Splitting](https://mlsanity.com/paper/1908.03878/) (2019)
- [Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms](https://mlsanity.com/paper/1905.09050/) (2019)
- [Stochastic Non-convex Ordinal Embedding with Stabilized Barzilai-Borwein Step Size](https://mlsanity.com/paper/1711.06446/) (2017)
- [Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements](https://mlsanity.com/paper/2107.08011/) (2021)
- [A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization](https://mlsanity.com/paper/2112.11928/) (2021)
- [A universal black-box optimization method with almost dimension-free convergence rate guarantees](https://mlsanity.com/paper/2206.09352/) (2022)
- [A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems](https://mlsanity.com/paper/2401.02040/) (2024)
- [A Stochastic Variance Reduction Algorithm with Bregman Distances for Structured Composite Problems](https://mlsanity.com/paper/2103.08822/) (2021)
- [An Improved Optimal Proximal Gradient Algorithm for Non-Blind Image Deblurring](https://mlsanity.com/paper/2502.07602/) (2025)

## Abstract (arXiv)

Bregman proximal stochastic gradient (BPSG) methods bring variance-reduced composite optimization to objectives whose geometry is poorly captured by Euclidean smoothness. Their performance, however, remains sensitive to the step size: raw stochastic curvature estimates can fluctuate sharply, whereas line searches add repeated proximal evaluations. We introduce Ada-BPSG, a line-search-free BPSG method that couples the SAGA gradient table with a stabilized Barzilai--Borwein (BB) candidate. A mediant aggregates incremental secant information so that nearly singular local ratios receive little weight, and an explicit safeguard translates the resulting curvature estimate into the bounded step-size sequence required for convergence. This design yields a direct analytical chain from relative smoothness and component-wise variance control to convergence in finite-dimensional normed spaces. We prove an O(n/K) ergodic rate for convex objectives, a restarted linear rate under relative quadratic growth, and an O(1/K) bound for a Bregman proximal residual in the nonconvex setting. On logistic regression and sparse nonnegative matrix factorization, Ada-BPSG combines low objective values with substantially less sensitivity to the initial step size than standard variance-reduced baselines, while avoiding line search.