Variance-Reduced Proximal and Splitting Schemes for Monotone Stochastic Generalized Equations

Shisheng Cui, Uday V. Shanbhag

Abstract

Stochastic generalized equations (SGEs) provide a powerful framework for modeling complex decision-making problems under uncertainty, ranging from game theory to robust control. However, traditional stochastic splitting methods often exhibit a significant performance gap compared to deterministic algorithms, typically slowing from linear convergence to $O(1/\sqrt{k})$. This paper introduces the Variance-Reduced Stochastic Modified Forward-Backward Splitting (vr-SMFBS) scheme to bridge this gap. By employing a strategically increasing batch size sequence, the proposed algorithm restores deterministic convergence rates—achieving linear convergence in strongly monotone settings and $O(1/k)$ in monotone settings—while maintaining optimal sample complexity. We demonstrate the algorithm's empirical superiority on stochastic variational inequality benchmarks, showing up to 35x speed improvements over standard methods.

Introduction

Generalized Equations (GE) are a versatile mathematical tool used to find points where the sum of two operators contains zero: $0 \in A(x) + B(x)$. This structure is foundational for solving Nash equilibria, training robust machine learning models, and designing advanced control systems. In many practical scenarios, the operator $A(x)$ is stochastic, defined as an expectation $\mathbb{E}[A(x, \omega)]$ over some random variable $\omega$. Because this expectation is often impossible to compute exactly, researchers rely on stochastic splitting algorithms. However, the introduction of noise typically degrades convergence rates from fast deterministic speeds to a much slower $O(1/\sqrt{k})$ rate.

Problem Formulation

The core challenge addressed in this work is the efficient solution of SGEs where one operator is subject to noise. Many constrained optimization problems, such as Chance-Constrained Programming (CCP), can be reformulated into this SGE framework.

Mapping a Chance-Constrained Problem (CCP) to a Stochastic Generalized Equation (SGE).

As shown in the figure above, a standard CCP can be transformed into an inclusion problem of the form $0 \in T(\mathbf{z})$, where $T$ is a combination of a mapping $H(\mathbf{z})$ and a normal cone operator $\mathcal{N}_{\mathcal{Z}}(\mathbf{z})$. This transformation allows the application of splitting methods that handle the smooth and non-smooth parts of the problem separately.

The vr-SMFBS Algorithm

The authors propose the Variance-Reduced Stochastic Modified Forward-Backward Splitting (vr-SMFBS) scheme. The algorithm alternates between a "forward" step involving a sample-average estimate of the stochastic operator $A$ and a "backward" step involving the resolvent (or proximal) operator of $B$.

The key innovation is the use of increasing batch sizes ($N_k$). By progressively increasing the number of samples used to estimate $A(x)$ at each iteration, the algorithm effectively reduces the variance of the stochastic operator estimate. This allows the scheme to "clean up" the noise over time, eventually mimicking the behavior of a deterministic algorithm. Furthermore, the "modified" aspect of the FBS ensures stability for monotone operators, which might otherwise exhibit oscillatory behavior. To analyze the convergence in the most general "monotone" case, the authors utilize the Fitzpatrick gap function, a sophisticated metric for measuring the distance to the solution set in inclusion problems.

Theoretical Convergence and Complexity

The theoretical contributions of this paper are summarized in the comparison of convergence rates and sample complexities against existing literature.

Comparison of convergence rates and sample complexities for vr-SMFBS versus existing methods.

As illustrated in the table, vr-SMFBS achieves superior rates across different problem classes. In strongly monotone regimes, it achieves linear convergence ($O(q^k)$) with an optimal oracle complexity of $O(1/\epsilon)$. For the broader class of monotone problems, it improves the standard $O(1/\sqrt{k})$ rate to $O(1/k)$. Notably, the algorithm is robust enough to handle biased oracles in strongly monotone settings, a significant relaxation of the common "unbiased noise" assumption.

Empirical Performance and Insights

The algorithm was evaluated using a two-stage Stochastic Variational Inequality (SVI) problem simulating a Cournot-Nash equilibrium among multiple firms under demand uncertainty. The results were striking: vr-SMFBS significantly outperformed both Stochastic Approximation (SA) and Sample-Average Approximation (SAA).

In scenarios with complex constraints where the "backward" resolvent step is computationally expensive, vr-SMFBS proved to be nearly 35 times faster than SAA. This efficiency stems from the fact that vr-SMFBS requires far fewer iterations—and thus fewer expensive resolvent evaluations—to reach a target accuracy. Additionally, the algorithm's ability to handle state-dependent noise makes it highly applicable to real-world engineering problems where uncertainty may scale with the system's state.

Conclusion and Future Work

While vr-SMFBS offers a significant leap in performance, it currently requires knowledge of problem-specific constants, such as Lipschitz and monotonicity parameters, to tune the step sizes and batch growth rates. Future research directions include developing adaptive schemes with diminishing step sizes to eliminate this requirement and extending variance reduction to cases where both operators in the generalized equation are stochastic.

Summary updated

BibTeX
@article{cui2023variance,
  author = {Shisheng Cui and Uday V. Shanbhag},
  title = {{Variance-Reduced Proximal and Splitting Schemes for Monotone Stochastic Generalized Equations}},
  journal = {IEEE Trans. Automatic Control},
  year = {2023},
  doi = {10.1109/tac.2023.3290121},
}
Figure