acceptodds
Under review as a conference paper at ICLR 2027

Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries

Abstract

We study acceleration of stochastic first-order methods for monotone Lipschitz inclusions with a fixed number of oracle queries per iteration, measured by the expected squared residual. Existing methods either have suboptimal oracle complexity, require an increasing number of oracle queries per iteration, or both. We develop variance-reduced anchored forward-backward (VRAF), an anytime and composite method that makes two oracle queries per iteration, both using the same sampled stochastic operator. VRAF attains oracle complexity, thereby achieving the optimal dependence on the stochastic operator variance for the first time, even among methods allowing an increasing number of queries. This, however, leaves open whether the optimal deterministic term can also be attained. We establish an impossibility result by extending the lower bound of Foster et al. (2019) to stochastic oracles permitting repeated queries to sampled stochastic operators, showing that oracle complexity is unattainable in general. We therefore develop recentered regularized stochastic extragradient (RRSEG), which attains the near-optimal oracle complexity previously achievable only with an increasing number of queries per iteration, while using a fixed number of queries.

Primary area:
optimization
Keywords:
optimization, acceleration, stochastic, monotone inclusion, minimax, anchoring, Halpern iteration, variance reduction

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_36jKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies stochastic monotone Lipschitz inclusions with a fixed number of oracle queries per iteration. It proposes VRAF, which achieves optimal stochastic variance dependence, and RRSEG, which achieves an optimal deterministic rate with a near-optimal stochastic rate. The paper also establishes a lower bound showing that the two optimal rates cannot generally be attained simultaneously.

Critical strengths

1. Meaningful theoretical contributions. VRAF achieves an O(1/N)O(1/N) expected squared residual bound with optimal variance dependence, while RRSEG achieves O(L2D2/N2+σ2log⁡3N/N)O(L^2D^2/N^2+\sigma^2\log^3N/N), both using only two oracle queries per iteration.

2. Interesting lower bound. The impossibility result provides useful insights into the tradeoff between deterministic acceleration and stochastic variance reduction, even under same-sample oracle access.

3. A coherent theoretical framework with detailed analysis. The paper connects variance reduction, anchoring, and recursive regularization in a coherent manner. In particular, the recentering mechanism in RRSEG provides an interesting way to control the movement of the solutions to successive regularized problems.

Critical weaknesses

1. Algorithmic novelty. RRSEG builds on the single-loop recursive regularization framework of RAIN-SL. While the new convergence guarantee is valuable, the paper could more clearly distinguish the essential algorithmic modifications from the improvements in parameter design and theoretical analysis.

2. Incomplete characterization of the optimal complexity. While the lower bound establishes the necessity of logarithmic factors, RRSEG achieves a stochastic term with a log3Nlog^3 N factor, leaving a gap to the lower-bound threshold. Moreover, the necessity of the additional LΔ2D2/NL_\Delta^2D^2/N dependence in VRAF is not established. A tighter characterization of these dependencies would further strengthen the theoretical contributions.

Questions for authors

Q1. Could the authors clarify which modifications from RAIN-SL are essential for establishing the convergence guarantee of RRSEG, particularly the choice of regularization centers and the horizon-dependent parameter schedule?

Q2. The lower bound rules out stochastic rates with a logarithmic factor log⁡pN\log^p N for p<1p<1, while RRSEG achieves a log⁡3N\log^3 N factor. Could the authors comment on whether this gap is inherent to RRSEG or could potentially be reduced through a tighter convergence analysis?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 36JK

We thank the reviewer for their positive assessment and questions about RRSEG's update and logarithmic rate.

Q1. Regularization centers and horizon-dependent parameters.

The main structural change from RAIN-SL is the center of each new regularization term:

=H_k^{\mathrm{RAIN\text{-}SL}}(z)+\rho_k(z-z_k), \qquad H_{k+1}^{\mathrm{RRSEG}}(z) =H_k^{\mathrm{RRSEG}}(z)+\lambda_k(z-z_{k+1}).$$ Here $a_k$ is the current regularization coefficient, $\lambda_k=a_{k+1}-a_k\ge0$, and $r_k$ is the zero of $H_k^{\mathrm{RRSEG}}+A$. Recentering at $z_{k+1}$ gives $$||z_{k+1}-r_{k+1}||^2\le||z_{k+1}-r_k||^2.$$ This is the central inequality in RRSEG's convergence proof (Lemma D.2). Centering the added term at $z_k$, as in RAIN-SL, gives an analogous bound with an extra multiple of $||z_{k+1}-z_k||^2$, which requires a separate estimate (Appendix D.1.2). The horizon-dependent schedule is the other ingredient in our proof. RAIN-SL was obtained by taking a single stochastic extragradient step at each regularization update of RAIN, without a convergence analysis of this variant. In contrast, RRSEG selects its horizon-dependent parameters to control the errors from these single-step updates in the proof (Appendix D). ### Q2. The gap between $\log N$ and $\log^3N$. We do not have a matching worst-case example, so our results do not establish that RRSEG's $\log^3N$ factor is inherent. A tighter analysis or a different parameter schedule could reduce the power.

Thanks for your clarification. I would like to keep my score

We are glad to hear that our response clarified the points you raised. We appreciate your time and thoughtful feedback.

Reviewer_AeLFOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies stochastic algorithm for monotone inclusion problems with Lipschitz operators. The authors make three main contributions:

  • VRAF algorithm, which requires two same-sample evaluations of the stochastic operator and achieves a complexity of O(σ2/ϵ+((L+LΔ)D)2/ϵ)\mathcal{O}(\sigma^2 / \epsilon + ((L+L_\Delta)D)^2/\epsilon) under the mean-square Lipschitz noise.
  • A lower-bound showing that it is impossible to achieve the optimal stochastic O(σ2/ϵ)\mathcal{O}(\sigma^2 / \epsilon) and deterministic O(LD/ϵ)\mathcal{O}(LD/\sqrt{\epsilon}) complexities simultaneously.
  • RRSEG algorithm, which achieves the convergence rate O((LD/N)2+σ2log⁡3N/N)\mathcal{O}((LD/N)^2 + \sigma^2 \log^3 N / N) and matches the lower bounds up to logarithmic factors.
Critical strengths

The main strength of this paper is that it presents a valuable contribution to the research direction. VRAF achieves optimal log-free stochastic complexity, which appears to be a new result. Lower complexity bound is a nice adaptation of the arguments by Foster et al. (2019) to the monotone inclusion setting and repeated-query stochastic oracle. RRSEG may be not particularly impressive in terms of new complexity bounds, but it simpler compared to RAIN, because it does not require solving auxiliary subproblems in an inner loop, while maintaining near-optimal convergence guarantees.

Critical weaknesses

Some of the results can be seen as a bit incremental. In particular, the derivation of the lower bounds is largely based on existing arguments by Foster et al. (2019), and the complexity result for RRSEG does not improve the existing theoretical SOTA in terms of rates.

Questions for authors

n/a

2 comments
AuthorsOpenReview ↗

Response to Reviewer AeLF

We thank the reviewer for their positive assessment and constructive comments. We have revised the paper to state the scope of each contribution more precisely.

Relation to Foster et al. (2019).

We agree that the noisy-binary-search mechanism itself is inherited from Foster et al. (2019), and we do not claim a fundamentally new lower-bound technique. Our contribution is its extension to repeated same-sample access, which is not a direct consequence of their result: repeated queries to one sampled operator can reveal additional information.

RRSEG relative to the existing rate.

We agree that RRSEG has the same near-optimal oracle complexity order as the state-of-the-art method RAIN. The distinction is instead in its algorithmic structure: RRSEG is single-loop and avoids the prescribed inner iteration counts that guaranteed RAIN uses to meet worst-case subproblem accuracy requirements. Such iteration counts can be conservative when a subproblem is easier than the worst case. In our new comparison under a common 10710^7 oracle query limit, RRSEG achieved a lower mean squared residual than guaranteed RAIN on all three tested problems.

As the discussion period is coming to an end, we would appreciate it if you could review our rebuttal and revised manuscript before the final assessment. Thank you for your time and consideration.

Reviewer_ETLSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies stochastic monotone Lipschitz inclusions, where the operator can only be accessed through noisy samples. Progress is measured by the expected squared residual. The authors focus on "fixed-query" methods, meaning methods that use a bounded number of oracle calls per iteration, and make three contributions.

1. VRAF. The first method combines an anchored forward-backward step with a STORM-style recursive estimator of the operator. It uses two oracle calls per iteration, evaluated with the same sample, and it assumes the noise is Lipschitz in mean square. Its step sizes do not depend on the horizon, so it can be stopped at any time. The guarantee for the last iterate is

E[R(zN)2]≤35(L2+LΔ2)D2+σ2N+2.\mathbb E[R(z_N)^2] \le 35\frac{(L^2+L_\Delta^2)D^2+\sigma^2}{N+2}.

The authors present this as the first log-free O(1/ϵ) complexity under these oracle assumptions, and therefore as optimal in its dependence on the noise variance. They also show that the 1/N deterministic part cannot be improved for this step-size schedule, and that the iterates themselves need not converge.

2. A lower bound. Building on the noisy binary search construction of Foster et al. (2019), the authors show that the following complexity cannot be achieved in general, even when the algorithm can query the same random sample several times:

O(LDϵ+σ2ϵ).O\left(\frac{LD}{\sqrt\epsilon}+\frac{\sigma^2}{\epsilon}\right).

A corollary shows that fixed-query methods cannot get the logarithmic factor in the noise term below power one.

3. RRSEG. The second method is a single-loop version of the recursive regularization behind RAIN (Chen & Luo, 2024). Each iteration takes one stochastic extragradient-type step on a regularized problem and then moves the regularization center to the new iterate. It needs only unbiased samples with bounded variance, uses two independent samples per iteration, and requires the horizon in advance. For a corrected final output it achieves

E[R(z^N)2]=O(L2D2N2+σ2log⁡3NN),\mathbb E[R(\widehat z_N)^2] = O\left(\frac{L^2D^2}{N^2}+\frac{\sigma^2\log^3 N}{N}\right),

which the authors describe as matching RAIN's near-optimal rate without increasing the number of queries per iteration.

Validation. The theory is supported by full proofs in the appendix, including symbolic checks for the VRAF proof. The experiments use three small synthetic monotone problems and a rock-paper-scissors game, and compare against BC-(P)SEG+, stochastic GOMA, a single-loop RAIN variant, and E-Halpern.

Critical strengths

1. VRAF gives a clean, practical guarantee and is honest about its limits.

VRAF is simple to run: two oracle calls per step, no batches, no inner loops, and step sizes that do not depend on when you plan to stop. Its guarantee holds for the last iterate rather than a random or averaged one, and it has no logarithmic factors. As far as I know, this combination is new for composite monotone inclusions under same-sample access. I also appreciated that the authors map out where the method stops working. They prove that its deterministic rate cannot be improved for this schedule, and they give a counterexample showing that small residuals do not imply that the iterates converge. This matters for my assessment because it is the most clearly new and usable result in the paper.

2. The RRSEG analysis is careful and useful in its own right.

Chen & Luo proposed a single-loop variant of RAIN but did not analyze it. This paper does. The proof is built from understandable pieces: a one-step contraction for each regularized problem, a bound on how much the target moves when the regularization is recentered, and a tracking argument that ties the two together. The final output for composite problems is a nice touch, since it reuses oracle values already computed while controlling both their noise and how far apart they were evaluated. The deterministic part of the rate also avoids the extra log-log factor in RAIN's bound. The lower-bound extension to repeated sample queries also looks correct to me. Together these make the paper technically solid even where I question the framing.

Critical weaknesses

1. The main claims are broader than what the paper actually shows.

The paper's central selling point is the difference between fixed-query methods and methods like RAIN, which the abstract says need "an increasing number of queries per iteration." Section 2, however, never says what counts as an iteration. This matters because RAIN's inner solver (Algorithm 3 in Chen & Luo) already uses exactly two oracle calls per extragradient step, the same as RRSEG. RAIN does more total work only because its inner loops get longer. If each inner step is counted as an iteration, RAIN is also fixed-query under the paper's own definition. So the abstract's claim that RRSEG achieves something previously possible only with growing per-iteration cost is not established.

RRSEG still has real merits: a different update structure, a terminal output for composite problems, and a slightly better deterministic log factor. But these are more modest than the headline claim, and the paper should present them as such. Ideally it would also explain what concrete benefit the fixed-query property is meant to capture.

A similar issue affects the optimality story. VRAF is optimal in its dependence on the noise variance, but its bound also contains a term from the noise Lipschitz constant, which can dominate:

LΔ2D2N.\frac{L_\Delta^2 D^2}{N}.

The lower bound does not rule out a method that improves the deterministic part while keeping this term, for example one with complexity

O(LDϵ+LΔ2D2ϵ+σ2ϵ).O\left(\frac{LD}{\sqrt\epsilon}+\frac{L_\Delta^2D^2}{\epsilon}+\frac{\sigma^2}{\epsilon}\right).

So the paper establishes that a tradeoff exists, but not where it lies. That is fine as a result, but it is narrower than the "optimal variance dependence plus impossibility" framing suggests. This is the main reason for my rating: the math looks correct, but once the claims are stated accurately, the contribution is smaller than presented.

2. The experiments do not test the claims that matter most.

The most natural baseline, RAIN with its theoretical guarantees, is missing. Only a heuristic single-loop variant is run, and it blows up on every problem, which says little about how RRSEG compares with the real method at the same oracle budget. Two of the three monotone test problems have symmetric Jacobians, so they are really convex minimization problems in disguise and do not exercise the rotational dynamics typical of saddle-point problems. The rock-paper-scissors example lies outside the theory, as the authors note. The figures also never vary the noise level or the noise Lipschitz constant, so the predicted tradeoff between VRAF and RRSEG is never actually observed. I do not expect large-scale benchmarks from a theory paper, but a matched-budget comparison with RAIN and a simple sweep over the noise parameters on the existing problems would make the empirical story much more convincing. I treat this as a supporting concern rather than the deciding one.

Questions for authors

Clarification questions (answers could change my assessment):

  1. What does "fixed-query" mean? Under the definition in Section 2, why does RAIN not count as fixed-query if each of its extragradient steps is treated as an iteration? What practical or theoretical advantage is the distinction meant to capture?

  2. RRSEG versus RAIN. Could you state the advantage of RRSEG over RAIN directly, in terms of the update structure, the terminal output for composite problems, and the improved deterministic log factor? How does RRSEG compare with the guaranteed version of RAIN on your test problems at the same oracle budget?

  3. Scope of the lower bound. Under same-sample access and Lipschitz noise, is it still open whether the following complexity can be achieved?

    O(LDϵ+LΔ2D2ϵ+σ2ϵ)O\left(\frac{LD}{\sqrt\epsilon}+\frac{L_\Delta^2D^2}{\epsilon}+\frac{\sigma^2}{\epsilon}\right)

    If so, please make the distinction between optimal dependence on the variance and joint optimality in all parameters explicit in the paper.

For information only (not a criticism and not a factor in my rating):

  1. Version 2 of Kim and Alacaoglu, posted September 24, 2026, after the September 16 submission deadline, describes an anytime proximal Halpern method with a STORM estimator and two same-sample calls per iteration. The September 14 version did not include this result. Their main theorem bounds the expected residual, but their second-moment lemma seems to also give a log-free squared-residual bound. A short discussion of how VRAF relates to it would help readers, for instance in terms of parameter dependence, step sizes, and VRAF's coverage of general maximally monotone operators rather than proximal terms only. Under the ICLR 2027 reviewer guidelines, the absence of this comparison is not grounds for rejection.

Suggestion (not required):

  1. A small experiment that varies the noise variance and the noise Lipschitz constant on the existing problems would show the predicted crossover between VRAF and RRSEG directly.
3 comments
AuthorsOpenReview ↗

Response to Reviewer ETLS

We thank the reviewer for the constructive suggestions. We revised the manuscript to clarify the scope, limitations, and contributions of our results, expanded the comparisons with related work, and added experiments addressing the questions about RAIN and rotational dynamics.

Q1. Fixed-query and single-loop.

As the reviewer observes, RAIN also qualifies as fixed-query under our definition in Section 2 if each inner stochastic extragradient step is counted as an iteration. Fixed-query alone therefore did not make the algorithmic scope we intended clear.

We therefore state our algorithmic scope as single-loop fixed-query: each regularization update uses no nested stochastic subproblem solver. RRSEG advances its regularization after one stochastic forward-backward-forward step with two independent oracle queries. Guaranteed RAIN instead runs an inner solver for a prescribed number of iterations to meet worst-case subproblem accuracy requirements. Such stage-specific iteration counts can be conservative when a subproblem is easier than the worst case. RRSEG avoids these inner iterations and accuracy targets; this is a practical advantage of its update structure, without a general claim of better oracle complexity order.

We have clarified these distinctions in the title, abstract, problem setting, introduction, related work, and comparison table.

Q2. RRSEG versus RAIN and the guaranteed RAIN experiment.

Update structure. RRSEG is single-loop, whereas the theoretically guaranteed RAIN method uses a nested stochastic subproblem solver. The practical advantage of this structure is explained in Q1. RAIN also has a single-loop experimental variant (Algorithm 9), but no convergence rate is proved for it.

Terminal output for composite problems. RRSEG guarantees the expected squared residual of a corrected terminal output for general monotone inclusions, including A≠0A\ne0. The guaranteed RAIN result covers equations (A=0A=0) and uses a randomized output from its inner solver. Thus RRSEG's guarantee covers a broader problem class and provides a nonrandomized terminal output.

Improved deterministic log factor. For the expected squared residual, RRSEG's deterministic oracle complexity term O(LD/ϵ)O(LD/\sqrt\epsilon) improves the corresponding RAIN guarantee by removing a log⁡log⁡\log\log factor. Specifically, the revised Appendix A.1 derives the following oracle complexity from RAIN's published proof, whose theorem is stated for the expected residual:

\frac{LD}{\sqrt\epsilon} \left[1+\log\log\left(e+\frac{LD}{\sqrt\epsilon}\right)\right] +\frac{\sigma^2}{\epsilon} \log^3\left(e+\frac{LD}{\sqrt\epsilon}\right) \right).$$ **Theoretically guaranteed RAIN experiment.** We added the theoretically guaranteed RAIN method with its theorem parameters to the experiments. Each method was allowed at most $10^7$ oracle queries per experiment. The mean squared residuals over 50 runs at the last completed outputs under this common limit are: | Problem | RAIN squared residual | RRSEG squared residual | |:--|--:|--:| | 1 |$9.14\times10^{-3}$ | $2.13\times10^{-8}$ | | 2 |$1.27\times10^{-2}$ | $1.34\times10^{-9}$ | | Nonlinear rotation |$4.44\times10^{-2}$ | $4.98\times10^{-8}$ | RRSEG has a lower mean squared residual on all three problems under the common $10^7$-query limit. We compare guaranteed RAIN in all examples except Problem 3 and RPS, which its theorem does not cover.
AuthorsOpenReview ↗

Response to Reviewer ETLS (Continued)

Q3. Scope of the lower bound.

Yes. Our lower bound does not rule out the oracle complexity proposed in the question:

+\frac{L_\Delta^2D^2}{\epsilon} +\frac{\sigma^2}{\epsilon}\right).$$ To clarify what our lower bound says about the joint dependence on $L$, $L_\Delta$, $D$, and $\sigma^2$, we have revised the theorem to rule out a uniform oracle complexity guarantee of $$O\left(\frac{\overline L D}{\sqrt\epsilon}+\frac{\sigma^2}{\epsilon}\right),$$ which is equivalent to $O\left(\frac{LD}{\sqrt\epsilon} + \frac{L_\Delta D}{\sqrt\epsilon} + \frac{\sigma^2}{\epsilon}\right)$. Whether the proposed guarantee can be attained remains open. We have also revised the paper to state explicitly that VRAF's optimal dependence on the variance $\sigma^2$ does not establish joint optimality in these parameters. ### Q4. Concurrent STORM proximal Halpern method. Kim and Alacaoglu's concurrent Algorithm 2 independently obtains essentially the same STORM–Halpern recursion as VRAF. We have therefore revised the paper to acknowledge this overlap and to state VRAF's remaining distinctions more narrowly. Their analysis permits unbounded variance; under bounded variance it implies $O(H^2(D^2+\sigma^2)/N)$, while VRAF gives $O((\overline L^2D^2+\sigma^2)/N)$ with separate Lipschitz and variance terms. The step-size schedules differ but have the same $k^{-1/2}$ order. ### Q5. Noise sensitivity and rotation. We added an example with a nonzero skew Jacobian component and compared all methods at fixed noise parameters to address the concern about rotational dynamics. Varying $\sigma$ and $L_\Delta$ separately on this example shows a crossover between VRAF and RRSEG. The full comparison and both sweeps are reported in Appendix E.3.

As the discussion period is coming to an end, we would appreciate it if you could review our rebuttal and revised manuscript before the final assessment. Thank you for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.