# Stochastic Bregman Proximal Gradient Method Revisited: Kernel Conditioning and Painless Variance Reduction

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2024.

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

- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms](https://mlsanity.com/paper/2404.08073/) (2024)
- [On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem](https://mlsanity.com/paper/2507.15264/) (2025)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [Non-KKT Accumulation in Entropic Mirror Descent](https://mlsanity.com/paper/2608.01658/) (2026)
- [A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis](https://mlsanity.com/paper/2603.12838/) (2026)

## Abstract (arXiv)

We investigate stochastic Bregman proximal gradient (SBPG) methods for minimizing a finite-sum nonconvex function Psi(x):=frac1nsumi=1nfi(x)+φ(x), where φ is convex and nonsmooth, while fi, instead of gradient global Lipschitz continuity, satisfies a smooth-adaptability condition w.r.t. some kernel h. Standard acceleration techniques for stochastic algorithms (momentum, shuffling, variance reduction) depend on bounding stochastic errors by gradient differences that are further controlled via Lipschitz property. Lacking this, existing SBPG results are limited to vanilla stochastic approximation that cannot yield the optimal O(√n) complexity dependence on n. Moreover, existing works report complexities under various nonstandard stationarity measures that largely deviate from the standard minimal limiting Fr'echet subdifferential dist(0,partialPsi(·)). Our analysis reveals that these popular stationarity measures are often much smaller than dist(0,partialPsi(·)), leading to overstated solution quality and non-stationary output. To resolve these issues, we design a new gradient mapping Dφ,hλ (·) by BPG residuals in dual space and a new kernel-conditioning (KC) regularity, under which the mismatch between |Dφ,hλ (·)| and dist(0,partialPsi(·)) is provably O(1) and instance-free. Moreover, KC-regularity guarantees Lipschitz-like bounds for gradient differences, providing general analysis tools for momentum, shuffling, and variance reduction under smooth-adaptability. We illustrate this point on variance reduced SBPG methods and establish an O(√n) complexity for |Dφ,hλ (·)|, providing instance-free (worst-case) complexity under dist(0,partialPsi(·)).