We investigate stochastic Bregman proximal gradient (SBPG) methods for minimizing a finite-sum nonconvex function \(\Psi (x):=\frac{1}{n}\sum _{i=1}^nf_i(x)+\phi (x)\) , where \(\phi \) is convex and nonsmooth, while \(f_i\) , 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 mostly limited to vanilla stochastic approximation schemes that cannot obtain the optimal \(O(\sqrt{n})\) complexity dependence on n. Moreover, existing works report complexities under various nonstandard stationarity measures that largely deviate from the standard minimal limiting Fréchet subdifferential \(\textrm{dist}(0,\partial \Psi (\cdot ))\) . Our analysis reveals that these popular nonstandard stationarity measures are often much smaller than \(\textrm{dist}(0,\partial \Psi (\cdot ))\) by a large or even unbounded instance-dependent mismatch factor, leading to overstated solution quality and producing non-stationary output. This also implies that current complexities based on nonstandard measures are actually asymptotic and instance-dependent if translated to \(\textrm{dist}(0,\partial \Psi (\cdot ))\) . To resolve these issues, we design a new gradient mapping \(\mathcal {D}_{\phi ,h}^\lambda (\cdot )\) by BPG residuals in dual space and a new kernel-conditioning (KC) regularity, under which the mismatch between \(\Vert \mathcal {D}_{\phi ,h}^\lambda (\cdot )\Vert \) and \(\textrm{dist}(0,\partial \Psi (\cdot ))\) 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(\sqrt{n})\) complexity dependence for \(\Vert \mathcal {D}_{\phi ,h}^\lambda (\cdot )\Vert \) , providing instance-free (worst-case) complexity under \(\textrm{dist}(0,\partial \Psi (\cdot ))\) .
