Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems

Introduction

Recently, nonconvex-nonconcave minimax problems have received an increased attention in the optimization community and the machine learning community due to their applications to generative adversarial network and adversarial training . In this paper, we consider a smooth structured nonconvex-nonconcave minimax problem:

So far little is known under the nonconvex-nonconcave setting, compared to the convex-concave setting. Recent works studied extragradient-type methods for minimax problems under various structured nonconvex-nonconcave settings. In other words, they consider various non-monotone conditions on $\bm{F}$, such as the Minty variational inequality (MVI) condition , the weak MVI condition , and the negative comonotonicity . Relations between the conditions on $\bm{F}$ considered in this paper is summarized in Figure 1. Among them, this paper focuses on the negative comonotonicity condition for a Lipschitz continuous $\bm{F}$. To the best of our knowledge, the following two-time-scale variant of the extragradient method, named EG+:

is the only known (explicit) A proximal point method converges under the negative comonotonicity , but such implicit method is not preferable over explicit methods in practice due to its implicit nature. method, using $\bm{F}$, that converges under the considered setting The EG+ was originally shown to work under the weak MVI condition of $\bm{F}$, which is weaker than the negative comonotonicity. , where $\bm{z}_{k}:=(\bm{x}_{k},\bm{y}_{k})$. The EG+, however, has a slow $\mathcal{O}(1/k)$ rate on the squared gradient norm. Note that a similar two-time-scale approach has been found to stabilize the stochastic extragradient method with unbounded noise variance .

Meanwhile, under the smooth convex-concave setting, recent works suggest that Halpern-type (or anchoring) methods, performing a convex combination of an initial point $\bm{z}_{0}$ and the last updated point $\bm{z}_{k}$ at each iteration, has a fast $\mathcal{O}(1/k^{2})$ rate in terms of the squared gradient norm. In particular, developed the following anchoring variant of the extragradient method, named extra anchored gradient (EAG):

This is the first (explicit) method with a fast $\mathcal{O}(1/k^{2})$ rate on the squared gradient norm, when $\bm{F}$ satisfies both the Lipschitz continuity and the monotonicity. also showed that such $\mathcal{O}(1/k^{2})$ rate is optimal for first-order methods using a Lipschitz continuous and monotone $\bm{F}$.

Built upon both EG+ and EAG, this paper studies the following class of two-time-scale anchored extragradient methods, named fast extragradient (FEG):

Note that (Class FEG) reuses the $\bm{F}\bm{z}_{k}$ term in the $\bm{z}_{k+1}$ update, unlike the standard extragradient-type methods, which we found essential for handling the negative comonotonicity condition. We leave further understanding the use of $\bm{F}\bm{z}_{k}$ and the formulation of (Class FEG) as future work. The proposed FEG method (with appropriately chosen step coefficients $\alpha_{k}$, $\beta_{k}$ and $\rho_{k}$ discussed later) has an $\mathcal{O}(1/k^{2})$ rate on the squared gradient norm, under the Lipschitz continuity and the negative comonotonicity conditions on $\bm{F}$. To the best of our knowledge, this is the first accelerated method under the nonconvex-nonconcave setting. The FEG also has value under the smooth convex-concave setting. First, when $\bm{F}$ is Lipschitz continuous and monotone, the rate bound of FEG is about 27/4 times smaller than that of EAG. Also note that the rate bound of FEG is only about four times larger than the $\mathcal{O}(1/k^{2})$ lower complexity bound of first-order methods under such setting , further closing the gap between the lower and upper complexity bounds. Second, when $\bm{F}$ is cocoercive, FEG has a rate faster than that of a version of Halpern iteration in .

We also develop an adaptive variant of FEG, named FEG-A, which updates its parameters, $\alpha_{k}$ and $\rho_{k}$ in (Class FEG), adaptively using a backtracking line-search . FEG requires the knowledge of the two problem parameters for the Lipschitz continuity and the comonotonicity of $\bm{F}$. However, those global parameters can be conservative, and in practice, they are even usually unknown. For such cases, the FEG-A adaptively and locally estimates the problem parameters, while preserving the fast rate $\mathcal{O}(1/k^{2})$ on the squared gradient norm for smooth structured nonconvex-nonconcave minimax problems.

Our main contributions are summarized as follows.

We propose the FEG method that has an accelerated convergence rate $\mathcal{O}(1/k^{2})$ on the squared gradient norm for smooth structured nonconvex-nonconcave minimax problems.

We present that the FEG method has a rate faster than those of the EAG and the Halpern iteration for smooth convex-concave problems.

We construct a backtracking line-search version of FEG, named FEG-A, for the case where the Lipschitz constant and comonotonicity parameters of $\bm{F}$ are unavailable.

We analyze a stochastic version of FEG, named S-FEG, for smooth convex-concave problems.

Related work

The extragradient method is one of the widely used methods for solving smooth convex-concave minimax problems (see, e.g., for its extensions and applications). In terms of the duality gap, $\max_{\bm{y}^{\prime}\in\mathcal{Y}}f(\bm{x},\bm{y}^{\prime})-\min_{\bm{x}^{\prime}\in\mathcal{X}}f(\bm{x}^{\prime},\bm{y})$, where $\mathcal{X}$ and $\mathcal{Y}$ are compact The convergence analysis on the duality gap of the extragradient type methods are generalized under the unbounded domain assumption in . domains, the ergodic iterate of the extragradient-type methods have an $\mathcal{O}(1/k)$ rate. Such $\mathcal{O}(1/k)$ rate on the duality gap is order-optimal for the first-order methods , leaving no room for improvement. On the other hand, the last iterate of the extragradient method has a slower $\mathcal{O}(1/\sqrt{k})$ rate on the duality gap, under an additional assumption that $\bm{F}$ has a Lipschitz derivative . In terms of the squared gradient norm, $\|\bm{F}\bm{z}\|^{2}$, the best iterate of the extragradient-type methods have an $\mathcal{O}(1/k)$ rate . The last iterate of the extragradient method also has a rate $\mathcal{O}(1/k)$, when $\bm{F}$ is further assumed to have a Lipschitz derivative . Unlike the duality gap, the $\mathcal{O}(1/k)$ rate on the squared gradient norm is not optimal . From now on throughout this paper, we mainly study and compare the convergence rates on the squared gradient norm, which still has room for improvement in convex-concave problems, and has meaning for nonconvex-nonconcave minimax problems, unlike the duality gap.

2 Methods for nonconvex-nonconcave minimax problems

For $L$-Lipschitz continuous $\bm{F}$, showed that the extragradient-type methods have an $\mathcal{O}(1/k)$ rate on the squared gradient norm under the MVI condition, and developed the (EG+) method under the weak MVI condition (and thus under the negative comonotonicty), which also has an $\mathcal{O}(1/k)$ rate on the squared gradient norm. To the best of our knowledge, there is no known accelerated method for the nonconvex-nonconcave setting; our proposed FEG method is the first method to have a fast $\mathcal{O}(1/k^{2})$ rate under the nonconvex-nonconcave setting. The convergence rates of the existing methods and the FEG on the squared gradient norm are summarized in Table 1.

Preliminaries

For some $L\in(0,\infty)$, $\bm{F}$ satisfies

For some \rho\in\big{(}-\frac{1}{2L},\infty\big{)}, $\bm{F}$ satisfies

The $\rho$-comonotonicity consists of three cases depending on the choice of $\rho$; the negative comonotonicity when $\rho<0$, the monotonicity when $\rho=0$, and the cocoercivity when $\rho>0$. The negative comonotonicity is weaker than the other two, and is the main focus of this paper. The following is an examplary nonconvex-nonconcave condition that is stronger than the negative comonotonicity .

Let $f$ be twice continuously differentiable and $\gamma$-weakly-convex-weakly-concave. Further assume that $f$ satisfies

for some $\alpha\geq 0$ and $\eta>\gamma$, named $\alpha\geq 0$-interaction dominant condition in . Then, the saddle gradient of $f$ satisfies the $-\frac{1}{\eta}$-negative comonotonicity. (See Appendix A.1.) For any $\gamma$-weakly-convex-weakly-concave function, the condition (2) holds with $\alpha=-\gamma<0$. Its extreme case is $f(x,y)=-\frac{\gamma}{2}x^{2}+\frac{\gamma}{2}y^{2}$, where there is no interaction between $x$ and $y$. On the other hand, when the the second terms in the left-hand side of (2) are sufficently positive definite, a nonconvex-nonconave function satisfies the condition (2) with a nonnegative $\alpha$. In specific, the $\alpha\geq 0$-interaction dominant condition is satisfied when the interaction term of Hessian $\nabla_{\bm{x}\bm{y}}^{2}f$ is dominating any negative curvature in Hessians $\nabla_{\bm{x}\bm{x}}^{2}f$ and $-\nabla_{\bm{y}\bm{y}}^{2}f$ .

We next present our proposed FEG, and illustrate that the FEG outperforms existing methods such as EG+, EAG, and the Halpern iteration, for each three comonoticity case, respectively.

Fast extragradient (FEG) method for Lipschitz continuous and comonotone operators

This section considers an instance of (Class FEG) with $\alpha_{k}=\frac{1}{L}$, $\beta_{k}=\frac{1}{k+1}$, and $\rho_{k}=\rho$ for all $k\geq 0$. The resulting method, named FEG, is illustrated in Algorithm 1, which has an $\mathcal{O}(1/k^{2})$ fast rate with respect to the squared gradient norm, in Theorem 4.1. The proof of Theorem 4.1 is provided in Section 7.

For the $L$-Lipschitz continuous and $\rho$-comonotone operator $\bm{F}$ with $\rho>-\frac{1}{2L}$ and for any $\bm{z}_{*}\in\bm{Z}_{*}(\bm{F})$, the sequence $\{\bm{z}_{k}\}_{k\geq 0}$ generated by FEG satisfies, for all $k\geq 1$,

The following example shows that the bound (3) of the FEG is exact for $\rho=0$ and $k=4l+2$. The bound (3) is not known to be exact in general, and we leave finding the exact bound as future work.

We next compare the rate bound (3) with existing analyses for the three cases $-\frac{1}{2L}<\rho<0$, $\rho=0$, and $\rho>0$.

Under the negative comonotonicity with $-\frac{1}{8L}<\rho<0$, the (EG+) method with $\alpha_{k}=\frac{1}{2L}$ and $\beta=\frac{1}{2}$ has an $\mathcal{O}(1/k)$ rate on the squared gradient norm. To the best of our knowledge, this is the best known rate, and the FEG has a faster $\mathcal{O}(1/k^{2})$ rate with a wider region of convergence $-\frac{1}{2L}<\rho<0$.

2 Comparison to EAG under the monotonicity (ρ=0𝜌0\rho=0)

For an $L$-Lipschitz continuous and monotone operator $\bm{F}$, proposed two EAG methods, named EAG-C and EAG-V, with same $\beta_{k}=\frac{1}{k+2}$ but with different choices of $\alpha_{k}$. EAG-C sets $\alpha_{k}$ to be a constant $\frac{1}{8L}$ for all $k\geq 0$ in (EAG), and has a large constant $260$ in its convergence rate, $\|\bm{F}\bm{z}_{k}\|^{2}\leq\frac{260L^{2}\|\bm{z}_{0}-\bm{z}_{*}\|^{2}}{(k+1)^{2}}$ for all $k\geq 0$. On the other hand, while EAG-V requires a complicated recursive update for $\{\alpha_{k}\}$, \alpha_{k+1}=\frac{\alpha_{k}}{1-\alpha_{k}^{2}L^{2}}\big{(}1-\frac{(k+2)^{2}}{(k+1)(k+3)}\alpha_{k}^{2}L^{2}\big{)} for all $k\geq 0$, with $\alpha_{0}=\frac{0.618}{L}$, its rate has a smaller constant $27$.

The FEG takes a constant $\alpha_{k}=\frac{1}{L}$, unlike EAG-V, but has an even smaller constant $4$ in its convergence rate $\|\bm{F}\bm{z}_{k}\|^{2}\leq\frac{4L^{2}\|\bm{z}_{0}-\bm{z}_{*}\|^{2}}{k^{2}}$ for $\rho=0$. Therefore, the FEG with $\rho=0$ has about $260/4$-times and $27/4$-times faster convergence rate compared to those of EAG-C and EAG-V, respectively. Furthermore, the rate bound of FEG with $\rho=0$ is only about $4$-times larger than the lower complexity bound of first-order methods under the considered setting , reducing the gap between the lower and upper complexity bounds from $27$ to $4$.

3 Comparison to the Halpern iteration under the cocoercivity (ρ>0𝜌0\rho>0)

For a $\rho$-cocoercive operator $\bm{F}$, an (explicit) version of Halpern iteration , studied in , has a fast rate, $\|\bm{F}\bm{z}_{k}\|^{2}\leq\frac{\|\bm{z}_{0}-\bm{z}_{*}\|^{2}}{\rho^{2}k^{2}}$. Note that while the $\rho$-cocoercivity implies the $\frac{1}{\rho}$-Lipschitz continuity, there is case where the $\rho$-cocoercive (and thus Lipschitz continuous) operator has a Lipschitz constant $L$ smaller than $\frac{1}{\rho}$. Since $L\leq\frac{1}{\rho}$, the FEG has a rate $\|\bm{F}\bm{z}_{k}\|^{2}\leq\frac{4\|\bm{z}_{0}-\bm{z}_{*}\|^{2}}{(1/L+2\rho)^{2}k^{2}}=\frac{4\|\bm{z}_{0}-\bm{z}_{*}\|^{2}}{9\rho^{2}k^{2}}$ that is faster than that of Halpern iteration. However, if we take into account that the FEG requires computing the saddle gradient twice per iteration, unlike Halpern iteration studied in , the FEG method has a slower rate in terms of the number of gradient computations. If we narrow down to the case $L<\frac{1}{2\rho}$, the FEG has a faster rate, $\|\bm{F}\bm{z}_{k}\|^{2}\leq\frac{4\|\bm{z}_{0}-\bm{z}_{*}\|^{2}}{(1/L+2\rho)^{2}k^{2}}<\frac{\|\bm{z}_{0}-\bm{z}_{*}\|^{2}}{4\rho^{2}k^{2}}$. For such case, the FEG has a rate faster than that of the Halpern iteration, even in terms of the number of gradient computations.

4 Toy example

We performed a toy experiment on a simple quadratic function, $f(x,y)=\frac{\rho L^{2}}{2}x^{2}+L\sqrt{1-\rho^{2}L^{2}}xy-\frac{\rho L^{2}}{2}y^{2},$ which has an $L$-Lipschitz continuous and $\rho$-comonotone saddle gradient. For the case $\rho=-\frac{1}{3L}$ and $L=1$, Figure 2 illustrates that the FEG converges with an accelerated rate whereas EG+, EAG-C, EAG-V, and the (explicit) version of Halpern iteration diverge. This example presents that the existing guarantees on convergence and acceleration of the aforementioned methods under the convex-concave setting do not generalize to the nonconvex-nonconcave setting.

FEG with backtracking line-search

The FEG requires the knowledge of the two global parameters $L$ and $\rho$ for Lipschitz continuity and comonotonicity, respectively. Those global parameters are often difficult to compute in practice and can be locally conservative. To handle these two disadvantages, we employ the backtracking line-search technique in FEG. We adaptively decrease the two step size parameters, $\tau$ and $\eta$, to satisfy the both conditions, the local $\frac{1}{\tau}$-Lipschitz continuity and the $\frac{\eta-\tau}{2}$-comonotonicity. In specific, $\tau$ and $\eta$ locally estimate $\frac{1}{L}$ and $\frac{1}{L}+2\rho$, respectively. One could have directly estimate $\rho$, instead of $\frac{1}{L}+2\rho$, but this complicates the line-search process to handle both positive and negative values of $\rho$, unlike our choice of $\eta$ in FEG-A. A pseudocode of the resulting method, named FEG-A, is illustrated in Algorithm 2. For a detailed description of the FEG-A, see Algorithm 4 in Appendix C.1.

The following lemma shows that each of the nonincreasing sequences $\{\tau_{k}\}_{k\geq 0}$ and $\{\eta_{k}\}_{k\geq 0}$ of the FEG-A has a positive lower bound, and thus FEG-A is well-defined This requires one to chooses $\tau_{-1}$ strictly greater than the unknown value $-2\rho$ when $\rho<0$., under the condition $\rho>-\frac{\tau_{k}}{2}$. This condition for $\rho$ can be weaker than the condition $\rho>-\frac{1}{2L}$ of FEG, since the local Lipschitz parameter $\frac{1}{\tau_{k}}$ can be smaller than $L$. This is another benefit of using a backtracking line-search in FEG, over the standard FEG.

For the $L$-Lipschitz and $\rho$-comonotone operator $\bm{F}$ and a given constant $\delta\in(0,1)$, the step size $\tau_{k}$ of FEG-A is lower bounded by a positive value \underline{\tau}:=\min\big{\{}\tau_{-1},\frac{1-\delta}{L}\big{\}} for all $k\geq 0$, and if $\rho>-\frac{\tau_{k}}{2}$, the step size $\eta_{k}$ is lower bounded by a positive value \min\big{\{}\eta_{0},(1-\delta)\big{(}\tau_{k}+2\rho\big{)}\big{\}} for all $k\geq 1$.

The FEG-A method also has the following $\mathcal{O}(1/k^{2})$ rate with respect to the squared gradient norm in Theorem 5.1, when $\rho>-\frac{\tau_{k}}{2}$. The proof is provided in Section 7 and Appendix C.3.

For the $L$-Lipschitz and $\rho$-comonotone operator $\bm{F}$ and for any $\bm{z}_{*}\in\bm{Z}_{*}(\bm{F})$, the sequence $\{\bm{z}_{k}\}_{k\geq 0}$ generated by FEG-A satisfies

for all $k\geq 1$, if $\rho>-\frac{\tau_{k}}{2}$.

This rate bound of FEG-A reduces to that of FEG in Theorem 4.1, when we choose $\tau_{-1}=\frac{1}{L}$ and $\eta_{0}=\frac{1}{L}+2\rho$ for FEG-A.

FEG under stochastic setting

The following theorem provides an upper bound of the expected squared gradient norm for the S-FEG. (See Appendix D.3 for the proof.)

for all $k\geq 1$. Furthermore, if $\sigma_{0}^{2}\leq\frac{\epsilon}{6}$, $\sigma_{k}^{2}\leq\frac{\epsilon}{6k}$ and $\sigma_{k+1/2}^{2}\leq\frac{\epsilon}{6(k+1)}$ for all $k\geq 1$, then the bound (4) reduces to

Here, we needed the noise variance $\sigma_{k/2}^{2}$ to decrease in the order of $\mathcal{O}(1/k)$ so that the stochastic error of the S-FEG does not accumulate. Otherwise, if $\sigma_{k/2}^{2}$ is a constant for all $k$, the error accumulates with rate $\mathcal{O}(k)$. In short, the S-FEG will suffer from error accumulation, unless the stochastic error decreases with rate $\mathcal{O}(1/k)$. Such error accumulation behavior also appears in a stochastic version of Nesterov’s fast gradient method for smooth convex minimization . Similar to , we believe that adjusting the step coefficients of the S-FEG can make the S-FEG become relatively stable even with a constant noise, which we leave as future work.

Convergence analysis with nonincreasing potential lemma

We analyze FEG and FEG-A by finding a nonincreasing potential function in a form $V_{k}=a_{k}\|\bm{F}\bm{z}_{k}\|^{2}-b_{k}\mathop{\langle\bm{F}\bm{z}_{k},\,\bm{z}_{0}-\bm{z}_{k}\rangle}\nolimits$ in the lemma below. We provide a similar potential lemma for S-FEG in Appendix D.2. The convergence analyses of EAG and Halpern iteration are also based on such potential function .

for all $k\geq 0$. Assume that the following conditions are satisfied.

with $a_{0}=\frac{\alpha_{0}(L_{0}^{2}\alpha_{0}^{2}-1)}{2}$, $b_{0}=0$, $b_{1}=1$,

for all $k\geq 1$ satisfies $V_{k}\leq V_{k-1}$ for all $k\geq 1$.

Based on the above potential lemma, we next provide a convergence analysis of FEG. The analyses for the convergence rate of FEG-A and S-FEG, i.e., the proofs of Theorem 5.1 and Theorem 6.1, are similar to that of FEG and are provided in Appendix C.3 and Appendix D.3.

Proof of Theorem 4.1. Recall that FEG is equivalent to (Class FEG) with $\alpha_{k}=\frac{1}{L}$, $\beta_{k}=\frac{1}{k+1}$, and $\rho_{k}=\rho$. It is straightforward to verify that the given $\{\alpha_{k}\}_{k\geq 0}$ and $\{\beta_{k}\}_{k\geq 0}$ satisfy the conditions in Lemma 7.1 with $L_{k}=L$ for all $k\geq 0$. Since

The desired result follows directly by dividing both sides by \frac{k^{2}}{2}\big{(}\frac{1}{L}+2\rho\big{)}\|\bm{F}\bm{z}_{k}\|. ∎

Discussion: first-order methods for Lipschitz continuous operators

Throughout this paper, we studied and constructed efficient methods in a class of first-order methods:

denoted by $\mathcal{A}$, for smooth structured nonconvex-nonconcave problems. We observed that all existing first-order methods, including the FEG, required an additional condition, such as the negative comonoticity, on a Lipschitz continuous $\bm{F}$ to guarantee convergence. One would then be curious whether or not there exists an (efficient) method in class $\mathcal{A}$ that guarantees convergence without any additional condition on a Lipschitz continuous $\bm{F}$. Unfortunately, the following lemma states that there exists a worst-case also introduce worst-case minimax examples that existing methods cannot find a stationary point. A key difference from our example is that their saddle-gradient operators are not Lipschitz continuous. In addition, the considered classes of methods in exclude EG+ and FEG, unlike the class $\mathcal{A}$. smooth example that none of the methods in $\mathcal{A}$ can find its stationary point. The corresponding smooth function is illustrated in Figure 3.

Its saddle-gradient operator $\bm{F}$ is $L$-Lipschitz continuous but not comonotone. Let \bm{z}=\big{(}\bm{x},\bm{x}+\sqrt{\frac{R}{L}}\big{)} and $\bm{w}=(0,0)$. Since $\bm{F}\bm{z}=(0,0)$ and $\bm{F}\bm{w}=(-\sqrt{LR},-\sqrt{LR})$, we get $\mathop{\langle\bm{F}\bm{z}-\bm{F}\bm{w},\,\bm{z}-\bm{w}\rangle}\nolimits=2\sqrt{LR}\bm{x}+R$ and $\|\bm{F}\bm{z}-\bm{F}\bm{w}\|^{2}=2LR$, which implies that $\rho=-\infty$ in the comonotonicity condition as $\bm{x}\to-\infty$. Then, the sequence $\{\bm{z}_{k}\}_{k\geq 0}$ generated by any first-order method in class $\mathcal{A}$ with $\bm{z}_{0}=(0,0)$ satisfies $\|\bm{F}\bm{z}_{k}\|^{2}=2LR$ for all $k\geq 0$.

The lemma implies that one should consider a class of methods, other than the class $\mathcal{A}$, to guarantee finding a stationary point of any smooth problem, which we leave as future work. We also leave finding additional conditions for a Lipschitz continuous $\bm{F}$, weaker than the weak MVI condition and the negative comonotonicity (with $\rho>-\frac{1}{2L}$), which guarantee convergence or its accelerated rate, respectively, as future work.

Conclusion

This paper proposed a two-time-scale and anchored extragradient method, named FEG, for smooth structured nonconvex-nonconcave problems. The proposed FEG has an accelerated $\mathcal{O}(1/k^{2})$ rate, with respect to the squared gradient norm, for the Lipschitz continuous and negative comonotone operators for the first time. The FEG also has value for smooth convex-concave problems, compared to existing works. We further studied its backtracking line-search version, named FEG-A, for the smooth structured nonconvex-nonconcave problems and studied its stochastic version, named S-FEG, for smooth convex-concave problems. We leave extending this work to stochastic, composite, or more general nonconvex-nonconcave setting and applying to more realistic problems as future work.

Acknowledgments and Disclosure of Funding

This work was supported in part by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2019R1A5A1028324), the POSCO Science Fellowship of POSCO TJ Park Foundation, and the Samsung Science and Technology Foundation (No. SSTF-BA2101-02).

References

Appendix

Let $f_{\eta}$ be the saddle envelope of $f$ :

and $\bm{F}_{\eta}$ be its saddle gradient operator. Proposition 2.10 in shows that $f_{\eta}$ satisfies

This implies that $\bm{F}_{\eta}$ is $\frac{\eta\alpha}{\eta+\alpha}$-strongly monotone (and thus monotone).

It is enough to show that $\bm{F}_{\eta}$ is monotone if and only if $\bm{F}$ is $-\frac{1}{\eta}$-comonotone. By Lemma 2.5 in , we have the relationship $\bm{F}_{\eta}\bm{z}=\bm{F}\bm{R}\bm{z}$, where \bm{R}:=\big{(}\bm{I}+\frac{1}{\eta}\bm{F}\big{)}^{-1} denotes the standard resolvent of $\frac{1}{\eta}\bm{F}$. The resolvent $\bm{R}$ is injective for $\eta>\gamma$. Let $Z:=\mathcal{X}\times\mathcal{Y}$. Then, $\bm{F}_{\eta}$ is monotone if and only if

which corresponds to the $-\frac{1}{\eta}$-comonotonicity of $\bm{F}$. ∎

B Proof for Section 4

Starting from $\bm{z}_{0}=(1,0)$, it is easy to verify that $\bm{z}_{1/2}=(1,0)$, $\bm{z}_{1}=(1,1)$, \bm{z}_{1+1/2}=\big{(}\frac{1}{2},1\big{)}, and $\bm{z}_{2}=(0,1)$. We next use the induction to show that \bm{z}_{k}=\big{(}0,\frac{2}{k}\big{)} for $k=4l+2$ and for all $l=0,1,2,\ldots$. Assume that \bm{z}_{k}=\big{(}0,\frac{2}{k}\big{)} for some $k=4l+2$. Then, the next eight consecutive iterates are as follows:

so \bm{z}_{4l+6}=\big{(}0,\frac{2}{4l+6}\big{)}. Therefore, we get \bm{z}_{4l+2}=\big{(}0,\frac{1}{2l+1}\big{)} for all $l\geq 0$. ∎

C Algorithm and proofs for Section 5

A detailed description of the FEG-A, in Algorithm 2, is provided in Algorithm 4.

C.2 Proof of Lemma 5.1

We show that \tau_{k}\geq\underline{\tau}:=\min\big{\{}\tau_{-1},\frac{1-\delta}{L}\big{\}} for all $k\geq 0$, and $\eta_{k}\geq\min\{\eta_{0},(1-\delta)(\tau_{k}+2\rho)\}$ for all $k\geq 1$ by contradiction. Note that since $\tau_{-1}>\max\{0,-2\rho\}$ and $\rho>-\frac{1-\delta}{2L}$, both $\underline{\tau}$ and $\underline{\eta}$ are positive.

First, suppose that $\tau_{k}<\underline{\tau}$ for some $k\geq 0$. (1) For the case $\tau_{-1}\leq\frac{1-\delta}{L}$, we get $\tau_{k}=\tau_{-1}$ for all $k\geq 0$ by the definition of $\tau_{k}$, which contradicts to the assumption $\tau_{k}<\tau_{-1}$. (2) Consider the case $\tau_{-1}>\frac{1-\delta}{L}$, where the assumption reduces to $\tau_{k}<\frac{1-\delta}{L}$. For $k=0$, by the definition of $\tau_{0}$, we get $\|\bm{F}\hat{\bm{z}}_{1}-\bm{F}\bm{z}_{0}\|>\frac{1-\delta}{\tau_{0}}\|\hat{\bm{z}}_{1}-\bm{z}_{0}\|$ where $\hat{\bm{z}}_{1}=\bm{z}_{0}-\frac{\tau_{0}}{1-\delta}\bm{F}\bm{z}_{0}$, which contradicts to the $L$-Lipschitz continuity of $\bm{F}$ as $\frac{1-\delta}{\tau_{0}}\;>\;L$. For $k\geq 1$, by the definition of $\tau_{k}$, there exists $i\leq k$ such that the two corresponding iterates

satisfy $\|\bm{F}\hat{\bm{z}}_{i+1}-\bm{F}\hat{\bm{z}}_{i+1/2}\|>\frac{1-\delta}{\tau_{k}}\|\hat{\bm{z}}_{i+1}-\hat{\bm{z}}_{i+1/2}\|$ for some $\hat{\eta}_{i}>0$. However, this inequality contradicts to the $L$-Lipschitz continuity of $\bm{F}$ as $\frac{1-\delta}{\tau_{k}}\;>\;L$. Therefore, we have $\tau_{k}\geq\underline{\tau}>0$ for all $k\geq 0$.

Similarly, suppose that $\eta_{k}<\min\{\eta_{0},(1-\delta)(\tau_{k}+2\rho)\}$ for some $k\geq 1$. (1) For the case $\eta_{0}\leq(1-\delta)(\tau_{k}+2\rho)$, we get $\eta_{i}=\eta_{0}$ for all $1\leq i\leq k$ by the definition of $\eta_{k}$, which contradicts to the assumption $\eta_{k}<\eta_{0}$. (2) Consider the case $\eta_{0}>(1-\delta)(\tau_{k}+2\rho)$, where the assumption reduces to $\eta_{k}<(1-\delta)(\tau_{k}+2\rho)$. Then by the definition of $\eta_{k}$, there exists $i\leq k$ such that the two corresponding iterates

satisfy $\mathop{\langle\bm{F}\hat{\bm{z}}_{i+1}-\bm{F}\hat{\bm{z}}_{i},\,\hat{\bm{z}}_{i+1}-\hat{\bm{z}}_{i}\rangle}\nolimits<\frac{\frac{\eta_{k}}{1-\delta}-\hat{\tau}_{i}}{2}\|\bm{F}\hat{\bm{z}}_{i+1}-\bm{F}\hat{\bm{z}}_{i}\|^{2}$ for some $\hat{\tau}_{i}\geq\tau_{i}$. However, this inequality contradicts to the $\rho$-comonotonicity of $\bm{F}$ as $\frac{\frac{\eta_{k}}{1-\delta}-\hat{\tau}_{i}}{2}<\frac{\tau_{k}+2\rho-\hat{\tau}_{i}}{2}\leq\rho$. Therefore, we have $\eta_{k}\geq\min\{\eta_{0},(1-\delta)(\tau_{k}+2\rho)\}$ for all $k\geq 0$. ∎

C.3 Proof of Theorem 5.1

Note that FEG-A is equivalent to (Class FEG) with $\alpha_{k}=\tau_{k}$, $\beta_{k}=\frac{1}{k+1}$, and $\rho_{k}=\frac{\eta_{k}-\tau_{k}}{2}$. The given sequence in FEG-A satisfies the conditions in Lemma 7.1 with $L_{k}=\frac{1}{\tau_{k}}$:

where the inequality follows from the fact that $\{\tau_{k}\}_{k\geq 0}$ and $\{\eta_{k}\}_{k\geq 0}$ are nonincreasing sequences. Since

Then by dividing both sides by $\frac{k}{2}((k-1)\eta_{k}+\tau_{k}+2\rho)\|\bm{F}\bm{z}_{k}\|$ and using Lemma 5.1, we get

D Proofs for Section 7

Hence, the sum of (6) and (7) with multiplying factor $\frac{\alpha_{0}}{2}$ yields

Next, for $k\geq 1$, here we note the following relations for later use:

Hence, the sum of (8) and (D.1) with multiplying factor $\frac{b_{k}}{2L_{k}^{2}\alpha_{k}\beta_{k}(1-\beta_{k})}$ yields

Note that the given conditions imply that

Note that \{\alpha_{k}\}_{k\geq 1}\subseteq\big{(}0,\frac{1}{L_{k}}\big{]} and $\{\beta_{k}\}_{k\geq 1}\subseteq(0,1)$ are the sufficient conditions for $\frac{b_{k}}{2L_{k}^{2}\alpha_{k}\beta_{k}(1-\beta_{k})}\geq 0$ and $\frac{b_{k}(1-L_{k}^{2}\alpha_{k}^{2})}{2L_{k}^{2}\alpha_{k}\beta_{k}(1-\beta_{k})}\geq 0$ for all $k\geq 1$. ∎

D.2 Convergence analysis for S-FEG

In this section, we consider the following class of stochastic methods:

Let $\{\bm{z}_{k}\}_{k\geq 0}$ be the sequence generated by (Class S-FEG) with $\{\alpha_{k}\}_{k\geq 0}$ and $\{\beta_{k}\}_{k\geq 0}$ satisfying $\alpha_{0}\in(0,\infty)$, \alpha_{k}\in\big{(}0,\frac{1}{L}\big{]}, $\beta_{0}=1$, $\{\beta_{k}\}_{k\geq 1}\subseteq(0,1)$ for all $k\geq 1$, and

We first prove the following lemma that is used in the proof of Lemma D.1.

Proof of Lemma D.1. First, for $k=0$, note that

The sum of (10) and (11) with multiplying factor $\frac{\alpha_{0}}{2}$ yields

Hence, the sum of (12) and (D.2) with multiplying factor $\frac{b_{k}}{2L_{k}^{2}\alpha_{k}\beta_{k}(1-\beta_{k})}$ yields

By the given conditions, we get $a_{k}=\frac{b_{k}(1-\beta_{k})\alpha_{k}}{2\beta_{k}}$ and

where the last inequality follows from Lemma D.2. ∎

D.3 Proof of Theorem 6.1

Note that S-FEG is equivalent to (Class S-FEG) with $\alpha_{k}=\frac{1}{L}$ and $\beta_{k}=\frac{1}{k+1}$. It is straightforward to verify that the given $\{\alpha_{k}\}_{k\geq 0}$ and $\{\beta_{k}\}_{k\geq 0}$ satisfy the conditions in Lemma D.1 for all $k\geq 0$. By noting that

In addition, if $\sigma_{0}^{2}\leq\frac{\epsilon}{6}$, $\sigma_{k}^{2}\leq\frac{\epsilon}{6k}$ and $\sigma_{k+1/2}^{2}\leq\frac{\epsilon}{6(k+1)}$ for all $k\geq 1$, then we have