Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper considers the average-case complexity analysis for bilinear game and normal operator problem.
Instead of worst-case analysis, they measure the expected complexity with respect to the random inputs, i.e., matrix $A$, points $x^*$ and $x_0$. 
To do this, they first show that this expectation is related to an integral of polynomials associated with the first-order method (Theorem 2.1). Then they invoke some previous work to indicate how to minimize the integral.

Although the authors pointed out the difference between this paper and the previous work Pedregosa & Scieur (2020) in Section 2.4, the contribution of this paper is still not very informative to me. 
They said that Pedregosa & Scieur (2020) considered the symmetric matrix $A$, while this work extends to normal (diagonalizable) matrix $A$, i.e., $AA^T=A^TA$ (Assumption 2). So what’s the difficulty for extending symmetric matrix to diagonalizable matrix? It seems that the analysis only needs the spectral information of the matrix. 
For the other difference, the domain of the integral is real or complex. So what’s the benefit of introducing complex instead of real.

Other comments: The writing can be improved by e.g. providing more discussions instead of just stacking the propositions and theorems.

review_title: Extend previous average-case complexity work from symmetric to normal matrices (i.e., diagonalizable)

final_score: rating: 7: Good paper, accept
review_content: The paper combines two recent areas of interest in optimization for machine learning: average-case analysis for acceleration and learning in bilinear games.  Average-case optimal methods are proposed for some distributions on eigenvalues for the Jacobian of the games vector-field. Also, a connection is made between average-case optimal methods in bilinear games and optimally solving the Hamiltonian.
 
 
Strengths:

The paper presents methods that improve on worst-case optimal algorithms for learning in games by using average-case optimal algorithms.  Numerical experiments confirm a reasonable benefit in the ill-conditioned regime.

The algorithm in (11) is easy to implement in the asymptotic regime -- ex., with (19).

Theorem 3.1 which connects optimal methods with minimization on the Hamiltonian highlights a recurring theme in the analysis of these kinds of problems, which other authors may be able to use in the future.


Weaknesses:

There are limited experimental results,  but they do succinctly show the expected results from average-case optimization in their setup.  

It’s not clear how to apply these methods towards more realistic problems we may want to solve.  For example, in optimizing GANs, how do the distribution of the eigenvalues of the Jacobian compare during training (for medium-scale problems with say 1-5k parameters) with the distributions you investigate?  Is there a useful distinction between how one would implement worst-case and average-case algorithms in situations where we don’t have a tight understanding of the eigenvalue distribution?

It’s not clear to me what assumptions are needed at some points in the paper.  When do we need A to be skew-symmetric (i.e., a zero-sum bilinear game)? Should Thm 3.1 be for “zero-sum bilinear games” instead of bilinear games in general?  If the zero-sum assumption is required, it might be worthwhile emphasizing when it is/isn’t needed when talking about “bilinear games”.  Prop 5.2 says it requires the assumptions of Theorem 4.2 which again says it requires the assumptions of Theorem 2.1.  I find this difficult to read and would appreciate a summary of the assumptions required directly at each step.
 
 
My recommendation is to accept the paper with a 7.  Studying learning in games is an important problem in machine learning, and establishing average-case algorithms complements recent worst in worst-case bounds for bilinear games. The asymptotic algorithms presented are simple to use for some eigenvalue distributions. The experimental results are weak, but almost unnecessary given the strong theoretical results.  If there were proposed ways (and results) to leverage the average-case algorithm variants in more-general setups like GANs I would raise the score.
 
 
The following point did not affect my score but may help the authors:
 
If you are pressed for space to add details, it’s not clear to me that you need to re-state the result Prop 5.1 in the main body.
 
It’s unclear to me what is meant by “For bilinear games, since the average-case optimal algorithm is average-case optimal algorithm of an optimization algorithm.”
 
Some terms are not defined explicitly in the main body of the text before being used.  For example, D_{C, R}. However, this did not strongly hinder comprehension.
 
The paper states “This result complements [1], proved that Polyak Heavy Ball algorithm on the Hamiltonian is asymptotically worst-case optimal.”  It’s unclear to me how this is shown in their paper. Could you elaborate on this?
 
Wa¨ıss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Accelerating smooth games by manipulating spectral shapes, 2020.

review_title: Reviewer 1

final_score: rating: 7: Good paper, accept
review_content: In this submission, first-order methods for solving smooth games are studied in the average case. In particular, first-order methods are derived and studied that are average-case optimal for certain optimization problems. In particular average-optimal first-order methods for solving zero-sum minimax games are presented. Also for finding the root of non-symmetric affine operators average-case optimal operators are derived if either the relevant matrix is normal or the eigenvalues are supported in a disk. Some experiments with the derived methods are conducted but the focus lies clearly on the theoretical results.

For the analysis of first-order methods a well-known and elegant connection to residual polynomials is used. The analysis is quite technical and rather densely written. I find the line of research natural and in particular I find it interesting that average-case optimal methods (under certain assumptions) can explicitly be derived.

As a non-expert in this area I had some difficulties in following the analysis and I had to read some of the related work to understand the contribution of this submission. My suggestion would be to add maybe one page to the introduction that describes in more detail the context and the relevant terminology.
review_title: interesting average-case analysis of first-order methods

Meta-review: The reviewers overall liked the paper and the mathematical contribution seems substantial and elegant. The two dominant concerns were whether this is really applicable to GANS, and whether the increment from symmetric to normal matrices (e.g., real to complex eigenvalues, still unitary eigenvectors) was significant enough. Our consensus is that this result is a step toward analyzing practical GANS, and (based on the authors' response) that the extension to complex eigenvalues was substantial enough. Hence I'm happy to recommend the paper.
Decision: Accept (Poster)