TL;DR
This paper introduces Stochastic Projective Splitting (SPS), the first projective splitting algorithm capable of using stochastic gradient oracles to solve monotone inclusion and min-max problems. SPS can handle multiple constraints and nonsmooth regularizers simultaneously without requiring artificial product-space reformulations, achieving almost-sure iterate convergence and an $\mathcal{O}(K^{-1/4})$ rate on the expected operator residual.
What Problem Does This Paper Address?
Modern machine learning increasingly relies on min-max optimization and game-theoretic formulations, such as distributionally robust supervised learning (DRSL) and generative adversarial networks (GANs). Standard methods like Gradient Descent-Ascent (GDA) frequently fail to converge on these problems due to rotational dynamics—even on simple bilinear games.
While monotone inclusion algorithms provide a mathematically sound foundation for solving convex-concave games, handling multiple regularizers (e.g., $\ell_1$ penalties) and constraints (e.g., norm balls) at scale remains a hurdle:
- Deterministic Bottlenecks: Existing projective splitting (PS) methods natively handle multiple regularizers via individual proximal and projection operators, but strictly require deterministic gradients, making them impractical for large datasets.
- Product-Space Reformulation (PSR) Pitfalls: Competing stochastic splitting methods require lifting problems into higher-dimensional product spaces to handle multiple operators, which unnaturally couples skew-symmetric matrices with Lipschitz operators and harms stepsize tuning.
Methods
The authors consider monotone inclusions of the form: $$0 \in \sum_{i=1}^n A_i(z) + B(z)$$ where each $A_i$ is a maximal monotone (often set-valued) operator representing constraints or nonsmooth penalties, and $B$ is a monotone, $L$-Lipschitz operator accessible via a stochastic gradient oracle.
SPS extends the projective splitting framework through several key innovations:
- Relaxed Hyperplane Projection: Classical PS constructs a separating hyperplane between the current primal-dual iterate and the Kuhn-Tucker solution set $\mathcal{S}$, projecting directly onto it. Because stochastic noise perturbs the hyperplane, SPS replaces exact projection with a relaxed update along the hyperplane generator gradient using decaying or carefully chosen constant stepsizes ($\alpha_k, \rho_k$).
- Noisy Two-Forward-Step Oracle: For the smooth operator $B$, SPS queries an unbiased, variance-bounded stochastic oracle twice per iteration.
- Full Splitting Without Product Spaces: Each regularizer $A_i$ is evaluated individually via its standard resolvent (proximal or projection operator), avoiding the dimension inflation and stepsize bottlenecks of product-space reformulations.
- Memory-Efficient Updates: A reformulated bookkeeping routine reduces storage from $(3n+5)d$ to $(n+7)d$ vector elements.
When $n=0$ (no regularizers/constraints), SPS reduces exactly to the Double Stepsize Extragradient Method (DSEG), giving DSEG a new geometric interpretation as a projective splitting method.
Datasets
Experiments were conducted on three standard benchmark datasets from the LIBSVM repository for Distributionally Robust Sparse Logistic Regression (DRSLR):
epsilon: $m = 400{,}000$ samples, $d = 2{,}000$ features.SUSY: $m = 2{,}000{,}000$ samples, $d = 18$ features.real-sim: $m = 72{,}309$ samples, $d = 20{,}958$ features.
No new datasets were introduced.
Key Insights and Ideas
- Stochastic Quasi-Fejér Monotonicity (SQFM): By controlling gradient variance and stepsize schedules ($\sum \alpha_k \rho_k = \infty$, $\sum \alpha_k^2 < \infty$, $\sum \alpha_k \rho_k^2 < \infty$), the authors prove almost-sure convergence of the iterates $z^k \to z^*$ without needing ergodic iterate averaging.
- Direct Approximation Residual vs. Restricted Gap: Variational inequality rates typically rely on the restricted gap function, which depends on arbitrary compact bounding sets whose diameters are rarely bounded in practice. Instead, this paper establishes rates directly on an explicit approximation residual $G_k = 0 \iff p^k \in \mathcal{S}$.
- Sparsity Preservation: Because SPS evaluates regularizers through explicit proximal maps rather than relying on ergodic iterate averaging (which washes out zero entries), intermediate iterates maintain exact structural sparsity.
Key Results
- Theoretical Guarantees:
- Iterates converge almost surely to the true solution $z^*$: $z^k \to z^*$ as $k \to \infty$.
- For total iterations $K$ with $\rho = \min\{K^{-1/4}, 1/(2L)\}$ and $\alpha = C_f \rho^2$, the expected residual achieves an explicit non-asymptotic rate: $$\frac{1}{K} \sum_{j=1}^K \mathbb{E}[G_j] = \mathcal{O}(K^{-1/4}).$$
- Empirical Performance: Tested against deterministic PS, Tseng's method, Forward-Reflected-Backward (FRB), and stochastic PSR baselines (Stochastic Tseng and FRB with Variance Reduction):
- Speed: SPS reached medium-accuracy solutions significantly faster in wall-clock time and epochs across all three benchmark datasets.
- Sparsity: On
epsilonandreal-sim, SPS produced sparse intermediate iterates throughout training, whereas iterate-averaging methods failed to retain sparsity.
Limitations and Future Work
- Convergence Rate: The $\mathcal{O}(K^{-1/4})$ rate on the squared residual is sublinear and relatively slow, reflecting the difficulty of discontinuous, set-valued operators under stochastic noise.
- Monotonicity Assumption: The core theoretical guarantees require global monotonicity (convex-concave games). While the authors outline a proof sketch for local convergence on non-monotone problems, formal non-monotone theory remains open.
- Distributed Extensions: Unlike modern deterministic PS variants, SPS currently requires synchronous updates across all operators. Extending SPS to asynchronous and block-incremental distributed settings is left for future work.
Summary updated