Stochastic Lipschitz Monotone Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Lipschitz Monotone Root Finding
We seek a zero of a monotone,
The root-finding problem is
Our assumptions:
Assumption 1 (Monotonicity and Lipschitz
continuity). For every
Assumption 2 (Nearby zero). There exists
Assumption 3 (Stochastic operator oracle). There
exist a probability measure
Queries may be made at any point of
Results
In a finite-dimensional real Hilbert space with its Borel structure,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) InertialMonotoneResidual
(Ours) |
|||
| (2) RRSEG (Lee and Kim 2026), Cor. 6.2 | (1) saves at least a
factor |
(1) uses growing batches instead of two calls per update; does not cover composite inclusions. | |
| (3) Accumulative regularization (Ji et al. 2026), Thm. 2.2 | (1) replaces the
statistical factor |
(1) does not cover constrained variational inequalities. | |
| (4) S-Dual-OHM (Yoon and Loizou 2026), Cor. 3.6 | (1) needs only mean
regularity and fresh samples. On the overlap, removes the deterministic
|
Abbr: