Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers solving stochastic monotone inclusions with respect to a (continuous) operator $F$ under three setting:
1. $F$ is $\gamma$-cocoercive (implying $\frac{1}{\gamma}$-Lipschitz continuity and monotonicity)
2. $F$ is monotone and Lipschitz
3. $F$ satisfies a sharpness condition, which is weaker than strong monotonicity

The authors propose 3 variants of stochastic Halpern iterations that achieve improved stochastic oracle calls $O(1/\epsilon^3)$ for the first two settings and $O(1/\epsilon^2 \log(1 / \epsilon))$ under additional sharpness condition. 

strengths_and_weaknesses: The paper is written in a clear manner for the most part. The related work seems cover the relevant literature sufficiently. The algorithm and the settings are studied and the proof techniques are highlighted with possible challenging components. I would suggest to talk about the techniques in the high level in section 1.2 after formalizing the setting and set of assumptions. Moreover, Theorem 4.1 and 5.1 were presented in a somewhat hasty manner without sufficient discussions.

The authors highlight the connections and differences between monotone inclusions (MI) and monotone variational inequalities (VI), role of unbounded/bounded set for approximately solving each case, the classical Halpern iterations with its properties in relation to the problem setting considered. The authors also lay out the challenges pertaining to the stochastic setting and their algorithmic framework. 

While doing so, they motivate the algorithmic choices in conjunction with the main challenges in solving stochastic monotone inclusions with Halpern iteration. I find the high level explanations in Section 1.2 to be informative and helpful for following the main claims of the manuscript. The authors also build upon their main results by explaining the key properties of their variance reduction (VR) framework, and the respective variance bounds. Then, they consider a simple iterative scheme that uses a ``conceptual’’ estimator with target properties, which is later expanded to mini-batch setting and the final VR scheme. It helps the reader understand the main components of the convergence bound and the main difficulties of the analysis.

Given the results in the literature and the discussion about tightness of the bounds in Appendix A (which could be mathematically more rigorous for more concrete deductions), the VR framework proposed in Algorithms 1,2 and 3 provide interesting convergence results in terms of the dependence on target accuracy and variance. I find the results of Section 4 and 5 (Lipschitz monotone and Lipschitz monotone with sharpness condition, respectively) to be more interesting in general, but, to my knowledge, the results exhibit novelty to some extend in the literature. Moreover, Corollary 3.2 and Lemma 3.3 presents nice complementary results. Especially, Lemma 3.3 proves bounds on the norm of the difference of consecutive iterates, which might be of use for future work.

My main criticism is with respect to the parameter choices of the algorithms. Specifically, the requirement to know the initial distance to a solution, which is a rather restrictive assumption to make, and the need to fix the target accuracy ahead of time. The algorithms proposed need to know the variance of stochastic oracle, target accuracy and distance to the solution to set the number of iterations and the (adaptive) batch-size. Although the sample complexities achieved in the paper are important and propose good contributions, these algorithmic requirements, to my understanding, limit the impact.

questions: - Can you remove the need to know the distance to a solution and replace it with some proxy for this quantity?
- Can you comment on the requirement of $\lVert u_0 – u^\star \rVert$, $\epsilon$ and $\sigma$? Would it be possible to remove the dependence on any of them with a reasonably simple algorithm?
- Can the existing VR frameworks for VIs, such as [1, 5, 34], be extended for monotone inclusions in the setting you consider? These methods consider finite-sum-like structures, but could there be a way to extend their results in your opinion?

limitations: I would suggest the authors to comment on the need for $\lVert u_0 – u^\star \rVert$, $\epsilon$ and $\sigma$ in setting the parameters of the algorithms proposed. They are partially addressed in the main text, but I believe a more thorough discussion would be preferable.

To my knowledge, I do not suspect any potential negative societal impact of this work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes several stochastic Halpern iteration algorithms with recursive variance reduction for solving monotone inclusion problems such as robust regression and adversarial learning.
strengths_and_weaknesses: Strengths：
This paper proposes a stochastic Halpern iteration algorithm, which has O(1/\epsilon^{-3}) stochastic oracle complexity.

Under an additional sharpness assumption, the complexity of the proposed algorithm has a better stochastic complexity, O((1/\epsilon^{-2})log(1/\epsilon)).

Weaknesses：

The proposed algorithm uses both stochastic Halpern iteration and recursive variance reduction techniques, which are NOT new. Thus, the novelty of this paper is limited.

By using an additional sharpness assumption, the proposed algorithm can have a better convergence property. However, it is not clear whether the proposed algorithm converges faster than existing methods in practice.

The authors should report some numerical results to show the advantage of the proposed algorithm.
questions: 1. The proposed algorithm can have a better convergence property. However, it is not clear whether the proposed algorithm converges faster than existing methods in practice.

2. The authors should report some numerical results to show the advantage of the proposed algorithm.

3. What’s the advantage of the proposed algorithm against existing Halpern iteration algorithms?

4. There are several variance reduction techniques such as SVRG, SAGA and SARAH. Why the authors choose the variance reduction technique in SARAH?

5. The writing of this paper should be improved, for instance, “stochastic variants of these methods had not been considered prior to our work”.

limitations: 1. The proposed algorithm can have a better convergence property. However, it is not clear whether the proposed algorithm converges faster than existing methods in practice.

2. The authors should report some numerical results to show the advantage of the proposed algorithm.

3. What’s the advantage of the proposed algorithm against existing Halpern iteration algorithms?

4. There are several variance reduction techniques such as SVRG, SAGA and SARAH. Why the authors choose the variance reduction technique in SARAH?

5. The writing of this paper should be improved, for instance, “stochastic variants of these methods had not been considered prior to our work”.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The framework of Monotone variational inequalities capture several well-studied optimization problems, including convex minimization, saddle-point problems, and min-max optimization. 
This paper studies stochastic versions of monotone variational inequalities, and presents algorithms based on stochastic Halpern iteration. The paper shows that for Lipschitz-monotone *stochastic* variational inequalities, a two step version of Halpern iteration (which can be thought of as extending the extra-gradient method to variational inequalities) can find a solution that is within $\varepsilon$ of the optimal solution within $O(\varepsilon^{-4})$ iterations. Combining with variance reduction, the paper shows that the iteration count can be improved to  $O(\varepsilon^{-3})$.
Under stronger sharpness assumptions on the operator (this can be thought of as the assumption that the operator is "strongly convex" around the solution, not necessarily everywhere else), the paper establishes that a suitably restarted version can further improve the iteration complexity to $\tilde{O}(\varepsilon^{-2})$.
The paper further establishes, via reductions from stochastic convex minimization, that these rates are optimal in $\varepsilon$ up to logarithmic factors.

Edit (post-rebuttal): The authors clarified that it is more accurate to identify their contributions as combining Halpern iteration with stochastic variance reduction methods to achieve near-optimal guarantees in statistical settings.
strengths_and_weaknesses: **Strengths**:
+ Several important recent applications in machine learning, e.g. GANs, adversarial learning, require solution concepts that cannot be captured by minimizing a single variable function. A more powerful framework of min-max optimization captures the solution concepts proposed in these settings. Variational inequalities captures min-max optimization and hence algorithms for Variational inequalities have received renewed attention recently.
+ The stochastic version of the VI problem studied in this paper is very natural given that the operator in most machine learning applications are stochastic in nature. This paper seems to establish (to my knowledge), the first upper bounds in the stochastic setting. 
+ The reductions from stochastic convex minimization presented in the paper show that the existing lower bounds for stochastic convex minimization imply that the rates achieved in this paper are near-optimal in the most-well studied Lipschitz monotone setting.

**Weakness**:
- The primary weakness of the paper in my view is that the technical novelty in the algorithms is limited. The main algorithm in the Lipschitz-monotone setting is based on combining the 2-step Halpern iteration studied in [45] and the proof is based on the same potential function, combined with the variance reduced estimator PAGE from [26].

[26] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. arXiv preprint arXiv:2008.10898, 2020.
[45] Quoc Tran-Dinh and Yang Luo. Halpern-type accelerated and splitting algorithms for monotone inclusions. arXiv preprint arXiv:2110.08150, 2021.
questions: The authors mention in the abstract that the $O(\varepsilon^{-4})$ rate achievable by combining stochastic Halpern iteration with mini-batch estimates is "current state of the art", but I don't see that result being directly attributed to a reference. The only mention of this result seems to be in line 148, attributed to [12]
Q1. Was this result known for stochastic monotone-lipschitz VIs for a computable iterate? "Best iterate" results are less interesting since it is not feasible to compute the best iterate.
Q2. Was this result known for the stochastic mini-batch Halpern iteration?
limitations: In my view, this is a strong work that establishes near-tight bounds for an important problem, and I don't see any serious limitations. It would be interesting to extend these ideas to a practical setting, but that is beyond the scope of this work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The work focuses on solving stochastic monotone inclusions problems. where the information on the problem is available through the calls of unbiased stochastic oracle with bounded variance. Moreover, stochastic realizations are assumed to be Lipschitz-continuous in expectation. In particualr, the authors study the convergence of Halpern iterations with stochastic unbiased estimator and PAGE-like variance reduced estimator and derive new complexity bounds for the expected norm of the operator in 3 different cases: 1) when the target operator is cocoercive, 2) monotone and Lipschitz, and 3) $\mu$-sharp and Lipschitz. The derived upper bounds for Halpern iterations with PAGE-like estimator are near-optimal in $\epsilon$ for the second and the third cases.
strengths_and_weaknesses: ## Strengths
1. **Clarity.** The paper is clearly written. The discussion of the related work is detailed enough to place the work in the literature properly.
2. **Guarantees for the last iterate.** In contrast to the majority of existing results for solving stochastic variational inequalities/monotone inclusions, the results of this work are derived for the last iterate, which is usually more challenging than obtaining results for the averaged or the best iterate.

## Weaknesses
1. **Large batchsizes.** The derived results require to use $\Theta(1/\epsilon^2)$ batchsizes at each iteration on average. These batchsizes are very large and, therefore, cannot be used in the majority of practical tasks. Moreover, in the analysis, under such batchsizes the stochasticity almost vanishes : as Corollary 2.2 states $\mathbb{E}\|\tilde F(u_k) - F(u_k)\|^2 \leq \frac{\epsilon^2}{k}$ implying that the method is almost deterministic. The analysis of such method reduces to the analysis of deterimistic method with bounded additive error (in expectation). All these facts dramatically limit the significance of the contributions.
2. **No empirical evaluation.** The paper proposes a new method, but does not studies its behavior in numerical experiments. In particular, given the limitations of the analysis, it would be interesting to study the impact of the batchsize on the convergence of Halpern-PAGE and Halpern-SGD at least in the experiments. Moreover, it would be also important to validate the importance of using PAGE estimator in comparison to SGD and the importance of using Halpern iterations in the stochastic settings.
questions: 1. It might be hard for some non-expert readers to understand Section 1.2 before reading the technical details from the further sections. I suggest to move this discussion further in the paper.
2. Line 247, "... with probability at least $1-\epsilon$, both $\|F(u_k)\|$ and $\| \tilde{F} \|$ are $O(\epsilon)$ in expectation": this sentence is unclear to me. Could you please explain this formally?
3. Line 278: The upper bound for $\mathbb{E}\|F(u_i)\|$ does not give an upper bound for $\mathbb{E}\|F(u_i)\|^2$, since $(\mathbb{E}\|F(u_i)\|)^2 \leq \mathbb{E}\|F(u_i)\|^2$. Nevertheless, the proof can be easily fixed if one assumes a proper upper bound on $\mathbb{E}\|F(u_i)\|^2$ in (i). Moreover, the resulting upper bound from line 278 should have $\epsilon^2$-term as well.
4. Line 282: one should point out that the number of oracle call is given in expectation.
5. Theorem 5.1: the resulting upper bound has a term $O(\frac{L^3}{\mu^3\epsilon^3})$, which is typically extremely large, since $L/\mu$ is large. For such problems, one can simply apply SGDA and get better rate (in terms of the dependence on $\mu$ and $L$), see [28] and also Beznosikov et al. "Stochastic gradient descent-ascent: Unified theory and new efficient methods." arXiv preprint arXiv:2202.07262 (2022). Indeed, these assumptions imply star-cocoercivity, which is sufficient to derive $O(1/\mu^2 \varepsilon^2)$ rate in this settings (see Beznosikov et al. (2022)).
6. What is the main challenge in the analysis? If I am not mistaken, in view of Corollary 2.2 everything reduces to the analysis of deterministic Halpern iterations with bounded additive error in the operator values. Analyzing optimization methods with bounded additive error is usually relatively straightforward.
limitations: There are no potential negative social impact: the work is purely theoretical.
review_title: null

Meta-review: metareview: Reviewers appreciated the technical difficulties and novel theoretical results established in this work and recommend acceptance.
confidence: Certain
Decision: Accept