- 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 to the near-optimal through an optimized batch-size schedule. The approach is then extended to monotone Lipschitz operators using approximate stochastic resolvents, yielding a complexity of , with . The theoretical results are complemented by numerical experiments.
Critical strengths
-
Near-optimal complexity under cocoercivity: The paper improves the previous complexity of stochastic dual anchoring to through an optimized batch-size schedule within the existing S-DUAL-OHM framework.
-
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
-
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?
-
Can the authors establish convergence guarantees for the practical variant using only two inner iterations, which achieves the best experimental performance?
2 comments
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.
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
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.
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
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)) for i=1,…,n be sample logistic losses and suppose there is a linear constraint Ax=b. The Lagrangian of the regularized population loss would be f(x,y)=n1∑i=1nℓi(x)+2μ∣x∣2+y⊤(Ax−b), and uniform sampling of i yields the sample saddle operators F((x,y);i)=(∇ℓi(x)+μx+A⊤y,b−Ax) which are monotone and Lipschitz with parameter L=μ+4R2+∣A∣ where R=maxi=1,…,n∣ai∣. The stochastic noise is not additive as it depends on x, while the variance is globally bounded by R2 because ∣∇ℓi(x)∣≤∣ai∣≤R. Samples can be reused because the corresponding data indices can be retained, with which the component gradients can be reevaluated.
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.