Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions
Authors: Xufeng Cai
Chaobing Song
Cristóbal A Guzmán
Jelena Diakonikolas
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic
monotone inclusion
Halpern iteration
last iterate convergence
variance reduction
min-max optimization

Abstract: We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel variants of stochastic Halpern iteration with recursive variance reduction. In the cocoercive---and more generally Lipschitz-monotone---setup, our algorithm attains $\epsilon$ norm of the operator with $\mathcal{O}(\frac{1}{\epsilon^3})$ stochastic operator evaluations, which significantly improves over state of the art $\mathcal{O}(\frac{1}{\epsilon^4})$ stochastic operator evaluations required for existing monotone inclusion solvers applied to the same problem classes. We further show how to couple one of the proposed variants of stochastic Halpern iteration with a scheduled restart scheme to solve stochastic monotone inclusion problems with ${\mathcal{O}}(\frac{\log(1/\epsilon)}{\epsilon^2})$ stochastic operator evaluations under additional sharpness or strong monotonicity assumptions. 

Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions
Xufeng Cai
Chaobing Song
Department of Computer Sciences University of Wisconsin-Maddisnn
Department of Computer Sciences
University of Wisconsin-Madisen
xca 74 @ sc edu
songcbl g0 com
Cristóbal Guzmán
Jelena Diakonikolas
Institute for Mathematical and Computational Eng. Facultad de Matemáticas and Escuela de Ingeniería Pontificia Universidad Católica de Chile
Department of Computer Sciences University of Wisconsin-Madison
jelena@cs wisc.edi
erguzmanp @mat uc
Abstract
We study stochastic monotone inclusion problems, which widely appear in ma- chine learning applications, including robust regression and adversarial learning- We propose novel variants of stochastic Halpern iteration with recursive variance reduction. In the cocoereive-and more generally Lipschiz--monotone- algorithm attains norm of the operator with O stochastic operator evalua- tions, which significantly improves over state of the art ( stochastic operator evaluations required for existing monotone inclusion solvers applied to the same problem classes. We further show how couple one of the proposed variants of stochastic Halpern iteration with a scheduled restart scheme to solve stochastic monotone inclusion problems with O log ((lo stochastic operator evaluations under additional sharpness or strong monotonicity assumptions.
our
Introduction
Recent trends in machine learning (ML) involve the study of models whose solutions do not reduce to optimization but rather to equilibrium conditions. Standard examples include generative adversarial networks, adversarially robust training of MI. models, and training of MI. models under notions of fairness. turns out that several of these equilibrium conditions (including, but not limited to, first-order stationary points, saddle- saddle-points, and Nash equilibria of minimax games) can be cast as solutions to a monotone inclusion problem, which is defined as the problem of computing zero of (maximal) monotone operator F _ + nd (see MI) for a formal definition). In the context of min-max optimization problems, monotone inclusion reduces to a stationarity condition, which for unconstrained problems boils down to finding a point with small gradient norm.
Of particular interest to machine learning are stochastic versions of these problems, in which the operator F' is not readily available, but can only be accessed through stochastic oracle F. Such are the settings mentioned above, where the definitions of equilibria involve expectations over continuous high-dimensional spaces. The corresponding problem, known as the stochastic monotone inclusion, has not been thoroughly studied, particularly in the context of its stochastic oracle complexity. Understanding stochastic oracle complexity of monotone inclusion in all standard settings with Lipschitz operators, from the algorithmic aspect, is the main motivation of this work.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Contributions
We study three main classes of stochastic monotone inclusion problems with Lipschitz operators, defined by the assumptions made about the operator itself: (i) cocoercive class, which is the most restricted class, but nevertheless fundamental for understanding monotone inclusion, as it relates to the problem of finding a fixed point of a nonexpansive (1-Lipschitz) operator; (ii) Lipschitz monotone class, which is perhaps the most basic class arising in the study of smooth convex-concavy min-man optimization problems; and (iii) Lipschitz monotone class with additional sharpness property of the operator. Sharpness is a widely studied property of optimization problems, often referred to as the "local error bound" condition, which is weaker than strong convexity and roughly corresponds to the problem landscape being curved outside of the solution set (see for a survey of classical results).
From an algorithmic standpoint, we consider variants of classical Halpern iteration [21], which was originally introduced for solving fixed point equations with nonexpansive operators. Variants of this iteration have recently been shown to lead to (near-)optimal first-order oracle complexity for all aforementioned standard problem classes in deterministic settings [12
| 53 However, to the best of our knowledge, stochastic variants of these methods have received very limited attention prior to our work. The only results we are aware of are for a two-step extragradient-like variant of Halpern iteration in negative comonotone Lipschitz settings [29] and which show that when variance of operator estimates is bounded by order- & in iteration k, the method attains operator norm e after (+)) iterations. However, 2 does not discuss how such variance control would be obtained. Simple mini-batching, as we show, only leads to (+4) stochastic oracle complexity.
We show that existing variants of the Halpern iteration 12 51
can be effectively combined with recursive variance reduction P2 to obtain ( stochastic oracle complexity in the cocoercive and
Lipschitz monotone setups. We then show that the complexity can be further reduced to O log(
under an additional sharpness assumption about the operator. The last bound is unimprovable in terms of the dependence on e, due to existing lower bounds, as we argue for completeness in Appendix A
To the best of our knowledge, our work is the first to use variance reduction reduce stochastic oracle complexity of monotone inclusion (small gradient norm in min-max optimization settings), and the attained bounds are the best achieved to date for direct methods.
1.2 Techniques
Inspired by the potential function originally used by 12 and later used either in the same or slightly modified form by 13 29 53 we adapt this potential function based argument to account for stochastic error terms arising due to the stochastic oracle access to the operator. We first show that in the cocoercive minibatch setting, this argument only leads (++) stochastic oracle complexity, and it is unclear how to improve it directly, as the analysis appears tight. We then combine the
cocoercive variant of Halpern iteration [2] with the PAGE estimator [32] to reduce the stochastic
oracle complexity to ( The same variance reduced estimator is also used in conjunction with
the two-step extrapolated variant of Halpern iteration introduced by [5T], as a direct application of Halpern iteration is not known to converge on the class of Lipschitz monotone operators.
While the basic ideas in our arguments are simple, their realization requires addressing major technical obstacles. First, the variance reduced estimator that we use 32) was originally devised for smooth nonconvex optimization problems, where was coupled with a stochastic variant of gradient descent. This is significant, because the proof relies on a descent lemma, which allows cancelling the error arising from the variance of the estimator by the "descent" part. Such an argument is not possible in our setting, as there is no objective function to descend on. Instead, our analysis relies an intricate inductive argument that ensures that the expected norm of the operator is bounded in each iteration, assuming suitable bound on the variance of the estimator. To obtain our desired result for the variance, we propose a data-dependent batch allocation in PAGE estimator B22 (see Corollary 2.2 which scales proportionally to the squared distance between successive iterates, similar to B We inductively argue that the squared distance between successive iterates arising in the batch size of the estimator reduces at rate in expectation. This allows to further certify that the estimators do not only remain accurate, but their variance decreases O /k), where k is the iteration count.
In the context of the potential function argument, unlike in the deterministic settings, we do not establish that the potential function is non- non-increasing, even in expectation. The stochastic error terms

---

that arise due to the stochastic nature of the operator evaluations are controlled by taking slightly smaller step sizes than in the vanilla methods from 12 5I. which allows us to "leak" negative quadratic terms that are further used in controlling the stochastic error. The argument for controlling the value of the potential function itself coupled with the inductive argument for ensuring that the expected operator norm remains bounded.
Finally, while applying a restarting strategy is standard under sharpness conditions [4 obtaining the claimed stochastic oracle complexity result of O log(z)) requires rather technical argument to bound the total number of stochastic queries to the operator.
1.3 Related work
Monotone inclusion and variational inequalities. Variational inequality problems were originally devised to deal with approximating equilibria. Their systematic study was initiated by [50] The relationship between variational inequalitics and min- mix-max optimization was observed soon after [4
while of the earliest papers to study solving monotone inclusion generalization of variational
inequalities, convex and min-max optimization, and complementarity problems is 455 For a historical overview of this area and an extensive review of classical results, see
In the case of monotone operators, standard variants of variational inequality problems (see Section 2 and monotone inclusion are thuivalent-their solution sets coincide. This is consequence of the celebrated Minty Theorem 335. However, there is a major difference between these problems when it comes solving them to finite accuracy. In particular,
unbounded domains, approximating variational incqualities is meaningless, whereas monotone inclusion remains well-defined. This is most readily seen from the observation that mapping from min-max optimization, variational inequalities correspond to primal-dual gap guarantees, while monotone inclusion corresponds to guarantee in gradient norm. For simple bilinear function f(r y) xy which has the unique min-max solution at (z, y) (0, 0), the primal-dual gap is infinite for any point other than (0, O), while the gradient remains finite and good proxy for measuring quality of solution. Further, even on bounded domains or using restricted gap functions on unbounded domains as in e.g., 377, optimal oracle complexity guarantees for approximate monotone inclusion imply optimal complexity guarantees for approximately satisfied variational inequalities (see, e.g., [12). The opposite does not hold in general. In particular, in deterministic settings, standard algorithms such as the celebrated
extragradient (28, [6). dual extrapolation [37], or Popov's method [42] that have the optimal oracle
complexity (
) for approximating variational inequalities are suboptimal for monotone inclusion
and attain oracle complexity of the order ( + IK
Halpern iteration. Halpern iteration is a classical fixed point iteration originally introduced by 221, and studied extensively in terms of both its asymptotic and non-asymptotic convergence guarantees [8 26 27
52 The first tight nonasymptotic convergence rate guarantee of 1/t was obtained in 33 This rate was also matched by 2
B1
33
The usefulness of Halpern iteration for solving monotone inclusion problems was first observed by [12 who showed that its variants can be used to obtain near-optimal oracle complexity results for all standard classes of monotone inclusion problems with Lipschitz operators also studied in this work. The near-tightness (up to poly-logarithmic factors) of the results from 1 was certified using
lower bound reductions from min-max optimization lower bounds introduced by [3 These lower bounds were made tight for the cocoercive setup in
The generalization of Halpern iteration from the cocoercive to Lipschitz monotone setup in 12 utilized approximating what is known as the resolvent operator, which led to double-loop algorithm and an additional log(1/e introduced a two-step variant of Halpern iteration, inspired by the extragradient method of (28 The
(1/c) /c) in the resulting complexity. This log factor was shaved off in [533] who
results of [2] 5
were further extended to other classes of Lipschitz operators by 229 51. Except
for 24 which considered controlled variance as discussed above, all of the existing results only targeted deterministic settings.
'Interestingly the algorithm proposed by (25 for cocoercive inclusion coincides with the Halpern iteration for related nonexpansive operator (see 9 Proposition 4.3))
3

---

Stochastic seftings and variance reduction. Vanilla stochastic gradient methods have constant variance of stochastic gradients, which creates bottleneck the convergence rate. To improve the convergence rate, in the past decade, powerful variance reduction techniques have been proposed.
For strongly convex finite-sum problems, SAG
48 which used biased stochastic estimator of the full gradient, was the first stochastic gradient method with linear convergence rate. 244 and [ improved [48 by proposing unbiased estimators of SVRG-type and SAGA-type. respectively.
Such unbiased estimators were further combined with Nesterov acceleration P
T or applied For nonconvex stochastic (infinite-sun) summ
to nonconvex finite-sumie caatte-sum/iiiiitt-sstite
problems
30
problems, SARAH [E and SPIDER [T8 54
estimators were proposed to attain the optimal oracle complexity of (11e²)) for finding an e-approximate stationary point. Both estimators are referred to as "recursive" variance reduction estimators, as they are biased when taking expectation w.r.t. current randomness but unbiased w.r.t. the randomness in history. PAGE (32) and STORM IC significantly simplified SARAH and SPIDER in terms of reducing the number of loops and avoiding large minibatches, respectively. f further extended this line of work by incorporating second-order information and dynamic batch sizes.
555
In the setting of min-max optimization and variational inequalities/moonooon inclusion, variance reduction has primarily been used for approximating variational inequalities, corresponding to the primal-dual gap in min-max optimization; see. for example 3 + 30 Under strong
monotonicity (or sharpness in the case of (44), such results generalize to monotone inclusion;
however, to the best of our knowledge, there have been no results that address monotone inclusion under the weaker assumptions considered in this work. In the context of monotone inclusion with Lipschitz operators, the tightest complexity result that we are aware of O()),, due to [4], and applies to more general class of structured non-monotone Lipschitz operators, for the best iterate. The same oracle complexity can be deduced for the last iterate of a two-step variant of Halpern from 22 Theorem 6.11. using mini-batching. All the results in our work are also for the last iterate.
2
Preliminaries
We consider a real d-dimensional normed space (IR'd |I-II), where ||-|| induced by an inner product associated with the space, i.e., ||-I| / -). Let C Rd be closed and convex; in the unconstrained case, U = _dd When is bounded, = maxu,vell |u v|l denotes its diameter.
Classes of monotone operators. We say that an operator F Fd Rd is
1. monotone, if Vu, v E R (F(u)- - F(v), u v) 2 0.
L-Lipschitz continuous for some L > 0, Vu, v Idd [F(u)) F(v)ll S L || -uwuu |vll-
3. y-cocoercive for some 7 > 0, if Vu, E Rd (F(u) - F(v). uvv. v) [[()) - -F(
4. j--stronlyy monotone for some f 0, if Vu, E R4, (F(u) F(v), v) 2 / 11 v/²
Note that we can easily specialize these definitions to the set 24 by restricting u, v to be from U.
Throughout the paper, the minimum assumption that we make about an operator F is that it is monotone and Lipschitz. Observe that any --cocoercive operator monotone and 1 -ipschiit. The converse to this statement does not hold in general.
Monotone inclusion and variational incqualities. Monotone inclusion asks for u² such that
O E F(u") + +'x(("), where by is the indicator function of the set 21 and (-)(-) denotes the subdifferential of hu-
(MI)
If F is continuous and monotone, the solution set to MI) is the same the solution set of the Stampacchia Variational Inequality (SVT) problem, which asks for u² E 2/ such that
(Vu 2 {F (u²), -- u²) 2 0.
(SVT)
Further, when monotone, the solution set of (VVI) is equivalent to the solution set of the Minty Variational Inequality (MVI) problem consisting in finding u* such that
(Vu e 2)) (F(u), u² u) S 0.
(MVI)

---

We assume throughout the paper that solution to monotone inclusion MI exists, which implies that solutions to both (SVI) and (VI) exist as well. Existence of solutions follows from standard results and is guaranteed whenever e.g. 2/ is compact, or, if there exists a compact set set such that ld maps UI to itself, where Id is the identity map [7]. As remarked in the introduction, in unbounded setups is generally not possible
approximate (MVI) and (SVI). whereas approximating (MI) is quite natural: we only need to find u such that 0 E F(u) + ŌIu + B(c), where 0 denotes the zero vector and (ec) denotes the centered ball of radius c.
Stochastic access to the operator. We consider the stochastic setting for monotone inclusion problems. More specifically, we make the following assumptions for stochastic queries to F. These assumptions are made throughout the paper, without being explicitly invoked. Assumption (Unbiased samples with bounded variance). For each query point E U, we observe F(x, 2) where 2 P. is a random variable that satisfies the following assumptions:
Eg [xx, 2)] F(x) and [x 2) F(x) ||²] o²²
Assumption 2 (Multi-point oracle). We can query a set of points (xI...., xn) and receive
2(x,,
where Ps.
Assumption (Lipschitz in expectation). E. [=
[)v,=)]]]] 1.2 |1 v E..
Vu,
We note that complexity results of the paper will bound the total number queries made to this oracle. In particular, if multiple query points and/or multiple samples are used in single iteration, our complexity given by the sum of all those queries throughout iterations of the method. Also, Assumption is primary with parameter L, by which F is also L-Lipschitz using Jensen's 's incquality.
PAGE variance-reduced estimator. We now summarize a variant of the PAGE estimator, origi- nally developed for smooth nonconvex optimization by (22 adapted to our setting. In particular, given queries to F, we define the variance reduced estimator F F(uR) for k 2 1 by
S Ei=l g(t))
Li F(u 24 (K))
W. PE:
F(uR)=
(2.1)
F(ux-1) $3
SSy) Ei
(F(us, (000-F(uu--e F(u;-112(1))
W. p. 1 pk
where po 1, (k) iid.
P., and 5(M) and ((x) are the sample sizes at iteration Observe that Assumption 2 guaranteess that we can query F at u, and u using the same random seed. Our analysis will make use of conditional expectations, and to that end, we define natural filtration FR by F& == o ((F(s)))) namely Fx contains all the randomness that arises in the definitions of F(u,) for j S k. Following similar argument as in 32), we recursively bound the variance of the estimator F, as summarized in the following lemma. The proof is provided in Appendix B
zi
7 Lemma 2.1. Let F be monotone operator accessed via stochastic queries F, under Assumptions
3 Then, the variance of F defined by Eq. 2.1 satisfies the following recursive bound: for all ls 2 1,
E| F(us) F((u))
o2o² s(R)
+ + - pk) (E)EEE ((u
L
u1
U 113
((())
With the choices of Pk. inequality from Lemma 2.1
(k)
S specified in the following corollary and using induction with the we obtain the following bound on the variance.
Corollary 2.2. Given a target error 0, if for all k > 1, ps
3
(kk)
>
PLe
"8L [ u 12_ .hen TE] [(ue) F(u))] c.
3 Stochastic Halpern iteration for cocoercive operators
In this section, we consider the setting of -cccoercivee operators F. While cocoercivity is a strong assumption that implies that an operator is both Lipschitz and monotone (as discussed in Section
5

---

it is nevertheless the most basic setup for studying the Halpern iteration. In particular, while Halper iteration can be applied directly to the nonexpansive counterpart cocoercive operator F (i.e., to the linear transformation Id - I. F. where T, is an upper bound on the cocoercivity parameter of F), convergence does not seem possible to establish for the more general class of Lipschitz monotone operators. We begin this section by providing a generic proof of stochastic oracle complexity, which we then use to briefly illustrate how to obtain ((+)) oracle complexity with a simple minibatch stochastic estimator of F. We then show how to improve this bound to O ( by applying the proposed variant of the PAGE estimator from Eq. 22. to Halpern iteration.
The stochastic variant of Halpern iteration that we consider defined by
U++1 1o (1 (1-111+1)))) )6+1) [u
2 L&+1
F(uE));
(3.1)
where F' is stochastic (possibly biased) estimator of F. AR+1 O(2) ) is the step size, and L8+1 2 L is a parameter of the algorithm. Compared to the classical iteration U = A8+1 Up + (1 - (b+)))(u where T : Id + Rd is nonexpansive (I-Lipschitz) map [21] T is replaced by the mapping Id
Lx+11 F. which is stochastic and may not be nonexpansive (as the stochastic
estimate F' of F is not guaranteed to be cocoercive even when F is). Compared to the iteration variant considered by [12]. the access to the monotone operator is stochastic and we also take slightly larger (by a factor of 2) values of Lx+1 to bound the stochastic error terms.
Our argument for bounding the total number of stochastic queries to F is based on the use of the following potential function C₂ d [( + BN (F(u)), uj Un). where {Aa [A&h22 and {B& hB2 are positive and non non-decreasing sequences of real numbers, while the step size '2 is defined Bg by A A₂ +
Such potential function was previously used for the deterministic case of Halper
Observe that even though we make oracle queries to F", the potential function Cs and the final bound we obtain are terms of the true operator value F.
iteration in 12
Compared to the analysis of Halpern iteration in the deterministic case 12 3 our analysis for the stochastic case needs to account for the error terms caused by accessing F via stochastic queries and is based on an intricate inductive argument. A generic bound on iteration complexity, under mild assumptions about the estimator F,, is summarized in Theorem 3.1 The proof is in Appendix C
Theorem 3.1. Given an arbitrary Ug E TRd. ssuppose that iterates un evolve according to Halpern iteration from Eq. 3.I.for k 2 1, where L 2T. and X E+I- Assume further that the stochastic
estimate F()) is unbiased for un and [B[] ((uo) - F(1 1 S. Given >> 0, if for all k 22 1, we have that F(un) - F(um)ll" S 4. then for all k 2 1,
((x)4( < Ao + A
(3.2)
where No 76L |luo - -u and A₁ = 4 As resuls, stochastic Halpern iteration frrationfrrm Eq. 3.1
returns a point un such that [(u))[ S 4e after at most N = 2AA = 0 Llluo-n') iterations.
We remark that the previous result states an iteration complexity bound under a rather high accuracy assumption for the operator estimators each iteration. In order to attain these accuracy requirements, we could either use a minibatch at every iteration, or use variance reduction. In what follows we explore both approaches. We further remark that we made no effort optimize the constants in the bound above, and thus the constants are likely improvable.
Finally, observe that due to the required low error for the estimates [[]]F(us)) ((,)) < T we can certify by Chebyshev bound that P[))F(u,)) F(u,))l 2 cl s L. In particular, after O iterations, if we have [ || < e (which holds in expectation). then [[x)) is also O(e) with probability at least stopping criterion can be based on the value of [(u)))l. which, unlike [[F(uu)]] can be efficiently evaluated.
This particularly important for practical implementations, where

---

3.1 Stochastic oracle complexity with a simple mini-batch estimate
direct consequence Theorem 3.1 that simple estimator F(us) St Disl F(us, 24 (x))) leads
to the overall ( (x)) oracle complexity, as stated below while the proof is deferred to Appendix C
Corollary 3.2. Under the assumptions of Theorem 3.1 if F(us)
3r E Flus, (K)) where
F(uR; 2 ) satisfies Assumption 1 and 2i"
(k) itd Pz. then setting Se-
o'(k21) for all l 2
e²
guarantees that [EI] S 4e after at most 0 " uu-u"ll"" queries F.
3.2 Improved oracle complexity via variance reduction
We now consider using the recursive variance reduction method from Eq. 2..1 obtain the variance bound required in Theorem 3.1 as summarized in Algorithm | Of course, in practice, || - u") is not known, and instead of running the algorithm for fixed number of iterations N, one could run for example, until reaching a point with |F(uu))] c.
Algorithm 1: Stochastic
(Halpern)
Input: Ug Rdd | ||, L, 0, a:
Initialize: Ao
76L [g -' N 2
88 F(uo)
5 Σi= F F(uo, ) 5:o
for k L:Noo do
u: x+I Up k-1 [uk-1 ((uR-1))
2 ((k) = _0
$2
8T.
m
Pk = K+I
p
Compute F(u)) based on Eq.
Return: uN
Notice that convergence is guaranteed by Theorem however it does not directly address the problem of the oracle complexity (as batch sizes depend on successive iterate distances). To resolve this issue, we first provide bound on ||uı ug-1 in Lemma 3.3 while the proof is deferred to Appendix C and make the appropriate parameter settings for the estimator from Eq. 2 is now possible to apply Theorem 3.1 to obtain the improved (1})) stochastic oracle complexity bound.
Lemma 3.3. Given an arbitrary initial point un E Rdd, let {ux]221 be the sequence of points produced by Algorithm
7
Assume further that ds = k+1 I = =L. all ls 2 0. Then,
1 [1)))
ifk 1,
U 14-111
<
41.2
21²
F ((uu-1)11= EtD 2(++1)2 k(k+1)=L2 [[,)) if 2 2.
(3.3)
1)(
Moreover, if for S S k 1, all of the following conditions hold (same as in Theo-
rem 3.1 (i) Bi] [(u))l S Ao + A2c, where Ao = 76L un u²ll and A1 = 4 4/3 (ii)
k. then Billux u 12] O | F(u)) - F(u.))l I &, and (iii) S Aa,
R2
Corollary 3.4. Given arbitrary us E Rd and 0, consider uy returned by Algorithm Then, B[][F(ux)]l] < 4e with expected O o² [ -uuuuuu ++ [n uu-"""l"" oracle queries F.
Proof. Let my be the number of stochastic queries made by the estimator from Eq. 2.1 in iteration k. Using Corollary 2.2 we have
E [m Fa-1] = Pk S( + 2(1 p1) Pk
80 Pic + +111 pk)]
11.
[
where the first equality holds because 5h is measurable w.r.t. Fk-1 and the only random choice that remains is the selection of the estimator in Eq. 2.I determined by probabilities pş and Ps-

---

Taking expectation with respect to all randomness on both sides, rearranging the terms, and using
the fact that [x| S x + for any I E IR, we obtain E[
8 16(1 Pa11-pa1..0
" 11-1 2.
Recalling that pk x+1 = O( and E[Ilu: u
12] O
No u
||*
by Lemma 3.3 it follows
k²
that [[ = ( 0 + - 12) As, by Theorem 3.1 the total number of iterations to attain 46
2²
norm of the operator expectation N 2Ae = 0 L/luo =='l and mg 5 0
_ the
total number of queries to F is [R[M E
E m&} = 0 0 mo || 1110 " "
We note in passing that the running time guarantee of this algorithm is of Las Vegas-type despite its iteration number being surely bounded by [2Am] O _.lluo="')) I),, the batch sizes (in particular
(/()) are random, and are not universally bounded.
We further argue that Algorithm D can be extended constrained settings by defining the operator mapping as in [12] and modifying the variance-reduced stochastic estimator accordingly based on the projection of F. We show that the newly defined operator mapping is also cocoercive while the variance of the modified estimator is bounded by the variance of F, so arguments from Theorem 3.1 and Corollary extend to this case. This modified estimator need not be unbiased (as neither is F); however, this is irrelevant to our analysis as it does not require unbiasedness. For completeness, a detailed extension to the constrained case is provided in Appendix C.2)
4 Monotone and Lipschitz setup
Throughout this section, we assume that F' is monotone and L-Lipschitz. While the previous section addresses the cocoercive setup using the classical version of Halpern iteration adapted to cocoercive operators, it is unclear how to directly generalize this result to the setting with monotone Lipschitz operators. In the deterministic setting, generalization to monotone Lipschitz operators can be achieved through the use of a resolvent operator (see (12)). However, such an approach incurs an additional (og(l factor in the iteration complexity coming from approximating the resolvent and it is further unclear how to generalize it to stochastic settings, as the properties of the stochastic estimate F of F do not readily translate into the same or similar properties for the resolvent of F. Instead of taking the approach based on the resolvent, we consider recently proposed two-step variant of Halpern iteration [5]], adapted here to the stochastic setting. The variant uses extrapolation and defined by
Vk == uo + (1 - A&.) us - m7F FVv-()
(4.1)
u == du (1 - Ax) uk- m). ((vx,
where A E 10. nh > O, and F is defined by 2. The resulting algorithm with a complete parameter setting is provided in Algorithm -
To analyze the convergence of the extrapolated Halpem variant from Eq.
the potential function 14- = Ag F (( + B& (F(ux), U2 - un) + + I.2] uu Vx-i prrvioossy used by [5]], where Ag, B& and cæ are positive parameters to be determined later. Observe that this is essentially the same potential function as Ck, corrected by the quadratic term cę |
4.1
In
V to account
for error terms appearing in the analysis of the two-step variant from Eq. the cocoercive setup, the potential function is not monotonically non-increasing, due to the error terms that arise due to the stochastic access to F. Bounding these error terms requires careful technical argument, and is the main technical contribution of this section. Due to space constraints, the complete technical argument is deferred to Appendix D while the main results are stated below. Theorem 4.1. Given an arbitrary initial point uo E Ra and target error e > O, assume that the iterates UN evolve according to Algorithm for to 2 1. Then, for all k 2 2,
Similarly as in
Ao
E | [( )1 2T.2 1m
VR-111? < (k 1k 22
2,
(4.2)
where Ag
4[L2 1)]l uo 1'
and A 5(1+Mmoo) My²
In particular, [[[[F(ux)]
2L2 |uy - vN s 2 ((2) after at most N Voo
o 00 ("luo-"')) iterations.
VATe
The total number of oracle queries to F is O 2 u u 1
in expectation.
8

---

Algorithm 2: Extrapolated Stochastic Halpern (E-Halpern)
Input: ug E RR 1100 u²I < 70 - 3/3L²
L, 6 > 0, 0;
Initialize: V-1 = uo, 5(-11 = - = [ [ 9--6 .
1- Mid
Set Ao 4 1000111111000 1) -u A1 = 5(1+Mmo)
N = vo
1;
9²
Way²
VaIe
F(v-1) = 5.-
Lisl 21 1111)) where zi
(-1) iid
Pai
for k = 1 . do
Vk-1 k+I Uo +
1
k+1 U2 1 7h
k
2v==22)
Pa-1 minn 2 1), S 1k)
S0²
S2
(k-1)
Vu vu-2
Pe-
Ph-
Compute F(v based on Eq.
Ug
k+1 k-1 11-11 T
1
k
F
(Vk-1):
(1- (k12)2 My ()++1)²
7j
(1- m/ ")a(k-2
7k-1
Return: UN
5
Faster convergence under sharpness condition
We now show that by restarting Algorithm we can achieve the O ( log 2) oracle complexity under a milder than strong monotonicity j-sharpness condition: for all u E U, (F(u) F(u*), u-="))
||u u 112. The scheme is summarized in Algorithm and the proof is deferred to Appendix
Algorithm 3: Restarted Extrapolated Stochastic Sallpern-Shany (Restarted E- H-llperm)
Input: V-1 = Up E Rd
U1
u²
||,
1o0 I 3/3L' L, 14, c > 0,
no (1
N = log [Vollu--u ) (vellu-u''1)]
Initialize: M = 2.2 7
1-M
for k = 1: N do
Call Algorithm
with initialization v
ub (R)
u Ck pe M
5 Myyo))))) and
s( -(-1) S(0)
18021 1. for K
[ / I
iterations, and return uy:
Return:
Theorem 5.1. Given L-Lipschitz and p-sharp F and the precision parameter e, Algorithm uy with Bll[uy- u² u²1]²] < e² as well as B [[][P(un)]]) < L²22 after N = O log
outputs
Uo Ma-uul
iterations with most of o² (x++ (ollL))log(llaa log([luo uu" +2 uu- mu-="'l²) queries to F in expectation.
332
6 Numerical experiments and discussion
We now illustrate the empirical performance of stochastic Halpern iteration on robust least square problems. Specifically, given data matrix A RRxd and noisy observation vector b E R² subject to bounded deterministic perturbation 8 with ||o]| S p. robust least square (RLS) min- imizes the worst-case residue as minxeR* max5:jjā Sp || yl with = b + 16 We consider solving MI induced from RLS with Lagrangian relaxation where u = (x,y)" and
-Vy,,,))),x,,,,,,,,,,x Lx,,xxx for L2 y). 2n ||Ax y1l 2n - bll We use a real-world superconductivity dataset [22] from UCI Machine Learning Repository [15] for our experiment, which of size 21263 x 81. To ensure the problem is concave in y, we need that A > 1; in the experiments, we set À = 1.5. For the experiment, we compare Halpern, E-Halpern, and Restarted E-HHappern algorithms with gradient descent-ascent (GDA), extragradient (EG) 2X], and Popov's 's method 12 in stochastic settings. Even though our theoretical results for Restarted
F(u) = (V y),

---

10
10
GDA
Single Sample
Minrbanch
Pepoy
PAGE
Halpor
10
Hallpp
10
Redarted E-Halomn
||
10-2
10-2
5000
10000 15000 20000 25000 30000
5000 10000 15000 20000 25000 30000
#grad
#grad
(a) Comparison on superconductivity dataset.
(b) E-Halpern with different stochastic estimators.
Figure Empirical comparison min- max algorithms on the robust least squares problem.
E- E-Halper require scheduled restarts based on known problem parameters, in the implementation. to avoid complicated parameter tuning and illustrate empirical performance, we restart E-Halpern whenever the norm of stochastic estimator F used in E-Halpern halves. All Halpern variants are implemented with PAGE estimator considered our paper, all other algorithms are implemented using minibatches. Additionally, we compare E- E-Halpern with the PAGE estimator against E- E-Halpern with single-sample and mini-batch estimators.
We plot the (empirical) operator norm [[]( against the number of stochastic operator evaluations. Note that evaluations of [[F(u)) are only used for plotting but not for running any of the algorithms. We use the same random initialization and tune the batch sizes and step sizes (to the values achieving fastest convergence under noise) for each method by grid search. We use constant batch sizes and constant step sizes for GDA, EG, and Popov. We also choose the batch sizes of PAGE estimator to ensure [|[ ((u,) F(uu))l I O ( which handles error accumulation 29 and early stagnation of stochastic Halpern iteration. We implement all the algorithms in Python and run each algorithm using one CPU core on a macOS machine with Intel 2.3GHz Dual Core i5 Processor and 8GB RAM
We observe that (i) Figure I(a) both Halpern and E-Halpern exhibit faster convergence to approxi- mate stationary points (with much smaller gradient norm after same number of gradient evaluations) than other algorithms, and restarting E-Halpern provides additional speedup, validating our theoretical insights; (ii) in Figure [[b]
E-Halpern with PAGE estimator displays faster convergence compared to other two estimators, agreement with our theoretical analysis.
7 Conclusion
We introduced stochastic variance reduced variants of Halpern iteration for addressing monotone inclusion problems. Our work addresses all standard classes Lipschitz monotone problems and achieves improved stochastic oracle complexity guarantees, all for the last iterate. Subsequent to this work, 7 obtained near-optimal bounds for the cases considered in this work, by reducing the Lipschitz monotone case to the Lipschitz strongly monotone using regularization. It is an open question to obtain such near-optimal bounds with direct method, without the use of regularization.
Acknowledgements
XC and CS were supported in part by the NSF grant 2023239, CG's research was partially supported by INRIA Associate Teams project, FONDECYT 1210362 grant, ANID Anillo ACT210003 grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID. Part of this work was done while CG was at the University of Twente. JD was supported by the NSF grant 2007757, by the and by the Wisconsin Alumni
Office of Naval Research under contract number 100014-22-1-220 Research Foundation. Part of this work was done while JD and CS were visiting Simons Institute for the Theory of Computing.
Code is available at httttp//ggihuub.oo///pp/rrr////p
10

---

References
[1] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Proc. COLT 2022.
[2] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):8194-82) 8244, 2017.
[3] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridha- ran. Second-order information in non-convex stochastic optimization: Power and limitations. In Proc. COLT 2020.
[4] Amir Beck. First-order methods in optimization, volume 25, SIAM, 2017.
[5] Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. In Proc. NeurlPS' 19, 2019.
[6] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien, Reducing noise in GAN training with variance reduced extragradient. In Proc. NeurlPS 19, 2019.
[7] Lesi Chen and Luo Luo. Npar-optimal algorithms for making the gradient small stochastic minimax optimization. arXiv preprint arXiv:2208.055) 2022.
[8] Horatiu Cheval, UIrich Kohlenbach, and Laurentiu Leustean. On modified Halpern and Tikhonoy-Mann iterations. arXiv preprint arXiv:2203. 1003, 2022.
[9] Juan Pablo Contreras and Roberto Cominetti. Optimal error bounds for nonexpansive fixed-point iterations in normed spaces. arXiv preprint, arXiv:2 10969, 2021.
[10] Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex SGD. In Proc. NeurlPS' 19, 2019.
[11] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Proc. NeurlPS /4, 2014.
[12] Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. In Proc. COLT'20, 2020.
[13] Jelena Diakonikolas and Puqian Wang. Potential funetion-based framework for minimizing gradients in convex and min-max optimization. SIAM Journal Optimization, 32(3): 1668- 1697, 2022.
[14] Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured noncomvex-nonconeen min-max optimization. In Proc. AISTATS 21, 2021.
[15) Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017. URL http:// archive. ics. uci edu.uuuue
[16] Laurent Ghaoui and Hervé Lebret. Robust solutions to least-squares problems problles with uncertain data. SIAM Journal on Matrix Analysis and Applications, 18(4): 1997.
[17] Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and com- plementarity problems. Springer Science & Business Media, 2003.
[18] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Proc. NeurlPS'J8 2018.
[19] Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99, 2016.
[20] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last it- erate is slower than averaged iterate in smooth convex-concave saddle point problems. In Proc. COLT'20, 2020.
[21] Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematcal Society, -357-96,, 1967.
11

---

[22] Kam Hamidich. A data-driven statistical model for predicting the critical temperature of superconductor. Computational Materials Science, 154:346-354 2018.
[23] Alfredo N lusem, Alejandro Jofré, Roberto Imbuzeiro Oliveira, and Philip Thompson. Extragra- dient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2):68--224 2017.
[24] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proc. NeurlPS' 13, 2013.
(25) Donghwan Kim. Accelerated proximal point method and forward method for monotone inclusions. arXiv preprint arXiv: 2019.
[26] Ulrich Kohlenbach. On quantitative versions of theorems due to F.E. Browder and R. Wittmann. Advances Mathematics, 226(3):2764-2777 2011.
[27] UIrich Kohlenbach and Laurenjiu Leuştean. Effective metastability of Halpern iterates in CAT(O) spaces. Advances in Mathematicx, 231(5))252625556 2012.
[28] GM Korpelevich, Extragradient method for finding saddle points and other problems. Matekon, 13(4):35-49, 1977.
[29] Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. In Proc. NeurlPS 2021.
[30] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex finite-sum optimization via SCSG methods. In Proc. NeurlPS' 17, 2017.
[31] Laurentiu Leustean. Rates of asymptotic regularity for Halpern iterations of nonexpansive mappings. Journal of Universal Computer Science, 13(11):1600-161, 2007.
[32] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proc. ICML'21, 2021.
[33] Felix Lieder. On the convergence rate of the iteration. Optimization Letters, 15(2): 405-418, 2021.
[34] Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. In Proc. NeurlPS 2021.
[35] George J Minty. Monotone (nonlinear) operators in Hilbert space. Duke Mathematical Journal, 29(3):341-346, 1962.
[36] Arkadi Nemirovski. Prox- Prox-method with rate of convergence (1/tt) for variational inequali- ties with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229 251, 2004.
[37] Yurii Nesterov. Dual extrapolation and applications to solving variational inequalities and related problems. Mathematical Programming, 109(2-3):319-444, 2007.
[38] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Proc. ICML 17, 2017.
[39] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-coneave bilinear saddle-point problems. Mathematical Programming, Aug 2019.
[40] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle- point problems. In Proc. NeurlPS' 16, 2016.
[41] Jong-Shi Pang. Error bounds in mathematical programming. Mathematical Programming, 79 (1):299-30) -322, 1997.
[42] I.. D. Popov. modification of the Arrow-Hurwiez method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-84) 848, Nov 1980.
12

---

[43] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In Proc. ICML' 16. 2016.
[44] Tyrrell Rockafellar. Monotone operators associated with fundtions and minimax problems. Nonlinear Functional Analysis, 18(part 1):397-407, 1970.
[45] R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-888 1976.
[46] Vincent Roulet and Alexandre d' Aspremont. Sharpness, restart, and acceleration. SIAM Journal on Optimization, 30(1):262-22) 2020.
[47] Shoham Sabach and Shimrit Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640 660, 2017.
[48] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1):83-112, 2017.
[49] Chaobing Song. Yong Jiang, and Yi Ma. Variance reduction via accelerated dual averaging for finite-sum optimization. In Proc. NeurlPS' 20, 2020.
[50] Guido Stampacchia. Formes bilineaires coercitives sur les ensembles convexes. Académie des Sciences de Paris, 258:4413-444 4416, 1964.
[51] Quoc Tran-Dinh and Yang Luo. Halpem-ttye accelerated and splitting algorithms for monotone inclusions. arXiv preprint arXiv:2 10.02//0000//55 2021.
[52] Rainer Wittmann. Approximation of fixed points of nonexpansive mappings. Archiv der Mathematik, (8(5):486449) 1992.
[53] Taeho Yoon and Ernest K Ryu. Accelerated algorithms for smooth convex-concave minimax problems with (11/k?) rate on squared gradient norm. In Proc. ICML 21, 2021.
[54] Dongruo Zhou, Pan Xu, and Quanquan Gu. Finding local minima via stochastic nested variance reduction. arXiv preprint arXiv: 1806 08782, 2018.
[55] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Proc. NeurlPS' 18, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The contributions are summarized in Introduction (Section I and fully supported by detailed proofs in the main body and the appendix. (b) Did you describe the limitations of your work? [Yes] Some specific examples are: (i) the algorithm being of the Las Vegas-type type, in Section 3.2 and (ii) the dependence on problem parameters other than and being likely suboptimal in Appendix A
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical paper with preliminary numerical results.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2
(b) Did you include complete proofs of all theoretical results? [Yes] See Sections 3 the main body and the appendix.
in
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See the url in
Section K
13

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section e
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We use the same initialization for all methods, and tune
the parameters each method to be optimal individually. Details can found in the README from the url in Section o
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 6
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes] See Section
(b) Did you mention the license of the assets? [Yes] See Section g
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Our code is included in the url in Section x
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] The data we used is from online public repository.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] The data we used is from online public repository.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "yUcmNpZVI07", "reviewer": "Reviewer_NtRF", "summary": "The framework of Monotone variational inequalities capture several well-studied optimization problems, including convex minimization, saddle-point problems, and min-max optimization. \nThis 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})$.\nUnder 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})$.\nThe paper further establishes, via reductions from stochastic convex minimization, that these rates are optimal in $\\varepsilon$ up to logarithmic factors.\n\nEdit (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.", "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]\nQ1. 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.\nQ2. 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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n+ 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.\n+ 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. \n+ 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.\n\n**Weakness**:\n- 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].\n\n[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.\n[45] Quoc Tran-Dinh and Yang Luo. Halpern-type accelerated and splitting algorithms for monotone inclusions. arXiv preprint arXiv:2110.08150, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mTo3NS5AJl", "reviewer": "Reviewer_KtEb", "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.", "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.\n2. 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?\n3. 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.\n4. Line 282: one should point out that the number of oracle call is given in expectation.\n5. 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)).\n6. 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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. **Clarity.** The paper is clearly written. The discussion of the related work is detailed enough to place the work in the literature properly.\n2. **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.\n\n## Weaknesses\n1. **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.\n2. **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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CccBXu4z2wk", "reviewer": "Reviewer_W3Ku", "summary": "The paper considers solving stochastic monotone inclusions with respect to a (continuous) operator $F$ under three setting:\n1. $F$ is $\\gamma$-cocoercive (implying $\\frac{1}{\\gamma}$-Lipschitz continuity and monotonicity)\n2. $F$ is monotone and Lipschitz\n3. $F$ satisfies a sharpness condition, which is weaker than strong monotonicity\n\nThe 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. \n", "questions": "- Can you remove the need to know the distance to a solution and replace it with some proxy for this quantity?\n- 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?\n- 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?\n", "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.\n\nTo my knowledge, I do not suspect any potential negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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. \n\nWhile 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.\n\nGiven 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.\n\nMy 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7Cs9HsCv93a", "reviewer": "Reviewer_qc4S", "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.", "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.\n\n2. The authors should report some numerical results to show the advantage of the proposed algorithm.\n\n3. What’s the advantage of the proposed algorithm against existing Halpern iteration algorithms?\n\n4. There are several variance reduction techniques such as SVRG, SAGA and SARAH. Why the authors choose the variance reduction technique in SARAH?\n\n5. The writing of this paper should be improved, for instance, “stochastic variants of these methods had not been considered prior to our work”.\n", "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.\n\n2. The authors should report some numerical results to show the advantage of the proposed algorithm.\n\n3. What’s the advantage of the proposed algorithm against existing Halpern iteration algorithms?\n\n4. There are several variance reduction techniques such as SVRG, SAGA and SARAH. Why the authors choose the variance reduction technique in SARAH?\n\n5. The writing of this paper should be improved, for instance, “stochastic variants of these methods had not been considered prior to our work”.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\nThis paper proposes a stochastic Halpern iteration algorithm, which has O(1/\\epsilon^{-3}) stochastic oracle complexity.\n\nUnder an additional sharpness assumption, the complexity of the proposed algorithm has a better stochastic complexity, O((1/\\epsilon^{-2})log(1/\\epsilon)).\n\nWeaknesses：\n\nThe proposed algorithm uses both stochastic Halpern iteration and recursive variance reduction techniques, which are NOT new. Thus, the novelty of this paper is limited.\n\nBy 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.\n\nThe authors should report some numerical results to show the advantage of the proposed algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept