TL;DR
This paper introduces a unified framework for the Bregman Stochastic Proximal Point Algorithm (BSPPA) enhanced with variance reduction techniques. By integrating non-Euclidean geometry with SAGA- and SVRG-style updates, the authors achieve faster, more stable convergence that avoids the "vanishing stepsize" bottleneck typical of standard stochastic proximal methods.
What Problem Does This Paper Address?
In the world of large-scale optimization, Stochastic Gradient Descent (SGD) is king, but it has a weakness: it is highly sensitive to the choice of stepsize. The Stochastic Proximal Point Algorithm (SPPA) emerged as a more robust alternative, but it comes with its own trade-off. To converge to an exact solution, standard SPPA requires "vanishing stepsizes"—meaning the steps must get progressively smaller—which significantly slows down the convergence rate.
Furthermore, most algorithms assume a flat, Euclidean geometry. However, many real-world problems (like those involving probability distributions or constrained sets) are better suited to non-Euclidean geometries. While Bregman distances allow algorithms to adapt to these geometries, combining them with stochastic updates and variance reduction (to allow for faster, constant stepsizes) has remained a theoretical and practical challenge.
Methods
The authors propose a generic framework for BSPPA with Variance Reduction. The core innovation is an implicit update rule that includes a "generic variance reduction term" ($e_k$).
Key components include:
- Generic BSPPA: An algorithm that solves a proximal subproblem at each step, modified by a linear perturbation to cancel out stochastic noise.
- BSAPA (Bregman SAGA): A single-loop version of the algorithm that stores a table of past gradients to reduce variance, adapted for Bregman distances.
- BLSVRP (Bregman Loopless SVRG): A version of the Stochastic Variance Reduced Gradient method that replaces the traditional fixed inner loop with a probabilistic (Bernoulli) update, making it easier to implement and analyze.
- Unified Analysis: The authors provide a mathematical framework that is flexible enough to recover convergence results for both the proximal point algorithms and standard Bregman SGD.
Datasets
The paper evaluates the algorithms using simulated data for specific inverse problems rather than standard machine learning benchmarks:
- Poisson Linear Inverse Problem: A synthetic setup with $n=500$ data points and $d=100$ dimensions, where the goal is to recover a signal from Poisson-distributed measurements.
- Tomographic Reconstruction: A more complex imaging task using the Shepp-Logan phantom (a standard test image in medical imaging) and a discrete Radon transform with $n=90$ projection angles.
Key Insights and Ideas
- The "Gain Function" Solution: Bregman distances are notoriously difficult to work with because they are not symmetric (the distance from $x$ to $y$ isn't the same as $y$ to $x$). The authors utilize a "gain function" ($G$) to manage this asymmetry in the convergence proofs.
- Stability over Speed: While variance reduction is usually advertised for speed, this paper highlights its role in stability. In the experiments, the variance-reduced versions remained stable at stepsize thresholds where vanilla methods either exploded or plateaued.
- Implicit vs. Explicit: The paper bridges the gap between "implicit" methods (proximal updates) and "explicit" methods (gradient updates), showing that the same variance reduction logic applies to both under a unified Bregman umbrella.
Key Results
- Theoretical Convergence: The authors prove sublinear convergence ($O(1/k)$) for general convex functions and linear convergence ($O(q^k)$) for relatively strongly convex functions using constant stepsizes.
- Oscillation Suppression: In numerical experiments, vanilla BSPPA with a constant stepsize oscillates around the minimum due to gradient noise. The proposed BSAPA eliminates these oscillations, converging directly to the minimum.
- Efficiency: In the tomographic reconstruction task, the variance-reduced algorithm (BSAPA) significantly outperformed the version with vanishing stepsizes, which "plateaued" early and failed to reach high precision.
Limitations and Future Work
- Inexact Proximal Mapping: The theory assumes the proximal subproblem is solved exactly. However, in practice (and in their own experiments), this subproblem is often solved approximately via an inner gradient descent loop. The authors note that a formal analysis of this "inexactness" is a necessary next step.
- Nonsmooth Functions: While the proximal point algorithm is naturally suited for nonsmooth optimization, the specific variance reduction analysis in this paper relies on "relative smoothness" assumptions. Extending the full variance reduction benefits to purely nonsmooth cases remains an open challenge.
- Stepsize Sensitivity: Although more robust than SGD, the algorithm still has a "breakdown point." If the stepsize exceeds a theoretical threshold (determined by the geometry and smoothness), the algorithm can diverge rapidly.
Summary updated