Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions
Authors: Xufeng Cai
Ahmet Alacaoglu
Jelena Diakonikolas
Venue: ICLR 2024 poster (2024)
Keywords: finite-sum problems
monotone inclusion
operator norm residual
stochastic Halpern iteration
last iterate convergence
variance reduction
min-max optimization
Primary area: optimization
TL;DR: We provide the first variance-reduced methods for finite-sum monotone inclusion problems, which as a special case lead to a near-optimal variance-reduced algorithm for minimizing the gradient in smooth convex-concave min-max optimization.

Abstract: Machine learning approaches relying on such criteria as adversarial robustness or multi-agent settings have raised the need for solving game-theoretic equilibrium problems. Of particular relevance to these applications are methods targeting finite-sum structure, which generically arises in empirical variants of learning problems in these contexts. Further, methods with computable approximation errors are highly desirable, as they provide verifiable exit criteria. Motivated by these applications, we study finite-sum monotone inclusion problems, which model broad classes of equilibrium problems. Our main contributions are variants of the classical Halpern iteration that employ variance reduction to obtain improved complexity guarantees in which $n$ component operators in the finite sum are ``on average'' either cocoercive or Lipschitz continuous and monotone, with parameter $L$. The resulting oracle complexity of our methods, which provide guarantees for the last iterate and for a (computable) operator norm residual, is $\widetilde{\mathcal{O}}( n + \sqrt{n}L\varepsilon^{-1})$, which improves upon existing methods by a factor up to $\sqrt{n}$. This constitutes the first variance reduction-type result for general finite-sum monotone inclusions and for more specific problems such as convex-concave optimization when operator norm residual is the optimality measure. We further argue that, up to poly-logarithmic factors, this complexity is unimprovable in the monotone Lipschitz setting; i.e., the provided result is near-optimal.

Published as a conference paper at ICLR 2024
VARIANCE REDUCED HALPERN ITERATION FOR FINITE-SUM MONOTONE INCLUSIONS
Xufeng Cai
Ahmet Alacaoglu" Jelena Diakonikolas
Department of Computer Sciences, University of Wisconsin-Madison
2 Wisconsin Institute for Discovery, University of Maaconsin-Madisse xcai i 74wwisc.ww.....................m edu, alacaoglu@wisee edu, jeweeeeeeee. wwwaaacsswsscc...... wwwc. edu
ABSTRACT
Machine learning approaches relying on such criteria as adversarial robustness multi-agent settings have raised the need for solving game-theoretic equilib- rium problems. Of particular relevance to these applications are methods target- ing finite-sum structure, which generically arises in empirical variants of learn- ing problems in these contexts. Further, methods with computable approxima- tion errors are highly desirable, as they provide verifiable exit criteria. Motivated by these applications, we study finite-sum monotone inclusion problems, which model broad classes of equilibrium problems. Our main contributions are vari- ants of the classical Halpern iteration that employ variance reduction to obtain improved complexity guarantees which n component operators the finite sum are average either cocoercive or Lipschitz continuous and monotone, with parameter L. The resulting oracle complexity of our methods, which provide guarantees for the last iterate and for the (computable) operator
residual, is On + ))) improving upon existing methods by factor up to vn. This constitutes the first variance reduction-type result for general finite-sum mono- tone inclusions and for specific problems convex-concave optimization when operator norm residual is the optimality measure. We further argue that, to poly-logarithmic factors, this complexity is unimprovable in the monotone Lips- chitz setting; i.e., the provided result is near-optimal.
INTRODUCTION
We study finite-sum monotone inclusion problems, where the goal is to find u, E RRd such that
E F(u.) G(u,),
(MI)
and where F(u): Rd Rd is monotone and Lipschitz, and G(u): Rd = Rd maximally mono- tone and possibly multi-valued. We consider the finite-sum structure, i.e., - Pu().
As is standard, we assume access to (i) the resolvent q/G for 1) > O, meaning that for any u we can find u such that û e ri)(ū) (generalizing the proximal operator); and (ii) evaluations of component operators F,. We measure oracle complexity of an algorithm in terms of evaluations of component operators F, and the resolvent operator of r/G:
The considered finite-sum settings are widespread machine learning; see e.g., Johnson & Zhang (2013); Defazio et al. (2014); Schmidt et al. (2017); Gower et al. (2020). While finite-sum mini- mization problems are well-studied, recent applications in areas such as generative adversarial net- works (Goodfellow al., 2014), robust machine learning (Madry al., 2018), and multi-agent inforcement learning (Zhang et al., 2021) require solving more general equilibrium problems. Such tasks are neatly unified under the umbrella of monotone inclusion (MI), which has rich history within optimization theory and operations research (Facchinei & Pang, 2003).
An important special case of (MI) the variational inequality (VI) problem defined as below, where G' is the subdifferential of the indicator function of a closed convex set C' C RR:
Find u. E C' such that (F (F.,)), u u.) 2 0 Vu C.
(VI)
'Equal contribution.

---

Published as a conference paper at ICLR 2024
A more specialized template that results in interesting examples of VI and monotone inclusion prob- lems is min-max optimization minx maxy f(x) g + $(x. y), where is convex convex-concave concave with Lipschitz gradients and f are proper convex lower semicontinuous (Issc.). This maps to (MI) by setting u-
(g), P(u) (- vy )(ws)) and G(u))
(ggly) (ar(s))
Optimality measures. A standard optimality measure for solving (VI) problems is the duality gap (Facchinei & Pang, 2003), defined
Gap(u) = (F)) vEC
(Gap)
However, (Gap) has significant drawbacks especially when the domain C' is unbounded. which is often the case. A common way to get around this is to use the restricted duality gap (Nesterov, 2007), which requires the identification of a compact including the iterates. However, such set generally affects the constants in the convergence bounds, and the restricted duality gap is not as interpretable as the duality gap. Additional drawbacks are that (i) neither of these measures is efficiently computable in general. (ii) the guarantees for these measures are typically obtained for an average or the best iterate, and (iii) such duality gap guarantees are generally not possible to obtain outside of monotone operator (convex-concave in the case of max optimization) settings.
An alternative optimality measure, which we focus on in this paper and argue to be more general than the duality gap, is the residual defined as
Res = [F + g()
(Res)
where g(u) G(u) and hence (Fst( G(u). 0) ((u)EG(u)
min [[ + g(() < (e)
The complexity results for (Res) can be translated to duality gap, but not vice versa (see, e.g., Di- akonikolas (2020, Section 1.2)). Moreover, this measure is most cases computable since the algorithms typically have access to F(u) + g()), which will become clearer in the sequel. Further, all our results are for the last iterate and the residual error guarantees are possible even for some classes of structured non-monotone operators.
Context. When restricted to the complexity results in terms of the duality gap, there exist optimal algorithms for finite-sum monotone VIs (Palaniappan & Bach, 2016; Carmon et al., 2019; Alacaoglu & Malitsky, 2022). These works show how to take advantage of the finite-sum structure with vari- ance reduction techniques to improve the complexity compared deterministic algorithms such as the extragradient method. However, as described earlier, these results do not translate to guarantees on the residual. Even more, we cannot expect these existing variance reduced algorithms have op- timal rates for the residual, since in the deterministic case they reduce to algorithms that are known to be suboptimal for residual guarantees (Golowich al., 2020).
On the other hand, even in the deterministic case, algorithms that are optimal for the residual error (in terms of oracle/iteration complexity) were obtained only recently (Diakonikolas, 2020; Yoon & Ryu, 2021). These results are based on variants of the classical Halpern iteration (Halpern, 1967) developed for solving fixed point equations with nonexpansive maps. Despite further developments relaxing the initial assumptions on F and G (Tran-Dinh & Luo, 2021; Lee & Kim, 2021; Cai et al., 2022b; Cai & Zheng, 2023; Kovalev Gasnikov, 2022) and addressing stochastic approximation settings (Cai et al., 2022a; Chen & Luo, 2022), none of the existing results consider the finite-sum structure nor lead to the /n improvements expected from variance reduction approaches in such settings.
Our contributions. We obtain the first variance-reduced complexity results for standard classes of (MI) problems that could lead to /n improvement compared to methods without variance reduc- tion, in line with similar results obtained for the less general minimization and min-max problems (focusing only the duality gap guarantees) in prior work; see Table 1 in App. A. In particular:
When F satisfies average & -cccoercivvtyy (see Assumption 3), we obtain an algorithm with oracle complexity Ö(n + )) To obtain this result, we incorporate recursive variance reduc- tion (Li et al., 2021) into constrained one-step Halpem iteration. While a similar strategy has been employed in Cai et al. (2022a) to address stochastic approximation (infinite sum) settings, their analysis is more complicated and their oracle complexity is strictly worse than ours whenever n is not too large (roughly, when o(1 )))
2

---

Published as a conference paper at ICLR 2024
When F is monotone and L-Lipschitz in expectation (see Assumption 2), obtain algorithm with oracle complexity (n vnL==1). This result is enabled by variant of Halpern iteration employing inexact resolvent evaluations of r7 + G) for 1 > O. While this strategy is similar to the approach taken in Diakonikolas (2020) address corresponding settings without the finite- sum considerations, unlike their work, our result is enabled by employing a stochastic variance reduced algorithm from Alacaoglu Malitsky (2022). A critical difference is that we carry out a stochastic error analysis with new inexactness criterion, due to the randomized nature of the inner algorithm. To obtain our result, we generalize the analysis for strongly monotone inclusion from Alacaoglu & Malitsky (2022) to the composite form (MI) with maximal monotone G.
The complexity results presented above are for the expected residual in view of (Res). Due to the computability of the residual, our results can also be easily translated to hold high probability with logarithmic dependence on confidence parameter. See the discussion after Remark 4.4 for details.
Further related work. Monotone inclusion and fixed point problems with finite-sum cocoercive operators have been the focus of study in several recent papers. Davis (2023) presented a possible speedup with variance reduction for root-finding problems with average cocoercivity only w.r.t. the solution point, but requiring additional quasi strong monotonicity assumption. Loizou et al. (2021); Gorbunov et al. (2022); Beznosikov et al. (2023) used similar assumptions to solve the VI problems and provided convergence results for stochastic gradient descent-ascent methods. A more general expected residual assumption was considered in Choudhury et al. (2023), but this work only proved O complexity for residual norm guarantees in our setting. which suboptimal for finite-sun sum monotone problems when n = o(s-)). Similar less desirable O(e=2) complexity on the residual norm was also obtained in Morin Giselsson (2022) with component cocoereivity. Tran-Dinh & Luo (2023) considered random coordinate methods for root finding problems with cocoercivity, which a different setting that does not improve upon the overall complexity over deterministic algorithms. For the finite-sum monotone Lipschitz setting, Johnstone et al. (2024) obtained O O(=-*) complexity for a generalized version of the residual and left open the problem of obtaining a better complexity for the residual norm by stochastic method in this setting, which results address.
PRELIMINARIES
We denote as || || the le norm. We say that an operator T: Rdd Rd is (i) monotone if for Vu, v E R4: (T(u) - u u-,.uvvv... u-vvv v) 2 O; (ii) Lp-Lipschitz if for Vu, v E R [T T(v) <
LF vll: (iii) -ccooercive for Yu, v Rd: (T(u) - T(v), u v) 2 + Monotonicity can be defined in the standard way for a multi-valued operator T: Rd Note that T, -cccoerriyvvtyy implies monotonicity and L-Lipschitzness, but not vice versa. Maximal monotone operators are those whose graph is not properly contained in the graph of any other monotone oper- ator where graph is defined in the standard way for operator T as graT {(x,y): y E T-x)). Common examples for this class include subdifferentials of proper convex lss.c. functions. For fur- ther discussion on these properties, Bauschke & Combettes (2011).
Given an operator T, its resolvent is defined as JTF = (Id + -/T)-1 for some 1) > 0, i.e.
1 (u u) E T(n). (u)(u) =
1
Important instances of resolvents include the proximal operator obtained when T = dg for a convex function g and projection Pe: obtained when T = a6c for the indicator function dc of a closed convex C. An important and useful property of the resolvent operator JTr is that it is single valued and nonexpansive (1-Lipschitz) when T' is maximally monotone.
Our work leverages the classical Halpern iteration (Halpern, 1967), commonly used for solving fixed point equations x = T(xx with nonexpansive operators T'. Halpern iteration is defined by
Uk+1 = d + - -xx)TT(ue).
(Hal)
where D is step parameter typically set be of the order- }. To address (MI), several vari- ants of (Hal) have been proposed, with different choices of the nonexpansive operator T. Notable examples most relevant to work include T JnG (Td F)F for cocoercive settings and
3

---

Published as a conference paper at ICLR 2024
T J= G)) for monotone Lipschitz settings (Diakonikolas, 2020). We defer other background information about the techniques used in the paper to Appendix A, due to space constraints.
We start with the common standard assumption that require in all of the results.
Assumption 1. The operator F; Rd - R is monotone and -i-Lischhit,, and the operator G: IR = Rd is maximally monotone. Their solution set is nonempty, i.c., (F + G) G) (0) * 0.
The next two assumptions characterize the two separate settings we consider in the sequel. Assumption 2. The operator F: TR." + IR LipLisschitz in expectation, meaning that given an oracle Fg and distribution Q such that (Fs=@(Fg(U)) F(u), we have for any u, v Rd.
Ce-olFFg(uu Fg 2v]l < L u v
This is the main requirement used in Section 4. This assumption holds, for example, when each F; Lipschitz-continuous, and standard for analyzing variance reduced algorithms (see e.g., Pala- niappan & Bach (2016); Carmon et al. (2019); Alacaoglu & Malitsky (2022) and also Table 1).
Alternatively, in Section 3 we assume that is cocoercive on average, which can be regarded as cocoercivity in expectation with uniform sampling.
Assumption 3. The operator F: Rd I2d is I coccoreiiee on average, i.e., for any u, v E IRd
- F(v)) u - v) 2 + E [F((u) - F.(v)]12. u
This assumption holds, for example, when each F; is cocoercive. In the minimization case, this corresponds the smoothness of component functions, which is standard in variance reduction literature (Allen-Zhu, 2017; Nguyen et al., 2017). In the case of fixed point problems, it implied by the nonexpansiveness of component operators. An example of this case given as convex feasibility problem in Malitsky (2019, Section 5.2). Similar assumptions also arise in Davis (2023); Morin & Giselsson (2022); Tran-Dinh & Luo (2023); Loizou et al. (2021).
Oracle complexity. As the standard convention for finite-sum problems (Palaniappan Bach, 2016; Carmon et al., 2019; Alacaoglu & Malitsky, 2022), we measure the oracle complexity of an algorithm by the number of calls to F; to make an optimality measure small (the number of calls to the resolvent of n/ for 1) > O is of the same order). Since our variance reduced estimators compute the full operator values with some probability, per-iteration costs are random and our complexity results are on the expected number of calls to F. This is also a standard way measure complexity with single-loop variance reduced algorithms (Li al., 2021; Kovalev et al., 2020). is possible to obtain deterministic per iteration costs by exchanging to multi-lopp algorithms (Carmon et al., 2019; Alacaoglu & Malitsky, 2022), which we avoid for simplicity.
3 ALGORITHM AND ANALYSIS IN THE COCOERCIVE CASE
In this section, we work under Assumption 3. The main reason that we study this case separately is because we can provide a simpler single-loop algorithm under cocoercivity. We use the following stochastic variant of the constrained Halpem iteration
u = Ju (Aauo - (1 A+)u: 1 nTF()))).
(3.1)
where F. is the variance-reduced PAGE estimator (Li et al., 2021). We summarize our approach in Alg. 1, and defer the details of the PAGE estimator to Appendix A, due to space constraints.
A similar constrained Halpern iteration scheme has been analyzed in Cai et al. (2022b); Kovalev & Gasnikov (2022) with an extrapolation step, but only for deterministic settings. For the stochastic counterpart, Alg. I can be seen as a simpler constrained version of Cai et al. (2022a), with a single parameter for the constant batch size that (unlike in the algorithm of Cai et al. (2022a)), independent of the accuracy E, the component variance, the norm of iterate differences, and a stage-wise choice of Рę- The reason we are able to simplify the batch size selection comes from our focus on the finite-sum problems, whereas Cai et al. (2022a) considered infinite-sum problems.
4

---

Published as a conference paper at ICLR 2024
Algorithm Halpern iteration with variance reduction
Input: Ug E Rdd, step size oj = z.. batch size b = [vm], A1
u -2 (uo 2X, ((o))) F(ui)= F(ui)
for 1,2,...de do
Vk S Vn
A k44
2
Pk+1
k+5
4
vk 2 vn
Vi+5
Us+1 Jn () uo + A (F(())))
Sample Sk+1 C ... without replacement and uniformly at random with |Sk+1| 1
F(UR+1)= = + + Eissen (Fi(uR+1) Fi(u)))
F(ux+1)
w.p. Pk+1-
w.p. - Pk+1-
The key technical ingredient in our analysis is the following lemma, which shows that, in expec- tation, in each iteration & we can reduce a potential function by a factor (1 >x)) This potential reduction, in turn, can be translated into the residual error decay rate X = O(1kk), shown in Theorem 3.2 below. Due to space constraints, the proofs are deferred to Appendix B.
Lemma 3.1. Let Assumptions 1 and 3 hold. Then, for the iterates un of Algorithm 1 and the potential function Ck defined by
Ck 2Xk
[[F(u)) + g+ll (F(us) + gk, un uo) + cs (F(s)) F(u))11; (3.2)
we have that E[ I (1 (1- 11-Ax)EE(A for k 2 1, where g++1 = 7 (A + (1111a)u - (n)ju-nF((u))) uk+1) G(u++1) and C ()++4)
Our potential function in (3.2) allows us to go beyond the deterministic setting analyzed in Kovalev & Gasnikov (2022), by handling the variance of the estimator F. which also helps us avoid the more complicated induction-based argument in Cai et al. (2022a). Another important aspect in the above bound is that e₁ can be of the order of /n. Hence, to make sure that we do not introduce spurious dependence on n, it critical that the first two iterations of the algorithm evaluate the full operator.
The following theorem states our main convergence result for this section.
Theorem 3.2. Let Assumptions I and 3 hold. Then, for the iterates ug of Algorithhm 1, have
E[ResF+c(uu)) < (E[Res) (ux))) 1/2 16L un u.
+44
In particular, given accuracy : > O, to return a point uk such that E[ResF+c(UKK] s E, the stochastic oracle complexity of Algorithm 1 is Ö(n + s/ul.lug u.ll
Observe that we use large batch size |Sa| R v to obtain our improvement from the employed variance reduction strategy, which common practice for stochastic algorithms with residual guarantees (Cai et al., 2022a; Lee & Kim, 2021). Prior work (Pethick et al., 2023) that avoids large batch size requires (s complexity and only provides residual guarantees on the best iterate. We also argue that in the finite-sum case, there is no inherent disadvantage of using ((Vi)) samples in every iteration since we provably show that this leads to a better dependence on n. in the final oracle complexity compared deterministic algorithms, which would use samples every iteration.
To compare with prior results, we first note that deterministic Halpern iteration for constrained VIs with cocoercive operators yields ((L complexity (Diakonikolas, 2020), for which our result in Theorem 3.2 replaces bLe with vnL and can provide improvements up v/i depending on the relationship between L and LF (see examples in Palaniappan & Bach (2016); Carmon et al. (2019); Alacaoglu & Malitsky (2022)). Moreover, compared complexity results O(LFE and Ö(LFE-) for algorithms developed for the infinite-sun sum stochastic settings in Cai et al. (2022a); Chen & Luo (2022), provide improvements in the regime o(1/ /n). assuming LF = L.
An important implication of this result on cocoercive inclusions is for finite-sum minimization where variance reduction has been studied extensively. The state-of-the-ar results with direct
5

---

Published as a conference paper at ICLR 2024
algorithms due to Lan et al. (2019) and Song et al. (2020), that provide oracle complexity On VnLe-T]lup u.ll) for the objective suboptimality. This result can be translated to the norm of the prox-mapping to get [ (uert)] S e with complexity V =)) which is the same as our result when specified to the case F /s for smooth convex function and G = 0g for a regularizer g. This complexity is not optimal for smooth convex minimization and has been improved for unconstrained minimization with indirect algorithms (Zhou et al., 2022; Allen-Zhu, 2018). Our results provide the best-known guarantees (among direct approaches) with a single-lopp algorithm. Single-loop versions of Katyusha (Allen-Zhu, 2017) were studied in Kovalev et al. (2020) and Qian et al. (2021), albeit without guarantees for the non-strongly convex case.
4 ALGORITHM AND ANALYSIS IN THE MONOTONE & LIPSCHITZ CASE
In this section, we consider the more standard setting where F is monotone and Lo-expected Lips- chitz for oracle distribution Q. We note that our results apply for general sampling distributions Q under which Assumption 2 holds; for concrete examples beneficial non-unifona sampling dis- tributions, see Remark 4.4. We omit the subscript and denote L LQ for brevity in this section, since the context is clear. To obtain the desired complexity, we make use of the resolvent opera- tor + (u) for some fixed 1) > 0 (specified later in this section). In particular, adapt the stochastic Halpern iteration to the following single-valued and cocoercive operator
(") == u (m)
Indeed, for any 1) > O, finding a point such that E]]] PM (u)]ll S ne is sufficient to approximate (MI) of F + G, as summarized in the following proposition with the proof deferred to Appendix C.
Proposition 4.1. For any fixed n) > 0, ler (*(u) = u (n If [[P)ll) S mE for some E >>0 0, then we have Resf+a(u) < E with u = u - (*(()= = (u)
This standard proposition gives us a simple way to convert the guarantees on || | [P]l))] to the residual norm (Res) conceptually, and we later provide computable approximation for u in Cor. 4.3. If P can be computed exactly, then (MI) can be solved by the standard, deterministic Halpern iteration, as (u( is nonexpansive. However, the exact evaluation of resolvent operators only happens in special cases, and even for those cases, the computation is usually prohibitive when n is large for the operator F. Instead, one efficiently approximate the resolvent by solving finite-sum strongly monotone VI problem, for which we provide more details in Section 4.2.
In the rest of the section, we provide overview of the analysis and main technical results. Due to space constraints, the proofs are deferred to Appendix C.
4.1 INEXACT HALPERN ITERATION WITH STOCHASTIC ERROR
Denoting the resolvent approximation by J ()(F))) we use the inexact Halpern iteration follows
u = Au + +(1 (1->x) (FCC(())) = Agun + (1 Ax) - (u:))) - (1 --xx)cs (4.1)
where C₁ = (ms) - Jn(F (u&) is the approximation error. To efficiently compute method (VR-FoRB, Alg. 3) proposed in Alacaoglu & Malitsky (2022) as subsolver for each iteration. We summarize our approach in Alg. 2, and defer our detailed discussion of VR-FoRB to Section 4.2.
JM(F+G) to certain accuracy, we use the variance-reduceed forward-refletted-backee
Halpern iteration with inexact resolvent computation has been shown to maintain O(1/k) conver- gence rate for deterministic problems (Diakonikolas, 2020), provided the approximation error |e sufficiently small. The critical difference is that can longer use the stopping criterion for the inner algorithm therein, due to the randomized nature of VR-FoRB. Their inexactness criterion ||ex|| < -π(K+1] for each iteration A requires pre-fixed accuracy and also leads to the bound on the number of inner iterations to depend on Ja(F+G)(u (ux) which is not feasible empirically. The latter is simply because the initial distance to the solution of the subproblem appears in the com- plexity bound (see, e.g., Theorem 4.6). To overcome these issues, we use a different inexactness criterion Eg [|]ex.]]] < (k+2]s" conditional the algorithmic randomness up to and including it- eration k which is, in fact, related to old idea of warm-starting (Rockafellar, 1976, eq. (B)). Such
[|r*(())]|

---

Published as a conference paper at ICLR 2024
Algorithm 2 Inexact Halpern iteration with VR-FoRB
Input: ug E _dd L LQ with the distribution Q -( 1- n, /
for 0,1,2.... do
A k+2 Ma 56(n + vT) log(2k + +4]
J JN(F+G7 (ux)) VR VR-FoRB ux, MR. ld (f G) Uk Q)
Uk+1 = Auu + (1 (c)
criterion can be guaranteed to hold by setting the number of inner iterations be sufficiently large, yet computable, number depending only on known constants, using the convergence results of VR-FoRB from Section 4.2. We summarize these results the following theorem.
Theorem 4.2. Let Assumptions I and 2 hold. Then, for the iterates uą of Algorithm 2, we have that Ex [x]]|= <
conditional on the algorithm randomness up to iteration k, and
(b+2))
7 Up u.
k
Moreover, given accuracy > O, to return a point uk such that [B[]] ("x]))) s me with v/ = L/2
the stochastic oracle complexity Ö(n viL.]uo-u.lly c
The final step is to characterize the precise point at which we have the residual guarantees. Corollary 4.3. Let Assumptions and hold and let ug be as defined in Theorem 4.2. Then, for Hont VR VR-FoRB(UKk [42(n
/n [42(1 + vn) log((9n)) Id + 1/( G) ug Q) with 1j L (( S 28.
The total stochastic oracle complexity for producing Wout is Ö (n y
Remark 4.4. Non-uniform sampling Q can be beneficial in terms of lowering the Lipschitz constant LQ and thus the overall algorithm complexity. As a specific example, consider the matrix game
min max (Ax, y) + 8 1 (x) + 8Am2 (y)
XER yERi?
for E M the simplices A,, A Am where is the indicator function. With u = (*). we have Fuu) = Axd and G(u) (as awa (x)). Denote the i-th row and the j-th column of A by A. and A.j. respectively. Let ||- be the operator norm for matrix, and || ||e be its Frobenius norm. Consider the standard importance sampling for Q, i.e., we sample & = -i,5) Q such that
a0 my
1 A:y: A
||A
A 11
Pe(u)=
Pools = (i, j) o. (1) (2)
R
(1)
T P
A
It is easy to verify that R [u)] F(u), and have TQq || while T.p ||A||]. Since it is possible for || and All2 to be of the same order, in those cases the improvement from the
variance reduction approaches (including ours) is of the order 2mmmm (order /m, for square ma-
+m
trices). Similar conclusions can be drawn more generally for linearly constrained nonsmooth convex optimization problems; see (Alacaoglu & Malitsky, 2022. Section 4) and App. C.5 for details.
In addition to complexity bounds for the expected residual, our results also have direct consequence for high probability guarantees. In particular, since result clearly implies Res (uour) S. with a constant probability by Markov's inequality and since the residual is computable, one can run the algorithm multiple times and monitor the residual, obtain high probability guarantee with logarithmic dependence on the confidence level. See, for example, Zhou et al. (2022); Allen-Zhu (2018) where such confidence boosting mechanism is used in similar context.
A few other remarks are in order here. First, our results imply the gap guarantee results in prior work (Alacaoglu & Malitsky, 2022; Carmon et al., 2019). On the other hand, the algorithms in these

---

Published as a conference paper at ICLR 2024
works are bound to be suboptimal for the residual since they reduce to the exragradient algorithm in the case n = 1, which is suboptimal for the residual guarantee (Golowich et al., 2020). Second, residual guarantees for these variance reduced algorithms currently unknown. Third, the im- plication to gap guarantees also ensures the near-optimality of our results since such complexity is known to be unimprovable for the gap guarantees (Alacaoglu & Malitsky, 2022; Han et al., 2024).
Next, compared to deterministic algorithms with O(nLpe=!) complexity for the residual (Di- akonikolas, 2020; Yoon & Ryu, 2021), we replace aLe with Vul. This brings improvements in important cases discussed in Palaniappan & Bach (2016); Carmon al. (2019); Alacaoglu & Mal- itsky (2022), including linearly constrained problems and matrix games discussed in Remark 4.4. This mirrors the recent improvements for the duality gap guarantees for VIs where Alacaoglu & ") complexity instead of O(nLpE
Malitsky (2022); Carmon et al. (2019) showed O( of deterministic methods (Nemirovski, 2004).
Finally, we show the extension to cohypomonotone settings defined by the existence of p > 0 such that (F(u) F(v), u u-v) v) 2 -pl -pl F(u) - F(v)] in the following corollary for completeness, with justifications in Appendix C.4. This result provides better dependence n compared to previous results with the drawback of more restrictive bound for y (roughly, p < Jn and using G O.
Corollary 4.5. [Cohypomonotone Assume that F is maximally p-cohypomonotone and L-expeetedd S mE
Lipschitz and G O. Given E > 0, Alg. 2 returns a point uk such that (1mo-ull] +1) stochastic oracle complexity, for any positive such that 1/
with δ (n+ /u I= nL+1
min
71 2 mLF
With 17 = V/- as before, this corresponds to p min
L
yR
VRLL
21
4.2 RANDOMIZED APPROXIMATION OF THE RESOLVENT
Approximating Jn (N for u+ Rdd corresponds to solving the finite-sum MI defined as:
Find u such that 0 nl + G)(( + û dt-ut. ut.
(4.2)
is immediate that the solution to (4.2) of the operator 7f + G) +Id ut corresponds to F (o)+t) by the definition of the resolvent. Note that ny F + GG + Id - -u can be represented as sum of two operators (", and nG(u), where
(" = = -u u Σ (u:",, ((uuut)===E(i + ---u u². (4.3)
is simple verify that F"(u; ut) is 1-strongly monotone and (n) -averrae Lipschitz w.r.t. u;
we provide a proof in Appendix C.1 for completeness, and 1/G is still maximally monotone as 1) > 0. Hence below we use more general notation and will set A(u) mentioned before, we use VR-FoRB from (Alacaoglu & Malitsky, 2022, Algorithm 4) to solve (4.2), which we present as Alg. 3. We now state its convergence result under strong monotonicity.
(", and B nGG. As
Algorithm 3 VR-FoRB(1, U1 M. A + B, Q) (Alacaoglu & Malitsky, 2022, Algorithm 4)
Vp(1~>) 21.
Input: Vo Wo - p- 1,2 a p.
distribution = {q: 1.2
for k 0,1,..., M 1 do
V4 = aV2 + (1 a))
Sample i e {1...., n according to Q
Vk+1 = JrB(( (Vh T[A(W*)) - -W)((w))))++++++ (nq.)
Vk+1 w.p. p
Wk+1
Wk
w.p. 1 1
Theorem 4.6. Let A: Rdd + Rd be monotone and LA-Lipschitz in expectation with A
En A. Let B: Bdd = Idd be maximally monotone, and A + be u-strongly monotone with
1 and v. = (A+ B))) + 0. Given > 0, Alg. 3 returns VM with Elll v. s E²
in [14nn+ + SoLAA) log vo iterations and O(n yTl. log [vo oracle queries.
1
8

---

Published as a conference paper at ICLR 2024
Operaton norm
10
VR-E5 EAG
Operator norm
10"
Algp
Alpce thee
10-1
10
10-2
1000
2000
30:00
4000
5000
0.2
0.4
1.0
of epochs
# of epochs
X20"
Matrix game
(b) Quadratic program
Figure 1: Comparison of Alg. 1, Alg. 2, deterministic extragradient (EG), extra anchored gradient (EAG), variance reduced extragradient (VR-EG) on the matrix games and quadratic programming.
We remark that only almost sure convergence was proved for VR-FoRB in Alacaoglu & Malitsky (2022). We show its non-asymptotic linear convergence which is needed for our main result in Theorem 4.2. A similar rate is in (Alacaoglu & Malitsky, 2022, Theorem 6) for strongly monotone VIs, but for a different algorithm variance reduced extragradient. Our result can seen as a "single-call" alternative to this method, for the slightly more general setting of strongly monotone inclusions. We provide this to keep the generality of our setting and also for possible interest in its own right, since such algorithms have been popular (Cai & Zheng, 2023; Hsich et al., 2019).
NUMERICAL EXPERIMENTS AND DISCUSSION
We provide preliminary numerical results for our proposed algorithms'. We compare Alg. 1 and Alg. 2 with existing algorithms matrix games and special quadratic program used for lower bound derivations in Ouyang & Xu (2021). We emphasize that our main contributions are theoret- ical, while the provided examples are mainly for illustration with two goals mind: (i) verify our improved complexity bounds compared to deterministic Halpern-based methods (Cai et al., 2022b), (ii) show benefits of our algorithms compared to prior variance reduced algorithms (Alacaoglu & Malitsky, 2022) for difficult problem instances used for establishing lower bounds.
We compare our algorithms with extragradient (EG) (Korpelevich, 1977), constrained anchored extragradient (EAG) (Cai et al., 2022b), and variance-reduced extragradient (VR-EG) (Alacaoglu matrix game with simplex constraints, i.e., minge m mg (Ax,y) with my m2 500. We use the policeman and burglar ma- trix (Nemirovski, 2013). Second problem we consider a quadratic program from Ouyang & Xu (2021) equivalent to the problem minxeRm1 maxyeRm> 1 Hx h. (Ax b, y). This prob- lem was used in Ouyang & Xu (2021) for establishing lower bounds for min-max optimization and this example with my m2 200 show the efficacy of Halpern-type algorithms. We use uniform sampling for all the algorithms, set Mr [0.05n log(k + 2)] for Alg. 2, and tune the stepsizes for each method individually. We implement all the algorithms in Python, and run the experiments on Google Colab standard CPU backend. We provide further details in App. D.
& Malitsky, 2022, Alg. 1). First problem
We summarize our numerical results and plot the operator norm against the number of epochs in Fig. 1, where one epoch means n individual component operator evaluations. Operator norm stands for [(((())) for the unconstrained case, and we follow the convention and use the norm of gradient mapping, i... VIIx - - (x A y] 2 + ly - Pama (y + Ax) 2 for the matrix game (which guarantees can be directly translated see for example (Cai et al.. 2022b, Fact 1)). We observe that (i) our variance reduced Alg. 1 and Alg. 2 converge faster than deterministic methods both cases, validating complexity results; (ii) VR-EG exhibits slightly faster convergence than Halpern-type algorithms in Fig. 1(a) (see similar empirical observations and comments in Park & Ryu (2022); Tran-Dinh (2023)), however VR-EG suffers stagnation while our algorithms progress on the difficult worst-case problem, as shown in Fig. 1(b).
Due to space constraints, conclusions and discussions about future directions appear in Appendix E.
Cooe available http://ggthaii...omo//yyy/////ie HaaeiiteSSSSu-aaaeee-eeeaainiin

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This research was supported in part by the NSF grant 2023239, the NSF grant 2007757, the NSF grant 2224213, the AFOSR award FA9550-21-1-0084, the Office of Naval Research under contract number N00014-22-1-2348.
REFERENCES
Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality meth- ods. Proc. COLT'22, 2022.
Ahmet Alacaoglu, Yura Malitsky, and Volkan Cevher. Forvard-effccee---ccwwwr method with variance reduction. Computational Optimization and Applications, 80(2)321-3366, 2021.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):8194-824) 2017.
Zeyuan Allen-Zhu. How make the gradients small stochastically: Even faster convex and non- convex sgd. In Proc. NewrIPS' 18, 2018
Heinz H Bauschke and Patrick L Combettes. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
Heinz H Bauschke, Walaa Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189:55-74, 2021.
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. In Pruc. AISTATS 2023.
Xufeng Cai, Chaobing Song, Cristóbal Guzmán, and Jelena Diakonikolas. Stochastic halpern itera- tion with variance reduction for stochastic monotone inclusions. In Proc. NeurlPS 22, 2022a.
Yang Cai and Weigiang Zheng. Accelerated single-call methods for constrained min-max optimiza- tion. In Proc. ICLR'22, 23, 2023.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for monotone inclusions and constrained nonconvex-nonconcave min-max optimization. 2rXiv:2206.05228, 2022b.
arXiv preprint
Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. In Proc. NeurlPS"/9 19, 2019.
Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. Proc. NeurlPS' 19, 32, 2019.
Lesi Chen and Luo Luo. Near-optimal algorithms for making the gradient small in stochastic mini- max optimization. arXiv preprini arXiv:2208.0523 05525, 2022.
Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragradient
methods for structured non-monotone variational inequalities: Improved analysis under weaker conditions. In Proc. NewrlPS'23 23, 2023.
Laurent Condat, Fast projection onto the simplex and the I ball. Mathematical Programming, 158 (1-2):575-585, 2016.
Damek Davis. Variance reduction for root-finding problems. Mathematical Programming, 197(1): 375-410, 2023.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Proc. NewrIPS" 2014.
Jelena Diakonikolas. Halpemn iteration for near-optimal and parameter-fre free monotone inclusion and strong solutions to variational inequalities. In Proc. COL,7"20 2020.
10

---

Published as a conference paper at ICLR 2024
Francisco Facchinei and Jong-Shi Pang. Finite-dinensiona variational inequalities and comple- mentarity problems. Springer Science Business Media, 2003.
Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Proc. NeurIPS' 18, 2018.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-coneave saddle point problems. In Proc. COLT'20, 2020.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Proc. NeurlPS 14, 2014.
Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient:
General analysis and improved rates. In Proc. AISTATS' 22, 2022.
Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for 2020.
machine learning. Proceedings of the IEEE,
Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6)9957-961, 1967.
Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. Journal of Machine Learning Research, 25(2):1-86, 2024.
Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, and Brian McWilliams. Variance re-
duced stochastic gradient descent with neighbors. In Proc. NeurlPS' 15, 2015.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Proc. NeurlPS' 19, 2019.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, 2013.
Patrick R Johnstone, Jonathan Eckstein, Thomas Flynn, and Shinjae Yoo. Stochastic projective splitting. Computational Optimization and Applications, 87(2):997-437, 2024.
GM Korpelevich. Extragradient method for finding saddle points and other problems. Matekon, 13 (4):35-49, 1977.
Dmitry Kovalev and Alexander Gasnikov. The first optimal algorithm for smooth and strongly- convex- sooee--stoongly-conavee minimax optimization. Proc. NeurlPS' 2022.
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop. In Proc. ALT'20, 2020.
Guanghui Lan, Zhize Li, and Yi Zhou. A unified variance-reduced accelerated gradient method for convex optimization. In Proc. NeurlPS' 19, 2019.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. In Proc. NeurIPS'21, volume 34, 2021.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal prob- abilistic gradient estimator for nonconvex optimization. In Proc. ICML'21, 2021.
Sharon L Lohr. Sampling: design and analysis. CRC press, 2021.
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Toannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. In Proc. NeurIPS 2021.
Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic algorithms for finite-sum unbalanced convex-concatd minimax optimization. arXiv preprint arXiv:2106.0176.
2021.
11

---

Published as a conference paper at ICLR 2024
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Proc. ICLR' 18, 2018.
Yura Malitsky, Golden ratio algorithms for variational inequalities. Mathematical Programming, Jul 2019.
Yura Malitsky and Matthew K Tam. A barkard splitting method for monotone inclusions without cocoercivity. SIAM Journal Optimization, 30(2):1451-1472 2020.
Martin Morin and Pontus Giselsson. Cocoercivity, smoothness and bias in variance-reduced stochas- tic gradient methods. Numerical Algorithms, 91(2):749-772 2022.
Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15())222--251, 2004.
Arkadi Nemirovski. Mini-course on convex programming algorithms. Lecture Notes, 2013.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. 109(2-3):319-344 2007.
Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In Proc. ICML'17, 2017.
Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex- concave bilinear saddle-point problems. Mathematical Programming, 185(1-2):1-35, 2021.
Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. In Proc. NeurlPS'16, 2016.
Jisun Park and Ernest K Ryu. Exact optimal accelerated complexity for fixed- -oint iterations. In Proc. ICML 22, 2022.
Thomas Pethick, Olivier Fercoq, Puya Latafat, Panagiotis Patrinos, and Volkan Cevher. Solving stochastic weak minty variational inequalities without increasing batch size. In Proc. (CLR'23, 2023.
Xun Qian, Zheng Qu, and Peter Richtárik. L-svrg and I-katyusha with arbitrary sampling. The Journal of Machine Learning Research, 22(1):991--5039 2021.
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1):83-112 2017.
Chaobing Song, Yong Jiang, and Yi Ma. Variance reduction via accelerated dual averaging for finite-sum optimization. In Proc. NeurlPS' 20, 2020.
Quoc Tran-Dinh. Sublinear convergence rates of extragradient- methods: A survey on classical and recent developments. arXiv preprint arX11:2303..7119, 2023.
Quoc Tran-Dinh and Yang Luo. Halpern-type accelerated and splitting algorithms for monotone inclusions. arXiv preprint arX0:22110008750, 2021.
Quoe Tran-Dinke and Yang Luo. Randomized block-coordinate optimistic gradient algorithms for root-finding problems. arXiv preprint 1XXv:22301.03113. 2023.
Erfan Yazdandoost Hamedani and Afrooz Jalilzadeh. stochastic variance-reduced accelerated
primal-dual method for finite-sum saddle-point problems. Computational Optimization and Ap- plications, pp. 1-27, 2023.
Tacho Yoon and Emnsst Ryu. Accelerated algorithms for smooth convex-concad minimax prob- lems with O11 (1/A22) rate squared gradient norm. In Proc. ICMI. 21, 2021.
12

---

Published as a conference paper at ICLR 2024
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp- 321-384, 2021.
Kaiwen Zhou, Lai Tian, Anthony Man-Cho So, and James Cheng. Practical schemes for finding near-stationary points of convex finite-sums. In Proc. AISTATS' 22, 2022.
13

---

Published as a conference paper at ICLR 2024
Table Comparison of our results with state of the in the monotone Lipschitz settings, in terms of stochastic oracle complexity required to output Xuuipul with E
I c in Column 2 and E [X I in Column 3. We refer Section 1 for the discussion regarding the difference in optimality measures Re and Gap and the importance of getting results Res
High Probabiiity Result
Complexity for Resy-
Complexity for Gap
Reference
Assumption
Kovalev & Gasnikov (2022)
(nLpe=))
O(nLae-1)
Assumption
N/A
Nemirovski (2004)
((nLpe=!)
Assumption
N/A
Cai et al. (2023s)
O (2)=-1)))))
O LD)e-
B. (x))
Assumption 1, 2, 5
Assumption I. G
Lao ot. (2021)
010"=-++Lp5"
0(0²e-+ + L
F (- Fx ((
F F(x) 5
Assumption 1.2 bounded domain (cf. Sec 5.4 (Carmon al., 2019))
Carmon et (2019)
Ō( vaLe b)
Assumption 1, bounled doraii
Palaniappan & Bach (2016)
Ō(n Vnle !)
(cf. Sec. 2 in (Palaniappan & Bach, 2016)
Assumption 1,2 (cf. Assumption in (Alacaoglu Malitsky. 2022))
Alacaoglu & Malitsky (2022)
O(n VnLe-t)
[Our results, Theorem 4.2]
Ö(n + vole-1)
Ō(n vīLe-1)
Assumption 1.2
A BACKGROUND
We first provide Table for the comparison of our results with the state-of-the-art in the monotone Lipschitz case.
VI algorithms, extragradient, FB, PP. Two of the most fundamental algorithms for solving VI problems with monotone operators and monotone inclusions are Hrwaard-Backward (FB) and proximal-point (PP) algorithms, see for example (Facchinei Pang. 2003; Rockafellar, 1976). For problem (MI), FB iterates as
U J+a(u: 7 F(uu)))
and converges when F is cocoercive under other restrictive assumptions such strong mono- tonicity of F' + G. On the other hand, PP, for the same problem, iterates as
u = Jr(F+c)((u)
and does not require cocoercivity of F. However, the computation of JT(F+C) is in general nontriv- ial even when J-G can be computed efficiently. Hence, the advantage of not requiring cocoercivity comes the cost of more expensive iteration.
Extragradient (EG) (Korpelevich, 1977) is a classical algorithm that gets the best of both worlds and, for problem (VT), it iterates as
Uk+ 1/2 Po(u: +F(u))
U&+1 Po(u: 1 FF(4++1/2)
This method converges with L-Lipschitz F and only uses JrG for G 06c. It turns out that PP and EG have the optimal convergence rates for the gap whereas they are suboptimal for guarantees on the residual, see Golowich al. (2020).
14

---

for a randomly selected index {L....,n]] n. and suitably selected point Wk. A common choice is to select Wj to be updated only once every couple of epochs. By using this estimator, recent work Alacaoglu & Malitsky (2022) showed how to obtain variance reduced extragradient algorithms Published as a conference paper at ICLR 2024
Variance reduction. The main idea of variance reduction is use estimator F such that (() - F())ll gets progressively smaller as we run the algorithm. There are several differ- ent estimators that used in minimization such SVRG (Johnson & Zhang, 2013; Kovalev et al., 2020), SARAH/SPIDER/PAGE (Nguyen et al., 2017; Fang et al., 2018; Li et al., 2021) or SAGA (Defazio al., 2014; Schmidt et al., 2017). For reference, given F E F, SVRG estimator is written as
F(us) F(wa) (ww) Fi(u;);
with optimal complexity for the gap in terms of both the number of operators n and the desired accuracy E.
Another estimator that is popular for minimization problems is the PAGE estimator (Li et al., 2021), written for operators as:
F(uR); F(ux-1) + Eies. (Fi(us) Fi(u:-1)),
F(ue)=
w.p. Pk w.p. 1 pk:
(A.1)
where Pk and the mini-batch S₁ with b = |S&] are the parameters. Even though this estimator has been shown have unique benefits for minimization, it not find much use for operators for finite- sum case. It was recently used by Cai et al. (2022a) for operators given as expectation. Here we introduce a useful result on the variance bound the PAGE estimator, for our later analysis. Note that this lemma is a slight modification of (Li et al., 2021, Lemma 3) by using without replacement sampling.
Lemma A.1. Let the minibatch Sy. be uniformly sampled from [n] without replacement. Then the variance of F defined by Eq. (A.1) satisfies the following recursive bound. For all k 2 1, it holds that
F[](F(us) F(ux)]( (1 P4) PB) F(u:
(n - b) Ph)
E
(A.2)
b(n
Proof. Let F& denote the filtration that contains all algorithmic randomness up to and including iteration Using the definition of F in (A.1) where F(uu) F(us) with probability pe, then conditional on Fk, we have for all Is > 1 that
E [((s)) 2 Fk
(1-px)E )x)
F Fuu iESt
(F(ug)) F.(ux-1)) - F(uu)) Fr
= -
|| 1((u-1)
(Fi(u,) Fi(u--1)) F(u+)) |7.
(1 Pk Es.
(A.3)
5 SES
where Es, denotes the expectation with respect to the randomness of Sg. Adding and substracting
F(u--1) in the quadratic, and noticing Ess Eies, (Pi(un) Ri(u = F(us) - F ((ug-1),
15

---

Published as a conference paper at ICLR 2024
have
Es,
F Uk 1) + b
(u
Σ
(F((u)) - Fi(ux-1)) - F(ue)l)
iESx
|1 Σ (F((u)) - (u (F(us) - F(ux-1)) |1] F(uu-1)) Fll
Ess
iESu
F(ux-1) - F(uE-1), Rs, [b
Σ
(Fi(us) P.(ux-1)) (F(us) F(us-1))
iESt
Σ (F((us) - Fi(ux-1)) - (F(us) - F(ux-1)) [
Ess
+ (1 Fllx11)l1.
(A.4)
With Sg sampled without replacement according the uniform distribution, have (see for ex- ample (Lohr, 2021, Section 2.7))
Est
11
Σ
(Fi(u)) Fi(ux-1)) (F(us) F(ux-1)) |
iES.
(n n
Fi(u)) F((ux-1) (F(us) - F(u
b(n
1)
n
(n
b)
[F((u))) F((ux-1)11
b(n 1)
n
where (i) holds because |
E[ S [[[ for any random variable X. Using this
estimate on (A.4) and plugging in the result to (A.3) give
E E((i((u)))))) F(ux)]1² Fi
b)
n
$ (1 - 11->:)l]F(u-111 F(uu-1))
Pk b(n
(u:) [u:))
(u
n
Taking expectation with respect all the randomness and using the tower rule, conclude.
B OMITTED PROOFS FROM SECTION (COCOERCIVE CASE)
We first prove the following lemma the useful conclusions of our parameter choices, which essential the proof Lemma 3.1.
Lemma B.1. For le 2 1, les
1 d =
2
(vn + 2)(k + 4)
b= Vn
Wk S vn
4L
lo 44
C
4L
Pk+1
Vk 2 vn
vn+5
as in Alg. and Lemma 3.1. Then, for k 2 1 holds that
A c Ck++ (1 pk+1)
-00
(B.la)
1 Ax
2n
C1+1(1 - Pk+1) (n b))
+
< 0.
(B.
b(n 1)(1 -1+)
Proof. We start by manipulating the last term on the left-hand side of (B. By the definition of b, have 2 /n which implies that
C++ (1 pk+ (n b)
Ck+1 (1 Pb++)((n VT)
Cc+1 (1 Pk+1)
b(n 11 -x+) Vū(n 1)(1 Ax)
(Vn + 1)(1 \xe)
16

---

Published as a conference paper at ICLR 2024
On the one hand, in view of this inequality and v Eq. (B.1b):
1. 32.
the following suffices to guarantee
(1 Pk+1)
vn +1
(B.2)
1 AB
2
On the other hand, with the definition of 17, Eq. (B.la) is equivalent to
Ck+1 (1 Pk++1)
S ck
(B.3)
- A
2A,L'
To get the best upper bounds in (B.2) and (B.3), we set Cx
/n++2 vn+1 and obtain C
2
2A, L
2A, L
thus ck+1
yT+2 Then the inequalities in (B.2) and (B.3) are equivalent to 2
1 PPP+ S (Vn 1)(1 An)
Pk+1
22x
Vū+1 AR+1 Ak)
Vn+2
dE
/m+1k+2
(B.4)
2
where we plug in the definition of Ck+1 for the first equality and the definition of A for the last equality. When ls Vū, have yn+1 vn+2
2 k+1 then it suffices choose Pk+1 E+5 ensure
k+2
that Eq. (B.4) holds. When 2 vn. we have This is the definition of p and the proof is completed.
k+2 v
and it suffices to take pk++1 V v=45"
k+5
Lemma 3.1. Let Assumptions I and 3 hold. Then, for the iterates un of Algorithm and the potential function Cu defined by
17 [[F())) + g+ + (F(us) + gk. u uo) + cs (c((F(uss)) F(uu)l?. (3.2)
C₁ = 2A
we have that E[(x+1] S (1 (1- (L-))) 1, where B6+1 = - (A + 11--)))u----- -nnnnn(uu
uR+1) E G(u++1) and (vn+ 2)(444)
4L
Proof. By Assumption on and the monotonicity of G, we have for 2
nL [ - (1(u))11 & (F(ug+1) + g6+1, us+1 - uR) (F(us) + gk. Uk+1 us),
where ge+1 G(u++1) and gi G(us). Dividing both sides by dc, we get
AgnL [F((u++)) - F1(u)
1 (F(ux+1) g++1, Uk+1 ug) A
(F(u:) gk. Us+1 ug)
(B.5)
A
Recall that by the definition of the resolvent operator and the definition of ug41, have for >
g } (Aauo + AA)u: nf(w))) ux41) E G(uu41),
which lets us rewrite the algorithm updates as
u++1 dg + (1 A n(((uu) gk+1).
By simple rearrangements on this representation of Us+1. we have for k: 2 1 that
U Up Au u:) (u(F(ux) + g++1)
(B.6a)
d (uo - u++1) - i- A (F(u)) + gL+1).
17
U Us 1- A
(B.6b)
17

---

Published as a conference paper at ICLR 2024
Plugging Eq. (B.6b) in the first term in the right-hand side of Eq. (B.5) and Eq. (B.6a) in the second term in the right-hand side of Eq. (B.5), we obtain
A (f(+++)) - F1
< 1- Aι (F(u++1) + Bk+1, Uo - u - Ax(1 Xa)
(F(u)+1) + Bk+1, F(us) + gk+1
- (F((u) + gg, Ug - us) + " (((ux) + ge, F(ux) + B8+1)
(B.7)
A
We next represent the second and fourth inner products in the right-hand side of Eq. (B.7) with squared norms as
"
(((u)) + gk. F(ux)()))))))))))())) + g++11
A
1)
[IF(us)) + BAll² [[F(uu)) gk+1 -B+()]=((F((u)) Bk F(us) gk++ 11²)
2
$ 2dh
1
[IF(us)) + glll [(u{)))) + s++1l?)
(B.8)
and
17
(F(Ug+1) + g.+11 F(u+) gg++1
Ax(1- - Av)) "
2Ax(1- - Ax) (IF(Uu+11)
+g ge+ill 1|2 + [[F(ue) + g++i 1|2 [[(u++)) F(m)))²). (B.9)
We now estimate the second term on the right-hand side of Eq. (B.9) by Young's inequality as
7 [((us) + gl+ill²
77 +
2(1 - Ax) ||F(ux + gk+1ll2
"
2Ax(1 )v)
2)x
S
77
[F(x)) + 1g+1ll2
F((++1) + gb+1ll
2
4(1 - As)
17 ((ux+1) -((n)) F(us))l
2(1 Axe)
We use this estimation in Eq. (B.9) and combine like terms by also using the definition As. which gives
21-(1-
3(I-Aa)
21 get
F(uu+1) + gk+1, F(us) + gu+1)
11 Ax)
|[((u++)) + 8 7 [(uu) + g++1l
< 2 (1 - 2x.)
2dt
+ 17(1 + >xa)
|F(u++1) F(u)))12
2Ax(1 - -Aa))
S 2 (1 - Nx)
11
||F(U ge+1
1)
[[(uu)) + ge+1
2dx
2n
21 (u(441) Fl
[(ux)) F(u))l1
(B.10)
nb
A
where the last step is by Young's inequality, Jensen's 's inequality and Combining Eq. (B.8) and Eq. (B.10), plugging into Eq. (B.7), joining like terms and rearranging give
1+Ax <
1-X;
1 [((u)))) + gx+1ll + (F(ux+1) + ge+1, Us+1 -mp)
1 A
2
F(())
) + g+ll + (F(u:) + +.. ub ww)
2
[((()1) 2 + 2n [I - 12. A
+ ndx
2m
L
18

---

Published as a conference paper at ICLR 2024
Adding Che1 [ F(ux+1)ll -F (e/P-ccclF((u))) ( 1-Ax the definition of Ck. obtain
Flu to both sides, rearranging, and using
1 Cu+1 S Ck +
Ck+1
[[F(U++1) F(u++1)11 (2 -cx) cx)
[1F(um) - F(u))ll
Axx
An
1- Av
1
2m
Σ (u(++1)) F
(B.11)
n>x
We recall the result of Lemma A. which states, for k 2 1, that
((u++() F(u++1))1
(1 Pk++ Pk++1 F(ux) - F(
(1 - Pk+ P
Σ [[((u))) ((
(B.12)
b(n - 1)
We take the expectation both sides of (B.11), and then upper bound the resulting second on the right-hand side of (B.11) by (B.12). As result, we have for k 2 that
1
E[Ck+1]
Av
2m
+ Ck+1(1 Pk+11) Bl]F(us) F(ux)11
< [|Cr]
+
Av
1 dx
+
2m Ax
1
+
Ck+1 - (n b) -b)
Σ
(1 Fr
(B.13)
A
b(n - 1)(1 AR)
By Lemma B.1, we have that the second and third terms on the right-hand side of (B.13) are non- positive. Hence, we get the result after multiplying both sides by 1 - Ak-
Theorem 3.2. Let Assumptions I and 3 hold. Then, for the iterates us of Algorithm I, we have
B[Res++((ua)) (E[ (ux))) 1/2
16L Un u.l
++
In particular, given accuracy ε > O, to return point ug such that F[Resr+G(Uk)) S e, the stochastic oracle complexity of Algorithhm I is Ö( + yulliug-u u.ll
Proof. After iterating the result of Lemma 3.1, we have
k-1
E|C₁] S
II (1 Xr) E(C.].
Since A 2
we have
F44
A-1
1-1 +
(k: 1)1/21
12
II
x
+ 4
(k + 3)1/41
(k: 2A: + 3)
which leads to
12
C.C, v (A: + 2) +
B[C.).
(B.14)
Next, bound [ECC), recalling the definition in (3.2). First note that F(u)) F(ui). know that C₁ does not involve any randomness, i.c., [C[ = C₁. and have
17 [P())) + gill + (F(u)) + gg.uu u1 un)
C = 2
Further, by the definition of uj we have
J - Up 2
F(uD)
" F(un)
gi-
2
2X
19

---

Published as a conference paper at ICLR 2024
With this, obtain
C "/ [F(u) + +1ll + (P(u)) + +11, u1 - -uo)
2
2 [F(uu)
+ gi 1|
" (F(u)) g1, F(u)) g1)
2
Decomposing the inner product term above, by adding and subtracting F(u,) in the second argu- ment, we obtain
2 C
[(())) + gill [[F())) + +g
" (F(u)) + -1, F(u)) F(ui))
2x1
2
(F(u)) +g, F(u,) - F(un))
2
Plugging in the definition gi
2d1 (uo u1) F(uo). obtain
7
C1
1]
(((u)) (((u))F((uu)
+
2
(uo F(u,)(u)) - F(uo)
2\1
7
[F(ui) F(u))
(F F(uo), u uu)
2
(8)
where (i) by --cocoercivityy of F and 2x= 167 +.- we obtain E[Cx] S in view of (B.14).
Recalling the definition of C₁ and noticing the term cj [F(u)) F(uu)] is nonnegative, we have
(
E
([F())) + gglll (F(u)) + gk uu un) S..
Since u, is solution to (MI), there exists g. such that g. E G(u,) and F(u.) + g. = -0, then we have
(F(u)) ge, us un) (F(ug) gt. us u.) (F(ug) + gk. u. un)
(F(us) + gi. u. un)
(4)
- [[F(u))) + Bxil|uu - u=ll IV
where we use the monotonicity of + G for (i) and Cauchy-Schwarz inequality for (ii). Noticing that F(u)) + g=ll] ([]]) + gx |1']) 1/2 by Jensen's inequality, then we have
17(k + 4) B F(u.) gx < d u. (B(IFFF)()))) + 1x 1/2
4
Completing the square and then solving for the quadratic gives
+g (o 1/2 =18] F(u))
[IE]
+ ge 12) 1/2 16L Un u.
Given E >> 0, to return a point such that (E]]] + 1x 1/2
< which also guarantees that E[]] [((x) + gx |] S by Jensen's inequality, the total number of iterations required is 167] ug ua 1. To obtain the total number of stochastic oracle queries, let m. be the number of
individual operator evaluations at iteration (in which we compute uk+1 and F(u as Alg. 1) for l: 2 1, and M = 2n + ΣK-1 K-1
be the total number of individual operator evaluations to return ug. Conditioned on the filtration F& that contains all algorithm randomness up to and not including iteration k we have for & >
k+5
4
if Vn.
E mm
FR] = PR++TT + (1 12b
k+5
1+5
if 2 Vn.
/at5
20

---

Published as a conference paper at ICLR 2024
Taking expectation w.r.. all randomness and summing from lc 1 to K, obtain
E[M]
2n
mk
Lyn
K-
2n
E mm
mm
k= T/
Lvn
2 2n + 4n
Σ
+ 2[ +6/n( Vn)
+
96 96 -u.l =((n+ VnL [n u.
S 4n 44/ 4n log(on/ 5)
8
which completes the proof.
C OMITTED PROOFS FROM SECTION (MONOTONE & LIPSCHITZ CASE)
Proposition 4.1. For any fixed 0, let Pa (u) u (u) If [P))l TE for some > 0, then we have ResF+a(ū) S s with ú PT(u) = ())))))
Proof. By the definition of resolvent operator, we have
u- - E ( +n)((u) = u E u u- (u)
= 0 e (G(
So have [ + ng| S ne, thus (()) gl S e, where g = ! (u - -) -)- F(u) E G(u).
In the rest of this section, for readability, we first provide, in Section C.I. the proofs for the conver- gence of Alg. 3 from Section 4.2. Then, in Section C.2, give the proofs for the convergence of inexact Halpern iteration from Section 4.1.
C.I APPROXIMATING THE RESOLVENT
Lemma C.1. Let F: Rdd - Rdd be monotone and Lo-Lipschitz in expectation in Assumption 2. Then for ut E RRd, the function 1-strongly monotone and (nLQ + 1)-Lipschitz in expectation.
("( = F) + -u+ defined in Eq. (4.3) is
Proof. Let L = LQ for brevity. For ut E Rd, strong monotonicity clearly follows since for any u v E Rd, we have
(u; (v;u"))
= u.) - u v) + u v|2 2 | v
where we use monotonicity of F for the last inequality. Further, since is L-Lippchitz in ex- pectation with oracle Fg Assumption 2, we have (u; ( + ut such that Eş- (u; = (u) + u- ut = ut) Then for any v E Rd
Ee~ F1 (" u - (P(v:u+)]1
Eg-ollInF (u) 1)FE(v) +u --vl
E (u( + 2y FG(v), v)].
Using L-Lipschitzness of F in expectation and Cauchy-Sehwarz inequality for the quantity above, we obtain
E [ Fv;
I 21 + 1)]lu viI 27/lu v FE(v)
_ 11 + 2 1)) -
v/1= (n 1
where (i) due to E [Ş(u) (v()))
< L//u- v|l by Assumption and Jensen's inequality.
Hence, F (u; ut) is [ 1)-Lipschitz in expectation. This finishes the proof.
21

---

Published as a conference paper at ICLR 2024
We move the convergence proof for VR-FORB of Alacaoglu & Malitsky (2022) which in- corporates the loopless SVRG variance reduction technique (Kovalev et al., 2020; Hofmann et al,, 2015) into FoRB method (Malitsky & Tam, 2020).
Theorem 4.6. Let A: RR_ + I be monotone and La-Lipschitz in expectation with A = Ei=1 A.. Let B: Rd = I2 be maximally monotone, and A + be p-strongly monotone with
J and V. = (A + B) B) (0) + 0. Given > 0, Alg. 3 returns VM with [ - v. S E²
in [14(n + viLLA) log vollvo
iterations and O((n vTILA log IVo-v.l oracle queries.
1
Proof. First, following the proof of (Alacaoglu Malitsky, 2022, Theorem 22) with the addition of strong monotonicity of A + B (ef. the equation after Eg. (56) in Alacaoglu & Malitsky (2022) which had used only monotonicity), and taking expectation w.r.t. all randomness on both sides, we
yp(l-p) and a
plug in our parameter choices 7 2/.4
and then obtain
(1 11-p-2ppm [[] v [[[[[[++ v. 11 p
[[ w
+ {Av - A(wx), v. - Vk+1)l
< (1 p)l - v= Blllw - -v.1l²] + pB[lIv v 1
(C.1)
+ (TE((A(VA)) - A(w 1), v. - -va)l 2 Blllv - -
1 P v - v*l1
To simplify the notation, we define
1
-BlllVK v=.13].
ag 2
1
P E[[IvE - v= + E||ww B - v.11 + ++pBlllvx - -
by
2
+ 2T 2T([(v) - A(w:-(w)))))) vn)]-
We first note that bk 2 O. Indeed, using Young's inequality, Lipschitzness of A and the definition of T in Algorithm 3, we have
12T (A(ve)))) A(wa-1), -va) S 2r SrT.allve W W
-v.ll
< 47
1
1|V* w
[[v v2
2(1 p)
2
P Vi - W 1 +
1 lvv v.
(C.2)
2
2
Then we have, by plugging in the definitions of ag, by in Eq. (C.1) and discarding the last term the right-hand side, that
be+1 S p)a + by "EllIvE w/ p p 4Tp)ax41
(C.3)
For a constant e > 0 to be set later, let us write the right-hand side of Eq. (C.3) as
- p)ap)a + by - (1 c)ax + (1 c)bu + eBlll Wr v + pcl Vv 1
+ + A(wx-1). v. - va)]]-
(C.4)
By using the definition of W4 in Algorithm and the tower rule, we have
cF|l| || [c Vı v. [1 + 2cBlllvx w
[| Vı v..l + 2c(1 E]] w
Combining this estimate with Eq. (C.2), and using trivial facts that cp S and 1 - S to further manipulate Eq. (C.4) gives
(1 p)ax by < (1 (1 c)az + c)-c)ba- 5c [[ vv.13]
7c
E B[Ilv 1
7c
< (1 6c)aa + (1 c)bb +
- Elll w1-1
(C.5)
2
22

---

Published as a conference paper at ICLR 2024
We now let 2 s 2 and use the estimation Eq. (C.5) in Eq. (C.3) get
(1 - + 4Tp)aR+1 + bb+1 S (1 + 6c)ax + (1 c)bx-
(C.6)
Let us also set 6e S 37 and then
(1 p 4T/))R+1 + bb+1 S (1 3T/)aa + (1 ccbbk
TH
(1 11p 4Tp)az +(1 c)dbk
1 p 4Tp
< min
{
+ 4Tμ' ct) ((1 - + 4T + bb)
TH
where the last step used nonnegativity of by. Let us also define min { 1 By iterating the inequality and using by 2 O, we have
(1 - p dTpjax s (1- min { (T+ TH
c)) (11 p 47p)a0 + bn)
(C.7)
4T
thus
Elllv 2 min ( ( 4TT
TH
ct) (aD
+ 4T bo)
Further using Vo Wo w-1 1 (see Alg. and definitions of agg bu, we have
1 - P
ao + 1 - p + 4rp
bp
lio - -v.12 + 1 - p 47
vo
v.l12
+ Vo -v.1
2
2
(8)
2 2
p
+ 2 +
Iive -v.11
Vio -v
1 1-
where we use 1 p 4TH 2 - p for (i). So we obtain
Elll v-1l < (1 min
I TH
ct)
44- 2p 1-p p-p
|lvo vol1?.
4TM
Given 0, we now see the exact number of iterations guarantee TE[| u.l13 11 E². We have
B Bl[VE v= < (1 min {
TH 1 4Tp
c)) k4 - 2g
|lvo - v
p
< 6exp
(- min { TH
c)kk lIvo v.11?
(C.8)
4rp
where we use
1 and assume 2 2 without loss of generality, thus
+ 4TP log
V6lvoo -val] max
1 4Tp
7 2
v6]lvo v=
k: 2 2 max
log
T/
TH
D THi
E
using e min
{ } Plugging in the choices that p = and T
/p(1-p
In-I
we have
21.A
2nl.s
2nLA 7n, 4nLa 2 2 max { 4+ nVn - pVn - log
V6ll Vall),
(C.9)
E
For simplicity, we assume without loss of generality that 2 then we have AnLs
TvALA
#vn-1
#
So it suffices to choose & = [[14(n + vnl..) log yoll vo vv Further, we notice that Alg. 3 has
constant expected per-iteration cost pn + = 3 by 1 so we have the oracle complexity to be
((1 (n + VoLA log [|v-v_]]
23

---

Published as a conference paper at ICLR 2024
C.2 INEXACT HALPERN ITERATION
Lemma C.2. Let be monotone and Lipschitz, and G be maximally monotone.
Assume that
conditional on the algorithm randomness up to iteration we have E& [ S
("ulll
(k+2)
[ue 1u4-JJpPpp (M(Fic)(())) for all k 1 and Ellleol1%]
(uo)l" Then the iterates ug generated by
[b+2) Alg. 2 satisfy
Blllu - 11.113] S 2/ un u.ll
(C.10)
where u, the solution point such that Jy(F- (u.) u.
Proof. By Eq. (4.1), definition of pa and noticing J Jn(F+G) ua, have
ug u.ll
1 (ug u.) + (1 -1- (1-
In (u.)) -1-- -----e---
Ak-1 uu - uu + (1 A 11 - + ( ill (10 x 1 - u.l + -
- u.ll (1 ---
where we use the triangle inequality for (i) and (ii) is due to nonexpansivenesss of resolvent, Iterating this inequality until i 1, we obtain
b II
Iu - -u. uul1
1 -
AA-1 +
(A--1
(1 )ل-1)) 11 u.
==1
1=1
j=++1
Tn
|le
II - X3 {-ا1))
(4) [2]
Plugging in
142 gives
i+1
k
i
Tnj
1,
T
k +
j
+
k +1
j=
and consequently,
[u u.ll
S Un
u.
Σ
+
Squaring the terms on both sides and taking expectation w.r.t. all randomness on both sides, we obtain
E [
u. [1
< E Il10 --.ll
+
1:
3 |un
3
2
u.ll
112
E
[ee_
(h: 1)2
(1) 3 | u. 2 +
3
E
2 le; 112]
1: +
where we use Young's inequality for (i) and the fact (E zz for (ii). Since [1]
< k E
1==1 x. for any IR
[[
- J.( r+0 (wx) )|
for all k 1. and consequently,
(k+2)
(k+2)
24

---

Published as a conference paper at ICLR 2024
B|||e/|
3|l (u:p((u:)]) I (x+2))
by tower rule, and E|]leo||?]
(")))
we have
27
3
|1 P 11111)111
( )l?
|||| Uk u. 11 S
Uu u=ll
++1
(i 1)
9 + 1)
3
B||| (u;)|l
(P*(un) 1
s U00 u.
k+1
(i 1)6
9(k + 1)
Noticing that P"(u,) = 0 and Pr is 2-Lipschitz by nonexpansiveness of the resolvent operator, we have for 2 0
(u,)) (u:)) - Pd (u.)ll < 4 4||u u.
which leads to
3 u.ll
12
Billu u; - 1.1
4 4 u. u.l
Billue- u..1²] S
2 2
Uu
(C.11)
k
1)6
9(k 1)
We claim that for all 2 1:
B| uk u. uul1 1 2 - u.
We prove this claim by induction. First, for the base case k 1. we have by Eq. (C.11)
[|||u u..l3 - 2 I 1.112 + In u. 11 < 2 un u.ll?.
Suppose that [[[ -u.l3]]
< 2 - u.ll for all < 1, then for the case 2 2, we have by
Eq. (C.11)
3
12
E u; - 11
4/|uu - u.
E Blllu
u
u.
1 <
2 Imo
12112 +
k+1
(i 1)6
9(k 1)
24
Un k +
u. 112
20
4 4 u.
VA
u.l
1) +
76
9(k + 1)
(0)
2
u.112
where we use & and
E
for (i). So our claim holds.
945
Lemma C.3. Let F be monotone and Lipschitz and let G be maximally monotone. Assume that conditional on the algorithm randomness up to iteration k, we have [x[[] < [|P"(uu]]** for all k and [[]]eo||a]
(x42)s
[PP(un)
Then for the iterates uy generated by Alg. we have
27
E(Ce+1] -B[c]] < 16||uo 1
(C.12)
(k: + 2)2
where
k(k + 1) (ux) (K + 1) (P"( u 10--m un)
C
(C.13)
2
Proof. By Eq, (4.1) and the definition ex. we have
Up+1 Up
Au - u+) (1 PT) Au)es,
(C.14)
d (mo - ub+1) - (uu()x -kk
Up+1 - Ug 1 Ae
(C.15)
25

---

Published as a conference paper at ICLR 2024
Noticing that Pd is -cocoercive by the nonexpansiveness of the resolvent operator and using the equations above, we have
1 } Pd (ux++)) P*(())]l - (P*(Ux+1) - P*(ux:; uk+1 us)
dk (P"(ux+)): up -ux+1)++1--00 (P" (ux+1). P*( + ck)
1 Ak
d (P"(ux) un un) + (1 Ax) (P"
In this inequality, expanding (1="( - (* and rearranging the terms, we obtain
d
(P*(uu+))1|+++ >
(P*(ux Us+1 uo)
$ [
1 - 2u > [In"()))]? + X (u:), un uo) + (ex, (1 - (x) - ("*
Plugging in A k+2
and multiplying by (k+1)((++) on bides, can bound the consecutive
change of Ck below
(K: + 1)(k+
1 p 1:k +1 | |P*(uz)1
Ck+1 -C Cx
(k: + 2) (u 1), Ub+1 - uo) -Ik+ 1) (us), up uu)
Eks k+1 pT((us pd P*
(A: 1)(k 2)
(C.16)
k
Noticing that (*( = and P" 2-Lisschitz by nonexpansiveness of the resolvent operator, we have
k: +
h +
("x( - ('((u+1)) =
(P" (us) - P*(())) (u PP
ek
Ck.
+
k +
1: +1
2 c/ 1l
[u u. | u.ll)
1: +
2
(k + lex12
+k+ 2) (1 - u. |ux+1 -u, 17).
where use Cauchy-Sehwarz inequality, triangle inequality and Lipschitzness of pa for (i), and (if) is due to k+1 1 and Young's inequality. With this and by taking expectation w.r.t. all ran- k+2
domness on both sides for Eq. (C.16) and using the results from Lemma C.2, we have for k 2 1
k ++1 1
E[C++1] - [[C,] < (K 1)(k + 2)
(ex:
P" ("(()) pn (u(++)))
k k
2
(k 1)(k + 2)E
(I: + 11x
(k: + 2) (lug -u. || 13)
( 4 u.113 [1a]
[E[l u. |1 [|]]++|lluaa B4ll u..l91)
(I: + 2)
(k+ + 2)
( 16 un u.
(A: + 2)²
where (i) is due to Bi[le [?
[PP(" (k+2) and [ux)) S 4llux -u.12 and Blllue
u.|l3 < 20 ug - 12 for (ii).
Theorem 4.2. Let Assumptions I and 2 hold. Then, for the iterates un of Algorithm 2, we have that conditional on the algorithm randomness to iteration k, and
Ex [|] < (P,))
(x+2))
P|] < (B]] 1/2 7 uo u.
k
/ Moreover, given accuracy to return a point uk such that [[]] Ill S ne with 17 I.
the stochastic oracle complexity Ö(n ym B.
26

---

Published as a conference paper at ICLR 2024
Proof. We first prove Rx [/e//// [2] - (k+2)* by our number of inner iterations in Alg. 2. Given and using the convergence results in Theorem 4.6, we have our subsolver Alg. 3 with initial point uN returns Jn(F+c)(u)) such that [( - In(F+G)
ER > O, noticing that ( |lux (
of with number of iterations
v6]]P"(ux]]
14(n+ + vi(mI + 1)) log
Ek
where we also use that 1 is 1-strongly monotone and (nLL + 1)-Lisschitz in expectation (see Lem. C. So it suffices to choose M₁ 2 [56(n vn(nI. 1)) log (2 + 2))] to reach the accuracy
Eg = (u=21
(k+2)*
Then with Assumptions I and 2, we have that the assumptions of Lemmas C.2 and C.3 hold. Sum- ming up Eq. (C.12) Lemma C.3 for k 1, 1,....k. k gives
1
B[C]] - B[G]] + 16 un u.
B[C]] 7| - u.112 (C.17)
(i 2++
Next, we bound E(G]). Recall that pa 2 ccccoercivve and u1 Ug - (u
co by
Eq. (C.14). Then, we have
(P"(u:) P"(())) i1 uo) 1
Pd P*())) - (uu)l)
2 PP'() v (P)( P*(())): - (ou, pd (u, pd (ua))
which leads to
C | +22 u1 un)
- P*((n)) + eo)
S (eo, (uo) (n)))
(C.18)
Note that
(eo, ("o))) - 2P
= 2 (eo. (un( - pr (eu, ("o))
K 3 3/ea| 2
(1)
1
pn (u,) )1 2 + _ 11))
3 |/eull 2 + 2 un un + 1 (un)))
(C.19)
where we use Young's inequality for (i): and (ii) due to pe being 2-Lipschitz. For the second
term in the right-hand side of (C.19), we use in u P j and Young's inequality again, and obtain
2|| unl1 2|
PTT + e < 2 _ + ア (0)))
2
With this, (9.19) becomes
(eo; (uo) - 2P )} - ||eo|| 1 + || 11²)
Taking expectation w.r.t. randomness on both sides and noticing that [|[|/// [P] < (uo))) < 4|| un u. 1 we have
and
27
El pM (*u)) (2 uo u..1?
which, in view of (C.18), leads to B(C,] E[(e,, (*((u) 2P }>}] 5/ un u.
As a result, we obtain in (C. 17) that
C < E(C] + 7 un u. 2 12 Un- u.ll?
(C.20)
27

---

Published as a conference paper at ICLR 2024
On the other hand, since P" is monotone and (", = 0, we have
(P"( us -uo) (P" - (u,),, up -u.) (Ps) u, - uo)
2 (P u. - uo)
- || (u=) u.ll u,ll
where we use Cauchy-Schward inequality. In view of the definition of C2 (3.2), the last estimation gives us the bound
k(k + 1) B|| Pd (ux)) (k: 1) up u. (ux))l(
E|Cx]
Using this bound in (C.20) gives
k(k + 1)
B [" (u:) 3| (A: 1)llum u. [B]] )1l 12| up u, u.1
2
By Jensen's inequality, have
k(k + 1)
2 E| (")
[1 < (A + 1)(luo u. u.I((E||PP (u:) 11 1/2 + u u.11?
By the larger root this quadratic inequality w.r.t. ("]]) (1 1/2 we obtain for A: 2
(1x))1"() 1/2
U1 u.ll
[n u.l1
24 Un u. ||
+
k
12
k(k + 1)
Un 2 +
u.ll
2/6llum uu u
k
Vk(k + 1)
7| Up u.ll
k
where (i) is due to the elementary inequality v la+bs V
Hence, guarantee that Algorithm returns point ug such that [ux)) S 17 which implies P" (ux II] S ne by Jensen's 's inequality, we need K =
70 outer iterations.
We now look at the cost of each inner loop to estimate Jn)F+G) (ux). Notice that for the subsolver VR-FoRB, take the number of inner iterations Mj. [28 max +=++((((+++) log (2(k+ 2)) with the constant oracle query cost (in expectation) for one iteration of VR-FoRB. Hence, we have ((n + vn(nL= 1)) log(k: & 2)) oracle queries for k-th inner loop. Then for the total number of oracle queries, we note that
K
Σ ((n vT(nI + log(k + +2) =0(( vn(gI 1)) K log(K (K + 2)).
Plugging in the choice of K and suppressing the logarithm terms, we obtain Ō(n + vn(nt + ())( + 1)) oracle complexity. Taking 7 = == we have the claimed result.
C.3 ESTIMATION OF THE OUTPUT
Corollary 4.3. Let Assumptions and 2 hold and ler ug be as defined in Theorem 4.2. Then, for Hont VR-FFRB(uuK, [42(n vn) log(19m)) Id v/( G) uu Q) with 1) L [ < 28.
The lotal stochastic oracle complexity for producing Unut is Ö (n+ Tull|uo-uu1|
Proof. We combine Lemma C.4 and Theorem 4.2.
28

---

Published as a conference paper at ICLR 2024
Lemma C.4. Let Assumptions 1 and 2 hold and ug be such that (EI pd (u (1))) S me with
v L. Then, for Vout outputted by VR-FoRB(us, M, ld + 7(F + G) uz), we have that
7 =
c - 28,
(C.21)
where M- = [42(n + vn) log(19n)] and complexity of this step is O (n log
u [ < ne, and consider the uniform sampling for brevity. Note that we have in this case A(u) nF(u) + u (u = (u) + u ug and B = s/.. By the update rule of VR-FoRB (where we use the index t for the inner loop to prevent confusion), we have a 1 p and then for t 2
Proof. Let denote _ + (u:), (E[I)*((::) (u=)) )11)))/22
V++1 + BB(4(+1) 9 (1 - p)v; + pw: - -T((v))
1 1 p (v, vet1) ((w. Ve+1) A(v++1) A(v.), - A(ve+1) + B(v(+1)
where Alv.) = A(w)) (w---) + Av(vi) and we also have the implicit definition 7/g++1 (1-R) v + fw, - A(v,) - +vi+1 (( = r)G((v+1) since B = nG..
By using the definitions A(u) = (u) + us, A.(u) (u) +u - uk. A(ve) = nw.()))++ W; u (W W + (vi) + Vi and rearranging we get
1 1-p --p(ve -v, v(+1) _ [(w, Ve+1)
F(((+1) 18++1
- (
+ (W - -v.)
(ux v.) -(w-1 w.).
Note that we have B[[lw; -vell E1l w,-1 and [[[| W Ill pP ww-1ll]
by Alg. 3 and the tower rule. As result, triangle inequalities and Lipschitzness of F give
1 "B[[Iv v++ill + C + nL B(l=) well] s
([Resp+o(V++a)
nLEIIVv - -w-1lll + E[llv, uill Ill + E[| -n - -
+ Blllw: - -wi-1ll
< - + nLF + +1)E[[lv, -v++1ll
(1 p)P + (1 - + p) ww-lll
+ B[[| B[+l - u [] + Blllu: - ufll
I 12 -1 + + + 3) E + ne.
(C.22)
where the last step is because LF I L and given accuracy È > 0, the output of VR-FoRB gives for t == M
BlIl++11 - uf Blll+41 - - B[ll, -
(C.23)
We now bound the oracle complexity and the number of iterations to get these bounds in (C.23).
Denote by E, the expectation conditioned on all the randomness up to and including u, Recall that A is (nL + 1)-Lisschitz in expectation and A + B is 1-strongly monotone, and we have our \p(1-p parameters to be p = +. = v and Tμ 2(
- 1. Then following the same 2n(vn+1) 2n
T.
derivation from Eq. (C.1) to Eq. (C.5) in the proof of Theorem 4.6, we first do not discard the last term on the right-hand side of Eq. (C.1), 1), and obtain (ef. (C.3))
(1 p 4Tp)a441 + b1t S (1 p)at + by
2 Ex I|lvv
w.-1 1|
1 - P Ex
V++1 (1
v.1l
(C.24)
2
2
29

---

Published as a conference paper at ICLR 2024
Further, without using p in (C.4), we have (cf. (C.5))
(1 - p)a bt < (1 p + 6c)a + (1 ())c [ccp 2c E& E&lllve wi-1l191
3pº + 4p
$ (1 - p+ p + (1 -c)bb-
Ex [lllvve wi-1l19),
14
where the last line used c S 4. Combining with (C.24) gives (cf. (C.6))
(1 1-p + 4rp)a4+1 + b S (1 6c)oz + (1 - c)bb
3p
p) E Ex[llv= -
1 P
Ex [[[[v - vell
14
2
(C.25)
With the same derivation as obtaining (C.8), we have after using 4т 2 0 and 4rp S 2p
- P Ex Exlllve+1 - vell + 3p(1 p)
E& - w + 1-
Ex (il1 - 1
2
14
2
(-ming min { (1+4TH 4TH ct + +1)+ -u
T/p c)
- 2
exp
where we also use that the solution of the inner subproblem ug. Unrolling the expectation and using that FoRB is initialized as vo = we have
3p(1 p)
(B[I|v/-1- -v E[[l w. B[[lv++1 -uğ 11)
14
VA
exp
- minn { 1 4Tμ
TH
el 1) Blllu: - -ugll
2
5
exp
min {
TH
ct(( 1) n²=²?
(C.26)
2
+ 4Tp'
where the last step is by Billux )n( (ux) || Elllu uill I 17222 Hence, in the end of Theorem 4.6, we have that (C.23) holds in 7 (n vn(nn 1)) log( 35 3p(1-p)e ) iterations
and with complexity O LE as 17 - In particular, we choose È
DE
2r 143
on (C.22) we get (C.21), and also have & S 10 +6. Plugging in this value
AnL(va1)) +3L+ Vi
Vn(n-1)
gives the number iterations as [42 + nn) 1og(19n)] and overall complexity as Onn
C.4 PROOF FOR THE COHYPOMONOTONE EXTENSION
Corollary 4.5. [Cohypomonotone] Assume that F is maximally p-cohypomonotone and L-expected
Lipschitz and G 0. Given 0, Alg. 2 returns point ug such that (Bil)P"(uk)]] (1x)) 1/2 S ne
[1 + +1) stochastic oracle complexity, for any positive n such that v p min 2' n With 1) as before, this corresponds to p < min
with ((n+ vū 1 )
2L
Proof. By definition, we have that F is maximally 7 g-cohypomonotone. When 2 < 1. have that Jnp single-valued and nonexpansive (Bauschke al., 2021, Prop. 3.7, Thm. 2.17). Subproblem in this case is finding such that
7
0 E (ld + ( - u
Since F is p-cohypomonotone and Lipsschhh we have that
(F(u) - -F(v), u ----vv v) 2 p - 2|
As result, our subproblem (1- )p) strongly monotone and (n + Lippschct in expectation
(see Lem. C.
30

---

Published as a conference paper at ICLR 2024
In summary, to ensure that the resolvent is nonexpansive, single-valued and the subproblem is strongly monotone, we require
L - 1 and pnL < 1 7 2
Of course, these bounds are optimized with 17 1.p However, this choice of y does not give the best oracle complexity with finite-sum form. In partic- ular, by using a standard deterministic extragradient algorithm as subsolver in framework (see e.g., (Diakonikolas, 2020, App A.3) for a proof for extragradient, with additional adaptivity that one can drop for simplicity), this would give complexity Ô nLg (T- Using a variance
v2 which leads to the requirement p
V2LF"
reduced solver with v2 does improve this.
I.P
Hence, we pick 7 yn I as before. We can then use the same estimations as in the proof of Theorem 4.2 by only changing the strong monotonicity parameter for the inner subproblem which affects the complexity of the inner subsolver and hence the final complexity.
C.5 DETAILS ABOUT REMARK 4.4
We now derive the bounds for LF and Lo for this important special case covering matrix games and linearly constrained convex optimization.
It is straightforward from the definition F(u) -14 that
LE ||||2 2--
Following Carmon et al. (2019) and Alacaoglu & Malitsky (2022), we derive for any u = (x)
my
R Fe (u)
A x5
(2)
(2)
A&y:
x, 1
1=1
|
(3)))
||,1))(2)
j=1
1122
m22
||||| 2
(y:)
)x
|
2
In view of this derivation, linearity of Fş and Assumption 2, we conclude that
Lg ||
(C.27)
As result, we have in this case that LQ V (A)LL.
In our analyses this section, we use the simplified assumption that computation of F; n times 1. This is the most natural assumption
cheaper than F a. >> F, which gave the choice given a generic F. This was the setting also in previous works such as Carmon et al. (2019); Ala- caoglu& & Malitsky (2022) when dealing with general F with finite sum form. On the other hand, our bounds could have been also written in terms of p (the probability for full operator evaluations for WK+1 in Alg. 3), in Alacaoglu & Malitsky (2022). In this case, the general form for in terms of the costs of F and F,, denoted for simplicity as Cost( [F) and Cost(F.) would = Cost( Ft) Cos(FF)
However, for specific examples such as matrix games or linearly constrained optimization, we would use p 2mimg given dense matrix A. We refer to Carmon et al. (2019); Palaniappan & Bach (2016); Alacaoglu & Malitsky (2022) for more details about this representation. This choice gives rise to the claimed complexity improvements in Remark 4.4 in view of the derivation Lp and Lg provided above.
31

---

Published as a conference paper at ICLR 2024
D EXPERIMENT DETAILS
In this section, we provide further details about our experiment setup. For the matrix game case (also mentioned in Remark 4.4), we solve the problem
min max (Ax;y) + damn (x) + dam2 (y) XER yERm2
for A E Th m the simplices A mh A where á is the indicator function. We use the policeman
and burglar matrix from Nemirovski (2013) with mi m2 500, where the entries given by
Ag z.(1 exp(-0li jl)) with = 0.8 and z ~ A 1mr): For the computation of JnG, which corresponds to projection onto the simplex in this case, we use (Condat, 2016, Algorithm 1).
For the test case of Lagrangian of quadratic program, we use the saddle function from Ouyang & Xu (2021) as follows
min max =x Hx h hxx x (Ax b,y), XER yER 2
where my
my = 200,
2A T and
-1 17
0
1
0
1
1 4
1
A
IR M
X
b
m
E
-
1
4
0
Also, for Alg. 2, we directly measure the residual on its output point ug. without doing another approximation step in Corollary 4.3 for simplicity. This is guaranteed by R|]] P"(u)]]]] = E| El - J,(FF)) (ux) Il]] = O (k)), and ug can be good empirical approximation of Jn(F+G)(
as the algorithm proceeds.
E FURTHER DISCUSSION AND PERSPECTIVES
We showed complexity guarantees for variance reduced algorithms that improve the best-known re- sults for minimizing the residual in finite-sum monotone inclusions. Our improvements mirror those that were shown for the duality gap for finite-sum VIs the recent literature; see e.g., Palaniappan & Bach (2016); Carmon et al. (2019); Alacaoglu & Malitsky (2022).
Our result for the cocoercive case is with a direct algorithm whereas for the Lipschitz monotone case, we have indirect algorithm. In particular, our algorithm in the latter case works by solving randomized approximations to the resolvent, which can be seen as an inexact Halpern iteration (Di- akonikolas, 2020). An important related open question is the development of direct algorithms that achieve the same complexity guarantee that we showed for the Lipschitz monotone case, which is optimal up log factors.
is worth pointing out that our results and this open question closely resemble the recent develop- ment of improved duality gap guarantees for finite-sum monotone VIs with variance reduction. In particular, it was the work of Palaniappan & Bach (2016) that provided the first variance reduced variational inequality algorithm which was indirect procedure based on the Catalyst proximal backward algorithm. This work already showed the benefit of variance reduction compared to deterministic algorithms for strongly monotone inclusions and monotone VIs with bounded domains by using standard reductions using regularization.
point framework and forward-backward
direct algorithm for the important special case of matrix games was provided by Carmon et al. (2019). At the same time, this work also handled the general monotone VI case with an indirect approach. Other direct algorithms, given in Chavdarova et al. (2019) for the strongly monotone case and in Alacaoglu et al. (2021) for the monotone case, were simple but did not improve the com- plexity bounds compared to deterministic algorithms. The work of Alacaoglu & Malitsky (2022) obtained direct and single-loop algorithms with complexity improvements for general monotone VIs, nearly five years after the indirect result of Palaniappan & Bach (2016). An alternative direct approach focusing finite-sum saddle point problems was also studied in Yazdandoost Hamedani
32

---

Published as a conference paper at ICLR 2024
& Jalilzadeh (2023). Soon after the direct algorithms, matching lower bounds for the duality gap were also provided for finite-sum monotone VIs (Han et al., 2024).
In this context, results for the monotone Lipschitz ance reduction for residual guarantees. This can be seen as corresponding to the results of Palaniap- pan & Bach (2016); Carmon al. (2019) that had indirect algorithms with complexity improvements for the duality gap for monotone VIs. What remains to be done to complete the picture for finite- sum monotone inclusions and monotone VIs developing direct algorithms with tight complexity guarantees for the residual, similar to the process that we have seen for duality gap guarantees.
provided the first improvement with vari-
33


Reviews:
[{"review_id": "eUS2jSGjCf", "reviewer": "Reviewer_P51Q", "summary": "The paper clearly presents two algorithms for monotone-inclusion problems in different conditions with the new analysis that improves oracle complexity.  In the cocoercive setting, the paper uses a single loop Halpern iteration with variance reduction to achieve the oracle complexity of O(n+ \\sqrt{n}L/\\epsion). In the Lipschitz case, the author uses the inexact Halpern iteration and computes the resolvent approximation by VR-FoRB method. It achieves the oracle complexity of $O(n+\\sqrt{n}L/\\mu)$.", "questions": "1. Can the author propose a framework to unify the two algorithms? Two different algorithms for two different conditions are not concise enough.\n2. Can the author describe the experiments more clearly? Like providing more details of matrix games and other tasks?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposed two algorithms in the cocoercive case and the monotone Lipschitz case, respectively. \n2. The new algorithms improve oracle complexity by a factor of $\\sqrt{n}$ compared with existing methods on some conditions.\n3. Numerical experiments are presented to further show the improvement of the new algorithms.\n4. The paper is clearly written and easy to follow.", "weaknesses": "1. Some concepts. E.g., monotonicity, maximal monotone, are not explicitly defined in the paper, which slightly impairs the completeness of the paper.\n2. Both Algorithms 1 and 3 are variants of existing algorithms. The Algorithm 1 is a simpler version of Cai et al. (2022a), while there is not enough comparison to present the novelty and advantage of the new algorithm. The Algorithm 2 is a combination of inexact Halpern iteration and VR-FoRB (Alacaoglu & Malitsky (2022)), which still doesn’t present much novelty. Although there are improvements on the oracle complexity bound, it seems that they mainly come from the analysis side and assumptions side instead of the algorithm side. Also, it would be good to discuss whether the improvements stem from specific assumptions.\n3. The new oracle complexity bound has an additional term of $n$. It may be beneficial to discuss why the new analysis introducing this term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "vEyldMFaPg", "reviewer": "Reviewer_wjm9", "summary": "The paper addresses game-theoretic equilibrium problems pertinent to adversarial robustness and multi-agent settings, by studying finite-sum monotone inclusion problems. The authors propose variants of the Halpern iteration with variance reduction, yielding improved complexity guarantees for problems where component operators are cocoercive or Lipschitz continuous and monotone on average.", "questions": "Kindly address the points raised above, which are briefly summarized here:\n1. **Clarity of Presentation:** The exposition is particularly convoluted and indirect. It could be re-structured for better comprehension. \n\n2. **Comparison with Existing Literature:** The paper should offer a clearer and more direct comparison with existing works. Such a comparison would be more insightful if it included a discussion on how the assumptions differ from those in the literature and the impact of these differences on the results. Additionally, the citations of relevant literature regarding expected Lipschitz continuity and variance reduction may require a review to ensure accurate representation. *The paper should address whether those cited works indeed operate under analogous assumptions or if there are misalignments which may affect the interpretation of the current work's contributions.*\n\n3. **Assumptions and Implications:** The paper would benefit from a critical examination of its assumptions, particularly Assumptions 2 and 3. Since the paper aims to address variance reduction, *assuming bounded second moments could be contradictory.* It's crucial to investigate whether they overly constrain the scenarios the variance reduction aims to address. \n\n4. **Proof Methodology:** Besides the strict assumptions, it is not immediately clear what novel proof techniques or insights contribute to the improved sample complexity bound. A more explicit articulation of these novel aspects would help delineate the paper's contributions from existing work.\n\n*Overall, I encourage the authors to meticulously delineate the parallels and distinctions, between the analysis, results, & proofs presented in this paper and those in prior studies. Clarifying this may enhance the perceived value of the work.*\n\n$\\textbf{[Update:]}$ After a thorough reflection on the merits and limitations, I have decided to bump up my score to a **6**. Still, I encourage the authors to refine their manuscript, including the nuanced discussions on $L$, spectral-norm & other dependencies, and the tail-bounds. (Ideally, mention important caveats in the early sections.)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In the paper's context, the authors claim an oracle complexity of \\\\( \\mathcal{O}(n + \\sqrt{n}L/\\varepsilon) \\\\) under their studied conditions, providing a considerable (theoretical) improvement over prior methodologies.", "weaknesses": "*Due to confusing presentation, there is doubt on whether the improvements stem from an innovative analysis approach, or is predominantly artifacts of the specific assumptions employed in their  (restricted) settings.*\n\n**Assumptions and Implications:**\n- Considering the decomposition, $\\mathbb{E}_{q \\sim Q} \\left[ \\| F_q(u) - F_q(v) \\|^2 \\right] = \\text{Var}_{q \\sim Q} \\left[ \\| F_q(u) - F_q(v) \\| \\right] + \\left( \\mathbb{E}_{q \\sim Q} \\left[ \\| F_q(u) - F_q(v) \\| \\right] \\right)^2$, assumptions (particularly 2 and 3) concerning bounded second moment warrant a deeper discussion on their necessity -- *particularly since variance reduction is typically sought in scenarios with large or unbounded variance.* Could the authors provide a discussion of the implications of these assumptions, and whether these could be relaxed without compromising the results? \n- The paper suggests that the bounded second moment assumption holds as standard for analyzing variance-reduced algorithms, referencing works such as (Palaniappan & Bach (2016)); (Carmon et al. (2019)); and (Alacaoglu & Malitsky (2022)). While all referenced works are implied to operate under similar conditions, however, it is unspecified whether those works inherently assume boundedness, or *derive it as a result of variance reduction*. It's unclear given the different problem settings, and if they indeed support such an assumption as a given, or if they use variance reduction techniques to bound the second moment, which are significant distinctions. \n- Therefore, claiming that such assumptions are standard in the context of variance-reduced algorithms might be misleading. A deeper analysis of the references in question, and how they relate to the specific assumptions made in this paper would be beneficial.\n\n**Presentation and Exposition:**\n- The paper's presentation of the problem setting, such as \"graph of maximal monotone operators\" in Section 2 is unclear. More precise definitions, without obscured notations, would greatly aid in comprehension.\n- The discussion post Lemma 3.1 could benefit from elaboration on what is meant by \"going beyond\" the deterministic setting. Clarification on the nature and implications of the \"more complicated induction-argument\" that is avoided may also add to the reader's understanding.\n- A structured overview would facilitate a more transparent evaluation of the work's context and contributions. To aid in the accurate evaluation of the paper's contributions, a side-by-side comparison with the assumptions, techniques, and results of existing work would be invaluable. A table format could be the most effective way to present this information, providing a quick reference to understand the advancements made. Could the authors provide a table comparing this work to the literature regarding key assumptions and results, such as variance bounds, Lipschitz conditions, sample complexity, and optimality measures?\n\n**Numerical Experiments:**\n- The numerical experiments section requires a clearer articulation of its goals and outcomes. The interpretation of the numerical experiments, particularly in Section 5, Figure 1, is not immediately apparent. Could the authors elucidate the objective of these experiments and how they substantiate the paper's claims?\n\n**Clarification on Algorithms:**\n- Considering the significant overlap with prior works on Algorithms 1, 2 and 3, would it be possible for the authors to detail the specific analysis differences and their implications? A tabulated summary including convergence rates, settings (deterministic versus stochastic), and the role of approximation errors would be highly informative. This should include the pivotal details, ensuring that all terms are precisely defined. It would also clarify the stochastic elements in the context of the algorithms proposed and how these factors are managed or analyzed differently from the literature. \n\n**Originality:**\n- The adaptation of Algorithms 1, 2, and 3 from existing literature and the application of martingale analysis proofs should be accompanied by a clear indication of the novel contributions of this work. Specifically, what is the new insight and proof technique that lead to the reported improvement in sample complexity? Currently, it seems to be mere artifact of the specific assumptions for this problem setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "UqIVc5ZmJW", "reviewer": "Reviewer_9YKM", "summary": "The paper studies finite-sum monotone inclusion problems. When assuming the operator is co-coercive, the paper proposes a direct single-loop algorithm combining PAGE and Halpern iteration that achieves $O(n+\\sqrt{n}\\epsilon^{-1})$ convergence rate. When assuming the operator is monotone and Lipschitz, the paper proposes an indirect inexact proximal point-based method with VR-FoRB as the inner-problem solver that also achieves $O(n+\\sqrt{n}\\epsilon^{-1})$ convergence rate. Both convergence rates are last-iterate guarantees on the operator norm.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and explains every detail of the algorithms and their contributions. The discussions and comparisons to previous works clearly reflect their differences and improvements. Although the algorithms and techniques are based on previous works, the obtained last-iterate guarantees on the operator norm for finite-sum monotone inclusion problems are new in the related literature.", "weaknesses": "1. PAGE was originally designed for nonconvex minimization problems and SVRG/SAGA is a common choice for convex problems. Although the problem to be solved is monotone, Algorithm 1 chooses PAGE as the base algorithm. Could the authors explain why? What happens if SVRG is used?\n\n2. I don't see any dependence and requirement on $L_F$ for both Algorithms 1 and 2. Is the assumption that $F$ is $L_F$-Lipschitz used anywhere in the analysis? Why is it required other than allowing easier comparisons with existing results? I also think the discussions on the relationship among $L_F$, $L$, and $L_Q$ should be clearly stated in the paper instead of just referring to existing works. It would be better if the paper just had one remark saying something like $L_F\\leq L\\leq\\sqrt{n}L_F$. This allows a better understanding of the regime when the improvements happen.\n\n3. I think a discussion about how and where the additional logarithmic factors in the convergence results of both algorithms come from would be great. I assume they come from different sources and thus require different techniques and efforts to get rid of (if possible).\n\n4. I still have questions on how to check the stopping criteria for the inner-problems in Algorithm 2. Is $E\\Vert e_k\\Vert^2$ something computable since it requires the exact solution $J_{\\eta(F+G)}(u_k)$?\n\n5. What are the examples of operators that are non-monotone but co-monotone other than $F(x)=-x$?\n\n6. In Figure 1(b), EAG and Algorithm 2 tend to have lots of oscillations but Algorithm 1 does not. Some explanations and discussions on this might be good.\n\n7. (Minor) Although the results in the paper are new, I am not so surprised by their algorithms and technical analyses given the rich literature on the related topics. It seems standard that the deterministic version of some problem is first studied and then variance reduction can be applied to improve the rates for its finite-sum extension. The results in this paper are thus expected by combining existing knowledge, especially given its infinite-sum version in (Cai, 2022a). Another small concern is about the practical use of variance reduction methods. Even though they offer plenty of benefits in the theoretical analysis, there are works that report these methods do not have good performances in practice as the theory suggests, e.g., [arXiv:1812.04529]. There is even no official support for variance reduction methods in the popularly used machine learning packages like PyTorch and TensorFlow despite rich literature showing their theoretical advantages on both convex and nonconvex problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)