Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes Stay-On-the-Ridge $(STON'R)$ algorithm, which according to the authors it is the first method that is guaranteed to converge to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. The proposed method is a second-order algorithm that provably escapes limit cycles as long as it is initialized at an easy-to-find initial point. Finally, the algorithm is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence.
strength_and_weaknesses: The paper proposes a novel idea for the convergence to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. The fact, that the proposed method and the analysis are motivated by the topological nature of the problem positions this paper in a different category than other classical and recent works.  As the authors mentioned the method is not designed to decrease some potential function but is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence.

Having in mind the tight timeline for the submission of the reviews (less than 2 weeks to review 3-5 papers), I would be positively surprised if any of the reviewers were able to follow and understand the proof techniques of this work. The paper is heavily theoretical and the proof arguments are not standard.  

Main Issue: Presentation

As it is now the paper gives the impression that it was rapidly cut before the submission to simply fit into 9 pages (looks more like a draft of a final paper). I understand that the authors try to fit the novel idea into the given ICLR space but in my opinion, this is an impossible task for such results. For having a proper presentation and allowing the reader to appreciate every aspect of this work I believe one needs much more space. 

Some suggestions for squeezing the results but keeping important parts in the main paper: 

1. I would suggest removing section 5.3 in the appendix and adding some experiments in the main paper as well as a conclusion.
2. In part of the main contributions in section 1 a table with what are the existing results in terms of convergence guarantees and the main contribution will give a better idea to the reader of what is needed. A paragraph explaining what are the challenges of the new approach will be also needed there. 

Question: 

How this method is related to the Hamiltonian gradient and consensus optimization methods proposed in Abernethy et al. (2019)? Why these second-order methods cannot be used in the setting under study?

Some missing references from related work on last-iterate convergence:

[1] E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O(1/K) last-iterate convergence for
monotone variational inequalities and connections with cocoercivity. AISTATS 2022

[2] Yang Cai, Argyris Oikonomou, Weiqiang Zheng
Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games, NeurIPS 2022
clarity,_quality,_novelty_and_reproducibility: Please see the above review for further details. 

summary_of_the_review: The paper in its current format is very hard to read. 

I believe the approach and results are interesting however a more clear presentation will be needed for the results to be able to be understood and get appreciated by a broader audience. 

For this reason, I gave a score of "5: marginally below the acceptance threshold" for this work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: To the authors' knowledge, this work proposes the first algorithm that provably converges to a local min-max equilibrium for smooth nonconvex-nonconcave minimax optimization. 
strength_and_weaknesses: Pros: This work is highly novel in both algorithm and proof technique, as elaborated in **Novelty** below. The convergence is also well supported by both theorem and experiments. 

Cons: A few points need to be clarified as listed in **Clarity** below. 
clarity,_quality,_novelty_and_reproducibility: **Clarity:**

This paper is generally clear. There are a few points that need to be clarified as listed below. 

(1) Right after eq. (1), you said "A solution to (1) corresponds to a Nash equilibrium of this sequential-move game." Could you give the definition? Why does "Nash equilibrium of the simultaneous-move game also constitutes a Nash equilibrium of the sequential-move game"? Could you give a brief proof or a citation that contains proof? 

(2) At the beginning of Section 2, in the definition of VI, should it be $V(x)^{\top}\cdot(x-y)\ge 0$ instead of $\le 0$? 

(3) Why do we need condition 3 of Definition 2? You may add the explanation after Definition 2. 

(4) In Assumptions 2 and 3, why not let $i>\max(s_1,\ldots,s_m)$ and $x_{\ell}\in${$0,1$} for only $\ell\in [i-1]\backslash S$ as seemingly required by the algorithm? Could you also add brief and intuitive explanation on why Assumptions 2 and 3 ensures unique $j$ in bad and middling events? 

(5) You mentioned in Section 5.1 that Assumption 1 guarantees unique direction $D_S^i(x)$ and that Assumptions 2 and 3 guarantee unique $j$. Could you cite the Lemmas that prove the uniqueness? 

(6) In Appendix A, What are the coordinates of local min-max equilibria for $f_1$ and $f_2$? 


**Quality:**

The convergence looks well supported by both theorem and experiments. 


**Novelty:**  

This paper is highly novel in at least 2 aspects: First, this work proposes the first algorithm that is guaranteed to converge to a local min-max equilibrium for smooth nonconvex-nonconcave minimax optimization. Second, the topological proof of convergence is elaborate and not commonly used. 


**Reproducibility:** 

Hyperparameters such as stepsizes of GDA and EG could be given to ensure reproducibility of experiments. 


**Minor comment:**

At the beginning of page 5, the two comments "this is so that XX is maintained" could be expressed as "this guarantees XX" or "To guarantee XX".
summary_of_the_review: This paper is very well written, which studies the unsolved challenging problem of finding local minimax equilibrium of nonconvex-nonconcave minimax optimization, with highly novel algorithm. The convergence is proved in a novel topological way, and also well demonstrated by experiments. There are a few unclear points which I think are not hard to clarify. Therefore, I would like to see this paper accepted.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This submission proposes a new algorithm called the STay-ON-the-Ridge (STON'R) for converging to the local minimax of constrained nonconvex-nonconcave games. The problem is reformulated in terms of variational inequalities. The key idea is to find a set of points on which one can define a directed graph with in- and out-degree at most one, with one node being the sought equilibrium.
strength_and_weaknesses: Strength:

- The ideas are substantially new.

Weaknesses: While I really appreciate the highly innovative algorithm and ideas, I feel like the paper, in its current state, is more of a draft than is ready to be published. I have three main concerns:

1. The presentation, especially on the proof, is very messy and difficult to follow. Here are only a few examples:
   - The argument for "Assumption 1 is mild" is very vague. For instance, can the authors explain why adding a periodic function wouldn't change the VI solutions? In its current form, the authors only gave an explanation to approximate stationary points but nothing on the boundary. Moreover, what is the basis for "In higher dimensions we do not provide a formal argument for a reduction, although we conjecture that it is true."?
   - The authors argued that Assumption 2 is mild since one can start in a smaller (random) subset of $[0,1]$. In this case, where do we initialize STON'R? Does this not destroy the pivot argument in the proof for Theorem 1? Moreover, the curve $C$ in Example 1 of Section C.2 is just a singleton $(1,0)$ so I don't really grasp its meaning.
    - Why does Lemma 8 imply Lemma 3? In Definition 7, pivots include boundary satisfied points, whereas Lemma 8 only deals with the cardinality of 0-satisfied points.

    This list can go on. Essentially, whenever I check for a rigorous statement, there is some ambiguity. I believe many of them can be easily fixed, but in its current form I find it almost impossible to verify the correctness of the paper. Since this paper is all about theory, I consider it a serious flaw.

2. The relevance of the proposed algorithm to machine learning is unclear:
    -  The authors claimed that the proposed algorithm is second-order, which is not really true. At best, it can be described as a **piecewise** second-order algorithm involving various breakpoints, but it is significantly more complicated than any bona fide second-order method. In any case, it is computationally much more demanding than existing second-order algorithms such as (Wang et al., 2019).
    
    - The claim that the authors have solved the open problem "Is there an algorithm which is guaranteed to converge to a local min-max equilibrium in the nonconvex-nonconcave setting (Wang et al., 2019)?" is an overstatement for me. Since the authors **changed** the problem formulation to constrained min-max problems, a simple grid search + Follow-the-Ridge of (Wang et al., 2019) would work; note that this naive algorithm is more practical than STON'R.

        This is not intended to say that the contribution of the paper is trivial; it simply points out that the interest of the paper mainly lies in its theoretical insights, something that is not accessible from prior works. I therefore suggest the authors to rephrase their contribution.


3. The argument seems to be highly specific for box constraints. For instance, how do I extend the algorithm to $\ell_2$-balls?

In addition, there are some issues with the reduction to VIs in Section 2. For instance, a local **max-min** (instead of min-max) in the interior would verify the VI proposed at the bottom of page 3, contradicting the authors' claim that VIs are equivalent to local min-max. Can the authors clarify?


clarity,_quality,_novelty_and_reproducibility: Clarity is the major problem of the paper, which also poses question marks regarding correctness. 

A few minor comments:

- Is there any reason for considering min-max optimization instead of general $k$-player games? The argument seems to work for general variational inequality problems.

- In the proof of Lemma 9, "...for an appropriately selected $L$": $L \rightarrow M$. 

- In the definition of $F^i(x)$ at page 21, what does it mean that "coordinate $\ell$ is fixed at $x$? It seems like the authors are suggesting that $F^{i}(x)$ are the set of points that are boundary satisfied. (Does it mean "frozen" as in Definition 6?)

summary_of_the_review: The paper proposes contains many novel ideas. However, my concerns are that 
1. The presentation is messy and it is almost impossible to check the proofs. 
2. Stylistically speaking, I believe this is more of a TCS paper than an ML paper. The relevance to ML is not very clear.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The presents an algorithm to solve variational inequalities over the unit cube under some seemingly mild assumptions. This implies that the algorithm can be used to find approximate local Nash equilibrium points for min-max optimization problems with non-convex-non-concave smooth objectives.

The reviewers agree that the paper proposes an interesting and novel algorithm, and I think that the main ideas are nicely flashed out in the main body of the paper. However, the reviewers found that the results are not stated properly and also that it was hard to verify the proofs. Although the authors made changes during the revision, it was not possible to fully check all the changes. The paper definitely has more typos left, e.g., the variational inequalities are still reversed in the proof of Lemma 1, although used correctly, or the definition of a pivot point should either state that there is an unsatisfied variable or $\ell$ should be defined to be at least $n$ in case no such variable exists (or make the same assumption in Lemma 3 instead), or Lemma 8 is referenced in place of Lemma 7 when proving Lemma 3, etc. While these issues are not serious and can be easily corrected, given the previous concerns of the reviewers, they suggest that the paper could benefit from another review cycle. 

More importantly, a revision should clarify the contributions better. Regarding the main results concerning variational inequalities, it would be good to quantify the dependence of $\bar{T}$ on its parameters in Theorem 1, and that of $\bar{M}$ in Theorem 2, together with some intuition (formula) how small the step size should be. Getting stronger arguments about why the assumptions are mild would also substantially improve the results. With respect to the approximate local Nash equilibrium, it would be important to clarify the meaning and limitation of this concept. As the authors also explained in their response, the approximate local Nash equilibrium concept is quite "fragile", as, for smooth functions, it is satisfied by any stationary point. Hence, one can easily find such a point by running gradient descent over both parameters (with sufficiently small step size). While this is clearly not an intended solution, the discussion of such issues would be needed. 

Based on the above, unfortunately I cannot recommend acceptance of this paper, but I am convinced that when properly revised, this might become an important contribution to the field. Personally, I would present the main contribution (title, introduction, etc.) about the results on variational inequalities, and then present min-max optimization (or even more generally, multi-player games) as an important application of the method.

Finally, the authors might consider to compare their method to the SGA algorithm of Balduzzi et al., The Mechanics of n-Player Differentiable Games, ICML 2018, and also describe how they parametrized (e.g., discretized for STON'R) the methods presented.
justification_for_why_not_higher_score: This was not an easy decision because of the potential in the paper, but eventually the negatives outweighed the positives, as explained above.
Decision: Reject