🔢 mathematics

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

This paper introduces Ada-BPSG, a line-search-free adaptive Bregman proximal stochastic gradient method that employs a stabilized Barzilai--Borwein step size with a mediant-based aggregation and explicit safeguard to achieve robust convergence rates for both convex and nonconvex composite optimization problems.

Original authors: Chenhan Jin, Shengze Xu, Binghui Xie, Kaiwen Zhou, Fan Jia, James Cheng, Tieyong Zeng

Published 2026-08-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Chenhan Jin, Shengze Xu, Binghui Xie, Kaiwen Zhou, Fan Jia, James Cheng, Tieyong Zeng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley. This is the daily life of a computer algorithm trying to solve complex math problems, from teaching a robot to recognize cats to figuring out how to mix chemicals perfectly. In the world of computer science, this is called "optimization." The valley represents a mathematical function, and the goal is to find the very bottom (the minimum).

To navigate this valley, algorithms usually take small steps. But the ground isn't always flat or predictable. Sometimes the ground is slippery, sometimes it's bumpy, and sometimes the map changes every time you look at it. To handle this, mathematicians use two main tricks. First, they use "variance reduction," which is like having a team of scouts who remember the terrain they've already seen so the group doesn't keep getting confused by the same bumps. Second, they use "adaptive step sizes," which means the algorithm tries to guess how big a step it can safely take based on how steep the ground is right now. If the ground is flat, it takes a big stride; if it's a cliff, it takes a tiny shuffle.

The problem is that guessing the steepness in a foggy, changing valley is incredibly hard. If the algorithm guesses wrong, it might take a step so huge it flies off a cliff, or so tiny it never gets anywhere. For a long time, the only safe way to guess was to stop, look around, and test different step sizes (a process called "line search"), which is slow and tedious. Researchers have been looking for a way to guess the step size instantly and safely without stopping to test, especially when the valley has a weird, non-standard shape that doesn't follow the usual rules of flat geometry.

This paper introduces a new method called Ada-BPSG (Adaptive Bregman Proximal Stochastic Gradient) that acts like a smart, self-correcting compass for these tricky valleys. The authors, a team of researchers from several universities, wanted to solve a specific headache: how to make these "smart step" guesses stable enough to work in complex, non-standard environments without needing to stop and test every time.

Here is how their invention works, using a simple story. Imagine the algorithm is a hiker with a backpack full of notes (the "SAGA table") about the ground it has walked on. Every time the hiker moves, it looks at its notes to guess how steep the next part of the trail is. A common way to guess this is to look at the ratio of how much the ground changed versus how far the hiker moved. But in a foggy, noisy valley, this ratio can be wild. Sometimes a single weird bump makes the hiker think the ground is a vertical wall, causing it to panic and take a step that is either impossibly huge or impossibly tiny.

The authors' solution is a "stabilized mediant." Instead of just averaging the hiker's recent guesses (which can be ruined by one bad guess), they use a special math trick called a "mediant." Think of it like a weighted vote. If one scout says the slope is 1,000 degrees (a crazy, impossible number) and another says it's 10 degrees, a simple average might still be skewed. But the mediant method listens to the scouts who have the most reliable data and ignores the ones screaming about impossible cliffs. It effectively says, "That one crazy number is probably a glitch; let's trust the steady ones."

Once the algorithm has this "calm" guess, it doesn't just run with it. It puts the guess through a "safeguard." Imagine a speed governor on a car. Even if the engine wants to go 200 mph, the governor ensures the car never exceeds a safe speed limit. Similarly, the algorithm takes its calm guess and clips it to a safe range. It also has a rule that says, "You can speed up, but you can never slow down your step size once you've decided to go faster." This prevents the algorithm from getting stuck in a loop of hesitation.

The paper proves that this method works. The researchers showed mathematically that in standard "flat" valleys, the method finds the bottom just as fast as the best existing methods, but without the need to stop and test step sizes. More importantly, they proved it works in "weird" valleys (called non-Euclidean spaces) where the usual rules of geometry don't apply. In these strange terrains, the method is guaranteed to converge to a solution, and they even showed it can speed up if the valley has a specific "quadratic" shape.

To test their idea, the team ran simulations on real-world problems. First, they tried it on standard tasks like classifying images (logistic regression). They found that their method was much less sensitive to the starting settings than other methods. While other algorithms would crash or move very slowly if the user picked a bad starting step size, Ada-BPSG just kept working smoothly, adjusting itself automatically.

Then, they moved to a much harder test: a problem involving "Poisson inverse problems" on a simplex (a shape like a triangle in high dimensions). This is a scenario where the ground is so bumpy that standard methods get stuck. The researchers set up a scenario where the "worst-case" math suggested the step size should be tiny and slow. However, their adaptive method realized the actual terrain was smoother than the worst-case scenario predicted. It confidently took larger steps, reaching the solution more than 100 times faster than the standard methods that were forced to stick to the tiny, safe steps. They even tested this on real data from a hyperspectral camera (looking at light from space), and the method performed just as well, finding the answer quickly without needing a human to tune the settings.

Finally, they tried it on a problem called "sparse nonnegative matrix factorization," which is used to break down complex data into simpler parts. Here, the algorithm again outperformed others, reaching lower error rates faster, all without needing the slow "line search" stops that other advanced methods required.

In short, the paper demonstrates that by combining a smart way to average noisy data (the mediant) with a strict safety belt (the safeguard), you can create an optimizer that is both fast and incredibly robust. It doesn't need a human to constantly tweak the settings, and it can handle the most bizarre, non-standard mathematical landscapes without losing its way. The authors proved this with rigorous math and confirmed it with experiments on everything from synthetic data to real-world space imagery.

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

1. Problem Statement

The paper addresses finite-sum composite optimization problems of the form:
$\min_{x \in E} F(x) := f(x) + h(x), \quad f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x)$
where $E$ is a finite-dimensional normed vector space, $f$ is a smooth component loss, and $h$ is a proper convex regularizer with a tractable proximal subproblem.

The authors focus on scenarios where the Euclidean geometry is a poor match for the problem structure (e.g., neural network training, matrix factorization, quantum tomography). In such cases, standard Euclidean smoothness assumptions fail, necessitating Bregman geometry, where the squared Euclidean distance is replaced by a Bregman divergence $D_\psi$ generated by a kernel $\psi$ . While Bregman Proximal Stochastic Gradient (BPSG) methods exist, their performance is highly sensitive to step-size selection. Fixed step sizes require knowledge of global smoothness constants, while line searches incur repeated proximal evaluations. Variance-reduced (VR) methods like SAGA reduce noise but typically rely on fixed step sizes or line searches in the Bregman setting.

2. Methodology: Ada-BPSG

The paper proposes Ada-BPSG, a line-search-free method that integrates the SAGA variance-reduction framework with a stabilized Barzilai–Borwein (BB) step-size rule adapted to Bregman geometry.

Core Mechanism:

SAGA Table Utilization: The algorithm maintains the standard SAGA gradient table. For each component update, it computes secant pairs $(s_{i,t}, y_{i,t})$ representing the difference in iterates and gradients.
Stabilized BB Candidate: Instead of using a simple arithmetic mean of stochastic BB ratios (which can be unstable due to near-singular denominators), the method aggregates secant information using a mediant.
- The raw candidate is computed as $\hat{\eta}^{BB}_k = \frac{1}{\alpha} \frac{\xi_k}{\delta_k + \theta \xi_k}$ , where $\xi_k$ and $\delta_k$ are accumulated sums of secant pair inner products and dual-norm squared gradients, respectively.
- The mediant formulation acts as a denominator-weighted mean, naturally suppressing contributions from nearly singular curvature estimates.
Safeguarded Update: The raw candidate is clipped to a safe interval $[\eta_{\min}, \eta_{\max}]$ $[η_{m i n}, η_{m a x}]$ and updated monotonically: $\eta_k = \max\{\eta_{k-1}, \text{clip}(\hat{\eta}^{BB}_k)\}$ $ηk=max{ηk−1,clip(η^kBB)}$ .
- This monotonicity is crucial for the convex convergence proof, allowing the Bregman distance to telescope.
- The bounds are determined by the relative smoothness constant $\bar{L}$ and the local component smoothness constant $M$ .

Implementation Efficiency:

For linear-prediction losses (e.g., logistic regression), the method reduces memory complexity from $O(nd)$ to $O(n)$ by storing only scalar predictions rather than full gradient vectors, without altering the update logic.
The step-size adaptation adds only two scalar accumulations per refreshed component and requires no line search.

3. Key Contributions

The paper makes three primary contributions:

A Stable Adaptive Step from SAGA Information:
The authors introduce a mechanism to aggregate component-wise secant pairs via a mediant, effectively weighting local BB ratios by their denominators. This stabilizes the curvature estimate against outliers. The resulting candidate is converted into a provably stable step-size sequence via clipping and monotonic updates, requiring no line search.
Convergence Analysis in General Normed Spaces:
Theoretical guarantees are established in a general finite-dimensional normed space, relying only on the dual norm and Bregman inequalities, without invoking Euclidean polarization identities. The analysis yields:
- Convex Setting: An ergodic convergence rate of $O(n/K)$ for the objective gap.
- Relative Quadratic Growth: A restarted linear convergence rate.
- Nonconvex Setting: An $O(1/K)$ bound on the expected squared Bregman proximal residual.
- Note: The analysis confirms that adapting within the safe interval does not degrade the standard $O(n/K)$ rate of fixed-step BPSG-SAGA, but provides robustness to initialization. Crucially, the convex ergodic and restarted-linear guarantees are novel to Ada-BPSG; the stochastic Bregman baselines it builds on (BPSG-SAGA, BPSGE) are analyzed only in the nonconvex regime and lack these convex convergence guarantees.
Empirical Validation:
Experiments demonstrate that Ada-BPSG combines low objective values with significantly reduced sensitivity to the initial step size compared to standard VR baselines (SAGA, SVRG, SARAH). The method avoids line searches while outperforming fixed-step baselines that are constrained by their own theoretical worst-case bounds.

4. Experimental Results

The paper evaluates Ada-BPSG on three distinct problem types:

Regularized Logistic Regression (Euclidean):
On datasets (mushrooms, ijcnn1, w8a, covtype), Ada-BPSG (specialized as SAGA-BB) achieves the smallest objective gaps with the fewest effective passes. Crucially, it maintains low gradient norms across a wide range of initial step sizes, whereas vanilla VR methods exhibit instability or poor performance at extreme values.
Simplex-Constrained Poisson Inverse Problem (Non-Euclidean):
Using the entropy kernel and $\ell_1$ norm, the authors test a problem where the global smoothness constant $M$ is inflated by log singularities, making fixed-step baselines extremely conservative.
- Fixed-step methods (held to their theoretical worst-case bounds) stagnate at high objective gaps ( $\sim 10^{-2}$ ).
- Ada-BPSG, by adapting to the local curvature (relaxing the worst-case cap heuristically), drives the gap down to $\sim 10^{-5}$ , outperforming the best fixed-step baseline by over two orders of magnitude.
- The method exhibits the predicted $O(n/K)$ convex rate in this genuinely non-Euclidean setting.
Real-Data Hyperspectral Unmixing:
Applied to the Samson hyperspectral scene, the method replicates the synthetic results. It achieves low objective gaps without per-instance tuning or line search, confirming the mechanism's robustness on real measured data.
Sparse Nonnegative Matrix Factorization (Nonconvex):
On the ORL face dataset, Ada-BPSG achieves the lowest objective trajectories among compared Bregman methods, including those using extrapolation and line search (BPSGE), demonstrating effectiveness even when the regularizer is nonconvex.

5. Significance and Claims

The paper claims that Ada-BPSG successfully bridges the gap between stochastic curvature adaptation and convergence guarantees in non-Euclidean composite optimization.

Theoretical Significance: It provides the first convergence analysis for a line-search-free, variance-reduced Bregman method in general normed spaces that achieves $O(n/K)$ rates for convex objectives and linear rates under relative quadratic growth. Previous stochastic Bregman methods were largely limited to nonconvex analyses or required line searches; notably, the convex and restarted-linear guarantees are new contributions of Ada-BPSG not present in the SAGA/SARAH-based stochastic Bregman baselines it extends.
Practical Significance: The method eliminates the need for expensive line searches and the fragility associated with tuning fixed step sizes. By leveraging the "mediant" aggregation, it stabilizes the BB step size against the high variance typical of stochastic curvature estimates.
Modesty: The authors explicitly note that their theoretical contribution is not an improvement in the asymptotic rate order (which remains $O(n/K)$ ) but rather the extension of these rates to general normed spaces under weaker geometric assumptions. The practical gain is described as "robustness to the initial step size" and the ability to adapt beyond conservative worst-case bounds in practice, rather than a faster worst-case theoretical rate.

The paper concludes that while the current theory relies on a deterministic bounded region and a strongly convex kernel, the stabilized candidate mechanism offers a promising direction for extending adaptive variance-reduced methods to memory-light estimators (like SARAH/SPIDER) and weaker geometric conditions.