Abstract
We present a new, stochastic variant of the projective splitting (PS) family of algorithms for monotone inclusion problems. It can solve min-max and noncooperative game formulations arising in applications such as robust ML without the convergence issues associated with gradient descent-ascent, the current de facto standard approach in such situations. Our proposal is the first version of PS able to use stochastic (as opposed to deterministic) gradient oracles. It is also the first stochastic method that can solve min-max games while easily handling multiple constraints and nonsmooth regularizers via projection and proximal operators. We close with numerical experiments on a distributionally robust sparse logistic regression problem.
Introduction
Modern machine learning is increasingly moving beyond simple empirical risk minimization toward more complex saddle-point (min-max) problems. Applications such as Generative Adversarial Networks (GANs), distributionally robust learning (DRL), and multi-agent games require finding equilibria rather than just minima.
The standard approach, Gradient Descent-Ascent (GDA), often fails in these settings. The competitive dynamics between players can lead to "rotational" behavior, where iterates spiral away from the solution rather than converging to it. While the mathematical framework of monotone inclusion provides tools to address these dynamics, existing algorithms face a significant bottleneck: they typically require deterministic gradients (full-batch updates) or struggle to handle multiple simultaneous constraints and nonsmooth regularizers. In the era of massive datasets, deterministic methods are computationally prohibitive.
The Stochastic Projective Splitting (SPS) Framework
To address these challenges, we introduce Stochastic Projective Splitting (SPS). This algorithm extends the Projective Splitting (PS) family—a class of methods that find solutions by constructing separating hyperplanes—into the stochastic regime.
Key Innovations
SPS introduces two critical modifications to the classical PS framework:
- Relaxed Projections for Noise Tolerance: In deterministic PS, the algorithm projects the current iterate directly onto a hyperplane that separates the current point from the solution set. In a stochastic setting, gradient noise makes these hyperplanes imperfect. SPS addresses this by using a decreasing stepsize and relaxed projections. This ensures that even with noisy gradient estimates, the iterates converge "on average" toward the solution.
- Full Splitting Modularity: SPS is a "full splitting" method. It decomposes complex problems into simpler sub-problems, handling each regularizer (e.g., $L_1$ penalties) and constraint (e.g., box constraints) individually using proximal operators and projections. This modularity allows users to solve problems with multiple constraints without ever needing to solve a difficult joint optimization sub-problem.
Theoretical Contributions
The transition to stochastic oracles requires a new theoretical foundation. We utilize the framework of stochastic quasi-Fejér monotonicity to prove that SPS iterates converge almost surely to a solution.
Convergence Rates
We establish a non-asymptotic convergence rate of $O(K^{-1/4})$ for the approximation residual. While stochastic monotone inclusion problems generally exhibit slower convergence than their deterministic counterparts, this represents the first such rate established for a full-splitting stochastic method.
Unifying Existing Methods
Our analysis reveals that the recently proposed Double Stepsize Extragradient Method (DSEG) is a special case of SPS. By viewing DSEG through the lens of projective splitting, we provide a new geometric interpretation of its behavior and demonstrate how it can be generalized to include multiple regularizers.
Numerical Experiments
We evaluated the performance of SPS on a Distributionally Robust Sparse Logistic Regression (DRSLR) task. This problem is particularly challenging because it involves both a saddle-point structure and sparsity-inducing regularizers.
Datasets and Performance
Experiments were conducted on three large-scale datasets from the LIBSVM repository:
- epsilon: 400,000 samples, 2,000 features.
- SUSY: 2,000,000 samples, 18 features.
- real-sim: 72,309 samples, 20,958 features.
SPS demonstrated significant empirical advantages over deterministic splitting methods. By utilizing minibatches (size 100) rather than full-batch gradients, SPS reached medium-accuracy solutions much faster in terms of total wall-clock time. Unlike many other stochastic methods, SPS does not require iterate averaging to achieve convergence, which simplifies implementation and often yields better practical performance.
Conclusion and Future Work
Stochastic Projective Splitting provides a robust, modular, and theoretically grounded framework for solving complex min-max problems in large-scale machine learning. By enabling the use of stochastic oracles within the projective splitting family, it bridges the gap between high-dimensional data and sophisticated game-theoretic formulations.
While the current $O(K^{-1/4})$ rate is a significant milestone, future research will explore faster convergence under stronger assumptions like strong monotonicity. Additionally, we aim to extend SPS to asynchronous distributed environments and investigate its application to non-monotone problems, such as standard GAN training, where local convergence guarantees are highly sought after.
Summary updated