Introduction
In standard machine learning, Stochastic Gradient Descent (SGD) is the workhorse for minimizing loss functions. However, SGD typically assumes the objective function is "smooth" in a Euclidean sense—meaning its gradient doesn't change too rapidly relative to standard distances.
Many important real-world problems violate this assumption. In tasks like tomographic reconstruction (e.g., CT scans) or Poisson inverse problems, the "curvature" of the function can become infinitely large near the boundaries of the search space. In these scenarios, standard SGD either fails entirely or requires painfully small step sizes to avoid diverging.
The "Relative Smoothness" framework addresses this by measuring smoothness against a custom reference function $h$ (using a Bregman divergence) rather than the standard Euclidean norm. While deterministic versions of these methods exist, their stochastic counterparts—and specifically how to reduce the variance of those stochastic gradients—have lacked sharp theoretical guarantees. This paper provides a rigorous convergence analysis for stochastic gradient methods using Bregman divergences and introduces a variance-reduced algorithm, Bregman-SAGA, capable of fast, linear convergence.
Methods: BSGD and Bregman-SAGA
The authors analyze two primary algorithms tailored for relatively smooth problems:
- Bregman Stochastic Gradient Descent (BSGD): A stochastic variant of Mirror Descent. Instead of taking a step that minimizes a local quadratic approximation (as in standard SGD), BSGD minimizes a linear approximation plus a Bregman divergence term $D_h(x, x_t)$.
- Bregman-SAGA: A variance-reduced algorithm designed for finite-sum problems (where the objective is an average of $n$ functions). SAGA stores past gradients to build a progressively more accurate estimate of the full gradient. The authors successfully adapt this variance reduction technique to the Bregman geometry.
Key Theoretical Innovations
To prove the convergence of these methods, the authors introduce several novel mathematical tools:
- Bregman Cocoercivity: They derive a new version of the "cocoercivity" lemma—a fundamental tool in convex optimization—specifically tailored for Bregman geometry.
- The Gain Function ($G$): Unlike Euclidean distance, Bregman divergences are not translation-invariant. To handle this, the authors introduce a "gain function" to bound how much the geometry "stretches" as the algorithm traverses the space, enabling a rigorous convergence proof.
- New Noise Assumption: Their analysis utilizes a variance condition based on the noise at the optimum, which provides much tighter bounds than previous approaches that evaluated noise along the entire optimization trajectory.
Applications and Key Results
The paper evaluates these methods across three distinct tasks, demonstrating both theoretical alignment and practical efficacy:
- Tomographic Reconstruction: Evaluated on the standard Shepp-Logan phantom (a common medical imaging benchmark), Bregman-SAGA performed on par with Multiplicative Updates (MU), the state-of-the-art specialized algorithm for tomography, while offering a much more general-purpose framework.
- Distributed Optimization: The authors performed logistic regression on the RCV1 (Reuters) dataset using a preconditioning strategy where the reference function $h$ is based on a data subset. Bregman-SAGA reached a suboptimality of $10^{-13}$ in about 80 epochs. In contrast, standard BSGD hit a "noise floor" and plateaued at $10^{-2}$ due to unmitigated gradient variance.
- Poisson Inverse Problems: On synthetic data where gradients at the optimum are zero (the "interpolation" setting), BSGD was significantly faster than its deterministic counterpart (BGD) because it updates the model much more frequently for the same computational cost.
Key Insights
- Interpolation is Special: If a model is powerful enough to fit the data perfectly (the interpolation setting), BSGD with a constant step size converges to the exact solution, not just a neighborhood. This provides theoretical backing for why these methods excel in overparameterized regimes.
- Asymptotic Speedup: While the "gain function" might be large initially (potentially slowing early progress), the geometry stabilizes as the algorithm approaches the optimum. Eventually, the convergence rate accelerates to match the "ideal" quadratic case.
- Geometry Matters More than Steps: Choosing a reference function $h$ that closely matches the objective's curvature allows for much larger, more effective steps than standard Euclidean SGD, proving that adapting to the geometry is often more impactful than tuning learning rates.
Limitations and Future Work
While powerful, the framework has some limitations. The current analysis assumes the optimal solution $x^*$ lies in the interior of the constraint set. If the optimum is on the boundary (which is common with log-barrier functions), the theoretical analysis becomes significantly more difficult. Additionally, calculating the explicit constant for the gain function $G$ can be complex, potentially leading to conservative step-size estimates in practice. Finally, achieving the best results for variance reduction requires the reference function $h$ to be quite smooth (its conjugate must have a Lipschitz Hessian), a property not shared by all Bregman functions.
Summary updated