Stable Nonconvex-Nonconcave Training via Linear Interpolation
Authors: Thomas Pethick
Wanyun Xie
Volkan Cevher
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Minimax optimization
Lookahead
Generative adversarial networks
Stability
Nonconvex-nonconcave
Cohypomonotone

Abstract: This paper presents a theoretical analysis of linear interpolation as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear interpolation can help by leveraging the theory of nonexpansive operators. We construct a new optimization scheme called relaxed approximate proximal point (RAPP), which is the first 1-SCLI method to achieve last iterate convergence rates for $\rho$-comonotone problems while only requiring $\rho > -\tfrac{1}{2L}$. The construction extends to constrained and regularized settings. By replacing the inner optimizer in RAPP we rediscover the family of Lookahead algorithms for which we establish convergence in cohypomonotone problems even when the base optimizer is taken to be gradient descent ascent. The range of cohypomonotone problems in which Lookahead converges is further expanded by exploiting that Lookahead inherits the properties of the base optimizer. We corroborate the results with experiments on generative adversarial networks which demonstrates the benefits of the linear interpolation present in both RAPP and Lookahead.

Stable Nonconvex-Vonconcave Training via Linear Interpolation
Thomas Pethick EPFL (LIONS) thomas. phomas.ppthickkepll..co
Wanyun Xie EPFL (LIONS) xinyuu..ie@epfl.ch
Volkan Cevher EPFL (LIONS) volkan. wolkan.cevhereepfl.co
Abstract
This paper presents theoretical analysis of linear interpolation as principled method for stabilizing (large-scale) neural network training. We argue that insta- bilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear interpolation can help by leveraging the theory of nonexpansive operators. We construct new optimization scheme called relaxed approximate proximal point (RAPP), which is the first 1-SCLI method to achieve last iterate convergence rates for p-comonotone problems while only requiring P "T." The construction extends to constrained and regularized settings. By replacing the inner optimizer in RAPP rediscover the family of Lookahead algorithms for which we establish convergence in cohypomonotone problems even when the base optimizer is taken to be gradient descent ascent. The range of cohypomonotone problems in which Lookahead converges is further expanded by exploiting that Lookahead inherits the properties of the base optimizer. We corroborate the results with experiments on generative adversarial networks which demonstrates the benefits of the linear interpolation present in both RAPP and Lookahead.
1 Introduction
Stability is a major concern when training large scale models. particular, generative adversarial networks (GANs) are known to be notoriously difficult to train. To stabilize training, the Lookahead algorithm of Zhang et al. (2019) was recently proposed for GANs Chavdarova et al. (2020) which linearly interpolates with slow moving iterate. The mechanism has enjoyed superior empirical performance both minimization and minimax problems, but it largely remains a heuristic with little theoretical motivation.
One major obstacle for providing a theoretical treatment, is in capturing the (fuzzy) notion of stability, Loosely speaking, training dynamics is referred to as unstable in practice when the iterates either cycle indefinitely or (eventually) diverge-aa as has been observed for the Adam optimizer (see e.g. Gidel et al. (2018, Fig. 12) and Chavdarova et al. (2020, Fig. 6) respectively). Conversely, stable dynamics has some bias towards stationary points. The notion of stability so far (e.g. in Chavdarova et al. (2020, Thm. 2-3)) is based the spectral radius and thus inherently local.
In this work, we are interested establishing global convergence properties, in which case some structural assumptions are needed. One (nonmonotone) structure that lends itself well to the study of stability that cohypomonotonicity studied in Combettes Pennanen (2004); Diakonikolas et al. (2021), since even the extragradient method has been shown to cycle and diverge in this problem class (see Pethick al. (2022, Fig. 1) and Pethick et al. (2023, Fig. 2) respectively). We provide geometric intuition behind these difficulties in Figure 1. Biasing the optimization schemes towards stationary points becomes central concern and we demonstrate in Figure that Lookahead can indeed converge for such nonmonotone problems.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table I: Overview of last iterate results with our contribution highlighted in blue Prior to this work there existed no rates for I-SCLI schemes handling p-comonotone problems with p E (-1/22, o0) and no global convergence guarantees for Lookahead beyond bilinear games.
Method
Setting
Handles constraints
p g-independent rates
Reference
Impllei
PP
Comonotone
1/2, 00)
(Gorbunov ct al., 2022b, Thm. 3.1)
Relaxed PP
Comonotone
//2, 2c)
Theorem 6.2
Extripoiat
Comonotone & Lips.
//S1,00)
X
(Gorbunov et al., 2022b, Thm. 4.1)
RG+
Comonotone & Lips.
Unknown rates
RAPP
Comonotone & Lips.
(-1/2L, 00)
v
Corollary 6.4
Local
X
(Chavdarova et al., 2020, Thm. 2)
Lockchhea
LA-GDA
Bilinear
x
(Ha & Kim, 2022, Cor. 7)
Comonotone & Lips.
(-1/av3L, oc)
x
Theorem 7.1
Bilinear
X
(Ha & Kim, 2022, Cor. 8)
LA-EG
Monotone Lips.
Theorem F.1
LA-CEG+
Comonotone & Lips.
(11/2,,,0 oc)
Corollary 7.7
A principled approach to cohypomonotone problems is the extragradient+ algorithm (EG+) proposed by Diakonikolas et al. 12 However, the only known rates are on the best iterate, which can be problematic to pick in practice. It is unclear whether last iterate rates for EG+ are possible even in the monotone case (see discussion prior to Thm. 3.3 in Gorbunov et al. (2022a)). For this reason, the community has instead resorted to showing last iterate of extragradient (EG) method of Korpelevich (1977), despite originally being developed for the monotone case. Maybe not surprisingly. EG only enjoys last iterate guarantee under mild form of cohypomonotonicity and have far only been studied in the unconstrained case (Luo & Tran- Dian: Gorbunov et al., 2022b). Recently, last iterate rate were established for the same (tight) range of cohypomonotone problems for which EG+ has best iterate guarantees. However, the analyzed scheme is implicit and the complexity blows up with increasing oohopomoootoncctty (Gorbunov al., 2022b). This leaves the questions: Can an explicit scheme enjoy last iterate rates for the same range of cohypomonotone problems? Can the rate be agnostic to the degree of cohypomonotonicity We answer both in the affirmative.
This work focuses on 1-SCLI schemes (Arjevani et al., 2015; Golowich et al., 2020), whose update rule only depends on the previous iterate in a time-invariant fashion. Another approach establishing last iterate is Halpern-type methods with an explicit scheme developed in Lee & Kim (2021) for cohy- pomonotone problems and later extended to the constrained case in Cai et al. (2022) (c.f. Appendix A).
As will become clear, a principled mechanism behind convergence in this nonmonotone class the linear interpolation also used in Lookahead. This iterative interpolation is more broadly referred to as the Krasnosel' -kii (KM) iteration in the theory of nonexpansive operators. We show that the extragradient+ algorithm (EG+) of Diakonikolas et al. (2021), our proposed relaxed approximate proximal point method (RAPP), and Lookahead based algorithms are all instances of the (inexact) KM iteration and provide simple proofs of these schemes in the cohypomonotone case.
More concretely we make the following contributions:
1. We prove global convergence rates for the last iterate of our proposed algorithm RAPP which additionally handles constrained and regularized settings. This makes RAPP the first 1-SCLI scheme to have non-asymptotic guarantees for p-comonotone problems while only requiring P -1/21. As a byproduct we obtain a last iterate convergence rate for an implicit scheme that is independent of the degree of cohypomonotonicity The last iterate rates are established by showing monotonic decrease of the operator norm-somethin which is not possible for EG+. This contrast is maybe surprising, since RAPP can be viewed as extension of EG+, which simply takes multiple extrapolation steps.
2. By replacing the inner optimization routine in RAPP with gradient descent ascent (GDA) and extragradient (EG) we rediscover the Lookahead algorithms considered in Chavdarova et al. (2020). We obtain guarantees for the Lookahead variants by deriving nonexpansive properties of the base optimizers. By casting Lookahead as a KM iteration we find that the optimal interpolation constant X = 0.5. This choice corresponds to the default value used in practice for both minimization and minimax- thhnaaashhuuaae providing theoretical motivation for the parameter value.

---

3. For T = 2 inner iterations we observe that LA-GDA reduces to a linear interpolation between GDA and EG+ which allows us obtain global convergence in p-comonotone problems when p > -1/3/3r. However, for large, we provide a counterexample showing that I.AGDDA cannot be guaranteed to converge. This leads us to instead propose LA-CEG+ which corrects the inner optimization to guarantee global convergence for p-comonotone problems when p > -1/21.
4. We test the methods on a suite of synthetic examples and GAN training where we confirm the stabilizing effect. Interestingly, RAPP seems to provide similar benefit as Lookahead, which suggest that linear interpolation could play a key role also experimentally.
An overview of the theoretical results is provided in Table and Figure 5$B.
2 Related work
Lookahead The Lookahead algorithm was first introduced for minimization in Zhang et al. (2019). In the context of Federated Averaging in federated learning (McMahan et al., 2017) and the Reptile algorithm in meta-learning (Nichol al., 2018), the method can seen as a single worker and single task instance respectively. Analysis for Lookahead was carried out for nonconvex minimization (Wang et al., 2020; Zhou al., 2021) and nested variant proposed in (Pushkin & Barba, 2021). Chavdarova et al. (2020) popularized the Lookahead algorithm for minimax training by showing state-of-the-art performance on image generation tasks. Apart from the original local convergence analysis in Chavdarova et al. (2020) and the bilinear case treated in Ha & Kim (2022) we are not aware of any convergence analysis for Lookahead for minimax problems and beyond.
Cohypomonotone Cohypomontone problems were first studied in Jusem et al. (2003); Combettes & Pennanen (2004) for proximal point methods and later expanded on in greater detail in Bauschke et al. (2021). The condition was relaxed to the star-variant referred to as the weak Minty variational inequality (MVI) in Diakonikolas et al. (2021) and the extragradient+ algorithm (EG+) was analyzed. The analysis of EG+ was later tightened and extended to the constrained case in Pethick et al. (2022).
Proximal point The proximal point method (PP) has a long history. For maximally monotone operators (and thus convex-concave minimax problems) convergence of PP follows from Opial (1967). The first convergence analysis of inexact PP dates back to Rockafellar (1976); Brézis & Lions (1978).
It was later shown that convergence also holds for the relaxed inexact PP as defined in (8) (Eckstein & Bertsekas, 1992). In recent times, PP has gained renewed interest due to its success for certain nonmonotone structures. Inexact PP was studied for cohypomontone problems in lusem et al. (2003). Asymptotic convergence was established the relaxed inexact PP for a sum cohypomonotone operators in Combettes & Pennanen (2004), and later considered in Grimmer et al. (2022) without inexactness. Last iterate rates were established for PP in p-comonotone problems (with a dependency on p) (Gorbunov et al., 2022b). Explicit approximations of PP through contractive map was used for concave minimax problems Cevher et al. (2023) and was the original motivation for MirrorProx of Nemirovski (2004). See Appendix A for additional references in the stochastic setting.
3 Setup
We are interested in finding a zero of an operator
-Fz
S Rd = Rd which decomposes into a Lipschitz continuous (but possibly nommonotone) operator F and maximally monotone operator A, i.c. find 2 e gd such that,
Figure 1: Consider min maxyey ((=) with = (z, y)- As opposed to convex- concave minimax problems, the cohy- pomonotone condition allows the gradients Fz = (V=0(=), - vz)(2)) to point away from the solutions (see Appendix B. for the relationship between cohypomonotonic- ity and the weak MVD. This can lead to instability issues for standard algorithms such the Adam optimizer.
0 Sz Most relevant in the context of GAN training is that (1) includes constrained minimax problems.
A + Fz.
(1)
Example 3.1. Consider the following minimax problem
min max (1., y). xEX yEY
(2)
The problem can be recast as the inclusion problem (1) by defining the joint iterates z (I. the stacked
3

---

gradients Fz = - y)), and A = (Nx,Ny) where N denotes the normal cone. As will become clear (af. Algorithm 1), A will only be accessed through the resol- vent Jn = (id 4y which reduces to the proximal operator. More specifically J7a(2)= (projx proiy()))
We will rely the following assumptions (see Appendix B for any missing definitions). Assumption 3.2. In problem (1),
(i) The operator A : IRd = R& muximally monotone.
(ii) The operator F; Rd + Rd is L-Lipschitz, i.e. for some L E [0,
F2 Fz'll s L|| 2' V2, 2' ER
(iii) The operator = =
+ A is p-comonotone for some E (-1/22, 0o), i.e.
(v (w- v' - x²) 2 2 ((u,)), (v', 2²) grph
Remark 3.3. Assumption 3.i also known as | plcoolyooooottoiccct when < O. which allows for increasing nonmonotonicity as |p| grows. See Appendix B.1 for the relationship with weak MVI.
When only stochastic feedback (. f) is available we make the following classical assumptions. Assumption 3.4. For the operator Fo ()) Fd Rd the following holds.
(i) Unbiased: Eg [2, = Fz Vz E Rd.
(ii) Bounded variance: Eg [Il (2 - ==17] V2, E Rd.
4 Inexact Krasnosellskii-Manne iterations
The main work horse we will rely on is the inexact Krasnosel ssni-MMnnn (IKM) iteration from monotone operators (also known the averaged iteration), which acts on an operator T Rd - R with incxact feedback.
++1 (1 111--0 x)** X(T2* + +e)),
(IKM)
where X (0, 1) and c a random variable with dependency on all variables up until (and including)
k. The operator T. : z + Tz + e can crucially be an iterative optimization scheme in itself. This is important, since
obtain RAPP, LA-GDA and LA-CEG+ by plugging in different optimization routines. In fact, RAPP derived by taking T3 to be a (contractive) fixed point iteration in itself, which approximates the resolvent.
We note that also the extragradient+ (EG+) method of Diakonikolas al. (2021), which converges for cohypomonotone and Lipschitz problems, can be seen as a Krasnosel'skin Mkii-Mann iteration on an extragradient step
EG(=) = =z- - FFz A+1 = -(1 + +AEG(=*)
(EG+)
where x E (0, 1). We provide a proof of EG+ in Theorem G.1 which extends the constrained case using the construction from Pethick et al. (2022) but through simpler argument under fixed stepsize.
Essentially, the IKM iteration leads to conservative update that stabilizes the update using the previous iterate. This is the key mechanism behind showing convergence in the nonmonotone setting known cobypomonotonicity. Very generally, it is possible provide convergence guarantees for IKM when the following holds (Theorem C. is deferred to the appendix due to space limitations).
Definition 4.1. An operator T Ra - Rdd said to quasi-nonexpansive if
T2 - 2'11 < || z'|l
Vz E Rd Y2' E T.
(3)
Remark 4.2. This notion is crucial to us since the resolvent Jn == (id + BB)+ (quasi)-nonexpansiil) if B is 1/o-oooyoooonooon (Bauschke et al., 2021, Prop. 3.9(i.)).

---

Approximating the resolvent
As apparent from Remark 4.2, the IKM iteration would provide convergence zero of the cohypomonotone operator S from Assumption 3.2 by using its resolvent T = Jys. However, the update is implicit, so we will instead approximate Jys. Given E IRd we seek 2' E IR such that
(2,(2) = (id +7:5 = (id +) -
This can be approximated with fixed point iteration of
Q: w + (id +> (2 FFw)
(4)
which is contraction for small enough since F is Lipschitz continuous. It follows from Banach's fixed-point theorem Banach (1922) that the sequence converges lincarly. We formalize this in the following theorem, which additionally applies when only stochastic feedback is available.
-++ = (id +>A) (( (
& C~p
(5)
Lemma 5.1. Suppose Assumptions 3.2(i), 3.2(i)) and 3.4. Given 2 E IR the iterates generated by (5) with y E (0, 1/L) converges a neighborhood linearly, i.e.
E [[lw" - -+s(s))111 S (7L) 1|00 -
w' (1 (171300
(6)
The resulting update in (5) is identical to GDA but erucially always steps from 2. We use this as subroutine in RAPP to get convergence under cohypomonotone operator while only suffering logarithmic factor in the rate.
Interpretation In the special of the constrained minimax problem in (2), the application of the resolvent (2) is equivalent to solving the following optimization problem
min max (,( v/) 6(z', v/) #'ex y'E)
1 2p
1|'
||
1 2μ
11
y1²3}
appropriately chosen μ E (0, oo). (5) can thus be interpreted as solving a particular regularized subproblem. Later we will drop this regularization arrive at the Lookahead algorithm.
6 Last iterate under cohypomonotonicity
As stated in Section 5, we can obtain convergence using the approximate resolvent through Theo- rem C.1. The convergence is provided in terms of the average, additional work is needed for last iterate result. IKM iteration on the approximate resolvent (i.e. TT(()) J7y(2) + e*) becomes,
z 2t t with vt <>S((**)))
(8a)
I+1 = (1- - A)2 + A(z + +
(8b)
with À E (0, 1) and 7 > 0 and error t E Rdd Without error, (8) reduces to relaxed proximal point
k+ (1 x)=* + {=)s(="))
(Relaxed PP)
For a last iterate result remains to argue that the residual [|*rs=*))= || is monotonically decreasing (up to an error we can control). Showing monotonic decrease fairly straightforward if = (see Lemma 1 and the associated proof). However, face additional complication due the averaging. which is apparent both from the proof and the slightly more complicated error term in the following lemma.
Lemma 6.1. If S is p-comonotone with > - then (8) satisfies for all z* E zer S,
[[>s(>*)~ = < ||,,s(**-1)) 2 + 5x(22)
where 6x(2) = |[] 2|1 + || 211)-
The above lemma allows us to obtain last iterate convergence for IKM on the inexact resolvent by combing the lemma with Theorem C.I.
5

---

Algorithm Relaxed approximate proximal point method (RAPP)
Require: z g" À E (0, 1), (1-2pl +/L))
Repeat for k 0, 1, ... until convergence
1: wg
2: for all 0, T....,T do
3: Ex. ~ P
4: u 1+ = (id
- Fo (x,))
5: gk+1 (1 A)zh k + Aun
Return g
Theorem 6.2 (Last iterate of inexact resolvent). Suppose Assumptions 3.2 and 3.4 with og. Consider the sequence (2*) keeN generated by (8) with E (0, and p -2 Then, for all x" E zer S.
Blll B[I))s((**) - =K1] 1| +11 +11=+> EK-1 sx(2*)
K K K-1
8,(2")
X(1 1
k= j=n
where (x(=) 1XEI|e= =Il] ^2 1 and 8n (x) == : [|[||= +||=
Specifically, it gets rid of the factor 7/(7 + 2p) which Gorbunov al. (2022b, Thm. 3.2) shows is unimprovable for PP. Theorem 6.2 requires that the iterates stays bounded. In Corollary 6.4 we will assume bounded diameter for simplicity, but relatively straightforward to show that the iterates can be guaranteed to be bounded by controlling the inexactness (see Lemma E.2).
Remark 6.3. Notice that the rate in Theorem 6.2 has no dependency
All that remains to get convergence of the explicit scheme in RAPP, is to expand and simplify the errors (2) and (2) using the approximation of the resolvent analyzed Lemma 5.1.
Corollary 6.4 (Explicit inexact resolvent). Suppose Assumption 3.2 holds. Consider the sequence keN generated by RAPP with deterministic feedbackk and p > - Then, for all zt E zer S with D = supjex || - 10 < oc,
=0 (i) with T To K EiT |1 -2 = 0 ||0-~0"|1
log
D2
A(1 A)K
[1-Xj
-HEL-=2T1 (ii) with Tog(V><)' || (2 z - M(- K +
log R² K²
D²
D2
Remark 6.5. Corollary 6.4(i)) implics an oracle complexity of O (oog[==)) the last iterate satisfies [=** - = 1 < e. A stochastic extension is provided in Corollary E.3 by taking the batch size increasing. Notice that RAPP, for 2 inner steps, reduces to EG+ in the unconstrained case where = 0.
for ensuring that
7 Analysis of Lookahead
The update in RAPP leads to fairly conservative update in the inner loop, since corresponds to optimizing a highly regularized subproblem as noted in Section 5. Could we instead replace the optimization procedure with gradient descent ascent (GDA)? we replace the inner optimization routine we recover what is known as the Lookahead (LA) algorithm
w = *
1 w/ FFFu -t= O,.,
(LA-GDA)
k
k-1 (1 A)=* Xuny
We empirically demonstrate that this scheme can converge for nommonotone problems for certain choices of parameters (see Figure 2). However, what global guarantees can we provide theoretically?
It turns out that for LA-GDA with inner steps (r 2) have affirmative answer. After some algebraic manipulation it not difficult to see that the update can be simplified as follows
k+1 } (2* 2x7F2 + (2 22* )).

---

100
16
11A
60
-05
RAPP
ICAPI
LAAGIA
LA-GDA
10713
A770
14
101
112
Figure 2: LA-GDA and RAPP converge for Hsich al. (2021, Ex. 5.2). Interestingly, set the stepsize y larger than 1/2 while RAPP remains stable. Approximate proximal point (APP) with the same stepsize diverges (the iterates of APP are deferred to Figure 6). In this example, it is apparent from the rates, that there is a benefit in replacing the conservative inner update in RAPP with GDA in LA-GDA explored in Section 7.
This is the average of GDA and EG+ (when À (0, 1/2). This observation allows us to show convergence under cohypomonotonicity. This positive result for nonmonotone problems partially explains the stabilizing effect of LA-GDA.
Theorem 7.1. Suppose Assumption 3.2 holds. Consider the sequence (z*) )EEN generated by LA-GDA with = 2, 2 1/1. and X E (0, 1/2). Furthermore, suppose that
2p > 21)7 and 2p Z 2X7 (1 72-
(10)
Then, for all xt zer F,
K-1
1/20 - 11 (y 2\)7 + 2p)
Σ K=
1
(11)
K
Remark 7.2. For X + and 7 7/L where e E (0, (0), sufficient condition reduces to 2 -7(1 11(1-22 2(11->(3)//2 01110)//2 of which the minimum is attained with c 1/V3, leading the requirement 2 -1/3/3L. A similar statement possible for = Thus, (LA-GDA) improves on the range of compared with EG (see Table 1).
For larger r, LA-GDA does not necessarily converge (see Figure 3 for a counterexample). We next ask what we would require of the base optimizer to guarantee convergence for any To this end, we replace the inner iteration with some abstract algorithm Alg Rd + Rd i.c.
w
++1 Alg(w() Vt = O.....,,
(LA)
k+I (1 (1- + Aw
Convergence follows from quasi-nonexpansivenes:
Theorem 7.3. Suppose Alg IRd + Rdd is quasi-noneexpansive. Then (2 )een generated by (LA) converges some z" E fix Alg.
Remark 7.4. Even though the base optimizer Alg might not converge (since nonexpansiveness is sufficient), Theorem 7.3 shows that the outer loop converges. Interestingly, this aligns with the benefit observed in practice of using the outer iteration of Lookahead (see Figure 4).
Cocoercive From Theorem 7.3 we almost immediately get converge of LA-GDA for cocrcive problems since V id - is nonexpansive iff F is 1/2-cocoercive.
Corollary 7.5. Suppose F is !/1-cocoercive. Then (=*) generated by LA-GDA with S 2/1.. converges to some 2* E zer F.
Remark 7.6. Corollary 7.5 can trivially be extended to the constrained case by observing that also V (id - F)F) nonexpansive when A is maximally monotone. As a special case this captures constrained convex and gradient Lipschitz minimization problems.

---

204
10-1
10:10
LA-GDDA 500y
LA-GDA ir 580)
LA-0X--2 (7 1901
LA-EZ- 17 1911
Figure 3: We test the Lookahead variants Pethick et al. (2022, Ex. 3(ii)) where P (-1/8L, -1/10)) (left) and Pethick et al. (2022, Ex. 5) with p = -1/3 (right). For the left example LA-GDA (provably) converges for diverges in the more difficult example on the right, while LA-CEG+ in contrast provably converges. It seems that LA-CEG+ trades off constant slowdown in the rate for convergence in larger class.
2, but may be nonconvergent for larger
illustrate. Both variants of LA-GDA
When only monotonicity and Lipschitz holds may instead consider the following extragradient based version Lookahead (first empirically investigated in Chavdarova et al. (2020))
Monotone
w 2t
w ++ = EG(
Vt = 0...,
(LA-EG)
2 A+1 = (1 (1- A)²* + Auyy
where =
We show in Theorem F.1 that the EG-operator of the inner loop is quasi-nonexpansivee which implies convergence of LA-EG through Theorem 7.3. Theorem F.1 extends even cases where A * by utilizing the swwarr-backward-forree (1991). This providing the first global convergence guarantee for Lookahead beyond bilinear games.
construction of Tseng
Cohypomon For cohypomonotons problems large may prevent LA-GDA from converging (see Figure 3 for a counterexample). Therefore we propose replacing the inner optimization loop in LA-GDA with the method proposed in (Pethick al., 2022, Alg. 1). Let H id FFF. F. We can write one step of the inner update with
10 as
CEG+ = w + 2a H Hw) with w = (id + 7A) Hw.
(12)
The usefulness of the operator CEG+ Rdd IR comes from the fact that is quasi-nonexpansive under Assumption 3.2 (see Theorem G.I). Thus, Theorem 7.3 applies even when F' is only cohy-
pomonotone we make the following modification to LA-GDA
w
w .++ CEG-(WE) (wt)) Vt 0,.,
(LA-CEG+)
z k+1 (1 A1- + Aw!,
In the unconstrained case (A = 0) this reduces to using the EG+ algorithm of Diakonikolas et al. (2021) for the inner loop. We have the following convergence guarantee. Corollary 7.7. Suppose Assumption 3.2 holds. Then (z*) kEN generated by LA-CEG+ with À E (0, 1).
7 (1-2pl++ 1/L) and (0,1+ 2g) converges some 2* zer S.
8 Experiments
This section demonstrates that linear interpolation can lead to an improvement over common baselines.
Synthetic examples Figures 2 and 3 demonstrate RAPP, LA-GDA and LA-CEG+ host of nonmonotone problems (Hsieh et (2021, Ex. 5.2), Pethick et (2022, Ex. 3(ii)), Pethick et al. (2022, Ex. 5)). See Appendix H.2 for definitions and further details.

---

Table 2: Adam-based. The combination of Lookahead and extragradient-lik methods performs the best.
Table 3: GDA-based. Both RAPP and Looka-
head increases the scores substantially.
FID
ISC
FID
ISC
GDA EG
19.36:10.08
7.84
Adam
21.04:12.20
1.61::0.15
18.9440.60
7.84
ExtraAdam
18.23++1113
7.79+:0.08
EG+
19.35
7.74
ExtraAdam+
1..94+1.93
7.65+20.13
LA-GDA
16.87+0.18
8.01
LA-Adam
17.63++0.65
7.86++0.07
LA-EG
16.91+0.66
7.97+0.12
LA-ExtraAdam
15.68+00677
7.97+00112
LA-EG+
17.20+t0.44
7.94
LA-ExtraAdam+
17.86:+1.03
8.08
RAPP
17.76:00.82
7.98
Image generation We replicate the experimental setup of Chavdarova et al. (2020); Miyato et al. (2018), which uses hinge version of the non-saturated loss and ResNet with spectral normalization for the discriminator (see Appendix H.2 for details). To evaluate the performance we rely on the commonly used Inception score (ISC) (Salimans et al., 2016) and Fréchet inception distance (FID) (Heusel et al., 2017) and report the best iterate. We demonstrate the methods on the CIFARIO dataset (Krizhevsky al., 2009). The aim is not to beat the state-of-the-art arr, but rather to complement the already exhaustive numerical evidence provided in Chavdarova et al. (2020).
For a fair computational comparison we count the number of gradient computations instead of iterations A as in Chavdarova et al. (2020). Maybe surprisingly, we find that the extrapolation methods such as EG and RAPP still outperform the baseline, despite having fewer effective iterations. RAPP improves over EG, which suggest that can be worthwhile to spend more computation on refining the updates at the cost of making fewer updates.
The first experiment we conduct matches the setting of Chavdarova et al. (2020) by relying on the Adam optimizer and using and update ratio of between the discriminator and generator. We find in Table 2 that LA- LA-ExxtaAdamm+ has the highest ISC (8.08) while LA-ExtraAdam has the lowest FID (15.88). In contrast, we confirm that Adam is unstable while Lookahead prevents divergence as apparent from Figure 4, which is in agreement with Chavdarova et al. (2020). addition, the outer loop of Lookahead achieves better empirical performance, which corroborate the theoretical result (cf. Remark 7.4). Notice that ExtraAdam+ has slow convergence (without Lookahead), which is possibly due to the 1/2-smaller stepsize.
Asart LiGdrradarn
100
Figure 4: Adam eventually diverges on CI- FAR10 while Lookahead is stable with the outer iterate enjoying superior performance.
We additionally simplify the setup by using GDA-based optimizers with an update ratio 1 1, which avoids the complexity of diagonal adaptation, gradient history and multiple steps of the discriminator as in the Adam-based experiments. The results are found in Table 3. The learning rates are tuned for GDA and we use those parameters fixed across all other methods. Despite being tuned on GDA, we find that extragradient methods, Lookahead-baad based methods and RAPP all still outperform GDA in terms of FID. The biggest improvement comes from the linear interpolation based methods Lookahead and RAPP (see Figure for further discussion on EG+). Interesting, the Lookahead based methods are roughly comparable with their Adam variants (Table 2) while GDA even performs better than Adam.
Conclusion & limitations
We have precisely characterized the stabilizing effect of linear interpolation by analyzing it under cohypomonotonicity We proved last iterate convergence rates for our proposed method RAPP. The algorithm is double-looped, which introduces a log factor in the rate as mentioned in Remark E,4. It thus remains open whether last iterate possible using only T inner iterations (for which RAPP reduces to EG+ in the unconstrained case). By replacing the inner solver we subsequently rediscovered and analyzed Lookahead using nonexpansive operators. In that regard, we have only dealt with compositions of operators. It would be interesting to further extend the idea to understanding and developing both Federated Averaging and the meta-learning algorithm Reptile (of which Lookahead can be seen single client and single task instance respectively), which we leave for future work.

---

10 Acknowledgements
Thanks Leello Dadi and Stratis Skoulakis for helpful discussion. This work was supported by Google. This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043). This work was supported by the Swiss National Science Foundation (SNSF) under This project has received funding from the European Research
grant number 100021_205011 Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n 725594 time-data).
References
Arjevani, Y., Shalev-Shwartz, S., and Shamir, O. On lower and upper bounds for smooth and strongly convex optimization problems. arXiv preprint arXiv:/503.066 06833, 2015.
Banach, S. Sur les opérations dans les ensembles abstraits leur application aux équations intégrales. Fund. math, 3(1):133-181, 1922.
Bauschke, H. and Combettes, P. I.. Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics. Springer, 2017. ISBN 978-3-319-483104.
Bauschke, H. H., Moursi, W. M., and Wang. X. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189(1):55-74, 2021.
Bertsekas, D. P. Incremental proximal methods for large scale convex optimization. Mathematical programming, 129(2):163-195, 2011.
Bianchi, P. On the convergence of a stochastic proximal point algorithm. In CAMSAP, 2015.
Bravo, M. and Cominetti, R. Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds. arXiv preprini NXXi:2208.004999 2022.
Brézis, H. and Lions, L. Produits infinis de résolvantes. Israel Journal of Mathematics, 29(4): 329-345, 1978.
Cai. Y., Oikonomou, A., and Zheng. W. Accelerated algorithms for monotone inclusions and constrained conconvex-noncomcat min-max optimization. arXiv preprint S.Kiv:2206.052444 2022.
Cevher, V.. Piliouras, G., Sim, R., and Skoulakis, S. Min-max optimization made simple: Approxi- mating the proximal point method via contraction maps, 2023. URL https: //axxiv org/ abs/ 2301.03931 03931
Chavdarova, T., Pagliardini, M., Stich, S. U.. Fleuret, F., and Jaggi, M. Taming GANs with Bookahead-Minmale arXiv preprint htth::000..15666 2020.
Combettes, P. L. Quasi-Fejérian analysis of some optimization algorithms. In Studies in Computa- tional Mathematics, volume 8. pp. 115-152. Elsevier, 2001.
Combettes, P. L. and Pennanen, T. Proximal methods for cohypomonotone operators. SIAM journal on control and optimization, 43(2):731-742, 2004.
Diakonikolas, J. Halper iteration for near-optimal and parameter-free monotone inclusion and strong solutions variational inequalities. Conference on Learning Theory, pp. 1428-14444441 1451. PMLR, 2020.
Diakonikolas, J., Daskalakis, C., and Jordan, M. I. Efficient methods for structured nonconvex- nonconcave min-max optimization. International Conference on Artificial Intelligence and Statistics, pp. 2746-2754, PMLR, 2021.
Eckstein, J. and Bertsekas, D. P. On the Douhlas-Rachford algorithm for maximal monotone operators. Mathematical Programming, 55(1):293-318, 1992.
Rachford splitting method and the proximal point
Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, A variational inequality perspective generative adversarial networks. arXiv preprint arXiv 1055,, 2018.
10

---

Golowich, N., Pattathil, S., Daskalakis, C., and Ozdaglar, A. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In Conference on Learning Theory, pp- 1758-1784. PMLR, 2020.
Gorbunov, E., Loizou, N., and Gidel, G. Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference Artificial Intelligence and Stafistics, pp. 366-402. PMIR, 2022a.
Gorbunov, E., Taylor, A., Horváth, S., and Gidel, G. Convergence of proximal point and extragradient- based methods beyond monotonicity: the case of negative comonotonicity. arXiv preprint arXiv:221O. 1..10...885 13831, 2022b.
Grimmer, B., Lu, H., Worah, P., and Mirrokni, V. The landscape of the proximal point method for nonconvex-noocoocave minimax optimization. Mathematical Programming, pp. 1-35, 2022.
Ha, and Kim, G. On convergence of Lookahead in smooth games. In International Conference on Artificial Intelligence and Statistics, pp. 4659 4684. PMLR, 2022.
Halpem, B. Fixed points of nonexpanding maps. 1967.
Heusel, M.. Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter. GANs trained by a two time-scale update rule converge to local Nash equilibrium. Advances in neural information processing systems, 30, 2017.
Hsieh, Y.-P., Mertikopoulos, P., and Cevher, V. The limits of min-max optimization algorithms: Convergence spurious non-critical sets. In International Conference on Machine Learning, pp. 4337-4348. PMLR, 2021.
Jusem, A. N., Pennanen, T., and Svaiter, B. F. Inexact variants of the proximal point algorithm without monotonicity. SIAM Journal on Optimization, 13(4):0080-1097, 2003.
Korpelevich, G. Extragradient method for finding saddle points and other problems. Matekon, 13(4): 35-49, 1977.
Krizhevsky, Hinton, G., al. Learning multiple layers of features from tiny images. 2009.
Lec, S. and Kim, D. Fast extra gradient methods for smooth structured nonconvex- minimax problems. Advances in Neural Information Processing Systems, 01122588-22600,,
Lieder, F. On the convergence rate of the halpern- salpern-iteration. Optimization letters, 15(2):405-418. 2021.
Luo, Y. and Tran-Dinh, Q. Extragradient-type methods for co-monotone root-finding problems.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effcienn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282, PMLR, 2017.
Miyato, T., Kataoka, T., Koyama, M., and Yoshida, Y. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:1802.0599) 2018.
Nemirovski, A. Prox-method with rate of convergence (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.
Nichol, A., Achiam, J., and Schulman, J. first-order meta-learning algorithms. arXiv preprint arXiv:1803.02999, 2018.
Obukhov, A., Seitzer, M., Wu, P.W.., Zhydenko, S., Kyl, J., and Lin, E. Y.-. High-fidelity perfor- mance metrics for generative models in Py 2020. URL torch-fidelity, Version: 0.3.0, DOI: 10.5281//2cooo0449577...
www.cooooooooooo toshas/
Opial, 7. Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bulletin of the American Mathematical Society, 73(4):591-597, 1967.

---

Patrascu, A. and Irofti, P. Stochastic proximal splitting algorithm for composite minimization. Optimization Letters, (000)2255-227.5 2021.
Patrascu, A. and Necoara, I. Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization. The Journal of Machine Learning Research, 18(1):7204-7255, 2017.
Pethick, T., Latafat, P., Patrinos, P., Fercoq, O., and Cevher, V. Escaping limit cycles: Global conver- gence for constrained nonconvex-monconcave minimax problems. In International Conference Learning Representations, 2022.
Pethick, T., Fercoq, O., Latafat, P.. Patrinos, P., and Cevher, V. Solving stochastic weak Minty variational inequalities without increasing batch size. In The Eleventh International Conference on Learning Representations, 2023.
Pushkin, D. and Barba, I.. Multilayer Lookahead: a nested version of Lookahead. arXiv preprint arXiv:21 10. 10.1444, 2021.
Rockafellar, T. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
Salimans, T., Goodfellow, I., Zaremba, W., Cheung, V., Radford, A., and Chen, X. Improved techniques for training GANs. Advances in neural information processing systems, 29, 2016.
Toulis, P., Horel, T., and Airoldi, E. M. The proximal Robbins-Monro method. arXiv preprint arXiv:1510.00900 009.0, 2015.
Toulis, P., Tran, D., and Airoldi, Towards stability and optimality in stochastic gradient descent. In Artificial Intelligence and Statistics, pp. 1290-1298. PMLR, 2016.
Tseng. P. Applications of splitting algorithm to decomposition in convex programming and variational incqualities. SIAM Journal on Control and Optimization, 29(1):119-138, 1991.
Wang, J., Tantia, V., Ballas, N., and Rabbat, M. Lookahead converges to stationary points of smooth non-convex functions. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 8604-8608. IEEE, 2020.
Yoon, T. and Ryu, E. K. Accelerated algorithms for smooth convex-concave minimax problems with (1/k* rate on squared gradient norm. In International Conference on Machine Learning, pp. 12098- 12909. PMLR, 2021.
Zhang, M., Lucas, J., Ba, J., and Hinton, G. E. Lookahead optimizer: k steps forward, step back. Advances in neural information processing systems, 32, 2019.
Zhou, P., Yan, H., Yuan, X., Feng, J., and Yan, S. Towards understanding why lookahead generalizes better than SGD and beyond. Advances in Neural Information Processing Systems, 34:27290- 27304, 2021.
12


Reviews:
[{"review_id": "loNaz3zxwK", "reviewer": "Reviewer_7YGi", "summary": "This paper continues a line of work motivated by the need to design algorithms for non-convex non-concave min-max problems. Such problems arise in the training of GANs as well as reinforcement learning via self-play. Since solving general non-convex non-concave min-max problems is intractable, the main approach in this line of work is to study the subclass of problems for which the gradient map (in the constrained case one additionally adds a map corresponding to the normal vectors of the constraints) is a cohypomonotone operator. Even for problems in this subclass previously developed algorithms can be shown to diverge.\n\nThe main contribution of this paper is a unified way of designing algorithms for finding zeros of cohhypomonotone operators in terms of the KM iteration from the theory of non-monotone operators. This leads to several new results including (1) a new algorithm RAPP which handles constraints and has a convergence rate independent of the cohypomonotonicity parameter $\\rho$, and (2) a simple analysis in terms of the KM iteration for the Lookahead algorithm, which additionally provides theoretical justification for the empirically most useful setting of the main hyperparameter for Lookahead.", "questions": "1. Is there a simple example of a non-concave-non-convex min-max problem so that it is easy to compute by hand that the associated operator is cohypomonotone?\n2. Is there a (even hand-wavy) theoretical reason to expect that cohypomonotonicity is a good fit for modelling large-scale min-max problems arising for GANs?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides both a new algorithm that provably converges for a broader class of problems (i.e. those with constraints and no dependence on the cohypomontonicity parameter) than previously known. \n2. The paper gives a simple and intuitive general framework for analyzing optimization algorithms for cohypomonotone operators, which gives additional insight into previously discovered algorithms (in particular Lookahead).\n3. There are also experimental results illustrating the convergence advantage of such algorithms, including in the setting of large-scale GAN training setting.", "weaknesses": "The paper is a little bit short on exposition explaining why finding the zeros of cohypomontone operators is important. Of course this strictly generalizes solving convex-concave min-max problems, but exactly how much it generalizes is not stated.\n\nIn particular, Example 3.1 gives an example of how the operator arises from a min-max problem, but does not explain when/why this operator will satisfy the conditions of Assumption 3.2. While the empirical results in the paper justify that there are practical min-max where the proposed algorithms converge while other approaches diverge, it would be nice to have a simple analytic example to illustrate more clearly what types of min-max problems give rise to cohypomonotone operators.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and address all remaining concerns below:\n\n**Generality of cohypomonotonicity and simple examples** One of the simplest examples is probably Example H.2 in the appendix where we also provide the closed-form solution to $\\rho$ and $L$. Another simple condition is the one proposed in [Example 1, Lee & Kim 2021](https://arxiv.org/pdf/2106.02326.pdf) which shows that a certain problem class is cohypomonotone when a second order condition is satisfied (known as the interaction dominant condition).\n\nAdditionally, all the results extend to weak MVIs apart from the last iterate result of RAPP (see Appendix B.1 where we discuss this). So other examples includes the two-agent zero-sum reinforcement learning problem mentioned in [Diakonikolas et al. 2021](https://arxiv.org/pdf/2011.00364.pdf), all quasi-convex-concave and all star-convex-concave problems. Note that for the last iterate result we only assume that cohypomonotonicity holds for all pairs of points for simplicity. We really only need the condition to hold for each *consecutive pair of points* of the iterates, so we could expect this to hold even in many weak MVIs.\n\n**Intuition behind applying to GANs** Our analysis primarily relies on application of cohypomonotonicity between a given iterate $z^k$ and some solution $z^\\star$. Let us for simplicity consider the unconstrained case where the condition reduces to\n\n$\\langle Fz^k, z^k-z^\\star \\rangle \\geq \\rho\\|Fz^k\\|^2$\n\nThis allows the gradients to point away from the solution set (when $\\rho$ is negative), which is generally the case in nonconvex landscapes. The slack provided on the angle is particularly large when the norm of the gradient is large, which is usually the case in the beginning of training. In general the slack can be larger when the stepsize is large through the relationship $\\rho > -2/\\gamma$ (large stepsizes of e.g. 0.1 is what is used in practice). It is definitely interesting to see if the condition can be relaxed further.\n\nAnother motivation for us was the instability at the solutions illustrated in [Figure 5, Berard 2020](https://arxiv.org/pdf/1906.04848.pdf) by inspection of the Hessian/Jacobian. Linear interpolation can be seen as a way to stabilize the dynamics also locally. We will comment on this in the final version.\n"}, {"review_id": "YiE8omKXx7", "reviewer": "Reviewer_TKoG", "summary": "This paper studies the global convergence problem under cohypomonotonicity structural assumption. The authors prove the global convergence rate for the last iterate of their proposed algorithm RAPP. RAPP is the first explicit scheme to\n58 have non-asymptotic guarantees for the full range of cohypomonotone problems. ", "questions": "N/A", "limitations": "Listed in Weakness section.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proves global convergence rates for the last iterate of our proposed algorithm RAPP which addi57 tionally handles constrained and regularized settings.\n2. By replacing the inner optimization routine in RAPP with GDA and EG, this paper rediscovers the Lookahead algorithms. Guarantees for the Lookahead variants by deriving nonexpansive properties of the base optimizers are also obtained.\n3. Their algorithm is tested experimentally. ", "weaknesses": "1. They have only dealt with compositions of operators.\n2. Whether RAPP could be extended to more general cases is not clear.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. \nWe agree that it is definitely interesting to see if we can extend the results further and we indeed have some preliminary positive results going beyond compositions."}, {"review_id": "txEZ84VMnE", "reviewer": "Reviewer_KxAB", "summary": "The paper gives a theoretical analysis of linear interpolation that can help stabilize neural network training. They show these instabilities in the optimization are caused by nonmonotonicity in the loss landscape. They also construct a new optimization scheme, called \"relaxed approximate proximal point\" (RAPP) which is the first explicit method to obtain last iterate convergence rates for cohypomonotone problems. They also show that the extragradient+ algorith, RAPP, and the Lookahead based algorithms are all instances of KM iteration. They show experiments on synthetic problems and GANs.", "questions": "- How did the wallclock time of Adam compare with the various Lookahead and Extragradient algorithms?\n\n- I know the authors mention that the point of the GAN experiment is not to beat the state-of-the-art, but are there any implications of these algorithms for achieving state-of-the-art performance?", "limitations": "- The authors don't really explicitly state their limitations, except perhaps to not compare their GAN experiment to the state-of-the-art. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Gives a nice summary of the problem setting and also clearly states what the paper is trying to resolve.\n\n- Resolves questions that were implied by the literature, and thus would be interesting to other researchers.\n\n- Gave nice proofs that generalize a number of methods as instances of the (inexact) KM iteration.", "weaknesses": "- An analysis of the wallclock time for the algorithms would have been nice.\n\n- It would have been nice to see experiments with different hyperparameters for the Adam optimizer, such as different learning rates or $\\beta$ parameters.\n\n- In the abstract: I'm not sure I am convinced that \"linear interpolation as a key method for stabilizing (large-scale) neural network training.\" The experiments haven't convinced me of this. I would probably rephrase it as \"helping stabilize\" or something similar.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and address all remaining concerns below:\n\n- **Wallclock time** The wallclock time is essentially made to be the same across all methods in the experiments by providing each method with the same number of gradient computations (see line 263-267). All the methods (Adam, SGD, Lookahead, extragradient methods and RAPP) carry out the same operator repeatedly: addition of a gradient and an iterate. The only (crucial) difference is *what* gradient and iterate are involved. So all the methods are provided with the same computational budget.\n- **Adam hyperparameters** We note that we have used the *optimized* hyperparameters of Adam from Chavdarova et al. (2020) (see [below Table 10](https://arxiv.org/pdf/2006.14567.pdf)).\n- **Implication for state-of-the-art** It is definitely interesting to try RAPP at larger scale, especially in transformer-based setups where tricks like gradient clipping are otherwise used for preventing divergence (see e.g. [StyleSwin](https://openaccess.thecvf.com/content/CVPR2022/papers/Zhang_StyleSwin_Transformer-Based_GAN_for_High-Resolution_Image_Generation_CVPR_2022_paper.pdf) and the associated code).\n- **Abstract** We will rephrased the abstract as suggested"}, {"review_id": "Gf3jdkQKlp", "reviewer": "Reviewer_RmjV", "summary": "This paper applies linear interpolation to make neural networks stable. Based on the analysis of instabilities, the authors propose a new optimization scheme, RAPP. RAPP achieves last-iterate convergence rates for the full range of cohypomonotone problems. Moreover, by replacing the inner optimizer in RAPP, the authors propose a new Lookahead algorithm, which is helpful for expanding cohypomonotone problems. The authors also do experiments to verify that linear interpolation is beneficial to RAPP and Lookahead.", "questions": "1. What’s the meaning of “id”?", "limitations": "See the weakness.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper applies linear interpolation to make neural networks stable. Based on the analysis of instabilities, the authors propose a new optimization scheme, RAPP. RAPP achieves last-iterate convergence rates for the full range of cohypomonotone problems. Moreover, by replacing the inner optimizer in RAPP, the authors propose a new Lookahead algorithm, which is helpful for expanding cohypomonotone problems. The authors also do experiments to verify that linear interpolation is beneficial to RAPP and Lookahead.", "weaknesses": "1. As illustrated in definition 4.1, formulation (4) is incorrect, because $z$ and $z^’$ have different dimensions.\n\n2. In Theorem 5.1, the authors claim that Algorithm 1 converges to a neighborhood linearly, but, according to formulation (6), the upper bound of the neighborhood is $\\infty$ when $\\gamma\\to 1/L$. This bound is too loose.\n\n3. The authors didn’t mention linear interpolation in their theorems, but they add linear interpolation in their experiments. The theorems about linear interpolation are lacking.\n\n\n4. The authors propose an optimization scheme RAPP and compare it to Adam. Then, the comparison with other optimization schemes lacked, such as Momentum, RMSprop, Adadelta, and so on.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their valuable feedback and address all remaining concerns below:\n\n- **Linear convergence** when we have $\\|w^{\\tau+1}-w^\\star\\| \\leq c \\|w^\\tau-w^\\star\\|$ for $c \\in (0,1)$ it is standard to refer to it as linear convergence, but we will add a remark clarifying that the rate suffers if $\\gamma$ is too close to $1/L$. Unfortunately this dependency is unavoidable and it also appears even for average iterate results of extragradient based methods (through e.g. $\\kappa$ in Cor. 3.2 of [Pethick et al. 2021](https://openreview.net/pdf?id=2_vhkAMARk)). \n- **Missing theory for linear interpolation** We think there might be a misunderstanding. The methods RAPP, IKM, EG+ and Lookahead are all using linear interpolation and are analysed in Lemma 6.1, Theorem 6.2, Corollary 6.4 and the theorem statements in Section 7. So the theoretical results covers the linear interpolation used in the algorithms.\n- **Additional baseline** As suggested we additionally tried SGD with momentum. We started with the the default of 0.9, but ended up consecutively decreasing the momentum parameter due to instability. As can be inferred from the table below, the only stable run we obtained was for momentum=0.1, for which the FID was still worse than for SGD without momentum (see Table 3 in the paper).\n\n    |  momentum  | 0.9 | 0.5 | 0.1 |\n    |----| -------- | -------- | -------- |\n    |FID | 319.52   | 153.39     | 20.90  |\n\n    Note that in the paper we already include comparison with both Adam and SGD.\n\n\nMinor comments: \n\n- **Typo in equation (4)** That is indeed a typo – the $n$ should have been $d$ (the correct definition can be found in Definition B.1 of the appendix). Thanks for catching it.\n- **Meaning of “id”** It refers to the identity mapping. We will add the definition to Appendix B where the rest of the definitions can be found.\n"}]

Author rebuttal:

Meta-review: All reviewers suggested acceptance. Moreover, I agree with the evaluations. There is no reason to be verbose in this metareview; I can simply just point to the original reviews. Congratulations on a nice paper.
Decision: Accept (spotlight)