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

Stochastic optimization methods often struggle when the objective's geometry is not well-captured by standard Euclidean distance. While Bregman proximal stochastic gradient (BPSG) methods address this by using problem-adapted kernels, they are typically sensitive to the choice of step size. Existing solutions either use diminishing step sizes, which are slow, or line searches, which are computationally expensive. The authors propose Ada-BPSG, which incorporates a stabilized Barzilai-Borwein (BB) step-size rule into the SAGA variance-reduction framework to adapt to local curvature without requiring line searches.

Ada-BPSG uses a mediant-based aggregation of secant information to estimate local curvature. By using a denominator-weighted mean, the algorithm suppresses spikes in the curvature estimate that often occur in stochastic settings. This raw estimate is then passed through an explicit safeguard—a clipping mechanism—that ensures the step size remains within a stable, pre-defined range. This design allows the algorithm to adapt its step size dynamically while maintaining the theoretical guarantees required for convergence in general finite-dimensional normed spaces.

The authors provide a rigorous convergence analysis, proving an O(n/K) ergodic rate for convex objectives, a restarted linear rate under relative quadratic growth, and an O(1/K) bound for nonconvex settings. Crucially, these results hold in general normed spaces without relying on Euclidean polarization identities. Experimental results on logistic regression and sparse nonnegative matrix factorization demonstrate that Ada-BPSG reaches low objective values faster than standard baselines and is significantly more robust to the initial step-size choice.