On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities TaeHo Yoon*

Nicolas Loizou*

arXiv:2608.06182v1 [math.OC] 6 Aug 2026

Abstract We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set X . Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independentsample SEG (I-SEG) and assume either that the domain X is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes. Keywords

Variational inequality · Stochastic optimization · Extragradient · Gap function · Almost sure convergence

Mathematics Subject Classification

65K15 · 90C33 · 62L20 · 90C15 · 49J40 · 47H05

Contents 1 Introduction 1.1 Extragradient and its stochastic variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Notion of convergence for VIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Summary of main contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 2 3 4

2 Background and preliminaries 6 2.1 Theoretical assumptions and their hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Prior work and closely related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Results on gap function convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Existing results on almost-sure last-iterate convergence . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3 A challenge of analyzing S-SEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Gap function analysis: New results with minimal assumptions 11 3.1 Analysis in compact domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.1 Warm-up: Convergence of S-SEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Importance of uniform Lipschitzness for S-SEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Analysis in general closed convex domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.1 High-probability gap function convergence under general variance bound . . . . . . . . . . . . . . . . 14 3.2.2 Beyond the high-probability theorems: Impossibility via counterexamples . . . . . . . . . . . . . . . 21 3.2.3 Effect of DSEG step-sizes on the convergence of SEG . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 Almost sure convergence of the last iterate 30 4.1 Convergence under quasi-strict monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 S-SEG may diverge even with DSEG step-sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5 Conclusion

33

∗ Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science,

nloizou}@jhu.edu

1

Johns Hopkins University. {tyoon7,

1

Introduction

A variational inequality problem (VIP)1 [66, 48], stated as find

x∈X

⟨F (u), x − u⟩ ≤ 0, ∀u ∈ X

(1)

where X ⊆ Rd is a closed convex domain, is a general problem class that arises naturally in optimization and game theory [23]. For a VIP, the objective operator F : Rd → Rd is typically assumed to be monotone. For example, F = ∇f may be
the gradient of a differentiable and convex function f : Rd → R, or F (x(1) , x(2) ) = ∇x(1) f (x(1) , x(2) ), −∇x(2) f (x(1) , x(2) ) may be the saddle operator associated with a differentiable and convex-concave function f : Rd1 × Rd2 → R [62]. In this sense, a monotone VIP encodes the first-order optimality conditions for constrained convex minimization and convex-concave minimax optimization, and can be viewed as their natural generalization. In modern optimization, objectives are often constructed from large datasets. For VIPs, a corresponding theoretical model is the objective operator F with the finite sum structure n

F (x) =

1X F (x; ξi ). n i=1

(2)

When d and n are large, the standard paradigm is to use stochastic first-order algorithms, which update the iterates using sample operator evaluations F (·; ξi ) rather than evaluations of the full-batch operator F . This will be the setting of interest for our work. A variety of algorithms for solving VIP (1) or its unconstrained case (which finds x ∈ Rd such that F (x) = 0) exist in the literature. Korpelevich’s celebrated Extragradient (EG) algorithm [37] is one of the algorithmic foundations for solving VIP. It has been generalized to the non-Euclidean Mirror-Prox algorithm [55], whose stochastic extension [35] has become a standard reference for stochastic VIP. More recent works have actively studied (stochastic) EG and its extensions in the context of machine learning [24, 46, 27, 28, 34, 49, 50, 51, 6, 30, 29, 17, 19]. Complementary lines of work seek single-call algorithms or different algorithmic structures. Popov’s method is an early alternative to EG requiring only one new operator evaluation per iteration [59], whose modern optimistic mirror descent interpretation was later proposed and popularized in the context of zero-sum games [60, 46] and machine learning [18, 33, 27, 31, 20]. The golden ratio algorithm considered in [45, 3] also uses one operator evaluation per iteration and admits an adaptive linesearch-free variant. Lightweight second-order algorithms such as Hamiltonian gradient descent or consensus optimization achieve linear convergence under favorable conditions [47, 41, 43, 1, 44]. Recently, a number of works adapted Halpern iteration for fixed-point problems [32, 42] to minimax, monotone inclusion problems and VIPs, and achieved accelerated residual norm convergence [22, 75, 40, 70, 16, 76, 13]. This inspired the development of distinct interpretations and new mechanisms for acceleration in these problem classes [68, 14, 63, 77, 67, 78, 74]. Some of these accelerated methods have been applied to stochastic VIPs or monotone inclusion problems via variance reduction [15, 4, 69]. Among all the aforementioned algorithms, in this paper, we focus on stochastic Extragradient (SEG), which is not yet fully studied in spite of being a fundamental algorithm for stochastic VIPs.

1.1

Extragradient and its stochastic variants

Although gradient descent is foundational in first-order optimization, its analogue for a general monotone VIP, defined by the update rule xk+1 = ΠX (xk − γk F (xk )) ,

(3)

where ΠX denotes projection onto the closed convex set X and γk are the step-sizes, may not converge. A standard counterexample is the rotation operator F : R2 → R2 given by F (x(1) , x(2) ) = (x(2) , −x(1) ) with X = R2 , arising from the two-player minimax problem with bilinear objective f (x(1) , x(2) ) = x(1) x(2) . For this operator, every iteration of (3) causes the iterates to further deviate from the unique solution x⋆ = (0, 0). While certain convergence results for (3) exist, they require additional conditions such as boundedness of the operator [53] or stability of the optimum [41, 10]; even then, convergence can be slow [47]. Consequently, there is broad consensus that additional mechanisms are required to solve (1) efficiently [73, 24, 25, 46, 75, 77, 80, 39, 64]. Extragradient (EG) [37] is a classical algorithm proposed for solving saddle point problems (minimax optimization) using two operator evaluations per iteration. In the language of VIPs, it has the update rule x̂k = ΠX (xk − γ̂k F (xk )) 1 We state the Minty (or “weak”) form of VIP [48] here, while formulation by Stampacchia (“strong”) VIP [66]: find x∈X

X , appeared earlier. The two formulations are equivalent if F is monotone and continuous.

2

⟨F (x), u − x⟩ ≥ 0, ∀u ∈

xk+1 = ΠX (xk − γk F (x̂k )) . The first line is commonly called the extrapolation step, and the second the update step; the latter uses the operator evaluated at the extrapolated iterate x̂k . Despite its simplicity, EG is remarkably effective. For a VIP with a monotone and Lipschitz continuous operator F , it achieves an O(1/k) convergence rate with respect to the gap function, one of the standard measures for this problem class [55]. This rate is optimal up to a constant [56, 55]. A wide range of algorithms now used for minimax optimization and VIPs can be viewed broadly as generalizations or extensions of EG [59, 71, 65, 60, 46]. Consequently, the convergence theory of EG has been studied extensively and is now well established [52, 7, 50, 51, 30]. Given the success of EG for deterministic VIPs, a natural stochastic counterpart for objective operators of the form (2) is stochastic extragradient (SEG), for which we have two variants: x̂k = ΠX (xk − γ̂k F (xk ; ξik ))
xk+1 = ΠX xk − γk F (x̂k ; ξîk )

x̂k = ΠX (xk − γ̂k F (xk ; ξik ))

(I-SEG)

(S-SEG)

xk+1 = ΠX (xk − γk F (x̂k ; ξik )) .

Here independent-sample SEG (I-SEG) selects independent random indices ik , îk from [n] = {1, . . . , n} in the extrapolation and update steps, and there is a large body of convergence theory for I-SEG and its extensions [35, 79, 36, 46, 24, 18, 34, 6, 9]. However, the dynamics of SEG depend heavily on how the stochastic indices are chosen. In particular, same-sample SEG (S-SEG) which uses a shared sample ξik = ξîk across the two steps, can follow trajectories entirely different from those of I-SEG on different stochastic monotone VIPs (Figure 1). In our view, S-SEG is at least as natural as I-SEG and may even be preferable in practice because it does not require two independent operator samples at each iteration. However, only a small body of prior work has focused on S-SEG [49, 29], and a relatively limited range of theoretical guarantees have been established. Thus, the theoretical understanding of S-SEG remains less developed than that of I-SEG, and the precise distinctions between the two variants remain underexplored. 6

S-SEG I-SEG Initial point

10

S-SEG I-SEG Initial point

4

5 2

0

0

−2 −5 −4 −10 −6 −10

−5

0

5

10

−6

−4

(a) (ρ, ν) = (2, 0)

−2

0

2

4

6

(b) (ρ, ν) = (0, 2).

Figure 1: Trajectories and I-SEG on two different two-dimensional stochastic monotone VIPs defined in  of S-SEG  0 −1 Lemma 3.11: J = , and F (x; ξ1 ) = (ρI + (1 + ν)J)x and F (x; ξ2 ) = (−ρI + (1 − ν)J)x for x ∈ X = R2 . 1 0 The two problems are constructed via different choices of ρ and ν, and both versions of SEG are run with step-size 1 for N = 100 iterations in both cases. In (a), S-SEG dynamics is unstable while I-SEG converges to γ̂k = γk = √k+25 the solution (0, 0), indicated with the “⋆” marker, while in (b), the roles of S-SEG and I-SEG are reversed. Thus, neither sampling rule uniformly dominates the other.

1.2

Notion of convergence for VIP

For VIP, the following (restricted) gap function [38, 57] is a standard measure of convergence used for deriving quantitative rates: ErrZ (x) = max ⟨F (u), x − u⟩ ≥ 0. u∈X ∩Z

3

(4)

Here Z is a compact set used to enforce the finiteness of (4). In cases where X is already compact, we take Z = X and simply write Err(x) = ErrX (x), and otherwise, when X is unbounded, we take the ball Z = B(y, D) for some y ∈ X and radius D > 0. Assuming that B(y, D) contains at least one solution to (1), for x in the interior of B(y, D), we have ErrB(y,D) (x) = 0 if and only if x is a solution to (1) [57, Lemma 1]. The seminal result of [55] showed Err(x̂N ) = O(1/N ) √   along the ergodic average of extrapolated iterates x̂N for EG, and [35] proved E Err(x̂N ) = O(1/ N ) for I-SEG. Another type of convergence of interest is whether the iterate sequence xk converges to a VIP solution x⋆ almost surely with respect to the randomness in the algorithm, i.e., whether xk → x⋆ with probability 1. Here, we typically focus on the last iterate rather than the averaged iterate. For deterministic EG, the original work [37] already proved the last-iterate convergence, and for I-SEG, prior works including [36, 46, 6, 34] have provided almost-sure convergence guarantees. On the other hand, whether the analogous results hold for S-SEG is mostly unknown, to the best of our knowledge.

1.3

Summary of main contributions

Here, we provide a detailed summary of our main technical contributions. See Table 1, which serves two complementary purposes: it provides a compact review of the existing convergence theory for I-SEG and S-SEG, and it identifies the open questions resolved in this paper. The comparison is organized along the three axes that govern the behavior of both versions of SEG: (i) the convergence criterion (restricted gap function convergence of averaged iterates or almost-sure last-iterate convergence), (ii) the boundedness of the domain, and (iii) the step-size selection. In Table 1, the previously known results are displayed in black text with citations, while the contributions of this paper are highlighted in red. The main message is that the choice between independent and same samples in the two versions of SEG is not simply an innocuous implementation detail. Under symmetric and square-summable step-sizes, the two variants admit a similar high-probability gap function convergence theory on possibly unbounded domains. Outside this regime, however, their behavior differs sharply: first, S-SEG guarantees rely on uniform Lipschitzness of sample operators, a condition beyond what is needed for I-SEG, and second, an asymmetric step-size choice from [34] that restores convergence for I-SEG can still lead S-SEG to diverge. Furthermore, our positive results—convergence guarantees—are accompanied by negative results—counterexamples—showing that, in the directions considered here, the assumptions and the probabilistic form of the results in our theorems cannot generally be improved. Altogether, our results delineate the boundary between convergence and failure for the two principal variants of SEG. We summarize the main contributions below, beginning with the results for possibly unbounded domains, which constitute the technical core of our analysis. ⋄ A sharp restricted-gap theory on general closed, convex, and possibly unbounded domains. Prior work establishes gap-function convergence for I-SEG on unbounded domains under uniformly bounded variance (Assumption 2.5) [24]. In contrast, the corresponding unbounded-domain behavior of S-SEG, as well as the behavior of I-SEG under the weaker generalized variance model (Assumption 2.6), is not clearly understood. P∞ For nonincreasing and symmetric step-sizes γ̂k = γk satisfying k=0 γk2 < ∞ and kγk → ∞, we prove conditional expected gap function bounds on a high-probability event for both I-SEG and S-SEG, under their respective assumptions (Theorems 3.3 and 3.4). These bounds immediately yield high-probability convergence guarantees via Corollary 3.5. In particular, for γk = Θ((k + 1)−α ) with 12 < α < 1, the conditional expected gap function decreases at rate O(N −(1−α) ). We complement these guarantees with two impossibility results via counterexamples. First, square summability cannot √ be removed in general: with the non-square-summable choice γ̂k = γk = 1/ k + 1, for both I-SEG and S-SEG, the last-iterate and average-iterate norms may both be unbounded (Theorems 3.9 and 3.10). Second, even with squaresummable symmetric step-sizes, the high-probability guarantee cannot generally be replaced with an unconditional guarantee on the expected gap function over a prespecified bounded region, as the limiting radius of the iterates can have unbounded support (Theorem 3.12). Together, these positive and negative results explain both why conditioning is needed, and why the high-probability form of our gap function theory is essentially unavoidable. ⋄ Almost-sure last-iterate convergence for S-SEG, and a fundamental separation from I-SEG. Prior work establishes almost-sure last-iterate convergence of I-SEG under quasi-strict monotonicity; see Proposition 2.16 P and [36, 46]. We prove the corresponding result for S-SEG: if F is quasi-strictly monotone, k γk = ∞, and γk , γ̂k are both square-summable, then the last iterate converges almost surely to a solution (Theorem 4.1). Without quasi-strict monotonicity, the two variants behave fundamentally differently. For I-SEG on X = Rd , the asymmetric step-size rule (DSEG) is known to yield almost-sure last-iterate convergence [34]; we additionally show that PN it gives an expected restricted-gap bound of order O(( k=0 γk )−1 ) for the weighted average of the iterates (Proposition 3.13). In contrast, the same step-size principle does not rescue S-SEG. We construct a uniformly Lipschitz stochastic

4

5

Almost sure convergence (Last iterate)

Gap function (Averaged iterate)

Result type

X unbounded (Section 4)

Assumption 2.6 (I-SEG) Assumption 2.3 (S-SEG)

γ k = γ̂k P 2 k γk = ∞

X unbounded (Section 3.2)

P Pk γk2 γ̂k = ∞ ∞ Pk γk < 2 k γk γ̂k < ∞

P Pk γk2 γ̂k = ∞ ∞ Pk γk < 2 k γk γ̂k < ∞ P 2 Pk γ̂k2 < ∞ k γk < ∞

Assumption 2.6 (I-SEG) Assumption 2.3 (S-SEG)

γ k = γ̂k P 2 k γk < ∞ kγk → ∞

Assumption 2.6 (I-SEG) Assumption 2.3 (S-SEG)

Assumption 2.8 Assumption 2.6 (I-SEG) Assumption 2.3 (S-SEG)

Assumption 2.6 (I-SEG) Assumption 2.3 (S-SEG)

Assumption 2.5 but not Assumption 2.3

Assumption 2.5 (I-SEG) Assumption 2.3 (S-SEG)

γk = γ̂k PN k=0 γk = o(N ) γN = ω(1/N )

X compact (Section 2.2, Section 3.1.1)

Assumptions

Step-size

Domain

xk → x⋆ almost surely [34].

xk → x⋆ almost surely [36, 46].

(New: Proposition 3.13).

xk may diverge almost surely (New: Theorem 4.2).

xk → x⋆ almost surely (New: Theorem 4.1).

γ

xN , x̂N may both diverge almost surely (New: Theorem 3.9).

xN , x̂N may both diverge almost surely (New: Theorem 3.10). However, expected gap function converges with stronger Assumption 2.5 [24].  −1  PN Converges with rate O k=0 γk

xN , x̂N may both diverge almost surely (New: Theorem 4.2).

High-probability conditional expectation bound holds (New: Theorem 3.4). Similar unconditional bound is generally not possible (New: Theorem 3.12).

High-probability conditional expectation bound holds (New: Theorem 3.3). Similar unconditional bound is generally not possible (New: Theorem 3.12).

step-size choice [35, 79].

May converge to x∞ ∈ / X⋆ almost surely (New: Proposition 3.2).

step-size choice [24].

  Converges with rate O N −1/2 with appropriate

  Converges with rate O N −1/2 with appropriate step-size choice [35, 79].   Converges with rate O N −1/2 with appropriate

S-SEG

I-SEG

Table 1: Comparison of convergence results for I-SEG and S-SEG considered in this work. New results are highlighted in red. Here, we globally assume that F is monotone and Lipschitz, and F (·; ξi ) is an unbiased sampling of F . Please see Section 1.3 for a detailed explanation of novel results, and Section 2.2 for a review of existing results.

monotone VIP with a unique solution, for which both the last iterate and the weighted average of the iterates diverge almost surely under DSEG step-sizes (Theorem 4.2). This separation shows that independence of the two samples ξik and ξîk is a central ingredient for the convergence mechanism of DSEG, rather than a proof convenience. ⋄ Bounded variance is insufficient for S-SEG, even on compact domains. On compact domains, the basic gap function convergence picture is largely known: with an appropriate choice of step-size, I-SEG and S-SEG achieve the standard O(N −1/2 ) expected gap convergence rate under their respective assumptions; see Proposition 2.9, [79, Proposition 4] and Proposition 2.11. Our contribution in this regime is to show that the stronger uniform Lipschitzness used in the S-SEG analysis is substantive. We construct a counterexample of monotone and Lipschitz stochastic VIP defined on a compact domain, whose stochastic oracle is unbiased and has bounded variance, and whose solution x⋆ is unique, but whose sample operators are not Lipschitz continuous. For a positive-measure set of initial points, the S-SEG iterates remain separated from x⋆ , and the averaged iterates also fail to converge to x⋆ (Proposition 3.2). This shows that bounded variance and Lipschitzness of F cannot replace uniform Lipschitzness in the S-SEG theory, so Assumption 2.3 used in all of our S-SEG theorems is not merely an artifact of the proofs.

2

Background and preliminaries

In this section, we establish a list of assumptions required for stating different convergence theories of SEG, and explore closely related prior results on SEG.

2.1

Theoretical assumptions and their hierarchy

An operator G : dom(G) → Rd is monotone if its domain dom(G) is convex and ⟨G(x) − G(y), x − y⟩ ≥ 0,

∀x, y ∈ dom(G).

∥G(x) − G(y)∥ ≤ L ∥x − y∥ ,

∀x, y ∈ dom(G).

For L > 0, we say G is L-Lipschitz if

Throughout the paper, we globally assume that (1) has a nonempty solution set X⋆ ⊆ X . Furthermore, we commonly use the following assumptions on the problem class. Assumption 2.1 (Mean monotonicity). The mean operator F = n1

Pn

Assumption 2.2 (Mean Lipschitzness). The mean operator F = n1

Pn

i=1 F (·; ξi ) is monotone.

i=1 F (·; ξi ) is L-Lipschitz for some L > 0.

Assumption 2.3 (Uniform Lipschitzness). In (2), F (·; ξi ) : X → Rd are uniformly L-Lipschitz for some L > 0, i.e., each F (·; ξi ) is L-Lipschitz. Clearly, Assumption 2.3 implies Assumption 2.2; while S-SEG requires Assumption 2.3 for convergence (as we show in Proposition 3.2), I-SEG only requires the weaker Assumption 2.2 and does not seem to directly benefit from assuming Assumption 2.3. Next, we state the assumptions on the stochastic gradients. Define by ∅ = F0 ⊆ F̂0 ⊆ F1 ⊆ F̂1 ⊆ . . . the natural filtration generated by the algorithm; more precisely, Fk = σ ξi0 , ξî0 , . . . , ξik−1 , ξîk−1 , F̂k = σ (Fk , ξik ) respectively encompass all randomness involved in determining xk and x̂k . For S-SEG, we have F̂k = Fk+1 . Assumption 2.4 (Unbiasedness). At each iteration k ≥ 0, the stochastic operator h is an unbiased i estimator of F (xk ) conditioned on Fk , i.e., E [F (xk ; ξik ) | Fk ] = F (xk ). For I-SEG, we also assume E F (x̂k ; ξîk ) F̂k = F (x̂k ).

6

i h 2 Assumption 2.5 (Bounded variance). There is σ > 0 such that E ∥F (xk ) − F (xk ; ξik )∥ Fk ≤ σ 2 for k ≥ 0. For h i 2 I-SEG, we also assume E F (x̂k ) − F (x̂k ; ξîk ) F̂k ≤ σ 2 . While Assumption 2.5 is common in the stochastic optimization literature, in this work, we more often consider the following more general bound. Assumption 2.6 (Generalized variance bound). There exist a solution x⋆ ∈ X⋆ and σ, A ≥ 0 such that i h 2 2 E ∥F (xk ) − F (xk ; ξik )∥ Fk ≤ A ∥xk − x⋆ ∥ + σ 2 i h 2 2 F̂k ≤ A ∥x̂k − x⋆ ∥ + σ 2 E F (x̂k ) − F (x̂k ; ξîk )

(5)

for k = 0, 1, . . . , where the second line is considered only for I-SEG. Under Assumption 2.2—which is a minimal and global assumption made throughout this paper—Assumption 2.6 is i h 2 2 equivalent to the condition E ∥F (x; ξi )∥ x ≤ B 2 ∥x − x⋆ ∥ + G2 (for all x where new stochastic sampling occurs, where B, G ≥ 0 are fixed), which dates back to [11, 26] and was also considered in more recent works including [72, 34, 58, 5, 2]. Notably, this type of variance bound is suitable for modeling unconstrained stochastic VIP with linear sample operators featuring random matrices, unlike the stricter Assumption 2.5. In fact, Assumption 2.6 is implied by uniform Lipschitzness (Assumption 2.3) and unbiasedness of stochastic operators (Assumption 2.4) in the finite sum setting that we consider in this paper: Proposition 2.7. Suppose that Assumptions 2.3 and 2.4 hold. Then, for any x⋆ ∈ X⋆ , (5) holds with A = 2L2 and 2

σ 2 = 2 max ∥F (x⋆ ; ξi )∥ < ∞. i=1,...,n

2

2

Furthermore, we have ∥F (xk ; ξik )∥ ≤ 2L2 ∥xk − x⋆ ∥ + σ 2 almost surely. Proof. By unbiasedness and Lipschitzness of F (·; ξik ), we have h i h i 2 2 2 E ∥F (xk ) − F (xk ; ξik )∥ Fk = E ∥F (xk ; ξik )∥ Fk − ∥F (xk )∥ h i 2 2 ≤ E 2 ∥F (xk ; ξik ) − F (x⋆ ; ξik )∥ + 2 ∥F (x⋆ ; ξik )∥ Fk 2

2

≤ 2L2 ∥xk − x⋆ ∥ + 2 max ∥F (x⋆ ; ξi )∥ . i=1,...,n

For I-SEG, E

h

F (x̂k ) − F (x̂k ; ξîk ) 2

2

i 2 F̂k can be bounded similarly. Finally, ∥F (xk ; ξik )∥ can be bounded as 2

2

2

2

∥F (xk ; ξik )∥ ≤ 2 ∥F (xk ; ξik ) − F (x⋆ ; ξik )∥ + 2 ∥F (x⋆ ; ξik )∥ ≤ 2L2 ∥xk − x⋆ ∥ + 2 max ∥F (x⋆ ; ξi )∥ . i=1,...,n

(6)

Note that in particular, when X is compact, Assumptions 2.3 and 2.4 imply Assumption 2.5. In theorems on S-SEG, we will not directly assume Assumptions 2.5 or 2.6, because they will be tacitly implied through other assumptions. Finally, we introduce the following notion, which will be used in the discussion of almost-sure iterate convergence. Assumption 2.8 (Quasi-strict monotonicity). For any x⋆ ∈ X⋆ and x ∈ X \ X⋆ , we have ⟨F (x), x − x⋆ ⟩ > 0. This assumption, also referred to as the acute angle condition [36] or strict coherence property [46], was used for deriving the almost-sure convergence of I-SEG variants. It states that any solution x⋆ is stable and attracts the negative operator directions, but excludes some monotone operators such as purely rotational ones. On the other hand, Hsieh et al. [34] states that I-SEG may not converge for merely monotone stochasticP VIP (without Assumption 2.8) with γ̂k = γk satisfying P∞ ∞ the standard Robbins–Monro type conditions k=0 γk = ∞ and k=0 γk2 < ∞. Our Theorem 3.12 demonstrates that quasi-strict monotonicity is also essential for the last-iterate convergence of S-SEG with symmetric step-size γ̂k = γk . 7

2.2

Prior work and closely related work

In the following, we introduce important prior work of high relevance, broadly dividing them into results on gap function and almost-sure last-iterate convergence. At the end of the section, we briefly explain the challenges of analyzing S-SEG compared to the case of I-SEG. 2.2.1

Results on gap function convergence

In this section, we review some existing results on the gap function convergence. After each statement, we highlight its dependence on restrictive assumptions such as the compactness of the domain or bounded variance condition, or other limitations. Unlike the results presented here, the main theorems of this paper are not subject to those limitations. We start with the analyses of I-SEG. Proposition 2.9. [35, Corollary 1] Let X be compact and let D = diam(X ). Suppose that Assumptions 2.1, 2.4 and 2.5 hold, and that F satisfies ∥F (x) − F (y)∥ ≤ L ∥xn− y∥ + M q for all x, y ∈ Xo(which is weaker than Assumption 2.2). Then I-SEG with constant step-size γk = γ̂k ≡ min

√1 , D 3L

1 7(N +1)(M 2 +2σ 2 )

exhibits the rate

s ) (       LD2 D(M + σ) 7LD2 M 2 + 2σ 2 √ E Err(x̂N ) = E max F (u), x̂N − u ≤ max , 7D =O + u∈X 8(N + 1) 6(N + 1) N N where x̂N = N1+1

PN

k=0 x̂k .

Remark. This is a classical result for compact domains, assuming uniformly bounded variance. It shows that the +σ) √ dependence of I-SEG on L is only in the non-dominant term, while the dominant term O D(M depends on σ and N M , the parameters quantifying stochasticity and nonsmoothness of F . That is, the components in the I-SEG  stochastic  analysis are not sensitive to the Lipschitzness parameter of F or F (·; ξi ). Similar O √1N rate on gap function at averaged   iterates can also be proved for I-SEG with step-sizes decaying at the rate γ̂k = γk = O √1k ; see, e.g., [79, Proposition 4]. Proposition 2.10. [24, Theorem’ 3] Let X be convex and closed. Under Assumptions 2.1, 2.2, 2.4 and 2.5, I-SEG with constant step-size γk ≡ γ ≤ 2√13L exhibits the rate   E ErrB(y,D) (x̂N ) = E for any D > 0, where x̂N = N1+1



 max

u∈X ∩B(y,D)

F (u), x̂N − u

≤

7γσ 2 D2 + γ(N + 1) 2

PN

k=0 x̂k .

  Remark. The above result shows that using the gap function, the O √1N convergence of I-SEG can be extended to possibly unbounded domain X , but it still requires uniformly bounded variance. Note that Lipschitzness of F is assumed but uniform Lipschitzness of F (·; ξi ) is not. Furthermore, while not formally stated as a theorem, [24, Theorem’ 3] in fact proved the more general rate N i h X D2 7σ 2 γ + PN γk2 E ErrB(y,D) (x̂N ) ≤ PN γ 2 γ k k k=0 k=0 k=0   P γ N γk x̂k , which can be used to derive a similar O √1N rate on gap function with decreasing step-sizes for x̂N = PN1 γ k=0  k  k=0 γ̂k = γk = O √1k . Next, we turn to S-SEG. Proposition 2.11. Let X be compact, x0 ∈ X and let D = diam(X ). Under Assumptions 2.1, 2.3 and 2.4, S-SEG with

8

 i deterministic, nonincreasing step-sizes γ̂k = γk ∈ 0, √12L (i.e, 0 < γk ≤ · · · ≤ γ0 ≤ √12L ) exhibits the rate N

  E Err(x̂N ) ≤

D2 1 X σD + (8L2 D2 + 2σ 2 ) γk + √ 2(N + 1)γN +1 N +1 N +1 k=0

PN

2

where x̂N = N1+1 k=0 x̂k and σ 2 = 2L2 D2 + 2 maxi=1,...,n ∥F (x⋆ , ξi )∥ is a uniform upper bound on operator variance, implied by Proposition 2.7. Remark. Proposition 2.11 provides a qualitatively similar conclusion as [24, Theorem’ 5], i.e., convergence of S-SEG on compact domains, but we present it in a slightly different form with a self-contained, distinct proof detailed in Section 3.1.1. One immediate difference observed in Proposition 2.11 from the previous results on I-SEG is that it uses Assumption 2.3, which implies both Assumptions 2.2 and 2.5 used in Proposition 2.9, when X is compact. Hence, it appears that SSEG requires a stronger assumption compared to I-SEG. In fact, this is not merely an artifact of the analysis but is a substantive  requirement (see Proposition 3.2). With concrete step-size selections, Proposition 2.11 directly yields the 2

σ2

following O LD +√N/L+σD convergence results, where L is the uniform Lipschitzness parameter, which also indicate the sensitivity of S-SEG to the geometry of sample operators. Corollary 2.12. Under the conditions of Proposition 2.11, for N ≥ 1, S-SEG using the constant step-size γk ≡ γ = √1 for k = 0, . . . , N + 1 exhibits the rate L N +1   1 E Err(x̂N ) ≤ √ N +1



2σ 2 + σD 9LD + L 2



 =O

2

LD2 + σ /L + σD √ N



Corollary 2.13. Under the conditions of Proposition 2.11, S-SEG with diminishing step-size γk = γ̂k = L√1k+2 exhibits the rate       2 √   1 LD2 √ 4σ 2 √ LD2 + σ /L + σD 2 √ E Err(x̂N ) ≤ N + 3 + 16LD + N + 2 + N + 1σD = O . N +1 2 L N Finally, we state a prior result on S-SEG with possibly unbounded domains. Proposition2.14. [49, Theorem 3] Let X be convex and closed. Under Assumptions 2.1, 2.3 and 2.4, S-SEG with γk = γ̂k = O √1kL satisfies max

u∈X ∩B(y,D)

for any D > 0, where x̂N = N1+1

E



F (u), x̂N − u



≤√

1 NL



L2 D2 + σ2 2



PN

k=0 x̂k .

Interpretation. Proposition 2.14, on a first look, seems to offer a cleaner analysis under a more  general setting, compared to Proposition 2.11 and its corollaries. However, the caveat is that it bounds ErrB(y,D) (E x̂k ), rather than the standard   error measure E ErrB(y,D) (x̂k ) . In general,         ErrB(y,D) (E x̂k ) = max E F (x), x̂k − x ≤ E max F (x), x̂k − x = E ErrB(y,D) (x̂k ) x∈X ∩B(y,D)

x∈X ∩B(y,D)

    so a bound on ErrB(y,D) (E x̂k ) is weaker. Interpreting this result, it states that E x̂k will be an approximate solution; however, to obtain this vector, one should run the stochastic algorithm multiple times and take the average of x̂k generated from each run. This does not adequately represent the type of guarantee that we typically want, and it does not prevent each individual run from failing loudly, as the following example demonstrates.

9

Proposition 2.15. [4, Example 1.1] Let F : R2 → R2 be the monotone operator defined as F (x1 , x2 ) = (x2 , −x1 ). For this F , the unique solution to (1) is x = (0, 0), but an algorithm that outputs ( (k, k) with probability 21 xk = (−k, −k) with probability 12 at each iteration k = 1, 2, . . . satisfies ErrZ (E [xk ]) = 0 for all k ≥ 1, for any compact set Z ⊂ R2 . Interpretation. Here, we see that the algorithm does not use any information of the operator F and outputs a random sequence whose norm diverges to infinity, but it appears to “achieve a perfect convergence” if ErrZ(E [xk ]) is taken as a  measure of convergence. This indicates the need to provide a guarantee in terms of E ErrB(y,D) (x̂k ) , rather than the one used in Proposition 2.14. 2.2.2

Existing results on almost-sure last-iterate convergence

While it is common to use same extrapolation and update step sizes γ̂k = γk for SEG, it is well known (for I-SEG) that such step-size choice fails to provide last iterate convergence for general monotone problems [34], but requires an additional condition such as Assumption 2.8. Proposition 2.16 ([46], 4.3). Let X be compact. Under Assumptions 2.1, 2.2, 2.4, 2.5 and 2.8, I-SEG with PTheorem P∞ ∞ γ̂k = γk > 0, satisfying k=0 γk = ∞ and k=0 γk2 < ∞, converges almost surely to a solution to (1)a . a The original result was stated in a more general form, but we simplify it for coherent exposition.

On the other hand, with step-sizes γ̂k , γk decaying at different rates, I-SEG can converge almost surely to a solution for any monotone Lipschitz stochastic VIP, without the need for the stronger assumption of quasi-strict monotonicity. Proposition 2.17. [34, Theorem 1] Let X = Rd . Under Assumptions 2.1, 2.2, 2.4, and 2.6, I-SEG with double step-size 1 √ extragradient (DSEG) step-sizes satisfying 0 < γk ≤ γ̂k < 3 max{L, for all k = 0, 1, . . . , and A} ∞ X

γk γ̂k = ∞,

k=0

∞ X

γk2 < ∞,

∞ X

γ̂k2 γk < ∞

(DSEG)

k=0

k=0

converges almost surely to some x∞ ∈ X⋆ , where F (x∞ ) = 0 since X = Rd . Interestingly, in Section 4.2, we show that even the DSEG step-sizes cannot resolve the non-convergence of S-SEG on certain monotone and Lipschitz stochastic VIP (see Theorem 4.2). 2.2.3

A challenge of analyzing S-SEG

Overall, we observe that the literature has pursued the study of I-SEG more extensively, and this is likely because analyzing S-SEG is trickier due to its bias term F (x̂k ; ξîk ) − F (x̂k ), xk .

(7)

This quantity becomes zero under total expectation for independent-sample SEG because h h ii hD h i Ei   E F (x̂k ; ξîk ) − F (x̂k ), xk = E E F (x̂k ; ξîk ) − F (x̂k ), xk F̂k = E E F (x̂k ; ξîk ) − F (x̂k ) F̂k , xk = 0. However, for same-sample SEG where x̂k relies on ξik , the stochastic operator F (x̂k ; ξik ) is no longer an unbiased estimator of F (x̂k ) conditioned on x̂k , so (7) does not vanish. This is not merely the limitation in the analyses, but can be viewed as the fundamental limitation preventing some positive results established for I-SEG from carrying over to S-SEG (e.g., see Theorem 4.2).

10

3

Gap function analysis: New results with minimal assumptions

In this section, we provide several missing components within the existing gap function analyses of SEG in the literature. We first consider the compact-domain analysis, and present the proof of Proposition 2.11, a convergence result for S-SEG. We then show that the uniform Lipschitzness requirement (Assumption 2.3) cannot be removed without replacement for S-SEG, by demonstrating an example of monotone VIP violating this assumption for which S-SEG fails to converge. Next, we explore the extension of existing convergence results for I-SEG and S-SEG to general (possibly unbounded) domain X . For I-SEG, convergence has been already established in [24] for uniformly bounded variance (Assumption 2.5), but not under the more general Assumption 2.6. We show in that case, we can guarantee a quantitative gap function convergence with high-probability; then we complement this with the impossibility results for some fundamentally stronger or more general guarantees. On the other hand, we show that with the DSEG step-size of [34], I-SEG converges with respect to the gap function. For S-SEG, we analyze it under the minimal Assumption 2.3, which is stronger than but is of comparable generality with Assumption 2.6, and prove a similar high-probability bound on the gap function with symmetric (i.e., γ̂k = γk ) and square-summable step-sizes, also complemented by negative results showing that this cannot be fundamentally improved. Finally, unlike in the case of I-SEG, DSEG step-size does not benefit S-SEG (see Section 4 for details).

3.1

Analysis in compact domain

This section covers gap function convergence results in the case where the domain X is compact. We start with a self-contained proof of Proposition 2.11. 3.1.1

Warm-up: Convergence of S-SEG

We first present a lemma that will be useful for subsequent proofs throughout the rest of the paper. Lemma 3.1. The k-th step of SEG satisfies, for any u ∈ X , 0≤

 1 1 1 2 2 2 2 ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ 2 2 2 + γ̂k F (xk ; ξik ) − γk F (x̂k ; ξîk ), xk+1 − x̂k − γk F (x̂k ; ξîk ), x̂k − u .

Proof. When y ∈ Rd , z = ΠX (y) and u ∈ X , we have ⟨u − z, z − y⟩ ≥ 0.

(8)

Applying (8) with y = xk − γ̂k F (xk ; ξik ), z = x̂k and u = xk+1 gives 0 ≤ ⟨xk+1 − x̂k , x̂k − xk + γ̂k F (xk ; ξik )⟩ = ⟨xk+1 − x̂k , x̂k − xk ⟩ + ⟨xk+1 − x̂k , γ̂k F (xk ; ξik )⟩  1 2 2 2 = ∥xk+1 − xk ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ + ⟨γ̂k F (xk ; ξik ), xk+1 − x̂k ⟩ 2 Similarly, taking y = xk − γk F (x̂k ; ξîk ), z = xk+1 in (8) gives

(9)

0 ≤ u − xk+1 , xk+1 − xk + γk F (x̂k ; ξîk ) = ⟨u − xk+1 , xk+1 − xk ⟩ + γk F (x̂k ; ξîk ), u − xk+1  1 2 2 2 ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥xk+1 − xk ∥ + γk F (x̂k ; ξîk ), u − xk+1 . = 2 Adding (9) and (10) together, we obtain  1 1 1 2 2 2 2 0≤ ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ 2 2 2 + ⟨γ̂k F (xk ; ξik ), xk+1 − x̂k ⟩ + γk F (x̂k ; ξîk ), u − xk+1  1 1 1 2 2 2 2 = ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ 2 2 2 + γ̂k F (xk ; ξik ) − γk F (x̂k ; ξîk ), xk+1 − x̂k − γk F (x̂k ; ξîk ), x̂k − u .

11

(10)

Proof of Proposition 2.11. Adding ⟨γk F (x̂k ; ξik ), x̂k − u⟩ to the both sides of Lemma 3.1 and using ik = îk and γ̂k = γk , we obtain  1 1 1 2 2 2 2 ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ ⟨γk F (x̂k ; ξik ), x̂k − u⟩ ≤ 2 2 2 + ⟨γ̂k F (xk ; ξik ), xk+1 − x̂k ⟩ + ⟨γk F (x̂k ; ξik ), x̂k − xk+1 ⟩  1 1 1 2 2 2 2 = ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ 2 2 2 + γk ⟨F (xk ; ξik ) − F (x̂k ; ξik ), xk+1 − x̂k ⟩ . Next, dividing throughout by γk and adding ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ to the both sides gives ⟨F (x̂k ), x̂k − u⟩ ≤

 1 1  1 2 2 2 2 ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ 2γk 2γk 2γk + ⟨F (xk ; ξik ) − F (x̂k ; ξik ), xk+1 − x̂k ⟩ + ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ .

(11)

We use Young’s inequality and Lipschitz continuity of F (·; ξik ) to bound: 1 γk 2 2 ∥F (xk ; ξik ) − F (x̂k ; ξik )∥ + ∥xk+1 − x̂k ∥ 2 2γk γk L2 1 2 2 ≤ ∥xk − x̂k ∥ + ∥xk+1 − x̂k ∥ 2 2γk

⟨F (xk ; ξik ) − F (x̂k ; ξik ), xk+1 − x̂k ⟩ ≤

and plug this into (11) to obtain  1  1 2 2 2 ∥u − xk ∥ − ∥u − xk+1 ∥ − (1 − γk2 L2 ) ∥x̂k − xk ∥ + ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ 2γk 2γk     1 1 1 1 1 2 2 2 = ∥u − xk ∥ − ∥u − xk+1 ∥ + − ∥u − xk+1 ∥ 2γk 2γk+1 2 γk+1 γk 1 2 (1 − γk2 L2 ) ∥x̂k − xk ∥ + ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ − 2γk     1 1 1 1 1 2 2 ≤ ∥u − xk ∥ − ∥u − xk+1 ∥ + − D2 2γk 2γk+1 2 γk+1 γk (12) 1 2 2 2 − (1 − γk L ) ∥x̂k − xk ∥ + ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ 2γk

⟨F (x̂k ), x̂k − u⟩ ≤

where the last inequality holds because γk+1 ≤ γk and ∥u − xk+1 ∥ ≤ D. Next, we bound the last term in (12): ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ = ⟨F (x̂k ) − F (xk ), x̂k − u⟩ + ⟨F (xk ) − F (xk ; ξik ), x̂k − u⟩ + ⟨F (xk ; ξik ) − F (x̂k ; ξik ), x̂k − u⟩ 1 2 2 ∥F (x̂k ) − F (xk )∥ + 4γk L2 ∥x̂k − u∥ + ⟨F (xk ) − F (xk ; ξik ), x̂k − u⟩ ≤ 16γk L2 1 2 2 + ∥F (xk ; ξik ) − F (x̂k ; ξik )∥ + 4γk L2 ∥x̂k − u∥ 16γk L2 1 2 ≤ ∥x̂k − xk ∥ + 8γk L2 D2 + ⟨F (xk ) − F (xk ; ξik ), x̂k − xk ⟩ + ⟨F (xk ) − F (xk ; ξik ), xk − u⟩ 8γk 1 1 2 2 2 ≤ ∥x̂k − xk ∥ + 8γk L2 D2 + 2γk ∥F (xk ) − F (xk ; ξik )∥ + ∥x̂k − xk ∥ + ⟨F (xk ) − F (xk ; ξik ), xk − u⟩ 8γk 8γk 1 2 2 ∥x̂k − xk ∥ + 8γk L2 D2 + 2γk ∥F (xk ) − F (xk ; ξik )∥ + ⟨F (xk ) − F (xk ; ξik ), xk − u⟩ . = 4γk Plugging this back into (12) and using monotonicity of F gives       1 1 1 1 1 1 1 2 2 2 ⟨F (u), x̂k − u⟩ ≤ ∥u − xk ∥ − ∥u − xk+1 ∥ + − D2 − − γk2 L2 ∥x̂k − xk ∥ 2γk 2γk+1 2 γk+1 γk 2γk 2 | {z } ≤0

12

2

+ 8γk L2 D2 + 2γk ∥F (xk ) − F (xk ; ξik )∥ + ⟨F (xk ) − F (xk ; ξik ), xk − u⟩ . We now sum this up for k = 0, . . . , N , take maximum over u ∈ X to get max u∈X

N X

⟨F (u), x̂k − u⟩

k=0

 ≤ max u∈X

+

N X

1 1 2 2 ∥u − x0 ∥ − ∥u − xN +1 ∥ 2γ0 2γN +1 2

2γk ∥F (xk ) − F (xk ; ξik )∥ +

k=0

≤

N X

 +

1 2



1 γN +1

−

1 γ0



D2 + 8L2 D2

⟨F (xk ) − F (xk ; ξik ), xk ⟩ + max u∈X

N

N

k=0

k=0

k=0

γk

k=0

k=0 N

N X

N X

(13)

⟨F (xk ) − F (xk ; ξik ), −u⟩

k=0

X X X D2 2 + 8L2 D2 γk + 2γk ∥F (xk ) − F (xk ; ξik )∥ + ⟨F (xk ) − F (xk ; ξik ), xk − x0 ⟩ 2γN +1 + max u∈X

N X

⟨F (xk ) − F (xk ; ξik ), x0 − u⟩ .

k=0

Now take the total expectation—under which the term

PN

k=0 ⟨F (xk ) − F (xk ; ξik ), xk − x0 ⟩ vanishes—to obtain

"N # " #   N X X  D2  1 2 2 2 E ⟨F (xk ) − F (xk ; ξik ), x0 − u⟩ . + (8L D + 2σ )E γk + E max (N + 1)E Err(x̂N ) ≤ u∈X 2 γN +1

(14)

k=0

k=0

Finally, we apply the standard trick ([54, Lemma 3.1], [8, Proposition 11]) to bound the final term. Denoting ∆k = F (xk ) − F (xk ; ξik ), we have E [∆k | Fk ] = 0. Therefore, E [⟨∆j , ∆k ⟩] = 0 for any j < k, which implies " E max u∈X

N X k=0

#

"

⟨∆k , x0 − u⟩ ≤ DE

N X

# ∆k

  ≤ D E 

k=0

N X

2

∆k

1/2 

=D

N X

h

E ∥∆k ∥

2

! i 1/2

√ ≤ Dσ N + 1.

k=0

k=0

Applying this bound for (14) and dividing throughout by N + 1 proves the desired result. 3.1.2

Importance of uniform Lipschitzness for S-SEG

We will now show that the uniform (samplewise) Lipschitzness assumption is a basic requirement for convergence of S-SEG. Without such assumption, S-SEG may fail to display any meaningful convergence even if X is compact, as the following result shows. Proposition 3.2. Let γk , γ̂k be any predetermined positive sequence satisfying γk ≤ γ̂k for all k ≥ 0. There exists a stochastic VIP (1) with compact domain X satisfying Assumptions 2.1, 2.2, 2.4 and 2.5 with unique solution x⋆ = 0, but each stochastic realization F (·; ξi ) (i = 1, 2) is not Lipschitz continuous, and there exists a closed subset of Y ⊂ X of positive measure such that x⋆ ∈ / Y and for every initialization PN x0 ∈ Y, S-SEG iterates satisfy xk ∈ Y for all k = 0, 1, . . . , and lim inf N →∞ x̂N ≥ 12 almost surely where x̂N = N1+1 k=0 x̂k . Proof. Let X = [0, a] ⊂ R, where a ≥ 2. ( 2x if x < 1 F (x; ξ1 ) = , −1 if x ≥ 1

( F (x; ξ2 ) =

0 3

if x < 1 . if x ≥ 1

At each iteration, ik will be sampled uniformly from {1, 2}. Then the mean operator is (
x if x < 1 1 F (x) = F (x; ξ1 ) + F (x; ξ2 ) = = min{x, 1}. 2 1 if x ≥ 1 This is an increasing function on R, so F is monotone, and additionally, 1-Lipschitz. However, both F (·; ξ1 ) and F (·; ξ2 ) have jump discontinuities, so they are not Lipschitz. Clearly, Assumption 2.4 holds if ik is sampled uniformly random in 13

{1, 2}. Also, because X = [0, a], we have |F (x; ξi ) − F (x)| ≤ a for all x ∈ X and i = 1, 2, so Assumption 2.5 holds with σ = a. We see that x⋆ = 0 is a solution to (1) because ⟨F (u), 0 − u⟩ = −uF (u) ≤ 0  for any u ∈ X . Positive values of x cannot be a solution and because taking u = x2 we have ⟨F (u), x − u⟩ = x2 min x2 , 1 > 0. This shows that X⋆ = {0}. Now define Y = [1, a]. Consider S-SEG initialized at any x0 ∈ Y. We show by induction that xk ∈ Y for all k ≥ 0. Assuming xk ∈ Y for some k ≥ 0, if ik = 1, then F (xk ; ξ1 ) = −1, so we have x̂k = ΠX (xk + γ̂k ) ≥ 1 =⇒ x̂k ∈ Y.

(15)

Hence we again have F (x̂k ; ξ1 ) = −1, which implies xk+1 = ΠX (xk + γk ) ≥ 1 =⇒ xk+1 ∈ Y. If ik = 2, so F (xk ; ξ2 ) = 3 and we have x̂k = ΠX (xk − 3γ̂k ). If x̂k ≥ 1, then we must have xk − 3γ̂k ≥ 1. Because in this case we have x̂k ∈ Y =⇒ F (x̂k ; ξ2 ) = 3, we obtain xk − 3γk ≥ xk − 3γ̂k ≥ 1 =⇒ xk+1 = ΠX (xk − 3γk ) ∈ Y. Otherwise, x̂k < 1 and we have F (x̂k ; ξ2 ) = 0, which implies xk+1 = ΠX (xk − 0) = xk ∈ Y. Thus, in either case, xk+1 ∈ Y. This completes the induction and shows that xk ∈ Y for all k ≥ 0. Now for the extrapolated iterates, because we always have xk ∈ Y, by (15) we have x̂k ≥ 1 if ik = 1. When ik = 2, it PN may be the case that x̂k < 1, but still we have x̂k ≥ 0 because x̂k ∈ X = [0, a]. This shows that x̂N ≥ N1+1 k=0 1{ik =1} , PN and by the law of large numbers, N1+1 k=0 1{ik =1} → 21 almost surely. Thus lim inf N →∞ x̂N ≥ 12 almost surely.

3.2

Analysis in general closed convex domain

We now turn to the gap function convergence results in the case where the domain X is closed and convex but possibly unbounded. We first provide the high-probability convergence results for both I-SEG and S-SEG. 3.2.1

High-probability gap function convergence under general variance bound

The proof of Proposition 2.11 in Section 3.1.1 relies on the fact that the iterates stay within a fixed radius, enforced via projection steps onto the compact domain X . Other prior results for I-SEG often use a similar assumption that the second moment of the stochastic operator is bounded. However, for more general problems with possibly unbounded domain X 2 and weaker variance condition in Assumption 2.6, we cannot provide a uniform, path-independent bound on supk≥0 ∥xk ∥ 2 2 or supk≥0 ∥F (xk ; ξik )∥ . Even if we use square-summable step-sizes γk = γ̂k , for which ∥xk − x⋆ ∥ converges almost surely 2 for x⋆ ∈ X⋆ and hence xk is almost surely bounded, supk≥0 ∥xk − x⋆ ∥ may still be arbitrarily large along rare stochastic paths; see Section 3.2.2 for details. 2 As a workaround, in this section, we provide P a uniform quantitative bound on ∥xk − x⋆ ∥ that holds with high ∞ probability, with step-sizes satisfying γk = γ̂k and k=0 γk2 < ∞. This allows us to prove a quantitative bound on the expected gap function ErrB(y,D) (x) conditioned on that high-probability event, as follows. Theorem 3.3 (I-SEG, conditional expected gap bound). Let X be a closed, convex, not necessarily bounded domain. 2 Suppose Assumptions 2.1, 2.2, 2.4 and 2.6 hold. Let x⋆ ∈ X⋆ and let σ⋆2 = σ 2 +2 ∥F (x⋆ )∥ . Then, for any δ ∈(0, 1), therei

1 is an event Eδ with Prob [Eδ ] ≥ 1 − δ such that I-SEG with nonincreasing predetermined step-size γ̂k = γk ∈ 0, √A+2L 2 P∞ 2 with Γ := k=0 γk < ∞ satisfies   2 2 2 ∥x − x ∥ + 6σ Γ e6(A+2L )Γ 2 0 ⋆ ⋆ Dδ 2 sup ∥xk − x⋆ ∥ ≤ := . 4 δ k≥0

On this event Eδ , there exists a constant C > 0 such that x̂N = N1+1   E Errx⋆ ,Dδ /2 (x̂N ) Eδ ≤

PN

k=0 x̂k satisfies

  s
N (A + 2L2 )Dδ2 + σ⋆2  Dδ2 1  8 (A + 2L2 )Dδ2 + σ⋆2 X γk + 2Dδ . + 2(N + 1)γN +1 1−δ N +1 N +1 k=0

14

  In particular, if γk = Θ((k + 1)−α ) with 21 < α < 1, then E Errx⋆ ,Dδ /2 (x̂N ) Eδ = O N −(1−α) .

Theorem 3.4 (S-SEG, conditional expected gap bound). Let X be a closed, convex, not necessarily bounded domain. Suppose Assumptions 2.1, 2.3 and 2.4 hold. Let x⋆ ∈ X⋆ . Then, for any δ ∈ (0, 1), there is an event  P∞Eδ with Prob [Eδ ] ≥ 1 1 − δ such that S-SEG with nonincreasing predetermined step-size γ̂k = γk ∈ 0, 9L with Γ := k=0 γk2 < ∞ satisfies   2 2 2 ∥x − x ∥ + 4σ Γ e24L Γ 2 0 ⋆ Dδ 2 sup ∥xk − x⋆ ∥ ≤ := 4 δ k≥0 2

where σ 2 = 2 maxi=1,...,n ∥F (x⋆ ; ξi )∥ . On this event Eδ , x̂N = N1+1   E Errx⋆ ,Dδ /2 (x̂N ) Eδ ≤

Dδ2 2(N + 1)γN +1

 +

1 1−δ

PN

k=0 x̂k satisfies

N 2 2 X  17L Dδ + 2σ

s

2

N +1

k=0

γk + D δ

L2 δDδ2/2 + 2σ 2

N +1

 

 
In particular, if γk = Θ((k + 1)−α ) with 12 < α < 1, then E Errx⋆ ,Dδ /2 (x̂N ) Eδ = O N −(1−α) .

Corollary 3.5 (SEG, high-probability convergence). Under the conditions of either Theorem 3.3 or Theorem 3.4, for any ρ ∈ (0, 1), the considered version of SEG respectively satisfies   rN (δ) ≥ 1 − δ − ρ, Prob Errx⋆ ,Dδ /2 (x̂N ) ≤ ρ   where rN (δ) is the upper bound on E Errx⋆ ,Dδ /2 (x̂N ) Eδ given in each theorem.   Proof. Given the bound E Errx⋆ ,Dδ /2 (x̂N ) Eδ ≤ rN (δ) with Prob [Eδ ] ≥ 1 − δ, the conditional Markov inequality implies      rN (δ) rN (δ) Prob Errx⋆ ,Dδ /2 (x̂N ) ≤ ≥ Prob Errx⋆ ,Dδ /2 (x̂N ) ≤ ∩ Eδ ρ ρ ≥ Prob [Eδ ] (1 − ρ) ≥ (1 − δ)(1 − ρ) ≥ 1 − δ − ρ.

To prove Theorems 3.3 and 3.4, we first present a handy lemma on controlling the growth of stochastic sequences. Lemma 3.6. Let (Ω, F, P, (Fk )k≥0 ) be a filtered probability space. Let ak , bk , ckP , dk be nonnegative, P∞ integrable, Fk ∞ measurable random variables such that E [ak+1 | Fk ] ≤ (1 + dk )ak − bk + ck , and k=0 ck < ∞, k=0 dk < ∞ almost surely. Then P∞ (i) ak converges almost surely and k=0 bk < ∞ almost surely. P∞ P∞ (ii) If a0 is fixed and ck , dk are deterministic sequences with C = k=0 dk < ∞, then k=0 ck < ∞ and D = E [ak ] ≤ (a0 + C)eD for all k ≥ 0 and supk ak < Rδ := (a0 +C)e δ

D

with probability at least 1 − δ.

Proof. (i) is standard; see, e.g., [61, Theorem 1]. P  P  Qk−1 k−1 k−1 log(1 + d ) ≤ exp d ≤ eD . For (ii), let p0 = 1 and pk = j=0 (1 + dj ) for k ≥ 1. Then pk ≤ exp j j j=0 j=0 Hence   ak+1 ak (1 + dk ) ck ak ck E Fk ≤ + = + , pk+1 pk+1 pk+1 pk pk+1 P∞ cj which shows that Mk = apkk + j=k pj+1 is a (nonnegative) supermartingale, satisfying E [Mk+1 | Fk ] ≤ Mk . In particular, P∞ E [ak ] ≤ pk E [Mk ] ≤ pk E [M0 ] ≤ eD (a0 + C) where we use M0 ≤ a0 + k=0 ck = a0 + C. Also, by Ville’s inequality, we 15

have   E [M0 ] a0 + C Prob sup Mk ≥ λ ≤ ≤ λ λ k≥0 for any λ > 0. Therefore, for any δ > 0, we have supk≥0 Mk < a0 +C with probability ≥ 1 − δ, and on this event, δ 



sup ak ≤

sup pk

k≥0

k≥0

a0 + C δ

 ≤

(a0 + C)eD = Rδ . δ

2

To apply Lemma 3.6, we provide the following key bounds on ∥xk − x⋆ ∥ for each version of SEG. Lemma 3.7. Given the setting and notation of Theorem 3.3, I-SEG satisfies i h
2 2 E ∥x̂k − x⋆ ∥ Fk ≤ 1 + γk2 (A + 2L2 ) ∥xk − x⋆ ∥ + γk2 σ⋆2 , i h
2 2 E ∥xk+1 − x⋆ ∥ Fk ≤ 1 + 6γk2 (A + 2L2 ) ∥xk − x⋆ ∥ + 6γk2 σ⋆2 . Proof. Using the variance bound (5), for z = xk or z = x̂k and the corresponding ξ = ξik or ξ = ξîk , h i h i 2 2 2 E ∥F (z; ξ)∥ z = ∥F (z)∥ + E ∥F (z; ξ) − F (z)∥ z   2 2 2 ≤ 2 ∥F (x⋆ )∥ + ∥F (z) − F (x⋆ )∥ + A ∥z − x⋆ ∥ + σ 2   2 2 2 ≤ 2 ∥F (x⋆ )∥ + L2 ∥z − x⋆ ∥ + A ∥z − x⋆ ∥ + σ 2 2

= ν ∥z − x⋆ ∥ + σ⋆2

(16)

where ν = A + 2L2 . Then, we have 2

∥x̂k − x⋆ ∥ = ∥ΠX (xk − γk F (xk ; ξik )) − ΠX (x⋆ )∥ ≤ ∥xk − γk F (xk ; ξik ) − x⋆ ∥

2

2

2

2

= ∥xk − x⋆ ∥ − 2 ⟨γk F (xk ; ξik ), xk − x⋆ ⟩ + γk2 ∥F (xk ; ξik )∥ . Taking expectation conditioned on Fk , the second term becomes −2γk ⟨F (xk ), xk − x⋆ ⟩ ≤ 0, and the last term can be bounded using (16). As a result, we obtain h i  
2 2 2 2 E ∥x̂k − x⋆ ∥ Fk ≤ ∥xk − x⋆ ∥ + γk2 ν ∥xk − x⋆ ∥ + σ⋆2 = 1 + γk2 ν ∥xk − x⋆ ∥ + γk2 σ⋆2 (17) where we used ⟨F (xk ), xk − x⋆ ⟩ ≥ 0. Using Lemma 3.1 with u = x⋆ , with γ̂k = γk we have 2

2

2

∥xk+1 − x⋆ ∥ ≤ ∥xk − x⋆ ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥

2

+ 2γk F (xk ; ξik ) − F (x̂k ; ξîk ), xk+1 − x̂k −2γk F (x̂k ; ξîk ), x̂k − x⋆ . {z } |

(18)

(I)

The last term, conditioned on F̂k , is nonpositive in expectation. Next, we can bound (I) as   2 2 2 2 2 (I) ≤ γk2 F (xk ; ξik ) − F (x̂k ; ξîk ) + ∥xk+1 − x̂k ∥ ≤ 2γk2 ∥F (xk ; ξik )∥ + F (x̂k ; ξîk ) + ∥xk+1 − x̂k ∥ . Plugging this into (18), taking the conditional expectation on Fk and using (16) and (17) with the tower property, we obtain h i h i h i h i 2 2 2 2 2 Fk E ∥xk+1 − x⋆ ∥ Fk ≤ ∥xk − x⋆ ∥ − E ∥x̂k − xk ∥ Fk +2γk2 E ∥F (xk ; ξik )∥ Fk + 2γk2 E F (x̂k ; ξîk ) | {z } ≥0

16

 i  h 2 2 2 ≤ ∥xk − x⋆ ∥ + 2γk2 ν ∥xk − x⋆ ∥ + 2γk2 σ⋆2 + 2γk2 νE ∥x̂k − x⋆ ∥ Fk + σ⋆2  
2 2 ≤ (1 + 2γk2 ν) ∥xk − x⋆ ∥ + 4γk2 σ⋆2 + 2γk2 ν 1 + γk2 ν ∥xk − x⋆ ∥ + γk2 σ⋆2 2

≤ (1 + 6γk2 ν) ∥xk − x⋆ ∥ + 6γk2 σ⋆2 where the last line uses γk2 ν ≤ 1, which follows by our step-size choice.

Lemma 3.8. Given the setting and notation of Theorem 3.4, S-SEG satisfies i h 2 2 E ∥xk+1 − x⋆ ∥ Fk ≤ (1 + dk ) ∥xk − x⋆ ∥ − bk + ck , with  bk = E

  1 2 2 2 − 17γk L ∥x̂k − xk ∥ + 2γk ⟨F (x̂k ), x̂k − x⋆ ⟩ Fk ≥ 0, 4

ck = 4γk2 σ 2 ,

dk = 24γk2 L2 .

Proof. Because x⋆ ∈ X⋆ be a solution to (1), it satisfies ⟨F (x), x − x⋆ ⟩ ≥ 0 for all x ∈ X . Now using Lemma 3.1 with u = x⋆ , we have 2

2

2

2

∥xk+1 − x⋆ ∥ ≤ ∥xk − x⋆ ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ + 2γk ⟨F (xk ; ξik ) − F (x̂k ; ξik ), xk+1 − x̂k ⟩ − 2γk ⟨F (x̂k ; ξik ), x̂k − x⋆ ⟩ 2

2

2

2

2

≤ ∥xk − x⋆ ∥ − ∥xk+1 − x̂k ∥ − ∥x̂k − xk ∥ + γk2 ∥F (xk ; ξik ) − F (x̂k ; ξik )∥ + ∥xk+1 − x̂k ∥ − 2γk ⟨F (x̂k ), x̂k − x⋆ ⟩ −2γk ⟨F (x̂k ; ξik ) − F (x̂k ), x̂k − x⋆ ⟩ {z } | =ek ≥0 2

2

2

≤ ∥xk − x⋆ ∥ − ∥x̂k − xk ∥ + γk2 ∥F (xk ; ξik ) − F (x̂k ; ξik )∥ − 2γk ⟨F (x̂k ; ξik ) − F (xk ; ξik ), x̂k − x⋆ ⟩ − 2γk ⟨F (xk ; ξik ) − F (xk ), x̂k − x⋆ ⟩ − 2γk ⟨F (xk ) − F (x̂k ), x̂k − x⋆ ⟩ − ek 1 2 2 2 2 ∥F (x̂k ; ξik ) − F (xk ; ξik )∥ + 4γk2 L2 ∥x̂k − x⋆ ∥ ≤ ∥xk − x⋆ ∥ − (1 − γk2 L2 ) ∥x̂k − xk ∥ + 4L2 − 2γk ⟨F (xk ; ξik ) − F (xk ), x̂k − xk ⟩ − 2γk ⟨F (xk ; ξik ) − F (xk ), xk − x⋆ ⟩ 1 2 2 ∥F (xk ) − F (x̂k )∥ + 4γk2 L2 ∥x̂k − x⋆ ∥ − ek + 4L2 1 2 2 2 2 2 ≤ ∥xk − x⋆ ∥ − (1 − γk2 L2 ) ∥x̂k − xk ∥ + ∥xk − x̂k ∥ + 4γk2 L2 (2 ∥xk − x⋆ ∥ + 2 ∥xk − x̂k ∥ ) 4 1 2 2 + 4γk2 ∥F (xk ; ξik ) − F (xk )∥ + ∥xk − x̂k ∥ − 2γk ⟨F (xk ; ξik ) − F (xk ), xk − x⋆ ⟩ 4 1 2 2 2 + ∥xk − x̂k ∥ + 4γk2 L2 (2 ∥xk − x⋆ ∥ + 2 ∥xk − x̂k ∥ ) − ek 4    1 2 2 2 − 17γk2 L2 ∥x̂k − xk ∥ + ek + 4γk2 ∥F (xk ; ξik ) − F (xk )∥ ≤ (1 + 16γk2 L2 ) ∥xk − x⋆ ∥ − 4 − 2γk ⟨F (xk ; ξik ) − F (xk ), xk − x⋆ ⟩ . The conclusion follows by taking the expectation conditioned on Fk and applying Proposition 2.7 to bound the third term. Proof of Theorem 3.3. Let ν = A + 2L2 . Applying Lemma 3.6(ii) to the bound of Lemma 3.7 with bk = 0, ck = 6γk2 σ⋆2 and dk = 6γk2 (A + 2L2 ), we obtain h i   δDδ2 2 2 E ∥xk − x⋆ ∥ ≤ ∥x0 − x⋆ ∥ + 6σ⋆2 Γ e6νΓ = 4 for all k ≥ 0, and an event Eδ with Prob [Eδ ] ≥ 1 − δ such that   2 ∥x0 − x⋆ ∥ + 6σ⋆2 Γ e6νΓ D2 2 sup ∥xk − x⋆ ∥ ≤ = δ. δ 4 k≥0 17

It remains to prove the gap function bound conditioned on Eδ . Let XDδ /2 := X ∩ B x⋆ , D2δ , and denote Gk = b k := F (x̂k ; ξ ) and ∆k = F (x̂k ) − G b k . For any u ∈ XD /2 , using Lemma 3.1, we obtain F (xk ; ξik ), G δ îk D E   D E b k , x̂k − u ≤ 1 ∥u − xk ∥2 − ∥u − xk+1 ∥2 − 1 ∥x̂k − xk ∥2 − 1 ∥xk+1 − x̂k ∥2 + Gk − G b k , xk+1 − x̂k G 2γk 2γk 2γk   1 1 1 2 2 2 2 ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥x̂k − xk ∥ − ∥xk+1 − x̂k ∥ ≤ 2γk 2γk 2γk 2 γk b k + 1 ∥xk+1 − x̂k ∥2 Gk − G + 2 2γk   2 1 1 γk 2 2 2 bk . Gk − G (19) ≤ ∥u − xk ∥ − ∥u − xk+1 ∥ − ∥x̂k − xk ∥ + 2γk 2γk 2 Now we add Tk = ⟨∆k , x̂k − u⟩ to the both sides of (19) and upper bound it as Tk = ⟨∆k , xk − u⟩ + ⟨∆k , x̂k − xk ⟩ γk 1 2 2 ≤ ⟨∆k , xk − u⟩ + ∥∆k ∥ + ∥x̂k − xk ∥ 2 2γk to obtain ⟨F (x̂k ), x̂k − u⟩ ≤

 γ 2 1  k 2 2 b k + ⟨∆k , xk − u⟩ + γk ∥∆k ∥2 . Gk − G ∥u − xk ∥ − ∥u − xk+1 ∥ + 2γk 2 2

Lower-bounding the left hand side with ⟨F (u), x̂k − u⟩ by monotonicity of F , summing from k = 0 to N , applying the same telescoping as in Proposition 2.11 and maximizing over u ∈ XDδ /2 , we obtain on Eδ max

u∈XDδ /2

N X

⟨F (u), x̂k − u⟩ = (N + 1)Errx⋆ ,Dδ /2 (x̂N ) ≤

k=0

Dδ2 + RN + SN , 2γN +1

(20)

where N

RN :=

1X γk 2



2

2



+ ∥∆k ∥

bk Gk − G

,

k=0

SN :=

N X

⟨∆k , xk − x⋆ ⟩ + max

u∈XDδ /2

k=0

N X

⟨∆k , x⋆ − u⟩ .

k=0

To bound the conditional expectations of RN and SN , define 

Dδ τ := inf k ≥ 0 ∥xk − x⋆ ∥ > 2

 ,

eN = 1 R 2

N X

 γk 1{τ >k}

2

bk Gk − G

2

+ ∥∆k ∥

 .

k=0 2

D2

Here τ is a stopping time such that 1{τ >k} is Fk -measurable, ∥xk − x⋆ ∥ ≤ 4δ on the event {τ > k}, and Eδ ⊂ {τ > k} for any k ≥ 0. Therefore, we can bound the conditional expectation of RN as h i eN Eδ ≤ E [RN | Eδ ] = E R

   N h i X 2 1 eN ≤ 1 b k + ∥∆k ∥2 E R γk E 1{τ >k} Gk − G 1−δ 1−δ k=0    N 2 1 X 2 2 b γk E 1{τ >k} 2 ∥Gk ∥ + 2 Gk + ∥∆k ∥ . ≤ 1−δ k=0

2

Dδ2

Now, using (16) and the fact that ∥xk − x⋆ ∥ ≤ 4 on the event {τ > k}, we have h i h h ii h  i 2 2 2 E 1{τ >k} ∥Gk ∥ ≤ E 1{τ >k} E ∥Gk ∥ Fk ≤ E 1{τ >k} ν ∥xk − x⋆ ∥ + σ⋆2 ≤ νDδ2 + σ⋆2 . Proceeding in a similar way using (16) together with (17), proved in Lemma 3.7, gives   h h ii 2 2 bk E 1{τ >k} G ≤ E 1{τ >k} E ν ∥x̂k − x⋆ ∥ + σ⋆2 Fk 18

(21)

i  h  
2 ≤ E 1{τ >k} ν (1 + γk2 ν) ∥xk − x⋆ ∥ + γk2 σ⋆2 + σ⋆2 ≤ 2 νDδ2 + σ⋆2 where we use γk2 ν ≤ 1 in the last inequality. Finally, using (17) again, ii h i h h 2 2 E 1{τ >k} ∥∆k ∥ ≤ E 1{τ >k} E ∥∆k ∥ F̂k i h  2 ≤ E 1{τ >k} A ∥x̂k − x⋆ ∥ + σ 2 i i h  h 2 ≤ E 1{τ >k} A E ∥x̂k − x⋆ ∥ Fk + σ 2 i  h   2 ≤ E 1{τ >k} A (1 + γk2 ν) ∥xk − x⋆ ∥ + γk2 σ⋆2 + σ 2
≤ 2 νDδ2 + σ⋆2

(22)

where in the last line, we use A ≤ ν and γk2 ν ≤ 1. Plugging these bounds back into (21), we obtain E [RN | Eδ ] ≤

N 8 νDδ2 + σ⋆2 X γk . 1−δ

(23)

k=0

i h e k = ∆k 1{τ >k} . Because 1{τ >k} is F̂k -measurable and E ∆k F̂k = 0, we also have Finally, to bound SN , define ∆ i h e k F̂k = 0. Moreover, on Eδ , ∆k = ∆ e k for every k ≥ 0, so E ∆ 1Eδ SN ≤

! N D N E X X e ek . ∆k , xk − x⋆ + Dδ ∆ k=0

+

k=0

e k, Therefore, by Cauchy-Schwarz inequality and the martingale difference property of ∆ 1 E [1Eδ SN ] Prob [Eδ ]     1/2  !2 1/2 2 N D N E X X 1   e k , xk − x⋆ e k    + Dδ E  ∆ ∆ ≤ E  1−δ 2

E [SN | Eδ ] =

k=0

k=0

! D N E2  1/2 D 1  X δ e k , xk − x⋆ E ∆ ≤ + 1−δ 2 

k=0

 We have the upper bound (22) on E

2

ek ∆

E

N X

 E

2

ek ∆

 !1/2 .

(24)

k=0

 D2 2 , and because ∥xk − x⋆ ∥ ≤ 4δ on {τ > k}, this also implies

D  E2  D 2  2 e k , xk − x⋆ ek ∆ ≤ δE ∆ 4

(25)

Plugging (22) and (25) into (24), we obtain E [SN | Eδ ] ≤

2Dδ 1−δ

q

(N + 1) (νDδ2 + σ⋆2 ).

Taking conditional expectation in (20) and using (23) and (26) gives the desired bound   s N 2 + σ2 X  
νD Dδ2 1  ⋆ δ E Errx⋆ ,Dδ /2 (x̂N ) Eδ ≤ + 8 νDδ2 + σ⋆2 γk + 2Dδ . 2(N + 1)γN +1 1−δ N +1 k=0

19

(26)

Proof of Theorem 3.4. Applying Lemma 3.6(ii) to the bound of Lemma 3.8, we have h i   2 δDδ2 2 2 E ∥xk − x⋆ ∥ ≤ ∥x0 − x⋆ ∥ + 4σ 2 Γ e24L Γ = 4 for all k ≥ 0, and with probability at least 1 − δ,  2

 2 2 ∥x0 − x⋆ ∥ + 4σ 2 Γ e24L Γ

sup ∥xk − x⋆ ∥ <

=

δ

k≥0

Dδ2 . 4

On this event Eδ , we proceed using the same argument as in the proof of Proposition 2.11; for any u ∈ XDδ /2 :=
X ∩ B x⋆ , D2δ , we have     1 1 1 1 1 2 2 ∥u − xk ∥ − ∥u − xk+1 ∥ + − Dδ2 ⟨F (x̂k ), x̂k − u⟩ ≤ 2γk 2γk+1 2 γk+1 γk (27) 1 2 (1 − γk2 L2 ) ∥x̂k − xk ∥ + ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ − 2γk because on Eδ , ∥xk − u∥ ≤ ∥xk − x⋆ ∥ + ∥x⋆ − u∥ ≤ Dδ for all k. Then we bound the last inner product as ⟨F (x̂k ) − F (x̂k ; ξik ), x̂k − u⟩ = ⟨F (x̂k ) − F (xk ), x̂k − u⟩ + ⟨F (xk ) − F (xk ; ξik ), x̂k − u⟩ + ⟨F (xk ; ξik ) − F (x̂k ; ξik ), x̂k − u⟩ 1 2 2 ∥F (x̂k ) − F (xk )∥ + 4γk L2 ∥x̂k − u∥ + ⟨F (xk ) − F (xk ; ξik ), x̂k − u⟩ ≤ 16γk L2 1 2 2 + ∥F (xk ; ξik ) − F (x̂k ; ξik )∥ + 4γk L2 ∥x̂k − u∥ 16γk L2 1 2 2 ∥x̂k − xk ∥ + 8γk L2 ∥x̂k − u∥ + ⟨F (xk ) − F (xk ; ξik ), x̂k − xk ⟩ + ⟨F (xk ) − F (xk ; ξik ), xk − u⟩ ≤ 8γk   1 1 2 2 2 2 2 ≤ ∥x̂k − xk ∥ + 8γk L2 2 ∥xk − u∥ + 2 ∥x̂k − xk ∥ + 2γk ∥F (xk ) − F (xk ; ξik )∥ + ∥x̂k − xk ∥ 8γk 8γk + ⟨F (xk ) − F (xk ; ξik ), xk − u⟩   1 2 2 + 16γk L2 ∥x̂k − xk ∥ + 16γk L2 Dδ2 + 2γk ∥F (xk ) − F (xk ; ξik )∥ + ⟨F (xk ) − F (xk ; ξik ), xk − u⟩ . = 4γk Plugging this back into (27), using monotonicity of F and telescoping, we obtain max

u∈XDδ /2

N X

⟨F (u), x̂k − u⟩

k=0 N

≤

X 1 Dδ2 − 2γN +1 2γk k=0



 N   X 1 2 2 − 33γk2 L2 ∥x̂k − xk ∥ + γk 16L2 Dδ2 + 2 ∥F (xk ) − F (xk ; ξik )∥ 2 k=0 | {z }

(28)

=RN

+

N X

⟨F (xk ) − F (xk ; ξik ), xk − x⋆ ⟩ + max

u∈XDδ /2

k=0

N X

⟨F (xk ) − F (xk ; ξik ), x⋆ − u⟩ .

k=0

{z

|

}

=SN

Note that 12 − 33γk2 L2 > 0 by our choice of γk , so the second term is nonpositive. Next, define 

Dδ τ = inf k ≥ 0 ∥xk − x⋆ ∥ > 2

 ,

eN = R

N X

  2 γk 1{τ >k} 16L2 Dδ2 + 2 ∥F (xk ) − F (xk ; ξik )∥ .

k=0 2

Here τ is a stopping time such that 1{τ >k} is Fk -measurable, ∥xk − x⋆ ∥ ≤

20

Dδ2 4

on the event {τ > k}, and Eδ ⊂ {τ > k}

for any k ≥ 0. Therefore, we can bound the conditional expectation of RN as i h eN Eδ ≤ E [RN | Eδ ] = E R

N h i    h i X 1 2 eN ≤ 1 E R γk 16L2 Dδ2 + 2 2L2 E 1{τ >k} ∥xk − x⋆ ∥ + σ 2 1−δ 1−δ k=0

(29)

N

17L2 Dδ2 + 2σ 2 X ≤ γk . 1−δ k=0

Finally, the conditional expectation of SN can be bounded similarly as in the proof of Theorem 3.3: letting ∆k = F (xk ) − F (xk ; ξik ),

e k = ∆k 1{τ >k} , ∆

i h e k on Eδ , which implies e k Fk = 0 and ∆k = ∆ we have E ∆ 1Eδ SN ≤

! N D N E X Dδ X e e ∆k . ∆k , xk − x⋆ + 2

k=0

k=0

+

e k , we obtain Using Cauchy-Schwarz and the martingale difference property of ∆   ! !1/2 D  N N E2  1/2 D X 2 1  X δ ek e k , xk − x⋆ . E [SN | Eδ ] ≤ E ∆ + E ∆ 1−δ 2 k=0

k=0

h i δD 2 2 Now we note that by Proposition 2.7 and E ∥xk − x⋆ ∥ ≤ 4 δ , 

2

ek ∆

E



h h ii h i L2 δD2 2 2 δ = E 1{τ >k} E ∥F (xk ) − F (xk ; ξik )∥ Fk ≤ E 2L2 ∥xk − x⋆ ∥ + σ 2 ≤ + 2σ 2 2 2

e k is supported on {τ > k} where ∥xk − x⋆ ∥ ≤ and furthermore, because ∆ E

D

e k , xk − x⋆ ∆

E2 

Dδ2 4 ,

      2 2 Dδ2 Dδ2 L2 δDδ2 2 2 e e ≤ E 1{τ >k} ∆k ∥xk − x⋆ ∥ ≤ E ∆k ≤ + 2σ . 4 4 2

Plugging the resulting bound on E [SN | Eδ ] and (29) into (28), we obtain " E

max

u∈XDδ /2

N X k=0

# ⟨F (u), x̂k − u⟩ Eδ

N

Dδ Dδ2 17L2 Dδ2 + 2σ 2 X γk + ≤ + 2γN +1 1−δ 1−δ

s (N + 1)

k=0



 L2 δDδ2 2 + 2σ . 2

The conclusion follows by dividing throughout by N + 1. 3.2.2

Beyond the high-probability theorems: Impossibility via counterexamples

Theorems 3.3 and 3.4 from the previous section P∞ provide high-probability guarantees on the gap function (Corollary 3.5) given the step-size satisfying γ̂k = γk and k=0 γk2 < ∞. In this section, we provide the results complementary to them. First we show that for both I-SEG and S-SEG, the square summability assumption on the step-size cannot be removed without replacement, by presenting a stochastic VIP for which even the high-probability gap functionPconvergence cannot ∞ be guaranteed with non-square-summable step-sizes. Then we show that even when γk = γ̂k and k=0 γk2 < ∞, there exists a counterexample where each SEG trajectory escapes any bounded disk with positive probability. Therefore, no pre-specified bounded region makes the gap function a meaningful measure of convergence with probability 1, showing that the high-probability approach of Theorems 3.3 and 3.4 is suitably tight. Theorem 3.9. There exists a stochastic VIP (1) on the unconstrained domain X = R2 with unique solution x⋆ = 0, 1 satisfying Assumptions 2.1, 2.3 and 2.4, but S-SEG with γ̂k = γk = √k+1 satisfies ∥xk ∥ → ∞ and lim supk→∞ x̂k = ∞

21

1 almost surely for every x0 ̸= x⋆ , where x̂k = k+1

Pk

j=0 x̂j . Consequently, for every D > 0,

Errx⋆ ,D (xk ) → ∞,

lim sup Errx⋆ ,D (x̂k ) = ∞ k→∞

almost surely.

Theorem 3.10. There exists a stochastic VIP (1) on X = R2 with unique solution x⋆ = 0, satisfying Assumptions 2.1, 1 satisfies ∥xk ∥ → ∞ and lim supk→∞ x̂k = ∞ almost surely for every 2.2, 2.4 and 2.6, but I-SEG with γ̂k = γk = √k+1 P k 1 x0 ̸= x⋆ , where x̂k = k+1 j=0 x̂j . Consequently, for every D > 0, Errx⋆ ,D (xk ) → ∞,

lim sup Errx⋆ ,D (x̂k ) = ∞ k→∞

almost surely. 1 Remark. While the counterexamples for the above theorems use the step-sizes γk = √k+1 for simplicity, they can be 1 replaced by √k+r with any r > 0 without any essential change to the proof, so that γk satisfies the requirements in convergence theorems presented in earlier sections.

In the proofs of Theorems 3.9 and 3.10 below and several later results, we will consider the specific linear counterexample sharing the same structure. We present a handy lemma for analyzing the iterates of SEG when run on general problems of such form.   0 −1 Lemma 3.11. Let J = , and let F (x; ξ1 ) = (ρI + (1 + ν)J)x and F (x; ξ2 ) = (−ρI + (1 − ν)J)x for x ∈ X = R2 , 1 0 where ρ, ν ∈ R are fixed. Then the stochastic VIP with F (x) = 12 (F (x; ξ1 ) + F (x; ξ2 )) satisfies Assumption 2.1 and p Assumption 2.3 with L = ρ2 + (1 + |ν|)2 , has the mean operator F (x) = Jx given that i ∈ {1, 2} is sampled uniformly, √ and has a unique solution x⋆ = 0. By identifying R2 with C via x = (x1 , x2 ) ←→ z(x) = x1 + ix2 where i = −1, the S-SEG iterates xk can be identified with zk = z(xk ) ∈ C generated by the following rule: • For S-SEG, ẑk = (1 − γ̂k (sk ρ + i(1 + sk ν))) zk and zk+1 = zk ·bsk (γk , γ̂k ) where sk ∈ {+1, −1} is sampled uniformly and
bs (γ, γ̂) = 1 + γ (ρ2 − (1 + sν)2 )γ̂ − sρ + iγ ((1 + sν)(2sργ̂ − 1)) . • For I-SEG, ẑk = (1 − γ̂k (uk ρ + i(1 + uk ν))) zk and zk+1 = zk · cuk ,sk (γk , γ̂k ) where uk , sk ∈ {+1, −1} are sampled uniformly and independently, and
cu,s (γ, γ̂) = 1 + γ (ρ2 su − (1 + sν)(1 + uν))γ̂ − sρ + iγ (ρ(s + u + 2suν)γ̂ − (1 + sν)) . Proof. It is clear that F (x) = Jx is monotone (Assumption 2.1) with unique zero x⋆ = 0. Additionally, both F (·; ξ1 ) and F (·; ξ2 ) are Lipschitz continuous with p L = max {∥ρI + (1 + ν)J∥ , ∥−ρI + (1 − ν)J∥} = ρ2 + (1 + |ν|)2 so Assumption 2.3 holds. Next, √ observe that under the identification of x = (x1 , x2 ) by z(x) = x1 + ix2 , the operator J acts as multiplication by i = −1 because iz(x) = i(x1 + ix2 ) = −x2 + ix1 = z(−x2 , x1 ) = z(Jx). Now for S-SEG, let sk ∈ {+1, −1} denote the sampled sign at iteration k, with sk = +1 corresponding to ξ1 and sk = −1 to ξ2 . Then the update rule, written in terms of the complex number, is given by ẑk = zk − γ̂k (sk ρ + i(1 + sk ν))zk = (1 − γ̂k (sk ρ + i(1 + sk ν)))zk zk+1 = zk − γk (sk ρ + i(1 + sk ν))ẑk = (1 − γk (sk ρ + i(1 + sk ν))(1 − γ̂k (sk ρ + i(1 + sk ν)))) zk and rearranging the last factor and using s2k = 1 yields the claimed form of bsk (γk , γ̂k ). Similarly, for I-SEG, let uk , sk ∈ {+1, −1} respectively denote the sampled sign for the extrapolation and update steps. Then the recursion is given by ẑk = zk − γ̂k (uk ρ + i(1 + uk ν))zk = (1 − γ̂k (uk ρ + i(1 + uk ν)))zk 22

zk+1 = zk − γk (sk ρ + i(1 + sk ν))ẑk = (1 − γk (sk ρ + i(1 + sk ν))(1 − γ̂k (uk ρ + i(1 + uk ν)))) zk and rearranging the last factor, we obtain the form of cuk ,sk (γk , γ̂k ). Proof of Theorem 3.9. Consider the stochastic VIP of Lemma 3.11 with ρ = 2, ν = 0 and γ̂k = γk , and let zk , ẑk be complex numbers corresponding to the S-SEG iterates xk , x̂k . We can write zk+1 = bsk (γk )zk where we write bs (γ) := bs (γ, γ) = 1 − γ(2s + i) + γ 2 (2s + i)2 = (1 − 2sγ + 3γ 2 ) − i(γ − 4sγ 2 ). By direct computation, we obtain |bs (γ)|2 = 1 − 4sγ + 11γ 2 − 20sγ 3 + 25γ 4 . Hence, by plugging t
= |bs (γ, γ)|2 − 1 = −4sγ + 11γ 2 − 20sγ 3 + 25γ 4 into the Taylor expansion 12 log(1 + t) = 1 3 1 1 2 2 t − 2 t + 3 t − · · · , we obtain log |bs (γ)| =

1 1 1 3 log(1 + t) = t − t2 + O t3 = −2sγ + γ 2 + O γ 3 2 2 4 2

provided that |t| < 1. Hence, if γ < 18 , there exists a constant C > 0 such that 3 log |bs (γ)| + 2sγ − γ 2 ≤ Cγ 3 , 2

|log |bs (γ)|| ≤ Cγ.

(30)

Additionally, tan arg bs (γ) = −

 
γ − 4sγ 2 = −γ(1 − 4sγ) 1 + (2sγ − 3γ 2 ) + (2sγ − 3γ 2 )2 + · · · = −γ + 2sγ 2 + O γ 3 2 1 − 2sγ + 3γ

1 where we use the Taylor expansion 1−t = 1 + t + t2 + · · · with t = 2sγ − 2γ 2 which holds when |t| < 1, and in particular,
3 5 if γ < 18 . Because arctan t = t − t3 + t5 − · · · , this implies arg bs (γ) = −γ + 2sγ 2 + O γ 3 , so by possibly increasing the constant C in (30), we have

arg bs (γ) + γ − 2sγ 2 ≤ Cγ 3 ,

|arg bs (γ)| ≤ Cγ

(31)

1 for γ < 81 . Since γk = √k+1 → 0, there exists K ∈ N such that conditions (30) and (31) will hold with γ = γk for all k ≥ K. Then, using those bounds and s2k = 1, we obtain

log |zN +1 | = log |zK | +

N X

log |bsk (γk )|

k=K

≥ log |zK | − 2

N X

√

N N X C sk 3 X 1 + − k + 1 2 k=K k + 1 k=K (k + 1)3/2

√

N 3 X 1 sk + − 3C k + 1 2 k=K k + 1

k=K

≥ log |zK | − 2

N X k=K

(32)

R∞ P∞ PN k where the last inequality follows from k=K (k + 1)−3/2 < k=1 k −3/2 ≤ 1 + 1 x−3/2 dx = 3. Now the Yk = √sk+1 are mutually independent and zero-mean random variables, and   Yk Var(Yk ) 1 Var = = 2 log(k + 2) log (k + 2) (k + 1) log2 (k + 2) P∞ Yk is summable, so by Kolmogorov’s two-series theorem, k=0 log(k+2) converges almost surely. On that event, by Kronecker’s P P PN N N 1 k lemma, we have log(N +2) k=0 Yk → 0. In other words, k=0 Yk = k=0 √sk+1 = o(log N ) almost surely. Together with (32), this implies N

log |zN +1 | ≥ log |zK | − 3C − o(log N ) +

3 X 1 3 = log N − o(log N ) = log N 2 k+1 2 k=K

23



3 − o(1) 2



3

and thus ∥xN ∥ = |zN | ≥ N 2 −o(1) → ∞ almost surely. Next, we turn to the ergodic average of the extrapolated iterates; let w bN =

N X

N

ẑk = (N + 1)ẑ N ,

ẑ N =

1 X ẑk . N +1 k=0

k=0

PN We will show that the limit superior of |ẑ N | = x̂N is infinity, where x̂N = N1+1 k=0 x̂k . Given N ∈ N, let mN = ⌊N 1/4 ⌋. For N sufficiently large so that N − mN ≥ K, for any N − mN ≤ k ≤ N , using the bound |log |bs (γ)|| ≤ Cγ from (30) we have log

N −1

N −1

j=k

j=k

X X |zk | C CmN √ ≤ log |bsj (γj )| ≤ = O(N −1/4 ). ≤√ |zN | j+1 N − mN

Similarly, using (31), |arg zk − arg zN | ≤

N −1 X

arg bsj (γj ) ≤

j=k

N −1 X

√

j=k

C CmN = O(N −1/4 ). ≤√ j+1 N − mN

Therefore, for all sufficiently large N , if N − mN ≤ k ≤ N , then 1 |zN | ≤ |zk | ≤ 2|zN |, 2

|arg zk − arg zN | ≤

π . 6

(33)

Moreover, since ẑk = (1 − γk (2sk + i)) zk and γk → 0, by increasing K if necessary, we may also assume that, for all k ≥ K, |1 − γk (2sk + i)| ≥

1 , 2

|arg (1 − γk (2sk + i))| ≤

π . 6

Hence, for all sufficiently large N and all N − mN ≤ k ≤ N , |ẑk | ≥

1 1 |zk | ≥ |zN |, 2 4

|arg ẑk − arg zN | ≤

π . 3

Now consider the partial sum N X

dbN :=

ẑk = w bN − w bN −mN −1 .

k=N −mN

Let uN = zN /|zN |. Then, for all sufficiently large N and all k = N − mN , . . . , N , Re (u∗N ẑk ) = |ẑk | cos(arg ẑk − arg zN ) ≥

1 1 |ẑk | ≥ |zN |, 2 8

where u∗N denotes the complex conjugate. Therefore,   |w bN − w bN −mN −1 | = |dbN | ≥ Re u∗N dbN =

N X

Re (u∗N ẑk ) ≥

k=N −mN

mN |zN | . 8

This implies max{|w bN |, |w bN −mN −1 |} ≥

|dbN | mN |zN | ≥ . 2 16

Dividing by the appropriate denominators gives  max{|ẑ N |, |ẑ N −mN −1 |} = max ≥

|w bN | |w bN −mN −1 | , N + 1 N − mN



1 mN |zN | max{|w bN |, |w bN −mN −1 |} ≥ . N +1 16(N + 1) 24

Because mN = Θ(N 1/4 ) and |zN | = N 3/2−o(1) almost surely, the right-hand side diverges to infinity almost surely. Therefore, lim sup |ẑ N | = ∞, N →∞

and equivalently, lim sup x̂N = ∞

a.s.

N →∞

Because Errx⋆ ,D (x) = D ∥x∥ for any x for this problem, we conclude that Errx⋆ ,D (xk ) → ∞,

lim sup Errx⋆ ,D (x̂k ) = ∞. k→∞

I-SEG dynamics on the same problem converges. When I-SEG is instead run on the same stochastic problem, xk converges to x⋆ = 0 almost surely, unlike S-SEG. See Figure 1a for visual comparison. To check this analytically, applying Lemma 3.11 and plugging in γk = γ̂k , we have zk+1 = cuk ,sk (γk )zk with
cu,s (γ) := cu,s (γ, γ) = 1 − 2sγ + (4us − 1)γ 2 − i γ − 2(u + s)γ 2 (34) and using u2 = s2 = 1, we obtain |cu,s (γ)|2 = 1 − 4sγ + (3 + 8us)γ 2 − 20uγ 3 + 25γ 4   5 =⇒ log |cu,s (γ)| = −2sγ + − + 4us γ 2 + O(γ 3 ). 2

(35)

Here the crucial difference is that the expectation of the second term is − 52 γ 2 has a negative coefficient, while for S-SEG, the coefficient of γ 2 is a positive constant. Therefore, taking the logarithm we obtain log |zN +1 | = log |zK | − 2

N X k=K

√

N N X sk 5 X 1 uk sk − +4 + O(1). k+1 k + 1 2 k=K k + 1 k=K

PN

PN PN 1 k k sk As before, we have k=K √sk+1 = − 25 log N + O(1), and k=K uk+1 converges = o(log N ) almost surely, − 52 k=K k+1 almost surely by Kolmogorov’s two-series as it is a sum of independent, zero-mean and square summable random variables. This shows that zN → 0 almost surely, which implies that both to 0 almost surely. h i xk and x̂k converges
2 2 It is worth noting that, on the other hand, E ∥xk+1 ∥ Fk = 1 + 3γk2 + 25γk4 ∥xk ∥ for I-SEG run on this example. 2

That is, even if the expectation of ∥xk ∥ strictly increases over iterations, we still have xk → 0 almost surely. There is no contradiction here—expectation of random variables may increase, and even blow up, even if the random variable itself converges to 0 almost surely: take, for example, the sample space Ω = [0, 1] and random variables Xn (ω) = n2 1(0,1/n] (ω). 2 Hence, showing that ∥xk − x⋆ ∥ increases in expectation, as done in several prior work [18, 34, 17], is by itself not sufficient to guarantee that the algorithm’s dynamics is truly divergent. In the proof of Theorem 3.10 below, we demonstrate a counterexample where I-SEG diverges almost surely. Proof of Theorem i3.10. Consider the stochastic VIP from Lemma 3.11 with ρ = 0 and ν = 2. Then, because h 2 2 E ∥F (x; ξ) − F (x)∥ = 4 ∥x∥ , (5) holds with A = 4 and σ = 0. By Lemma 3.11, for sk , uk ∈ {+1, −1}, we have ẑk = (1 − iγk (1 + 2uk )) zk ,

zk+1 = cuk ,sk (γk ) zk ,

where cu,s (γ) := cu,s (γ, γ) = 1 − γ 2 (1 + 2s)(1 + 2u) − iγ(1 + 2s).
Then, using u2 = s2 = 1, we obtain |cu,s (γ)|2 = 1 + (3 − 4u − 8su) γ 2 + O γ 4 . Thus, for γ small enough,   3 − 2u − 4su γ 2 + O(γ 4 ) log |cu,s (γ)| = 2 and | arg cu,s (γ)| = arctan

−γ(1 + 2s) 1 − γ 2 (1 + 2s)(1 + 2u) 25

= −γ(1 + 2s) + O γ 3

≤ Cγ

for some fixed constant C > 0. Now, we have log |zN | = log |z0 | +

N −1 X

log |cuk ,sk (γk )| = log |z0 | +

k=0

N −1  X k=0

 N −1 X
3 − 2uk − 4sk uk γk2 + O γk4 , 2 k=0

P∞ 4 and the last summation almost surely converges to a finite constant because k=0 γk < ∞. On the other hand,
2 3 2 3 4 − 2u − 4s u γ has mean γ and summable O(γ ) variance, so by Kolmogorov’s two-series theorem, we have k k k k k 2 2 k N

3 3X 2 log |zN | = γk + O(1) = log N + O(1). 2 2 k=0

Hence ∥xN ∥ = |zN | → ∞ almost surely. It remains to show that the ergodic average also diverges along a subsequence. Let mN = ⌊N 1/4 ⌋. Then for N sufficiently large and N − mN ≤ k ≤ N , similar argument as in the proof of Theorem 3.9, using N −1

log

X |zk | ≤C γj2 = O(N −3/4 ), |zN |

| arg zk − arg zN | ≤ C

j=k

N −1 X

γj = O(N −1/4 ),

ẑk = (1 + O(γk )) zk

j=k

yields max{ x̂N , x̂N −mN −1 } ≥

mN ∥xN ∥ . 16(N + 1)

Since mN = Θ(N 1/4 ) and ∥xN ∥ = N 3/2+o(1) almost surely, the right-hand side diverges almost surely, showing that lim supk→∞ x̂k = ∞. Interestingly, although we do not formally argue it here, the S-SEG dynamics on the same problem considered in the above proof converges (Figure 1b). This indicates that neither I-SEG nor S-SEG is not strictly preferred over the other, and they could behave differently depending on the geometry of the stochastic problem. Finally, we show that even when γk = γ̂k is square summable, we cannot have any uniform gap function guarantee. For the stochastic monotone VIP considered in the proof of Theorem 3.9, for any M > 0, albeit with low probability scaling down as M grows, we have lim supk→∞ Errx⋆ ,D (x̂k ) > M with both types of SEG. In this sense, the high probability bounds established in Theorems 3.3 and 3.4 are tight results for SEG using symmetric step-sizes in unbounded domains. Theorem 3.12. Consider the stochastic VIP from Theorem 3.9. If SEG (either same-sample or independent-sample) is run this problem with initial point x0 ̸= 0 and γ̂k = γk satisfying 0 < γk < γ for all k ≥ 0 and sufficiently small γ Pon ∞ and k=0 γk2 < ∞, then there exists a positive random variable R∞ such that ∥xk ∥ → R∞ almost surely. In particular, η if γ̂k = γk = k+1 where η > 0 is sufficiently small, then we also have ∥xk ∥ → p

R∞ 1 + η2

x̂k → p

,

R∞ 1 + η2

Pk Pk 1 1 almost surely, where xk = k+1 j=0 xj and x̂k = k+1 j=0 x̂j . Moreover, the law of R∞ is unbounded, and consequently, for every D > 0,     Prob lim Errx⋆ ,D (xk ) > M > 0, Prob lim Errx⋆ ,D (x̂k ) > M > 0, ∀M > 0. k→∞

k→∞

Proof. We first provide the proof for S-SEG. The I-SEG case follows from the essentially same arguments with minor modifications, which we specify at the end of the proof. Using Lemma 3.11 again, write zk+1 = bsk (γk )zk where sk ∈ {+1, −1} is chosen uniformly at each iteration. Because bsk (γk ) = 1 + O(γk ), for γk sufficiently small, we have |bsk (γk ) − 1| ≤ 21 . Then, using (30) and (31), we obtain
3 log |bsk (γk )| = −2sk γk + γk2 + O γk3 2
arg bsk (γk ) = −γk + 2sk γk2 + O γk3 .

26

(36) (37)

P∞ In (36), the series k=0 −2sk γk converges almost surely because each term has mean zero and their variances Var (−2sk γk ) = PN P∞ 2 4γ On that event, log |zN +1 | = log |z0 | + k=0 log |bsk (γk )| converges to a real limit because k=0 γk2 and Pk∞is summable. 3 k=0 γk are finite, and thus ∥xk ∥ = |zk | → R∞ almost surely for some finite, positive random variable R∞ > 0. η Next, fix our step-size selection to be γ̂k = γk = k+1 with η > 0 small enough so that |bs0 (η) − 1| ≤ 21 for both s0 = ±1. PN −1 1 Let HN = k=0 k+1 be the partial sum of the harmonic series. Then arg zN + ηHN = arg z0 +

N −1 X

arg bsk (γk ) +

N −1 X

k=0

k=0

N −1

X 2η 2 sk η +O = arg z0 + k+1 (k + 1)2



k=0

1 (k + 1)3



by (37), and the series in the right hand side converge absolutely, say, to θ∞ . Therefore, we obtain Since |zN | → R∞ , it follows that zN eiηHN = |zN |ei(arg zN +ηHN ) → R∞ eiθ∞ almost surely. It is well-known that limN →∞ (HN − log N ) = limN →∞ (HN − log(N + 1)) = γEuler ≈ 0.577 (the Euler constant), so we have zN eiηHN = zN eiη(log(N +1)+γEuler )+o(1) = zN eiηγEuler (N + 1)iη (1 + o(1)) → R∞ eiθ∞ so letting A∞ = R∞ ei(θ∞ −ηγEuler ) , we can write zN = A∞ (N + 1)−iη + |zN | o(1) = A∞ (N + 1)−iη + o(1) = A∞ (N + 1)−iη + rN almost surely, where rN = zN − A∞ (N + 1)−iη = |zN | o(1) = o(1) because |zN | → R∞ . Then the sequence rk is Cesàro PN summable with N1+1 k=0 rk → 0 as N → ∞. Hence zN =

N

N

N

N

k=0

k=0

k=0

k=0

1 X A∞ X 1 X A∞ X zk = (k + 1)−iη + rk = (k + 1)−iη + o(1). N +1 N +1 N +1 N +1

Now observe that N

N +1 

1 X 1 X (k + 1)−iη = (N + 1)−iη N +1 N +1 k=0

k=1

k N +1

−iη = (N + 1)

−iη

Z 1 x

−iη

 dx + o(1) =

0

(N + 1)−iη + o(1), 1 − iη

R1

1 and (N + 1)−iη = 1. The second equality follows from the x−iη dx = 1−iη R1 convergence of the Riemann sum representing the improper integral 0 x−iη dx, which exists because x−iη = 1 for any x > 0. Combining the above, we see that

where the last equality uses the fact that

zN =

0

A∞ (N + 1)−iη |A∞ | R∞ + o(1) =⇒ lim ∥xN ∥ = lim |z N | = =p N →∞ N →∞ 1 − iη |1 − iη| 1 + η2

almost surely. The same limit holds for the ergodic average of the extrapolated iterates. Indeed, since η (2sk + i)zk , k+1

ẑk = (1 − γk (2sk + i)) zk = zk − we have ẑ N − z N

√ N N 1 X η 5 X |zk | = (ẑk − zk ) ≤ . N +1 N +1 k+1 k=0

k=0

Since |zk | → R∞ almost surely, the sequence (|zk |)k≥0 is almost surely bounded. Hence, almost surely, ẑ N − z N

√ N η 5 supk≥0 |zk | X 1 ≤ →0 N +1 k+1 k=0

as N → ∞. Therefore, lim

N →∞

x̂N = lim |ẑ N | = lim |z N | = p N →∞

N →∞

27

R∞ 1 + η2

almost surely. Finally, we show that the law of R∞ is unbounded. For m = 1, 2, . . . , consider ∞ X

log Tm :=

log |bsk (γk )| = −2η

k=m

∞ X k=m

sk + o(1) k+1

 P ∞ 1 1 where the last expression follows from (36), which shows that the residual term is O k=m (k+1)2 + (k+1)3 , which P∞ P∞ sk sk is almost surely convergent, we have k=m k+1 → 0 almost surely converges to zero as m → ∞. But because k=0 k+1 as m → ∞. Therefore, we have Tm → 1 almost surely, and because    ∞ \  [ 1 1 {Tm → 1} ⊂ lim inf Tm ≥ = Tj ≥ m→∞ 2 2 m=1 j≥m

this in particular shows that Prob[Tm ≥ 1/2] → 1 as m → ∞. Next, consider the event Em = {s0 = · · · = sm−1 = −1}. On Em , we have m−1 m−1 X X 1 log Pm := + O(1) = 2ηHm + O(1) log |bsk (γk )| = 2η k+1 k=0

k=0

and the last quantity grows arbitrarily large with m. Hence, for any given M > 0, we can choose m that is large enough so that Prob[Tm ≥ 1/2] ≥

1 2

|z |P p0 m > M on Em . 2 1 + η2

and

Additionally, because {Tm ≥ 1/2} is independent of Em , we have Prob [Em ∩ {Tm ≥ 1/2}] = Prob [Em ] · Prob[Tm ≥ 1/2] ≥

1 2m+1

and on that event, R∞ = |z0 |Pm Tm ≥

p R∞ |z0 |Pm > 1 + η 2 M =⇒ lim x̂N = p > M. N →∞ 2 1 + η2

Note that this can be done for any M ; hence, given any M, D > 0, we can choose an event of positive probability on which limN →∞ x̂N > M D , so that lim Errx⋆ ,D (x̂N ) = lim D x̂N > M. N →∞

N →∞

Case of I-SEG. Lemma 3.11 yields zk+1 = cuk ,sk (γk )zk , where cu,s (γ) is given by (34), and as in (35) we can derive
log |cu,s (γ)| = −2sγ + − 52 + 4us γ 2 + O(γ 3 ). Furthermore, arg cu,s (γ) = −γ + 2uγ 2 + O(γ 3 ), so the first-order terms in γ are the same as in the S-SEG case, so we can proceed in the exact same way. Showing that R∞ has an unbounded law also uses the identical argument; we can take Em = {s0 = · · · = sm−1 = −1}, and show that for any M > 0, R∞ > M for sufficiently large m, uniformly over u0 , . . . , um−1 . 3.2.3

Effect of DSEG step-sizes on the convergence of SEG

The DSEG step-size rule [34] in Proposition 2.17 was designed to ensure almost sure last-iterate convergence of I-SEG for unconstrained problems under generalized variance condition similar to (5). Although [34] did not explicitly state it, as a consequence of their algorithm design and analysis, it is relatively straightforward to see that DSEG step-size also induces the gap function convergence of I-SEG on averaged iterates (Proposition 3.13). On the other hand, this is not the case for S-SEG, as we demonstrate in Section 4.2. Proposition 3.13. Let X = Rd , and let x⋆ ∈ X⋆ ∩ B(y, D), so F (x⋆ ) = 0. Suppose that Assumptions 2.1, 2.2, 2.4
1 and 2.6 hold. Then for every y ∈ Rd and D > 0, I-SEG run with initial point x0 ∈ B(y, D) and γk > 0, γ̂k ∈ 0, 3L satisfying (DSEG) satisfies h  γ i C y,D E ErrB(y,D) x̂N ≤ . ΓN

28

(38)

where Cy,D > 0 is a constant depending on y, D and the fixed problem data but not on N and x0 ∈ B(y, D), while PN PN γ ΓN = k=0 γk and x̂N := Γ1N k=0 γk x̂k . In particular, if γk = γ0 (k + 1)−a , γ̂k = γ̂0 (k + 1)−b h  γ i
with 12 < a < 1, a + b ≤ 1 and a + 2b > 1, then E ErrB(y,D) x̂N = O N −(1−a) . b k = F (x̂k ; ξ ), ∆k := F (x̂k ) − G b k , and let ηk = γ 2 + 2Lγk γ̂ 2 . Note Proof. For convenience, we write Gk = F (xk ; ξik ), G k k îk d that because X = R , we have bk , xk+1 = xk − γk G x̂k = xk − γ̂k Gk . We quickly establish some key estimates needed for the proof. First, we have i   i h h 2 2 2 2 2 E ∥Gk ∥ Fk = ∥F (xk )∥ + E ∥Gk − F (xk )∥ Fk ≤ (L2 + A) ∥xk − x⋆ ∥ + σ 2 ≤ C 1 + ∥xk − x⋆ ∥

(39)

 where we take C ≥ max L2 + A, σ 2 . Next, using E [Gk | Fk ] = F (xk ), we have i   i h h 2 2 2 2 E ∥x̂k − x⋆ ∥ Fk = ∥xk − x⋆ ∥ − 2γ̂k ⟨F (xk ), xk − x⋆ ⟩ + γ̂k2 E ∥Gk ∥ Fk ≤ C 1 + ∥xk − x⋆ ∥

(40)

1 by enlarging C if necessary, because of (39) and the fact that γ̂k is upper-bounded by 3L . This implies, again by enlarging C if necessary,   h i   2 2 2 b Fk ≤ (L2 + A)E ∥x̂k − x⋆ ∥ Fk + σ 2 ≤ C 1 + ∥xk − x⋆ ∥ . E Gk (41)

Now, we have D E 2 2 2 b k , xk − x⋆ + γk2 G bk ∥xk+1 − x⋆ ∥ = ∥xk − x⋆ ∥ − 2γk G D E D E 2 2 bk b k , x̂k − x⋆ − 2γk γ̂k G b k , Gk + γk2 G = ∥xk − x⋆ ∥ − 2γk G where we use xk − x̂k = γ̂k Gk . Conditioning first on F̂k and taking conditional expectation, the term

(42) D E b k , x̂k − x⋆ G

becomes ⟨F (x̂k ), x̂k − x⋆ ⟩ ≥ 0 so we can drop it. Furthermore, by L-Lipschitzness of F , hD E i h i b k , Gk Fk = E [⟨F (x̂k ), Gk ⟩ | Fk ] = ∥F (xk )∥2 + E [⟨F (x̂k ) − F (xk ), Gk ⟩ | Fk ] ≥ ∥F (xk )∥2 − Lγ̂k E ∥Gk ∥2 Fk . E G (43) Plugging this into (42) and also using (39) and (41), we obtain h i     2 2 2 2 E ∥xk+1 − x⋆ ∥ Fk ≤ ∥xk − x⋆ ∥ + 2Lγk γ̂k2 C 1 + ∥xk − x⋆ ∥ + γk2 C 1 + ∥xk − x⋆ ∥ 2

= (1 + Cηk ) ∥xk − x⋆ ∥ + Cηk . P∞ The DSEG step-size condition implies that k=0 ηk < ∞, so by Lemma 3.6(ii) we have ! ∞ h i X P∞ 2 2 sup E ∥xk − x⋆ ∥ ≤ ∥x0 − x⋆ ∥ + C ηk eC k=0 ηk := M < ∞. k≥0

k=0

Now fix u ∈ B(y, D) and rearrange the following identity similar to (42): D E D E 2 2 2 b k , x̂k − u − 2γk γ̂k G b k , Gk + γk2 G bk , ∥xk+1 − u∥ = ∥xk − u∥ − 2γk G to obtain γk ⟨F (u), x̂k − u⟩ ≤ γk ⟨F (x̂k ), x̂k − u⟩ 29

(44)

≤

 γ2 D E 2 1 2 2 b k − γk γ̂k G b k , Gk + γk ⟨∆k , x̂k − x⋆ ⟩ + γk ⟨∆k , x⋆ − u⟩ . ∥u − xk ∥ − ∥u − xk+1 ∥ + k G 2 2

Taking the sum of the above from k = 0 to N and using ∥x⋆ − u∥ ≤ ∥x⋆ − y∥ + ∥y − u∥ ≤ ∥x⋆ − y∥ + D := D⋆ , we have γ

ΓN ErrB(y,D) (x̂N ) =

max u∈B(y,D)

N X

γk ⟨F (u), x̂k − u⟩

k=0 N

X 1 2 ≤ ∥u − x0 ∥ + 2

k=0

 2 N N D E X X γk b 2 b Gk − γk γ̂k Gk , Gk + γk ⟨∆k , x̂k − x⋆ ⟩ + D⋆ γ k ∆k . 2 k=0

2

k=0

PN

Here we have 21 ∥u − x0 ∥ ≤ 2D2 because u, x0 ∈ B(y, D), the third term k=0 γk ⟨∆k , x̂k − x⋆ ⟩ vanishes under total expectation, and the second term can be bounded using (41), (43) and (44) as    2  2 h  i D E D E 2 2 γ b k − γk γ̂k G b k , Gk = E E γk G b k − γk γ̂k G b k , Gk Fk ≤ E Cηk 1 + ∥xk − x⋆ ∥2 ≤ Cηk (1 + M ). E k G 2 2 (45) The final term can be bounded using Cauchy-Schwarz, Jensen inequality, E [∆k | Fk ] = 0, (40) and (44): " E

N X

# ≤

γ k ∆k

k=0

N X

γk2 E

h

2

∥∆k ∥

! i 1/2

≤ AC(1 + M ) + σ

2 1/2

k=0

∞ X

!1/2 γk2

.

k=0

Putting altogether, we have ΓN E

h

i

γ ErrB(y,D) (x̂N )

2

≤ 2D + C(1 + M )

N X

ηk + D⋆ AC(1 + M ) + σ

k=0

2 1/2

∞ X

!1/2 γk2

.

k=0

Letting the right-hand side Cy,D , which is finite and independent of N , we obtain the desired result.

4

Almost sure convergence of the last iterate

Classical works on the almost-sure iterate convergence of I-SEG with square-summable step-sizes γk = γ̂k relied on an additional condition that the operator is quasi-strictly monotone. Indeed, without the additional assumption of quasistrict monotonicity (Assumption 2.8), I-SEG fails to achieve almost sure convergence xk → x⋆ with step-size γ̂k = γk , even when the step-size is square-summable. However, the double step-size extragradient (DSEG) by [34], where γ̂k and γk decay at different rates, allows I-SEG to attain xk → x⋆ almost surely for general monotone F that is not necessarily quasi-strict monotone, in the unconstrained domain X = Rd under the weaker variance assumption (5). In this section, we investigate the analogous results for S-SEG, which are missing in the literature. We first show that S-SEG also exhibits the iterate convergence xk → x⋆ almost surely for quasi-strictly monotone problems with squaresummable step-sizes. Our counterexample from Theorem 3.12 in the previous section shows that this cannot be extended to general monotone operators. Furthermore, we show that even the DSEG step-sizes fail to rescue the divergence of S-SEG, unlike it does for I-SEG; both xk and the weighted average of the iterates can diverge to infinity, and therefore, neither almost sure convergence nor gap function convergence can be expected for S-SEG.

4.1

Convergence under quasi-strict monotonicity

In the following, we show that S-SEG converges for quasi-strictly monotone problems with square-summable γk and γ̂k . Theorem 4.1. Under 2.1, 2.3, 2.4 and 2.8, S-SEG with deterministic γ̂k , γk > 0 satisfying P P∞Assumptions ∞ 2 2 γ̂ γ < ∞ and < ∞ converges almost surely to a solution to (1). k=0 k k=0 k

P∞

k=0 γk = ∞,

P∞ P∞ Proof. Let z ∈ X⋆ be a solution to (1). Because k=0 γ̂k2 < ∞ and k=0 γk2 < ∞, the sequences γ̂k , γk converge to 0, and in particular upper bounded; choose γ such that γk , γ̂k ≤ γ for all k ≥ 0. Now observe that because xk+1 = ΠX (xk − γk F (x̂k ; ξik ) and z ∈ X , by nonexpansiveness of ΠX , 2

∥xk+1 − z∥ ≤ ∥xk − γk F (x̂k ; ξik ) − z∥

2

30

2

= ∥xk − z∥ − 2γk ⟨F (x̂k ; ξik ), xk − z⟩ + γk2 ∥F (x̂k ; ξik )∥

2

2

2

= ∥xk − z∥ − 2γk ⟨F (xk ; ξik ), xk − z⟩ − 2γk ⟨F (x̂k ; ξik ) − F (xk ; ξik ), xk − z⟩ + γk2 ∥F (x̂k ; ξik )∥ . The second term becomes −2γk ⟨F (xk ), xk − z⟩ under conditional expectation on Fk . Next, −2γk ⟨F (x̂k ; ξik ) − F (xk ; ξik ), xk − z⟩ ≤ 2γk ∥F (x̂k ; ξik ) − F (xk ; ξik )∥ ∥xk − z∥ ≤ 2γk L ∥x̂k − xk ∥ ∥xk − z∥ ≤ 2γk L ∥γ̂k F (xk ; ξik )∥ ∥xk − z∥   2 2 ≤ γk γ̂k L ∥F (xk ; ξik )∥ + ∥xk − z∥   2 ≤ γk γ̂k L (1 + 2L2 ) ∥xk − z∥ + σ 2 where we again use nonexpansiveness of ΠX for the third inequality, and the last line follows from Proposition 2.7 with 2 σ 2 = 2 maxi=1,...,n ∥F (z; ξk )∥ . We also have 2

2

2

∥F (x̂k ; ξik )∥ ≤ (∥F (xk ; ξik )∥ + L ∥x̂k − xk ∥) ≤ (∥F (xk ; ξik )∥ + Lγ̂k ∥F (xk ; ξik )∥)   2 2 ≤ (1 + γL)2 ∥F (xk ; ξik )∥ ≤ (1 + γL)2 2L2 ∥xk − z∥ + σ 2 .

Putting altogether, we obtain h i
2 2 E ∥xk+1 − z∥ Fk ≤ 1 + γk γ̂k L(1 + 2L2 ) + 2γk2 L2 (1 + γL)2 ∥xk − z∥ − 2γk ⟨F (xk ), xk − z⟩
+ γk γ̂k L + γk2 (1 + γL)2 σ 2 . Because

P∞

k=0 γk γ̂k ≤

2 1/2 k=0 γk

P∞

2

ak = ∥xk − z∥ ,

2 1/2 < ∞, we can apply Lemma 3.6 with k=0 γ̂k

P∞

bk = 2γk ⟨F (xk ), xk − z⟩ ≥ 0,

ck = γk γ̂k L + γk2 (1 + γL)2 σ 2 ,

dk = γk γ̂k L(1 + 2L2 ) + 2γk2 L2 (1 + γL)2 P∞ 2 to see that ∥xk − z∥ converges and k=0 γk ⟨F (xk ), xk − z⟩ < ∞ almost surely. P∞Take any countable, dense subset D ⊆ X⋆ . Consider the event E of probability 1 on which ∥xk − z∥ and the series k=0 γk ⟨F (xk ), xk − z⟩ converge for every z ∈ D. Fix any z0 ∈ D. On E, ∥xk − z0 ∥ converges, and in particular, xk stays bounded in some closed ball B(z0 , R) for some random variable R > 0. Now we show that on E, xk has a limit point x⋆ ∈ X⋆ . Suppose to the contrary—since X⋆ ∩ B(z0 , R + 1) is compact, this implies there exists δ ∈ (0, 1) and N ∈ N such that dist(xk , X⋆ ∩ B(z0 , R + 1)) ≥ δ for all k ≥ N . As xk ∈ B(z0 , R), the closure C of the set {xk | k ≥ N } is compact, and dist(C, X⋆ ) ≥ δ. Then, by Assumption 2.8, the continuous function x 7→ ⟨F (x), x − z0 ⟩ is positive on C and thus attains P∞ a minimum m > 0 on C. This is a contradiction, since then ⟨F (x ), x − z ⟩ ≥ m for all k ≥ N , which implies k k 0 k=N 2γk ⟨F (xk ), xk − z0 ⟩ ≥ P∞ 2m k=N γk = ∞. This shows that xk must have a limit point x∞ ∈ X⋆ . Finally, it remains to show that in fact, xk → x∞ . Choose a sequence zj ∈ D such that zj → x∞ . On E, the limits ej = limk→∞ ∥xk − zj ∥ exist for all j. Hence, for any ϵ > 0, take sufficiently large j for which ∥zj − x∞ ∥ < ϵ. Then, taking k → ∞ in |∥xk − x∞ ∥ − ∥xk − zj ∥| ≤ ∥zj − x∞ ∥, we obtain ej − ϵ ≤ lim inf ∥xk − x∞ ∥ ≤ lim sup ∥xk − x∞ ∥ ≤ ej + ϵ. k→∞

k→∞

Since ϵ was arbitrary, this shows that limk→∞ ∥xk − x∞ ∥ exists, and because x∞ is a limit point of xk , that limit must be 0. This shows that xk → x∞ on E, completing the proof.

4.2

S-SEG may diverge even with DSEG step-sizes

We now turn to the question of what happens without quasi-strict monotonicity. Theorem 3.12 shows that we cannot expect the iterate convergence xk → x⋆ ∈ X⋆ with symmetric step-sizes. However, because DSEG step-sizes resolves this issue by breaking the symmetry, one may naturally hypothesize that S-SEG may exhibit almost-sure convergence with DSEG step-sizes. Below, we show that this is in fact not the case, by presenting a counterexample.

31

1 Theorem 4.2. For every fixed 0 < η < 10 , there exists a stochastic VIP on X = R2 satisfying Assumptions 2.1, 2.3 and 2.4 with unique solution x⋆ = 0, and a sufficiently large k0 > 1 such that for every x0 ̸= 0, S-SEG with η 1 , γk = k+k , which satisfy (DSEG), exhibits ∥xk ∥ → ∞ almost surely. Furthermore, denoting step-sizes γ̂k = log(k+k 0) 0 PN P γ γ N ΓN = k=0 γk and x̂N = Γ1N k=0 γk x̂k , we have x̂N → ∞ almost surely as N → ∞.

Proof. Fix 0 < η < 1/10, and choose an integer ρ ≥ 2 such that q := η(ρ2 − 1) > 1. Let L = k0 > 1 sufficiently large that 1 1 1 < , sup |bs (γk ) − 1| ≤ . log k0 3L 2 k≥0, s∈{−1,+1} The step-sizes satisfy the (DSEG) conditions X γk γ̂k = ∞,

X

k

X

γk2 < ∞,

k

because

p

ρ2 + 1. Choose an integer

γk γ̂k2 < ∞,

k

η2 , (k + k0 )2

η . (k + k0 ) log2 (k + k0 ) Now consider the stochastic VIP from Lemma 3.11 with ν = 0 and ρ. By Lemma 3.11, this problem satisfies the required assumptions with F (x) = Jx and has unique solution x⋆ = 0. In addition, with sk ∈ {−1, +1} sampled uniformly, we have ẑk = (1 − γ̂k (sk ρ + i)) zk , zk+1 = bsk (γk )zk ,

2 where bsk (γk ) = 1 + γk (ρ − 1)γ̂k − sk ρ + iγk 2sk ργ̂k − 1 . Because |bsk (γk ) − 1| ≤ 21 for all k ≥ 0 and any selection of sk , 2 3 the principal complex logarithm of bsk (γk ) is well-defined. Now using the series expansion Log(1 + u) = u − u2 + u3 − · · · for |u| < 1, we have γk γ̂k =

η , (k + k0 ) log(k + k0 )

γk2 =

γk γ̂k2 =

Log bsk (γk ) = −sk ργk − iγk + (ρ2 − 1)γk γ̂k + 2isk ργk γ̂k + O(γk2 ). (46) P∞ 2 P∞ 2 2 P∞ Because P∞we have k=0 γk < ∞ and k=0 γk γ̂k < ∞, by Kolmogorov’s two-series theorem, the random series k=0 sk γk and k=0 sk γk γ̂k converge almost surely. Moreover, we have N −1 X

γk γ̂k = η log log N + c1 + o(1),

k=0

N −1 X

γk = η log N + c2 + o(1)

k=0

for some deterministic constants c1 , c2 depending on k0 . The remainder O(γk2 ) in (46) is uniform in sk and summable. Therefore, summing (46) from k = 0 to N − 1, we see that there exists an almost surely finite nonzero complex random variable C such that zN = C(log N )q N −iη (1 + o(1)) where q = η(ρ2 − 1) > 1. In particular, this implies ∥xN ∥ = |zN | → ∞ almost surely. PN To analyze the averaged iterates, we need an estimate of the quantity TN := k=0 γk γ̂k zk . Rearranging the recursion
zk+1 − zk = −iγk zk + γk (ρ2 − 1)γ̂k − sk ρ + 2isk ργ̂k zk we obtain
γk zk = i(zk+1 − zk ) − iγk (ρ2 − 1)γ̂k − sk ρ + 2isk ργ̂k zk .

(47)

Now multiplying the above equation by γ̂k and summing gives TN = i

N X

γ̂k (zk+1 − zk ) − i(ρ2 − 1)

k=0

Observe that we have |γ̂k+1 − γ̂k | = O summation by parts we have N X

N X

γk γ̂k2 zk + iρ

k=0



1 k(log k)2



N X

sk γk γ̂k zk + 2ρ

k=0

N X

sk γk γ̂k2 zk .

(48)

k=0

and we already obtained |zk | = O((log k)q ) almost surely. Hence, by

γ̂k (zk+1 − zk ) = −γ̂0 z0 + γ̂N zN +1 +

k=0

N −1 X k=0

32

(γ̂k − γ̂k+1 ) zk+1

= O(1) + |γ̂N ||zN +1 | +

N −1 X

|γ̂k − γ̂k+1 | · |zk+1 |

k=0 q−1

= O (log N )

N −1 X

+O

k=0

(log k)q k(log k)2

! = O (log N )q−1

almost surely. We also have N X

γk γ̂k2 zk

N X

≤

k=0

k=0

almost surely. Finally, the two random series E [sk | Fk ] = 0 makes them martingale and ∞ X

N X (log k)q

γk γ̂k2 |zk | = O

γk2 γ̂k2 |zk |2 = O

k=2

P∞

k=0

k

k(log k)2

k=0 sk γk γ̂k zk and

k 2 (log k)2

< ∞,

= O (log N )q−1

P∞

∞ X

!

X (log k)2q

!

2 k=0 sk γk γ̂k zk in (48) converge almost surely because

X (log k)2q

γk2 γ̂k4 |zk |2 = O

k=0

k

k 2 (log k)4

! <∞

almost surely. This shows that TN = O (log N )q−1 = o ((log N )q ). Now summing the identity (47) and telescoping we obtain N X

γk zk = i(zN +1 − z0 ) − i(ρ2 − 1)TN + iρ

k=0

The last two series

sk γk zk + 2ρ

k=0

P∞

∞ X

N X

k=0

sk γk γ̂k zk .

k=0

P∞

k=0 sk γk zk and

γk2 |zk |2 = O

N X

k=0 sk γk γ̂k zk converge almost surely because

X (log k)2q k2

k

∞ X

! < ∞,

γk2 γ̂k2 |zk |2 = O

X (log k)2q

k=0

k

k 2 (log k)2

! < ∞.

Because we have zN = C(log N )q N −iη (1 + o(1)) and TN = o((log N )q ), this yields N X

γk zk = izN +1 + o((log N )q ) = iC(log N )q N −iη (1 + o(1)).

k=0

Finally, using ẑk = (1 − γ̂k (sk ρ + i)) zk we have N X

γk ẑk =

k=0

N X k=0

γk zk − ρ

N X k=0

sk γk γ̂k zk − i

N X

γk γ̂k zk ,

k=0

and we have already checked that the second series converges almost surely, while the last series is iTN = o(LqN ). Therefore, obtain N X γk ẑk = iC(log N )q N −iη (1 + o(1)). k=0

Because ΓN =

PN

k=0 γk = η log N + O(1), we conclude that γ

ẑ N :=

N

1 X iC γk ẑk = (log N )q−1 N −iη (1 + o(1)) ΓN η k=0

γ

γ

which implies x̂N = |ẑ N | → ∞ almost surely, since q > 1.

5

Conclusion

We present a convergence theory for SEG on stochastic monotone VIPs, providing results that have been missing from the literature despite the algorithm’s simplicity and popularity. Our analysis highlights the differences between I-SEG 33

and S-SEG, both in the assumptions required for convergence and their behavior across distinct problems and step-size choices. We further characterize the dynamics of SEG when the domain and operator variance are unbounded. While our results address several gaps in the literature on SEG, they also raise interesting questions for future work. A similar analysis may be possible for the single-oracle variant of EG, now commonly called optimistic gradient (OG) [60], which dates back to the work of Popov [59]. Prior work on stochastic OG (SOG) assumed uniformly bounded variance [21, 33, 24, 12] or large batch sizes depending on the desired accuracy level [12, 20], and it would be informative to determine whether SOG behaves similarly to SEG on stochastic monotone VIPs with unbounded variance over general closed convex domains. Another open direction is to identify a simple mechanism that induces convergence under the generalized variance condition (5). Recent methods use regularization or variance reduction to achieve convergence in similar settings [58, 5, 2], and it remains to determine whether these ideas can be distilled into a minimal update rule comparable to SEG. Finally, although we have shown that the DSEG step-size rule of Hsieh et al. [34] resolves the nonconvergence issue for I-SEG but not for S-SEG, it remains an open question whether the non-convergence of S-SEG is unavoidable or can be remedied by another carefully chosen step-size rule.

Acknowledgments The authors thank Sayantan Choudhury and Ahmet Alacaoglu for useful discussions during the early stages of this project. TaeHo Yoon’s contribution to this work was supported by NSF CCF 2504626. Nicolas Loizou’s contribution to this work was supported by NSF CCF 2504626 and NSF CAREER 2542902.

References [1] Jacob Abernethy, Kevin A. Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization. international Conference on Algorithmic Learning Theory, 2021. [2] Ahmet Alacaoglu and Jun-Hyun Kim. Solving stochastic variational inequalities without the bounded variance assumption. arXiv:2602.05531, 2026. [3] Ahmet Alacaoglu, Axel Böhm, and Yura Malitsky. Beyond the golden ratio for variational inequality algorithms. Journal of Machine Learning Research, 24(172):1–33, 2023. [4] Ahmet Alacaoglu, Volkan Cevher, and Stephen J. Wright. On the complexity of a simple primal-dual coordinate method. Mathematical Programming, 2025. [5] Ahmet Alacaoglu, Yura Malitsky, and Stephen J Wright. Towards weaker variance assumptions for stochastic optimization. arXiv:2504.09951, 2025. [6] Kimon Antonakopoulos, Thomas Pethick, Ali Kavis, Panayotis Mertikopoulos, and Volkan Cevher. Sifting through the noise: Universal first-order methods for stochastic variational inequalities. Neural Information Processing Systems, 2021. [7] Waı̈ss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradientbased methods for a whole spectrum of differentiable games. International Conference on Artificial Intelligence and Statistics, 2020. [8] Francis Bach and Kfir Y Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. Conference on Learning Theory, 2019. [9] Aleksandr Beznosikov, Pavel Dvurechenskii, Anastasiia Koloskova, Valentin Samokhin, Sebastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. Neural Information Processing Systems, 2022. [10] Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. International Conference on Artificial Intelligence and Statistics, 2023. [11] Julius R. Blum. Approximation Methods which Converge with Probability one. The Annals of Mathematical Statistics, 25(2):382–386, 1954.

34

[12] Axel Böhm. Solving nonconvex-nonconcave min-max problems exhibiting weak minty solutions. Transactions on Machine Learning Research, 2023. [13] Radu I. Boţ and Enis Chenchene. Extragradient method with flexible anchoring: Strong convergence and fast residual decay. SIAM Journal on Optimization, 36(3):1420–1445, 2026. [14] Radu Ioan Boţ, Ernö Robert Csetnek, and Dang-Khoa Nguyen. Fast Optimistic Gradient Descent Ascent (OGDA) Method in Continuous and Discrete Time. Foundations of Computational Mathematics, 25(1):163–222, 2025. [15] Xufeng Cai, Chaobing Song, Cristóbal A Guzmán, and Jelena Diakonikolas. Stochastic halpern iteration with variance reduction for stochastic monotone inclusions. Neural Information Processing Systems, 2022. [16] Yang Cai and Weiqiang Zheng. Accelerated single-call methods for constrained min-max optimization. International Conference on Learning Representations, 2023. [17] Jiseok Chae, Chulhee Yun, and Donghwan Kim. Stochastic extragradient with flip-flop shuffling &amp; anchoring: Provable improvements. Neural Information Processing Systems, 2024. [18] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. Neural Information Processing Systems, 2019. [19] Sayantan Choudhury and Nicolas Loizou. Extragradient method for (L0 , L1 )-Lipschitz root-finding problems. Neural Information Processing Systems, 2025. [20] Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragradient methods for structured non-monotone variational inequalities: Improved analysis under weaker conditions. Neural Information Processing Systems, 2023. [21] Shisheng Cui and Uday V. Shanbhag. On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 4510–4515, 2016. [22] Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. Conference on Learning Theory, 2020. [23] Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer-Verlag, 2003. [24] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. International conference on Learning Representations, 2019. [25] Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon LacosteJulien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. International Conference on Artificial Intelligence and Statistics, 2019. [26] EG Gladyshev. On stochastic approximation. Theory of Probability & Its Applications, 10(2):275–278, 1965. [27] Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. Neural Information Processing Systems, 2020. [28] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. Conference on Learning Theory, 2020. [29] Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient: General analysis and improved rates. International Conference on Artificial Intelligence and Statistics, 2022. [30] Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/K) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. International Conference on Artificial Intelligence and Statistics, 2022. [31] Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Neural Information Processing Systems, 2022.

35

[32] Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6): 957–961, 1967. [33] Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. Neural Information Processing Systems, 2019. [34] Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Neural Information Processing Systems, 2020. [35] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17–58, 2011. [36] Aswin Kannan and Uday V. Shanbhag. Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):779–820, 2019. [37] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 12(4):747–756, 1976. [38] Torbjörn Larsson and Michael Patriksson. A class of gap functions for variational inequalities. Mathematical Programming, 64(1):53–79, 1994. [39] Jaewook Lee, Hanseul Cho, and Chulhee Yun. Fundamental benefit of alternating updates in minimax optimization. International Conference on Machine Learning, 2024. [40] Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. Neural Information Processing Systems, 2021. [41] Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. International Conference on Artificial Intelligence and Statistics, 2019. [42] Felix Lieder. On the convergence rate of the Halpern-iteration. Optimization Letters, 15(2):405–418, 2021. [43] Nicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martineau, Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas. Stochastic Hamiltonian gradient methods for smooth games. International Conference on Machine Learning, 2020. [44] Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Neural Information Processing Systems, 2021. [45] Yura Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Programming, 184(1):383–410, 2020. [46] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, C.-S. Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. International Conference on Learning Representations, 2019. [47] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of GANs. Neural Information Processing Systems, 2017. [48] George J Minty. On the generalization of a direct method of the calculus of variations. Bulletin of the American Mathematical Society, 73(6):315–321, 1967. [49] Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisiting stochastic extragradient. International Conference on Artificial Intelligence and Statistics, 2020. [50] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. International Conference on Artificial Intelligence and Statistics, 2020.

36

[51] Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4): 3230–3251, 2020. [52] Renato D. C. Monteiro and B. F. Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):2755–2787, 2010. [53] A. Nedić and A. Ozdaglar. Subgradient Methods for Saddle-Point Problems. Journal of Optimization Theory and Applications, 142(1):205–228, 2009. [54] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009. [55] 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(1):229– 251, 2004. [56] A. S Nemirovsky. Information-based complexity of linear operator equations. Journal of Complexity, 8(2):153–175, 1992. [57] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319–344, 2007. [58] Gergely Neu and Nneka Okolo. Dealing with unbounded gradients in stochastic saddle-point optimization. International Conference on Machine Learning, 2024. [59] L. D. Popov. A modification of the Arrow–Hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845–848, 1980. [60] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Neural Information Processing Systems, 2013. [61] Herbert Robbins and David Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Optimizing Methods in Statistics, pages 233–257. Elsevier, 1971. [62] R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970. [63] Michael Sedlmayer, Dang-Khoa Nguyen, and Radu Ioan Bot. A fast optimistic method for monotone variational inequalities. Proceedings of the 40th international conference on machine learning, 2023. [64] Henry Shugart and Jason M Altschuler. Negative stepsizes make gradient-descent-ascent converge. arXiv:2505.01423, 2025. [65] M. V. Solodov and B. F. Svaiter. A hybrid approximate extragradient – proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Analysis, 7(4):323–345, 1999. [66] Guido Stampacchia. Formes bilineaires coercitives sur les ensembles convexes. Comptes Rendus Academie Des Sciences Paris, 258:4413–4416, 1964. [67] Quoc Tran-Dinh. Extragradient-type methods with O (1/k) last-iterate convergence rates for co-hypomonotone inclusions. Journal of Global Optimization, 89(1):197–221, 2024. [68] Quoc Tran-Dinh. From Halpern’s fixed-point iterations to Nesterov’s accelerated interpretations for root-finding problems. Computational Optimization and Applications, 87(1):181–218, 2024. [69] Quoc Tran-Dinh. VFOSA: Variance-reduced fast operator splitting algorithms for generalized equations. Journal of Machine Learning Research, 26(254):1–68, 2025. [70] Quoc Tran-Dinh and Yang Luo. arXiv:2110.08150, 2021.

Halpern-type accelerated and splitting algorithms for monotone inclusions.

[71] Paul Tseng. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431–446, 2000.

37

[72] Mengdi Wang and Dimitri P. Bertsekas. Stochastic first-order methods with random constraint projection. SIAM Journal on Optimization, 26(1):681–717, 2016. [73] Abhay Kumar Yadav, Sohil Shah, Zheng Xu, David W. Jacobs, and Tom Goldstein. Stabilizing adversarial nets with prediction methods. International Conference on Learning Representations, 2018. [74] TaeHo Yoon and Benjamin Grimmer. A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms. arXiv:2605.02231, 2026. [75] TaeHo Yoon and Ernest K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with O(1/k 2 ) rate on squared gradient norm. International Conference on Machine Learning, 2021. [76] TaeHo Yoon and Ernest K. Ryu. Accelerated minimax algorithms flock together. SIAM Journal on Optimization, 35(1):180–209, 2025. [77] TaeHo Yoon, Jaeyeon Kim, Jaewook J. Suh, and Ernest K. Ryu. Optimal acceleration for minimax and fixed-point problems is not unique. International Conference on Machine Learning, 2024. [78] TaeHo Yoon, Ernest K. Ryu, and Benjamin Grimmer. H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms. arXiv:2511.14915, 2025. [79] Farzad Yousefian, Angelia Nedić, and Uday V. Shanbhag. On Stochastic Mirror-prox Algorithms for Stochastic Cartesian Variational Inequalities: Randomized Block Coordinate and Optimal Averaging Schemes. Set-Valued and Variational Analysis, 26(4):789–819, 2018. [80] Tianqi Zheng, Nicolas Loizou, Pengcheng You, and Enrique Mallada. Dissipative gradient descent ascent method: A control theory inspired algorithm for min-max optimization. IEEE Control Systems Letters, 8:2009–2014, 2024.

38

Related documents

• Computation of Strong Solutions to Stochastic Variational Inequalities#927051
• Duality in convex stochastic optimization#240316
• Level proximal subdifferential, variational convexity, and pointwise quadratic approximation#155486
• Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex#986299
• The Ding--Song--Sun inequality via a maximum principle#997399