Stable Nonconvex-Nonconcave Training via Linear Interpolation

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.

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. 2. 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. 3. 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. 4. 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.

Questions

1. What’s the meaning of “id”?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

See the weakness.

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.

Strengths

- Gives a nice summary of the problem setting and also clearly states what the paper is trying to resolve. - Resolves questions that were implied by the literature, and thus would be interesting to other researchers. - 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. - It would have been nice to see experiments with different hyperparameters for the Adam optimizer, such as different learning rates or $\beta$ parameters. - 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.

Questions

- How did the wallclock time of Adam compare with the various Lookahead and Extragradient algorithms? - 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

- The authors don't really explicitly state their limitations, except perhaps to not compare their GAN experiment to the state-of-the-art.

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 58 have non-asymptotic guarantees for the full range of cohypomonotone problems.

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. 2. 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. 3. Their algorithm is tested experimentally.

Weaknesses

1. They have only dealt with compositions of operators. 2. Whether RAPP could be extended to more general cases is not clear.

Questions

N/A

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Listed in Weakness section.

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. The 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.

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. 2. 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). 3. 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. In 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.

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? 2. 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?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

Yes.