Abstract
We propose and analyze the convergence of a novel stochastic forward-backward splitting algorithm for solving monotone inclusions defined by the sum of a maximal monotone operator and a single-valued maximal monotone cocoercive operator. This framework encompasses several critical applications, including variational inequalities and convex minimization problems, where stochastic approaches are essential to account for data perturbations. The proposed algorithm is a stochastic extension of the classical deterministic forward-backward method, utilizing the composition of the resolvent of a maximal monotone operator with a forward step based on a stochastic estimate of the single-valued operator. Our study provides a non-asymptotic error analysis in expectation for the strongly monotone case, alongside almost sure convergence under weaker assumptions. Notably, the approach avoids iterate averaging—a feature vital for maintaining sparsity—and achieves convergence rates for minimization problems that match those of accelerated stochastic methods. Stochastic quasi-Fejér sequences serve as the primary technical tool for proving almost sure convergence.
Introduction
In fields ranging from machine learning to signal processing and control theory, many problems can be framed as monotone inclusions. The goal is to find a point $w$ in a Hilbert space such that:
$$0 \in Aw + Bw$$
In this formulation, $A$ is typically a multi-valued maximal monotone operator (such as the subdifferential of a non-smooth convex function), and $B$ is a single-valued cocoercive operator (such as the gradient of a smooth convex function). While deterministic splitting methods for these problems are well-established, they rely on the assumption of perfect access to the operators. In practical scenarios, we often only have access to "noisy" or stochastic estimates of $B$, either due to inherent randomness in data or the computational impossibility of calculating a full gradient across massive datasets.
This paper addresses the challenge of designing an algorithm that remains robust to this noise while preserving the convergence guarantees and structural properties—specifically sparsity—of deterministic methods.
The Stochastic Forward-Backward Algorithm
The authors introduce Algorithm 3.2, which extends the classical forward-backward splitting into the stochastic domain. The iteration process follows a three-step sequence:
- Forward Step: A step is taken in the direction of a stochastic estimate of the operator $B$ (denoted as $\mathfrak{B}_n$).
- Backward Step: The resolvent operator of $A$ (denoted as $J_{\gamma A}$) is applied. In the context of optimization, this is equivalent to a proximal step.
- Relaxation: The iterate is updated using a weighted average (relaxation) of the previous point and the new proposal, governed by parameters $\lambda_n$.
Theoretical Innovations
To analyze this algorithm, the authors employ the framework of Stochastic Quasi-Fejér Sequences. This mathematical tool allows for the proof of convergence even when the sequence of iterates is perturbed by random noise. Unlike traditional asymptotic analyses that only guarantee convergence "in the limit," this paper provides a non-asymptotic analysis, offering explicit $O(1/n)$ convergence rates for the error in expectation.
Key Insights and Advantages
Preserving Sparsity Without Averaging
A significant contribution of this work is the elimination of the need for iterate averaging. In many stochastic gradient methods, convergence is only guaranteed for the average of all previous iterates ($\frac{1}{n} \sum_{i=1}^n w_i$). However, if the operator $A$ is designed to induce sparsity (e.g., using an $L_1$ penalty), the individual iterates $w_n$ may be sparse, but their average typically is not. By proving that the iterates themselves converge, this algorithm preserves the sparsity-inducing properties of the problem.
Flexible Noise Assumptions
The analysis does not require the noise to be bounded by a fixed constant. Instead, it allows the variance of the stochastic estimate to grow relative to the true value of the operator. This "relative error" criterion makes the theory applicable to a broader range of real-world noise models where errors may scale with the magnitude of the data.
Convergence Results
- Almost Sure Convergence: Under uniform monotonicity, the sequence $w_n$ converges to the true solution with probability 1.
- Optimal Rates: For strongly monotone inclusions, the expected squared error $E[\|w_n - \bar{w}\|^2]$ converges at a rate of $O(1/n)$, matching the theoretical lower bounds for stochastic first-order methods.
- Robustness: The paper defines specific conditions for step-sizes ($\gamma_n$) and relaxation parameters ($\lambda_n$) that ensure stability even if the noise does not vanish over time.
Limitations and Future Directions
While the proposed method is robust, it requires the operator $B$ to be cocoercive, a condition that is standard for gradients of smooth convex functions but may exclude certain classes of monotone operators. Additionally, achieving the optimal $O(1/n)$ rate requires knowledge of the monotonicity and cocoercivity constants to tune the step-size, which may not be available in all applications. Finally, the current framework assumes the backward step (the resolvent of $A$) is computed exactly; extending this to cases where $A$ is also observed stochastically remains an open area for research.
Summary updated