Stochastic Cohypomonotone Inclusions
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Cohypomonotone Inclusions
We consider solving
The inclusion problem is to find
Our assumptions:
Assumption 1 (Lipschitz continuity and
cohypomonotonicity). For every
Assumption 2 (Initial distance). There exists
Assumption 3 (Stochastic operator access). There is
a probability measure
Assumption 4 (Exact resolvent access). There is a
map
Each call chooses either a stochastic query or a resolvent query;
both count toward the same total oracle-call budget. The index
The output
Results
In a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RegularizedProxExtragradientCohypomonotone
(Ours) |
|||
| (2) (Alacaoglu et al. 2026,
Cor. 4.1, Rem. C.7); stochastic, |
(1): |
(1) requires |
|
| (3) RAIN |
(1): Scope extends to composite inclusions. On the unconstrained overlap, matches polynomial parameter dependence, with a fixed budget instead of expected random cost. | (1) incurs |
|
| (4) AR (Ji et al. 2026,
Thm. 2.2); monotone |
(1): Scope extends from monotone constrained VIs to nonmonotone cohypomonotone inclusions with general resolvents; matches polynomial accuracy dependence on the overlap. | (1) has larger
logarithmic overhead at |
|
| (5) (Alacaoglu et al. 2026,
Thm. 2.1, Cor. 2.2); deterministic, |
(1): Scope extends to
noisy oracles; no established improvement when |
(1) has larger
logarithmic and |
Abbr: