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

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(·)).