acceptodds
Under review as a conference paper at ICLR 2027

Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding

Abstract

Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently been shown to admit a more robust direct stochastic extension than standard anchor acceleration. However, without additional strong monotonicity, the existing stochastic dual-anchoring guarantee by Yoon & Loizou (2026) has two limitations: first, it requires cocoercivity in expectation, and second, it attains only oracle complexity, leaving a gap to the near-optimal complexity achieved by other methods. In this work, we address both of these limitations by combining dual-anchoring with stochastic resolvent approximation and optimized variance control. For unbiased stochastic oracles with variance bounded by , where sample operators are monotone and uniformly -Lipschitz, our algorithm finds a point satisfying \mathbb{E} \left[ \left\\| F(x\_\epsilon)\right\\|\right] \le \epsilon with a near-optimal oracle complexity of , where and is the initial distance to a solution. This result improves the best known oracle complexity in the noise-dominated regime under these samplewise assumptions, reducing the poly-logarithmic factor from cubic to quadratic.

Primary area:
optimization
Keywords:
Monotone inclusion, Root-finding problem, Stochastic optimization, Acceleration, Optimal complexity

Reviews

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

The paper studies stochastic monotone root-finding using dual-anchor acceleration. In the cocoercive setting, it improves the oracle complexity of stochastic dual anchoring from O(ϵ−3)O(\epsilon^{-3}) to the near-optimal O~(ϵ−2)\widetilde O(\epsilon^{-2}) through an optimized batch-size schedule. The approach is then extended to monotone Lipschitz operators using approximate stochastic resolvents, yielding a complexity of O(LDϵℓ+σ2ϵ2ℓ2)O\left(\frac{LD}{\epsilon}\ell+\frac{\sigma^2}{\epsilon^2}\ell^2\right), with ℓ=log⁡(1+LD/ϵ)\ell=\log(1+LD/\epsilon). The theoretical results are complemented by numerical experiments.

Critical strengths
  1. Near-optimal complexity under cocoercivity: The paper improves the previous O(ϵ−3)O(\epsilon^{-3}) complexity of stochastic dual anchoring to O~(ϵ−2)\widetilde O(\epsilon^{-2}) through an optimized batch-size schedule within the existing S-DUAL-OHM framework.

  2. Extension beyond cocoercivity: By approximating stochastic resolvents while controlling approximation errors and inner-loop oracle costs, the authors extend dual anchoring to monotone Lipschitz operators, providing an alternative route to near-optimal oracle complexity.

Critical weaknesses
  • Limited improvement over existing near-optimal methods: Compared with RAIN (Chen & Luo, 2024), the improvement is limited to reducing the stochastic logarithmic factor from cubic to quadratic, at the cost of a worse deterministic logarithmic dependence. Moreover, the analysis relies on stronger samplewise assumptions, limiting the generality of the results.

  • Gap between theory and experimental performance: In the monotone experiment, the theoretically prescribed algorithm performs comparably to RAIN. The substantially better performance is achieved by a practical variant using only two inner iterations per sampled resolvent, rather than the theoretically prescribed accuracy schedule. However, no convergence guarantee is provided for this variant.

Questions for authors
  1. Can the authors identify practical applications beyond additive-noise models that satisfy the samplewise monotonicity and Lipschitz continuity assumptions, as well as the reusable-sample oracle requirement?

  2. Can the authors establish convergence guarantees for the practical variant using only two inner iterations, which achieves the best experimental performance?

2 comments

We thank the reviewer for the careful review, positive assessment and constructive comments that identify several points of clarifications that help improve the presentation of the paper. Below, we provide responses to the points raised by the reviewer.

Weaknesses

Limited improvement over existing near-optimal methods: ... the improvement is limited to reducing the stochastic logarithmic factor from cubic to quadratic ... Moreover, the analysis relies on stronger samplewise assumptions, limiting the generality of the results.

While we agree with the reviewer’s comment, we believe that these are features of our results rather than critical weaknesses. Yes, we do require samplewise assumptions, but we thereby achieve a meaningful reduction in the dominant term in the complexity bound, i.e., a logarithmic factor in the stochastic term. These distinctions are clearly mentioned in the paper.

We would like to also highlight that our paper has a broader conceptual contribution as we achieve near-optimal stochastic complexity based on the dual-anchor mechanism, which is clearly different from most prior work in the literature, including Chen & Luo (2024). This establishes a new route from deterministic acceleration to stochastic acceleration. It is a challenging and interesting open direction whether S-Dual-OHM can attain near-optimal complexity with relaxed oracle assumptions as in the case of RAIN.

Gap between theory and experimental performance: ... The substantially better performance is achieved by a practical variant using only two inner iterations per sampled resolvent ... However, no convergence guarantee is provided for this variant.

In the monotone operator experiment, we introduced the practical variant to emphasize that our proposed framework is empirically not sensitive to the accuracy of resolvent approximations, which was controlled conservatively in the theory, and also because reducing the oracle calls spent in the resolvent inner loops provided a visually distinguishable gain in the plots. For further context, the RAIN baseline itself is also a practical single-loop implementation that Chen & Luo (2024) used in their own experiments (see their Appendix E.1 and Algorithm 9), rather than the implementation as prescribed by the theorem.

Nevertheless, we understand that this choice has created the concern that the experiment was highlighting what was not fully supported by the theory. Therefore, in the revision, we re-run the experiment with the same Huber minimax operator construction but in a slightly different regime, and show that the algorithm prescribed by our theory (which we analyzed in Corollary 3.6) does provide performance gain over existing baselines. We no longer use the practical modification. Please see the updated Figure 1(b) and the paragraph on Experiment 2 on page 9.

Questions

  1. Can the authors identify practical applications beyond additive-noise models that satisfy the samplewise monotonicity and Lipschitz continuity assumptions, as well as the reusable-sample oracle requirement?

While our work is focused on the theory rather than applications, yes, there are relevant problems with samplewise monotonicity/Lipschitzness beyond additive-noise cases. A concrete example is the Lagrangian formulation of constrained logistic regression: let ℓi(x)=log⁡(1+exp⁡(ai⊤x))\ell_i(x)=\log(1+\exp(a_i^\top x)) for i=1,…,ni=1,\dots,n be sample logistic losses and suppose there is a linear constraint Ax=bAx=b. The Lagrangian of the regularized population loss would be f(x,y)=1n∑i=1nℓi(x)+μ2∣x∣2+y⊤(Ax−b)f(x,y) = \frac1n\sum_{i=1}^n\ell_i(x) + \frac\mu2\\|x\\|^2 + y^\top (Ax-b), and uniform sampling of ii yields the sample saddle operators F((x,y);i)=(∇ℓi(x)+μx+A⊤y,  b−Ax)\mathbb{F}((x,y);i)=\bigl(\nabla\ell_i(x)+\mu x+A^\top y,\;b-Ax\bigr) which are monotone and Lipschitz with parameter L=μ+R24+∣A∣L = \mu + \frac{R^2}{4} + \\|A\\| where R=max⁡i=1,…,n∣ai∣R = \max_{i=1,\dots,n} \\|a_i\\|. The stochastic noise is not additive as it depends on xx, while the variance is globally bounded by R2R^2 because ∣∇ℓi(x)∣≤∣ai∣≤R\\|\nabla\ell_i(x)\\| \le \\|a_i\\| \le R. Samples can be reused because the corresponding data indices can be retained, with which the component gradients can be reevaluated.

  1. Can the authors establish convergence guarantees for the practical variant using only two inner iterations, which achieves the best experimental performance?

We do not have such a guarantee, and based on the observation that removing inner solver for resolvent approximation boosts the empirical performance, pursuing a near-optimal single-loop version of S-Dual-OHM would be a valuable future direction. At the moment, we revise the paper so that it no longer uses the practical variant, for the sake of alignment between the theory and experiments.

We hope the above clarifications resolve the reviewer’s concerns about connection to prior work, and if that is the case, we kindly ask for your continued support. We will be happy to answer any additional concerns or points of discussion.

Thank you for the clarifications and revisions. The practical example is convincing, and the revised experiments appear to address my concern about the gap between theory and practice. The stronger assumptions and limited complexity improvement over RAIN remain, but I maintain my weak-accept recommendation.

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

The paper improves the sample efficiency of stochastic dual-anchoring by choosing different batch sizes across iterations. For cocoercive problems, this reduces the oracle complexity from O(ε⁻³) to Õ(ε⁻²). The authors also use approximate resolvents to handle monotone problems. This gives a better logarithmic factor than RAIN, but needs stronger assumptions. They test the approach on two synthetic problems.

Critical strengths
  1. The batch-size scheduling idea is simple and effective. For cocoercive problems, it improves the oracle complexity from O(ε⁻³) to Õ(ε⁻²) without changing the underlying update rule.

  2. The analysis allows errors and bias in the approximate resolvent computations. This makes it possible to apply dual-anchoring to monotone problems and obtain near-optimal complexity under the stated assumptions, without using MLMC.

Critical weaknesses
  1. RAIN++ (Chen & Luo, 2024, §5), although designed for structured nonconvex-nonconcave problems, also approximates a resolvent of the form J_{αF} with α = 1/(2L) and uses MLMC to reduce the estimation bias. Section 3 uses the same resolvent formulation but does not explicitly discuss this connection. A comparison of the approximation schemes, assumptions, and error analysis would help clarify the distinct technical contribution.
Questions for authors
  1. How does the approximate resolvent construction in Section 3 differ from that used in RAIN++? In particular, what allows your method to avoid MLMC, and how do the stronger samplewise assumptions contribute to this?

  2. Can the batch-size allocation of Section 2.1 also improve the oracle complexity of primal anchoring (S-OHM)?

2 comments

We thank the reviewer for the careful review and positive assessment. The reviewer’s constructive comments identify several points of clarifications that help improve the presentation and positioning of the paper. Below, we provide responses to those points.

Weaknesses

RAIN++ (Chen & Luo, 2024, §5) ... also approximates a resolvent of the form JαFJ_{\alpha F} with α=1/(2L)\alpha=1/(2L) and uses MLMC to reduce the estimation bias. ... A comparison of the approximation schemes, assumptions, and error analysis would help clarify the distinct technical contribution.

In our analysis, we view the resolvent computation as solving a 1-strongly monotone inclusion and simply use the inner loop of operator descent (Algorithm 1) to approximate it, rather than using MLMC. We provide further technical details on the difference and why MLMC is not needed for our purpose below, in our response to Question 1. We will include that comparison in the final version of the paper, once we are given additional space.

Questions

  1. How does the approximate resolvent construction in Section 3 differ from that used in RAIN++? In particular, what allows your method to avoid MLMC, and how do the stronger samplewise assumptions contribute to this?

Chen & Luo (2024) used Epoch-SEG with MLMC to reduce the expected bias in the resolvent computation for 12LF\frac{1}{2L}\mathbb{F} exponentially, as required by their analysis (see their Theorem 5.1). In our case, the resolvent bias is controlled by the parameter ρk\rho_k in our Condition 3.1, and they contribute to the final convergence bound of Theorem 3.2 as the cumulative error term proportional to ReRRe^R, where R=∑k=0N−2ρkR = \sum_{k=0}^{N-2} \rho_k. As O(1/N2)O(1/N^2) is the asymptotic limit for the convergence rate, it suffices to guarantee ReR=O(1/N2)Re^R = O(1/N^2) so that it does not slow down the overall order of convergence. We enforce this by taking ρk≡1/(2N3)\rho_k \equiv 1/(2N^3) in Corollary 3.6. Now, because the bias only needs to be polynomially small for our purpose, the simple operator descent (or equivalently, Picard iteration) in our Algorithm 1 is sufficient, and a sophisticated method like MLMC is not required.

Our view is that this is possible because we have built our framework based on Dual-OHM, and it is intrinsically less sensitive to operator variance and resolvent bias than anchor-based methods, including RAIN. On the other hand, the tradeoff is that the analysis of S-Dual-OHM requires the random maps Tk\mathbb{T}_k at each iteration to be nonexpansive in expectation, up to resolvent bias (Conditions 2.1 and 3.1). To guarantee this, we need the samplewise monotonicity and Lipschitzness, so that resolvent of each αγjF(⋅;ξj)\alpha\gamma_j \mathbb{F}(\cdot; \xi_j) is nonexpansive.

In summary, the stronger assumptions are the artifact of how stochastic Dual-OHM’s analysis is structured, but this allows us to avoid MLMC and use a simpler resolvent approximation scheme, with more lenient tolerance on the bias.

  1. Can the batch-size allocation of Section 2.1 also improve the oracle complexity of primal anchoring (S-OHM)?

Our batch allocation is based on Theorem 2.2, and the analogous result for primal anchoring can be found in prior work such as Lee & Kim (2021) [1], proposing FEG, an anchor-based monotone inclusion algorithm. [1, Theorem 6.1] analyzes the stochastic version of FEG, whose bound takes the form E[∣F(zk)∣2]≤4L2∣z0−z⋆∣2N2+6N2∑k=0N−1(k2σk2+(k+1)2σk+1/22).\mathbb E\left[\\|\mathbb{F} (z_k)\\|^2 \right] \le \frac{4L^2 \\|z_0 - z_\star\\|^2}{N^2} + \frac{6}{N^2} \sum_{k=0}^{N-1} (k^2 \sigma_k^2 + (k+1)^2 \sigma_{k+1/2}^2). Up to a constant, this is similar to having Theorem 2.2 but with aN,k=k2N2a_{N,k} = \frac{k^2}{N^2}, rather than aN,k=1(N−k)(N−k−1)a_{N,k} = \frac{1}{(N-k)(N-k-1)} as in our S-Dual-OHM case. Repeating the argument from our Section 2.1 with aN,k=k2N2a_{N,k} = \frac{k^2}{N^2}, we obtain SN=∑k=0N−2aN,k=Θ(N)S_N = \sum_{k=0}^{N-2} \sqrt{a_{N,k}} = \Theta(N), and with N=Θ(Dϵ)N = \Theta\left(\frac{D}{\epsilon}\right) the total oracle budget becomes Q=Θ(SN2ϵ2)=Θ(ϵ−4)Q = \Theta\left(\frac{S_N^2}{\epsilon^2}\right) = \Theta(\epsilon^{-4}) (the optimal batch allocation found by Cauchy-Schwarz here is Bk=Θ(k/ϵ2)B_k = \Theta(k/\epsilon^2), different from the case of Dual-OHM). This suggests that the oracle complexity of S-OHM is significantly worse than S-Dual-OHM and cannot be improved via simple batch-size scheduling. This is consistent with the observation from prior work such as Cai et al. [2, Corollary 3.2].

[1] S. Lee and D. Kim. Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems. NeurIPS 2021.

[2] X. Cai, C. Song, C. Guzman and J. Diakonikolas. Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions. NeurIPS 2022.

We hope the above clarifications resolve the reviewer’s concerns about connection to prior work, and if that is the case, we kindly ask for your continued support. We will be happy to answer any additional concerns or points of discussion.

Thanks for clarifications and detailed responses. I remain inclined to maintain my original score.

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

This paper studies the problem of finding a zero of a given operator FF, but when only the access to a stochastic oracle is available. The specific method considered is a stochastic variant of the dual-OHM method, which is known to attain an optimal rate of convergence in the deterministic setting. The main idea is to develop a clever way to "schedule" the minibatch sizes so that the control over the stochastic error term is improved without changing the total oracle evaluation count. With this newly developed technique, the authors were able to construct methods that achieve methods that enjoy worst-case optimal convergence rates, up to logarithmic terms.

Critical strengths

The work extends the prior work (Yoon & Loizou, 2026), which was limited to cocoercive problems, by providing stronger convergence guarantees that cover monotone problems. Monotone problems are (at least from my perspective) substantially more challenging than cocoercive problems, so this is significant progress. The given convergence rates are also the new state-of-the-art, reducing the logarithmic order by one.

Although the idea that increasing the batch size is in general beneficial for convergence was widespread, the attempt to actually design a schedule for the batch sizes was impressive to me.
The concept of scheduling the oracle queries extends to the approximations of the resolvents, and it being actually beneficial enough to provide convergence guarantees for monotone problems is also interesting.

Critical weaknesses

As the authors acknowledge (at around lines 184--185), the key ingredients for the analyses seem to be already existent in the prior work. The basic idea of increasing the batch size to get (improved) convergence is also a well known thing, and is not new in root-finding problems (e.g., Lee & Kim, 2021).

There is also a mismatch between theoretical analyses and the results from the numerical experiments. Methods with a theoretically worse guarantee seem to converge faster, and faster convergence only emerges when a variant of the proposed method (whose convergence is not guaranteed) is considered.
To me, scheduling the oracle queries is the crux of this work, but the method outperforming others only when that feature is discarded makes me confused about what the main takeaway is then.

Questions for authors
  1. As mentioned in the paper, the known convergence rate of RAIN is a logarithmic order of magnitude worse than the rate for stochastic dual-OHM established by you, but RAIN only requires the full operator FF to be monotone and Lipschitz. Wouldn't it be possible that the faster convergence rate is thanks to working with a stronger set of assumptions?

  2. Can you further elaborate, if possible with some intuition about why this is the case, on the discrepancy between the theoretical analyses and the numerical experiments? Is there a theoretical justification for using the "practical version"?

  3. Can you further clarify which parts of the tools used in the theoretical analysis are novel? As far as I am concerned, as aforementioned, the main ingredients can be found in the existing work (Yoon & Loizou, 2026), and I think the basic idea that getting a more accurate estimate of the operator gets more and more important as we get to the later stage of the training is commonly known, as reflected in strategies such as increasing the batch size as training progresses or accumulating past queries in a register in variance reduction techniques. This also raises the question of whether the insight mentioned in lines 186--187 is actually novel.

  4. A minor note: I think there is a typo in line 318, as the 11-strongly monotone operator should be z↦z+...z \mapsto z + ... instead of z↦I+...z \mapsto I + ....

4 comments

We thank the reviewer for the careful review and for recognizing the significance of the theoretical progress that we make over the prior work. The reviewer’s constructive comments identify several points of clarifications that help improve the presentation of the paper. Below, we provide responses to those points.

Weaknesses

The basic idea of increasing the batch size to get (improved) convergence is also a well known thing, and is not new in root-finding problems.

We agree, and we do not claim that varying batch sizes or allocating more samples to more influential error terms is new by itself. Our contribution in Section 2 is to identify the uneven error weight distribution specific to the tight proof of Dual-OHM, and exploit that to show that batch allocation is sufficient for closing the polynomial gap that existed in Yoon & Loizou (2026) for the cocoercive case. We would like to also highlight that the batch sizes BkB_k have to grow linearly in the number of iterations kk in stochastic anchor-based algorithm analysis from Lee & Kim (2021), while in our Dual-OHM analysis, we use BkB_k proportional to log⁡NN−k\frac{\log N}{N-k}, and in particular the largest batch size is only O(log⁡N)\mathcal{O}(\log N). To the best of our knowledge, this is a novel batch schedule that has not existed in the literature, and this is what makes Dual-OHM more advantageous over Halpern-type methods for under stochasticity. We believe that this provides a sufficient technical novelty, and we have further clarified this point in the revision.

There is also a mismatch between theoretical analyses and the results from the numerical experiments. … To me, scheduling the oracle queries is the crux of this work, but the method outperforming others only when that feature is discarded makes me confused about what the main takeaway is then.

The practical variant retains the batch-allocation profile in (16). It changes only the number of descent steps used to approximate the resolvent of each sample operator. Thus, the scheduling mechanism of Section 2 is still present. Please also note that in the cocoercive operator experiment, no resolvent approximation is needed, and the plot labeled as S-Dual-OHM (scheduled) in Figure 1(a) directly shows the benefit of our proposed algorithm, exactly as in the theory.

In the monotone operator experiment, we introduced the practical variant to emphasize that our proposed framework is empirically not sensitive to the accuracy of resolvent approximations, which was controlled conservatively in the theory, and also because reducing the oracle calls spent in the resolvent inner loops provided a visually distinguishable gain in the plots. For further context, the RAIN baseline itself is also a practical single-loop implementation that Chen & Luo (2024) used in their own experiments (see their Appendix E.1 and Algorithm 9), rather than the implementation as prescribed by the theorem.

Nevertheless, we understand that this choice has created the concern that the experiment was highlighting what was not fully supported by the theory. Therefore, in the revision, we re-run the experiment with the same Huber minimax operator construction but in a slightly different regime, and show that the algorithm prescribed by our theory (which we analyzed in Corollary 3.6) does provide performance gain over existing baselines. We no longer use the practical modification. Please see the updated Figure 1(b) and the paragraph on Experiment 2 on page 9.

Questions

  1. RAIN only requires the full operator FF to be monotone and Lipschitz. Wouldn't it be possible that the faster convergence rate is thanks to working with a stronger set of assumptions?

Yes, we did rely on slightly stronger assumptions to reduce the log⁡3\log^3 term in RAIN analysis to log⁡2\log^2. Nevertheless, the improved bound does not follow simply by imposing stronger assumptions. We do not see a direct way to replace the stochastic term with cubic logarithm in the established RAIN complexity by a squared logarithm merely by adding our assumptions.

Whether a squared-logarithm bound is achievable under only monotonicity and Lipschitzness of FF is an interesting open question. We suspect that a method based on dual-anchor mechanism or similar ideas may attain it, but this would require a novel insight beyond our results.

  1. Can you further elaborate ... on the discrepancy between the theoretical analyses and the numerical experiments? Is there a theoretical justification for using the “practical version”?

Please see our response to the second weakness. We believe that our revised experiment now more clearly highlights the benefit of the dual-anchor acceleration in stochastic settings while resolving this question/concern.

  1. Can you further clarify which parts of the tools used in the theoretical analysis are novel? ... This also raises the question of whether the insight mentioned in lines 186–187 is actually novel.

The precise distinction is described in our response to the first weakness. Also, in the revision, we clarify that we are not claiming that the idea of weighing noise terms from different iterations differently is new by itself, but we are new in observing that such an approach is effective for S-Dual-OHM.

  1. I think there is a typo in line 318, as the 1-strongly monotone operator should be z↦z+⋯z\mapsto z+\cdots instead of z↦I+⋯z\mapsto I+\cdots. Thank you for catching this. We have corrected it in the revision.

We hope the above clarifications and updates to the paper resolve the reviewer’s concerns about novelty and experiments, and if that is the case, we kindly ask for your continued support. We will be happy to answer any additional concerns or points of discussion.

Thank you for the rebuttal. The updates experiments are interesting but also raises some questions:

  1. Comparing to the initial submission, it seems like the plots for the Huber experiments are changed significantly for almost every methods tested, can you briefly explain what changed?
  2. In the Huber experiments, the plots for SEG and RAIN are near-identical; is this expected, and if so, can the authors provide some explanation on why that would be the case?
  3. Out of pure curiosity, scheduled S-Dual-OHM behave as if it plateaued for quite a long time in the early stages, and suddenly shows a sharp decrease in the loss; do the authors have a intuition on why such a behavior appears?

We thank the reviewer for the thoughtful questions. We are happy to provide explanation as below.

  1. Compared to the initial submission, it seems like the plots for the Huber experiments were changed significantly for almost every method tested, can you briefly explain what changed?

In terms of the experimental settings, the important changes are that we reduced the problem dimension from 1024 to 128, increased the radius of the quadratic part of the Huber function ν\nu from 5×10−55\times 10^{-5} to 5×10−45\times 10^{-4}, slightly reduced the value of σ\sigma, and increased the oracle budget from 2×1052\times 10^5 to 5×1055\times 10^5.

All these changes were applied to provide each algorithm more oracle budget to escape the performance plateau by letting each coordinate enter [−ν,ν][-\nu, \nu]. Note that we use a minimax objective involving a Huber loss, and the Huber derivative cν(t)c_\nu (t) is constant when ∣t∣>ν|t| > \nu. In the original experiment, for all algorithms except for the practical variant of scheduled S-Dual-OHM, the trajectories were coordinatewisely trapped within the region ∣t∣>ν|t| > \nu and displayed very similar operator norm values.

In the revision, we changed the parameters so that the steady convergence phase in ∣t∣≤ν|t| \le \nu can be reached and captured within the plot even without making the practical modification. In the new plot, all algorithms display significantly different plots from before because they mostly attained ∣t∣≤ν|t| \le \nu in each coordinate, and the qualitative distinction between algorithms became more clearly visible.

  1. In the Huber experiments, the plots for SEG and RAIN are near-identical; is this expected, and if so, can the authors provide some explanation on why that would be the case?

Thank you for your careful look. This is not immediately expected from the problem and algorithm design. However, the overlap coincidentally occurred because the tuning of both methods eventually selected the same batch-size B=4B=4 and step-size η=0.008\eta=0.008. Single-loop RAIN is different from SEG as it additionally applies the anchor term rk(v)=βk(v−xˉk)r_k (v) = \beta_k(v-\bar x_k) (after simplification), where the anchoring coefficient is βk=0.003(e15k/T−1)/(e15−1)\beta_k=0.003(e^{15k/T}-1)/(e^{15}-1). Now, because the total number of extragradient updates T=⌊Q/(2B)⌋T=\lfloor Q/(2B)\rfloor is 6250062500 with Q=500000Q=500000 and B=4B=4, βk\beta_k was less than 1.66×10−61.66\times10^{-6} halfway through the run and went close to 0.0030.003 near the end. Furthermore, both algorithms used the same random seeds, so the curves were almost identical, especially in the earlier iterations. There was numerical difference of 0.10.1\\% in the end, with the values of ∣F(xk)∣\\|\mathbb{F}(x_k)\\| being 9.017×10−49.017\times10^{-4} for SEG and 9.008×10−49.008\times10^{-4} for RAIN, but the difference is visually indistinguishable in the figure.

  1. Out of pure curiosity, scheduled S-Dual-OHM behave as if it plateaued for quite a long time in the early stages, and suddenly shows a sharp decrease in the loss; do the authors have an intuition on why such a behavior appears?

This is a deeper question. It has been observed in earlier works that even in the deterministic setting, Dual-OHM applied to deliberately designed worst-case operators typically tends to make limited progress in early iterations and sharp progress within the final, relatively few iterations (e.g., [1, Figure 2a] and [2, Figure 7a]). However, a clear theoretical explanation of this phenomenon is not known, and seems to be an open research question.

Specifically in the case of our experiments, the batch-size BkB_k for S-Dual-OHM starts at 11 and increases up to 31293129. Hence, in the earlier iterations, the stochastic noise is dominant and keeps coordinates within the Huber-saturated region ∣t∣>ν|t| > \nu, partially accounting for the “plateaued” phase. Later, as the algorithm’s trajectory enters the quadratic region ∣t∣≤ν|t| \le \nu and larger batches are used to reduce the effect of noise, the progress becomes steadier.

[1] Yoon et al. Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique. ICML, 2024.

[2] Yoon and Grimmer. A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms. 2026.


We hope the above clarifications address the reviewer’s questions on the experiments. Once again, we thank the reviewer for their interest in our work and the thoughtful discussion.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response to reviewers

We thank the reviewers for their feedback and constructive suggestions. We are delighted that all reviewers provided uniformly positive assessments and recognized the significance of our theoretical results.

In the revision, we have added a new experiment for the root-finding setting with a monotone operator to address the comments of Reviewers S39e and QhVq. The experiment section now uses and compares only algorithms equipped with theoretical convergence guarantees, without including a practical variant. We have also clarified the scope of novelty in our batch-size allocation, as requested by Reviewer S39e.

We believe these changes, together with our responses to each reviewer below, resolve the concerns raised. We look forward to further discussion with the reviewers.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.