Average-case Acceleration for Bilinear Games and Normal Matrices
Authors: Carles Domingo-Enrich
Fabian Pedregosa
Damien Scieur
Venue: ICLR 2021 Poster (2021)
Keywords: Smooth games
First-order Methods
Acceleration
Bilinear games
Average-case Analysis
Orthogonal Polynomials

Abstract: Advances in generative modeling and adversarial learning have given rise to renewed interest in smooth games. However, the absence of symmetry in the matrix of second derivatives poses challenges that are not present in the classical minimization framework. While a rich theory of average-case analysis has been developed for minimization problems, little is known in the context of smooth games. In this work we take a first step towards closing this gap by developing average-case optimal first-order methods for a subset of smooth games. 
We make the following three main contributions. First, we show that for zero-sum bilinear games the average-case optimal method is the optimal method for the minimization of the Hamiltonian. Second, we provide an explicit expression for the optimal method corresponding to normal matrices, potentially non-symmetric. Finally, we specialize it to matrices with eigenvalues located in a disk and show a provable speed-up compared to worst-case optimal algorithms. We illustrate our findings through benchmarks with a varying degree of mismatch with our assumptions.

Published as a conference paper at ICLR 2021
AVERAGE-CASE ACCELERATION GAMES AND NORMAL MATRICES
FOR BILINEAR
Carles Domingo-Enrich
Fabian Pedregosa Google Research
Computer Science Department Courant Institute of Mathematical Sciences
pedregosa@google..o
New York University
New York, NY 10012, USA cd2 7 edu
Damien Scieur
Samsung SAIT Lab & Mila Montreal, Canada damien. wcweeregeaiuamiamco..co.om com
ABSTRACT
Advances in generative modeling and adversarial learning have given rise to re- newed interest in smooth games. However, the absence of symmetry in the ma- trix of second derivatives poses challenges that not present in the classical minimization framework. While a rich theory of average-case analysis has been developed for minimization problems, little is known in the context of smooth games. In this work we take a first step towards closing this gap by develop- ing average-case optimal first-order methods for a subset of smooth games. We make the following three main contributions. First, we show that for zero-sum bilinear games the average-case optimal method the optimal method for the minimization of the Hamiltonian. Second, we provide an explicit expression for the optimal method corresponding to normal matrices, potentially non-symmetric. Finally, specialize to matrices with eigenvalues located in disk and show a provable speed-up compared to worst-case optimal algorithms. We illustrate our findings through numerical simulations with varying degree of mismatch with our assumptions.
INTRODUCTION
The traditional analysis of optimization algorithms is a worst-case analysis (Nemirovski, 1995; Nes- terov, 2004). This type of analysis provides complexity bound for any input from function class, no matter how unlikely. However, since hard-to-solve inputs might rarely occur in practice, the worst-case complexity bounds might not be representative of the observed running time.
A more representative analysis is given by the average-case complexity, averaging the algorithm's complexity over all possible inputs. This analysis standard for analyzing, e.g., sorting (Knuth, 1997) and cryptography algorithms (Katz & Lindell, 2014). Recently, line of work (Berthier et al., 2020: Pedregosa & Scieur, 2020; Lacotte Pilanci, 2020; Paquette et al.. 2020) focused on optimal methods for the optimization of quadratics, specified by symmetric matrix. While worst-case analysis uses bounds on the matrix eigenvalues to yield upper and lower bounds on convergence, average-case analysis relies the expected distribution of cigenvalues and provides algorithms with sharp optimal convergence rates. While the algorithms developed this context have been shown to be efficient for minimization problems, these have not been extended to smooth games.
different line of work considers algorithms for smooth games but studies worst-case optimal methods (Azizian et al., 2020). In this work, combine average-cast analysis with smooth games, and develop novel average-case optimal algorithms for finding the root of a linear system determined by (potentially non-symmetric) normal matrix. We make the following main contributions:

---

Published as a conference paper at ICLR 2021
1. Inspired by the problem of finding equilibria in smooth games, develop average-case opti- mal algorithms for finding the root non-symmetric affine operator, both under a normality assumption (Thm. 4.1), and under the extra assumption that eigenvalues of the operator sup- ported in disk (Thm. 4.2). The proposed method shows polynomial speedup compared to the worst-case optimal method, verified by numerical simulations.
2. We make novel connection between average-case optimal methods for optimization, and average-case optimal methods for bilinear games. In particular, we show that solving the Hamil- tonian using average-case optimal method is optimal (Theorem 3.1) for bilinear games. This result complements (Azizian et al., 2020), who proved that Polyak Heavy Ball algorithm on the Hamiltonian is asymptotically worst-case optimal for bilinear games.
AVERAGE-CASE ANALYSIS FOR NORMAL MATRICES
In this paper we consider the following class of problems.
Definition 1. Let A E Rdddd d be real matrix and x* E I vector The non-symmetric (affine) operator (NSO) problem is defined as:
Find x F(x)) del A(x-x*) 0.
(NSO)
This problem generalizes that of minimization of convex quadratic function f. since can cast the latter in this framework by setting the operator F Vf. The set of solutions is an affine subspace that we will denote X We will find convenient consider the distance this set, defined as
dist(æ, æ x²) def
min | EEx
vll?, with X = {æ E Rd A(x - x²) 03.
(I)
In this paper we will develop average-case optimal methods. For this, we consider A and x" to be random vectors, and random initialization zo. This induces probability distribution
NSO problems, and we seek to find methods that have an optimal expected suboptimality w.rt. these random problems, have that average-case optimal methods they verify the following property at each iteration
this distribution. Denoting AA 2s) the expectation
min ((A,a* (mo) dist(x;, x²*) s.t. D. By (F) W t]. S2
(2)
The last condition e, stems from restricting the class of algorithms to first-order methods. The class of first-order methods encompasses many known schemes such as gradient descent with mo- mentum, full-matrix AdaGrad. However, methods such as Adam (Kingma & Ba, 2015) diag- onal AdaGrad (Duchi et al., 2011 are not in this class, as the diagonal re-scaling creates iterates o; outside the span of previous gradients. Although we will focus on the distance the solution, the results can be extended to other convergence criteria such as [xx))))
Finally, note that the expectations in this paper on the problem instance and not on the random- ness of the algorithm.
2.1 ORTHOGONNLL RESIDUAL POLYNOMIALS AND FIRST-ORDER METHIODS
The analysis of first-order methods simplifies through the use of polynomials, This section provides the tools required to leverage this connection.
Definition 2. residual polynomial is a polynomial P that satisfies P(O) 1.
(Hestenes et al., 1952) If the sequence (æt)eez is generated by a first-order method, then there exist residual polynomials P,, each one of degree most t, verifying
Proposition 2.1.
xt x² = P(() =x')-
(3)
As we will see, optimal average- case method are strongly related orthogonal polynomials. We first define the inner product between polynomials, where we use 8 for the complex conjugate of E C.
2

---

Published as a conference paper at ICLR 2021
Definition 3. For P.Q [[X], define the inner product (, p. for measure over C as
(P.Q), dnf J P()Q(()* dp(A).
(4)
Definition 4. A sequence of polynomials {P.} is orthogonal (resp. orthonormal) w.r... ) if (Po P). 0 i-
(Ps, Pil > 0 (resp. = 1);
2.2 EXPECTED SPECTRAL DISTRIBUTION
Following (Pedregosa & Scieur, 2020), we make the following assumption on the problem family. Assumption 1. 3p a² is independent A, and Biae, 2*) [ x=' (2zo xx) ) d Ia-
n2a
We will also require the following definitions to characterize difficulty of problem class. Let {Ai...., Aa be the cigenvalues matrix A E gaxd define the empirical spectral distri- bution of A the probability measure
(x,
where 6x, is the Dirac delta, a distribution equal to zero everywhere except at X; and whose integral over the entire real line is equal one. Note that with this definition, fo A corresponds the proportion of eigenvalues in D.
When a matrix-valued random variable, PA is measure-valued random variable. As such, we can define its expected spectral distribution
PA
E (MA),
(6)
which by the Riesz representation theorem is the measure that verifies f f E Alf dua) for all measureable Surprisingly, the expected spectral distribution the only required characteristic to design optimal algorithms in the average-case.
2.3 EXPECTED ERROR OF FIRST-ORDER METHODS
In this section we provide an expression for the expected convergence in terms of the residual poly- nomial and the expected spectral distribution introduced in the previous section. To go further in the analysis, we have to assume that A is a normal matrix.
Assumption 2. The (real) random matrix A is normal, that is, verifies AAT ATA A.
Normality equivalent to having the spectral decomposition UAU" where U is unitary, iee, U = U = I. We now have everything to write the expected error of first-order algorithm applied to (NSO).
Theorem 2.1. Consider the application of first-order method associated to the sequence of polynomials {P.} (Proposition 2.1) on the problem (NSO). Let be the expected spectral distribution of A. Under Assumptions and 2, we have
X*) R² f
|P/ dy,
Before designing optimal algorithms for certain specific distributions, we compare our setting with the average-case accelerating for minimization problems of Pedregosa Scieur (2020), who pro- posed optimal optimization algorithms in the average-case.
2.4 DIFFICULTIES OF FIRST-ORDER METHODS ON GAMES AND RELATED WORK
This section compares our contribution with the existing framework of average-case optimal meth- ods for quadratic minimization problems.

---

Published as a conference paper at ICLR 2021
Definition 5. Let H E Raxd be random symmetric positive-deftnit matrix and x² E R random vector. These elements determine the following random quadratic minimization problem
min (f(x) def 2 [x==2""((xxx))
(OPT)
As in our paper, Pedregosa & Scieur (2020) find deterministic optimal first-order algorithms in ex- pectation w.r.t. the matrix H. the solution x", and the initialization æp- Since they work with problem (OPT), their problem is equivalent to (NSO) with the matrix A H. However, they have the stronger assumption that the matrix is symmetric, which implies being normal. The normality assumption is restrictive in the case of game theory, they do not always naturally fit such applica- tions. However, this set is expressive enough to consider interesting cases, such as bilinear games, and our experiments show that our findings are also consistent with non-normal matrices.
Using orthogonal residual polynomials and spectral distributions, they derive the explicit formula of the expected error. Their result is similar to Theorem 2.1, but the major difference is the domain of the integral, a real positive line in convex optimization, but shape in the complex plane in our case. This shape plays crucial role in the rate of converge of first-order algorithms, as depicted in the work of Azizian et al. (2020); Bollapragada et al. (2018).
In the case of optimization methods, they show that optimal schemes in the average-case follow simple three-term recurrence arising from the three-term recurrence for residual orthogonal poly- nomials for the measure Ap(A). Indeed, by Theorem 2.1 the optimal method corresponds to the residual polynomials minimizing (P, P)μ, nز and the following result holds:
Theorem 2.2. (Fischer, 1996, $2.4) When is supported in the real line, the residual polynomial of degree minimizing P). pa is given by the degree residual orthogonal polynomial w.r.. Ap(A).
However, the analogous result does not hold for general measures in C, and hence our arguments will make use of the following Theorem 2.3 instead, which links the residual polynomial of degree most that minimizes (P, P) to the sequence of orthonormal polynomials for μ.
Theorem 2.3. [Theorem 1.4 of Assche (1997)] Let i be positive Borel measure in the complex plane. The minimum of the integral Jc PP dp(A) over residual polynomials P of degree lower or equal than is uniquely attained by the polynomial
(*()) = Ek-o du (0)"
with optimal value Sc (P)))) Ei (0)
1
(8)
(xx
where (dx)) is the orthonormal sequence of polynomials with respect to the inner product )
In the next sections we consider cases where the optimal scheme identifiable.
3 AVERAGE-CASE OPTIMAL METHODS FOR BILINEAR GAMES
We consider the problem of finding Nash equilibrium of the zero-sum minimax game given by
min max E(0,, 02) def (0) -11) M(0 03). 02
Let 01,07 RRd, 0g 03 E Rdd M Rddxdd and d def d, + d2- The vector field of the game
(Balduzzi et al., 2018) is defined as F(x) = A(x x ),,, where
Vo, (0,, 0.) (o, 02)
0
M
0
0 A(x x*). (10)
F(01, 02)
M
0
0
As before, X denotes the set of points x such that F(x) = 0, which is equivalent to the set of Nash equilibrium. If M is sampled independently from Dg x and Do xx has covariance g² Ias Assumption fulfilled. Since skew-symmetric, it is in particular normal and Assumption is also satisfied.
4

---

Published as a conference paper at ICLR 2021
We show that the optimal average-case algorithm to solve bilinear problems is Hamiltonian gradient descent with momentum, described below in its general form. Contrary to the methods in Azizian et al. (2020), the method propose is anytime (and not only asymptotically) average-case optimal.
Optimal average-case algorithm for bilinear games.
Initialization. #-1 30 (01.0, 02.0). sequence (he,m)) given by Theorem 3.1.
Main loop. For t 2 0,
g: F - F(x:)) - F(+))
(= 2 F(=)) by (12))
(11)
1++1 = Dt h4t19t + 11+11 Xx)
The quantity 2 Fx))l is commonly known as the Hamiltonian of the game (Balduzzi et al., 2018),
hence the name Hamiltonian gradient descent. Indeed, gt V [=())()))) when F is affine:
F(x - F(x)) F(x)) = A(x A(x x²) ) A(xx - x²) = A(A((r - x²))
A (A(x - -====") x²)) = V |1Aa x²)1 = ( (1
(12)
The following theorem shows that (11) is indeeed the optimal average-cast method associated to the minimization problem min, (b ((x)|1 the following theorem shows.
Theorem 3.1. Suppose that Assumption holds and that the expected spectral distribution of MM is absolutely continuous with respect to the Lebesgue measure. Then, the method (11) average-case optimal for bilinear games when h4, m, are chosen be the coefficients of the average-case optimal minimization of / (a=))
How to find optimal coefficients? Since || [ is quadratic problem, the coefficients {he, me} can found using the average-case framework for quadratic minimization problems of (Pedregosa & Scieur, 2020, Theorem 3.1).
Proof sketch. When computing the optimal polynomial æ; P.(A) - x²), we have that the residual orthogonal polynomial P, behaves differently if even or odd.
Case 1: t is even. In this case, we observe that the polynomial Pi(A) can be expressed as Q1/2(-A7 where (Qr)ı2 the sequence of orthogonal polynomials w.r.t. the expected spectral density of -A2, whose eigenvalues are real and positive. This gives the recursion in (1
Case is odd. There no residual orthogonal polynomial of degree for odd. Instead, odd iterations do correspond to the intermediate computation of g: in (11), but not actual iterate.
3.1 PARTICULAR CASE: M WITH I.I.D. COMPONENTS
We show the optimal method when the entries of M are i.i.d. sampled. For simplicity, order the players such that dj S d2.
Assumption 3. Assume that each component of M is sampled iid from a distribution of mean 0 and variance o², and we take dy d2 - oo with d +
de
In such case, the spectral distribution of d, T tends the Marchenko-Paae law, supported in [e, L] and with density:
PMr(A) del ([)-)
where del
o2 vr)2, del 02 v7)2. (13)
2ro2r1
5

---

Published as a conference paper at ICLR 2021
Proposition 3.1. When M satisfies Assumption 3, the optimal parameter of scheme (11) are
h1
my + pôg, where p Ltr 6 = (-p--1-1)) ó0 = 0. (14)
Proof. By Theorem 3.1, the problem reduces to finding the optimal average-case algorithm for the problem min 1 | (x))l Since the expected spectral distribution of J MMM is the Marchenko- Pastur law, we can use the optimal algorithm from (Pedregosa & Scieur, 2020, Section 5).
4 GENERAL AVERAGE-CAST OPTIMAL METHOD FOR NORMAL OPERATORS
In this section we derive general average-case optimal first-order methods for normal operators. First, need to assume the existence of three-term recurrence for residual orthogonal polynomials (Assumption 4). As mentioned in subsection 2.4, for general measures in the complex plane, the existence of three-term recurrence of orthogonal polynomials is not ensured. In Proposition B.3 in Appendix B we give a sufficient condition for its existence, and in the next subsection we will show specific examples where the residual orthogonal polynomials satisfy the three-term recurrence.
Assumption 4 (Simplifying assumption). The sequence of residual polynomials (1/a )20 orthogo- nal w.r.. the measure μl, defined on the complex plane, admits the three-term recurrence
1- 0, to 1, (A) = (ot + beA))/z + (1 az a))))=
(15)
Under Assumption 4, Theorem 4.1 shows that the optimal algorithm can also be written as aver- age of iterates following a simple three-terms recurrence.
Theorem 4.1. Under Assumption 4 and the assumptions of Theorem 2.1, the following algo- rithm is optimal in the average case, with y-1 = yo No:
y: = ar9t-1 + (1 at) + (()-)
B.
Be
B yt, Be = (0), B. = B,-1+ Br-1, Bo 0. (16)
Ft B,+B. x1-1
where (0))k20 can be computed using the three-term recurrence (upon normalization). Moreover, E (A,=",,) mn) dist(x;, X*) converges to zero at rate 1/Br
Remark. Notice that it is not immediate that (16) fulfills the definition of first-order algorithms stated in (2), as ys is clearly first-order method but 2, an average of the iterates yt- Using that F is an affine function we see that x, indeed fulfills (2).
Remark. Assumption 4 is needed for the sequence (yt)120 to be computable using three-term recurrence. However, for some distribution, the associated sequence of orthogonal polynomials may admit another recurrence that may not satisfy Assumption 4.
4.1 CIRCULAR SPECTRAL DISTRIBUTIONS
In random matrix theory, the circular law states that if A is an n matrix with i.i.d. entries of mean C' and variance R2 n, as n + do the spectral distribution of tends to the uniform distribution on Dc.a. In this subsection we apply Theorem 4.1 class of spectral distributions specified by Assumption 5, which includes the uniform distribution on Dc. Even though the random matrices with i.i.d entries are not normal, are consistent with our theoretical results under the normality assumption.
will see in section 6 that the empirical results for such matrices
Assumption 5. Assume that the expected spectral distribution JAA. is supported in the complex plane on the disk De. n of center C E RR, C' > O and radius R < C. Moreover, assume that the spectral density circularly symmetric, i.e. there exists a probability measure p. supported on [0, R) such 1 d0 duæ(r).
for all ff measurable and r E j0, R). du "r" 2n
Proposition 4.1. If μ. satisfies Assumption 5, the sequence of orthonormal polynomials is (01)
(x) = (A-C)² where KG, = v fot 2. dpæ(r))
(17)
Ken

---

Published as a conference paper at ICLR 2021
Example. The uniform distribution in De, is to dur nt dr, and KG, RR
From Proposition 4.1, the sequence of residual polynomials is given by (i(A)/á, - (1 (1- - O)' which implies that Assumption 4 is fulfilled with dr 1, = - Thus, by Theorem 4.1 we have
Theorem 4.2. Given an initialization To = æo)) if Assumption 5 is fulfilled with R < C and the assumptions of Theorem 2.1 hold, then the average-cass optimal first-order method is
y: yt-1 F(ytt1))
Be /
B B + BL-1,
Be
3
(18)
at B² B
2t-1+
y
Be + B
Moreover, E (A, 200) (1is X*) converges zero at rate 1/B
We now compare Theorem 4.2 with worst-case methods studied in Azizian al. (2020). They give a worst-case convergence lower bound of (R/C)² on the quantity dist(z,, (**) for first-order meth- ods (z: (20 on matrices with eigenvalues in the disk De. By the classical analysis of first-order methods, this rate is achievable by gradient descent with stepsize 1/C, i.e. the iterates ye defined in (18). However, by equation (79) Proposition D.3 we have that under slight additional assumptions (those of Proposition 5.2), Lim E [dist( //E [dist yr, X²)] = T
R holds. That is, the
average-case optimal algorithm outperforms gradient descent by a constant factor depending on the conditioning R/C.
5 ASYMPTOTIC BEHAVIOR
The recurrence coefficients of the average-case optimal method typically converges to limiting val- ues when + oc, which gives an "average-case asymptotically optimal first-order method" with constant coefficients. For the case of symmetric operators with spectrum in [e, L), Scieur & Pe- dregosa (2020) show that under mild conditions, the asymptotically optimal algorithm is the Polyak momentum method with coefficients depending only on & and L.. For bilinear games, since the average-case optimal algorithm is the average-case optimal algorithm of optimization algorithm, can make use of their framework to obtain the asymptotic algorithm (see Theorem 3 of Scieur & Pedregosa (2020)).
Proposition 5.1. Assume that the expected spectral density PMM of M MM is supported in [e, L] for 0 < E < L, and strictly positive in this interval. Then, the asymptotically optimal algorithm for bilinear games the following version of Polyak momentum:
gr F(x:: -F(xx)) F(xx))
E++1 = Et
(VI-Vi) VI+VE
(x. -xx) - -x))
-v)in))) gt
(19)
Notice that the algorithm in (19) is the worst-case optimal algorithm from Proposition 4 of Azizian et al. (2020). For the case of circularly symmetric spectral densities with support on disks, we can also compute the asymptotically optimal algorithm.
Proposition 5.2. Suppose that the assumptions of Theorem 4.2 hold with pn P(10, Rl) fulfilling
[u[(r, R)) = S2(RR r)" for r in [ro. R for some ro E [0, R) and for some K. E Z. Then, the average-case asymptotically optimal algorithm is, with yo Doi
y: y1-1 F F3)1-1))
(20)
(1-())) yc-
Moreover, the convergence rate for this algorithm is asymptotically the same one as for the optimal algorithm in Theorem 4.2. Namely, lim, E [dist( x,, x²))
The condition Pæ simply rules out cases in which the spectral density has exponentially small mass around 1. It is remarkable that in algorithm (20) the averaging coefficients can be expressed so simply in terms of the quantity R/C. Notice also that while the convergence rate of the algorithm

---

Published as a conference paper at ICLR 2021
slower than the convergence rate for the optimal algorithm by definition, both rates match in the limit, meaning that the asymptotically optimal algorithm also outperforms gradient descent by constant factor 1 nt in the limit - 00.
6 EXPERIMENTS
We compare some of the proposed methods on settings with varying degrees of mismatch with our assumptions.
Bilinear Games. We consider min-max bilinear problems of the form (10), where the entries of M are generated i.i.d. from a standard Gaussian distribution, We vary the ratio r = d/n parameter for d 1000 and compare the average-case optimal method of Theorems 3.1 and 5.1, the asymp- totic worst-case optimal method of (Azizian et al., 2020) and extragradient (Korpelevich, 1976). In the convergence-rate optimal step-size assuming knowledge of the edges of the spectral distribution.
all cases,
The spectral density for these problems is displayed in the first row of Figure 1 and the benchmark results on the second row. Average-case optimal methods always outperform other methods, and the largest gain is in the ill-conditioned regime (r 1).
Circular Distribution. For our second experiment choose A as matrix with iid Gaussian random entries, therefore the support of the distribution of its eigenvalue does not satisfy the normality assumption of Assumption 2. Figure (third row) compares the average-case optimal methods from Theorems 4.2 and 5.2 on two datasets with different levels of conditioning. Note that the methods converge despite the violation of Assumption 2, suggesting broader applicability than the one proven this paper. We leave this investigation for future work.
disk. Note that A
7 DISCUSSION AND FUTURE RESEARCH DIRECTIONS
In this paper, we presented a general framework for the design of optimal algorithms in the average- case for affine operators F, whose underlying matrix is possibly non-symmetric. However, our approach presents some limitations, the major one being the restriction to normal matrices. Fortu- nately, the numerical experiments above suggests that this assumption theory without that assumption is left for future work. Another avenue for future work is to analyze the nonlinear-case in which the non-symmetric operator A is non-linear, as well the case which it is accessed through a stochastic estimator (as done by (Loizou et al., 2020) for the worst-case anal- ysis).
be relaxed. Developing
ACKNOWLEDGEMENTS
C. Domingo-Enrien has been partially funded by "la Caixa" Foundation (ID 100010434). under agreement LCF/BQ/AA 18/1 1680099, and partially funded by the NYU Computer Science Depart- ment.
8

---

Published as a conference paper at ICLR 2021
Bllinear Problems
r=0.9
r=0.95
r=1
r=1.2
limit density empirical dersity
eigenvele lue density
-25
0.0
2.5
-25
0.0
2.5
2.5
0.0
2.5
22
0.0
2.5
102
M
10P
10
109
109
10a
[Pa]]
10
10
10y
10
10"
10a
10
D-12
10a1
200
400
200
400
200
400
200
400
Iterations
iterations
Iterationn
iterations
Average case Acceleration (Th. 3.2)
Azizian et al. 2020
Extragradient
Problers with Circular
Suboptimality
Eigervvalue Distribution
Subopiimality
Eigervalue Distribution
10P
[Rba]]
104
Irr ag
004
10
1120
=wel conditionnn oned
small zap =lll conditione
0.0
0.5
1.3
200
300
U.S
1.
Real
Realiy)
-4- Avtrage case onceleration (Th. 4.2
Average case Acte eration 5.2)
Extr AetraGrddimn eeett
Gradiem: Descert
Figure 1: Benchmarks and spectral density for different games. Top row: spectral density asso- ciated with bilinear games for varying values of the ratio parameter r = n//d (the x-axis represents the imaginary line). Second row: Benchmarks. Average-case optimal methods always outperform other methods, and the largest gain is in the ill-conditioned regime (r z 1). Third row. Bench- marks (columns I and 3) and eigenvalue distribution of design matrix generated with iid entries for two different degrees of conditioning. Depite the normality assumption not being satisfied, we still observe an improvement of average-case optimal methods vs worst-case optimal ones.

---

Published as a conference paper at ICLR 2021
REFERENCES
Walter Van Assche. Orthogonal polynomials in the complex plane and on the real line. In Fields Institute Communications, volume 14, pp. 211-245, 1997.
Waiss Azizian, Damien Scieur, loannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Ac- celerating smooth games by manipulating spectral shapes. In Proceedings of Machine Learning Research, 2020.
David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, and Thore Grae- pel. The mechanics of n-player differentiable games. In Proceedings of the International Con- ference on Machine Learning, 2018.
Raphaël Berthier, Francis Bach, and Pierre Gaillard. Accelerated gossip in networks of given di- mension using Jacobi polynomial iterations. SIAM Journal on Mathematics of Data Science, (1):24-47, 2020.
Raghu Bollapragada, Damien Scieur, and Alexandre d' Aspremont. Nonlinear acceleration of mo- mentum and primal-dual algorithms. arXiv preprint arXiv:/810.04539 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Bernd Fischer. Polynomial Based Iteration Methods for Symmetric Linear Systems. Vieweg+Teubner Verlag, 1996.
Magnus R Hestenes, Eduard Stiefel, al. Methods of conjugate gradients for solving linear systems.
Journal of research of the National Bureau of Standards, 1952.
Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography. CRC press, 2014.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Donald Knuth. The art of computer programming, volume 3. Pearson Education, 1997.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Malecon, 12, 1976.
Jonathan Lacotte and Mert Pilanci. Optimal randomized first-order methods for least-squares prob- lems. Proceedings of the 37th International Conference on Machine Learning, 2020.
Nicolas Loizou, Hugo Berard, Alexia Jolicocur-Martineau, Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas. Stochastic Hamiltonian gradient methods for smooth games. arXiv preprint vrXiv:2007.04202 2020.
Arkadi Nemirovski. Information-basse complexity of convex programming. Lecture Notes, 1995.
Yurii Nesterov. Introductory Lectures Convex Optimization. Springer, 2004.
Courtney Paquette, Bart van Merriënboer, and Fabian Pedregosa. Halting time is pre- dictable for large models: A universality property and average-case analysis. arXiv preprint arXiv:2006.0422 04299, 2020.
Fabian Pedregosa and Damien Scieur. Average-case acceleration through spectral density estima- tion. In Proceedings of the 37th International Conference Machine Learning, 2020.
Damien Scieur and Fabian Pedregosa. Universal average-case optimality of Polyak momentum. In Proceedings of the 37th International Conference on Machine Learning, 2020.
10

---

Published as a conference paper at ICLR 2021
A PROOF OF THEOREM 2.1
A. PRELIMINARIES
Before proving Theorem 2.1, we quickly analyze the distance function (I), recalled below,
dist(æ, X²) min vEX
x vl|2.
The definition of the distance function is not practical for the theoretical analysis. Fortunately, it possible to find a simple expression that uses the orthogonal projection matrix to the kernel Ker(A). Since II is orthogonal projection matrix the kernel of a linear transformation, it satisfies
I IT? TTe II, and AnT 0. The normality assumption on A implies also that
(21)
IIA O.
(22)
Indeed, the spectral decomposition of A is
A 0
=
U
U2]
U [U]U
and then 11 = U2U2. The next proposition uses 1l to derive the explicit solution of the (1).
Proposition A.1. We have that
dist(y, x²*) = ||(1 (y - x²)] Ve" E X
Proof. We first parametrize the set of solution x By definition we have
x {æ A(x x=) 0).
Which can be written in terms of the kernel of A as
X x * + Tww w Rd).
From this, we can rewrite the distance function (1) as
dist(y. X²) min | - (x* + Ilw)
wcRd
The minimum can be attained at different points, but in particular at -w - x²), which proves the statement.
We now simplifies further the result of the previous proposition in the case where æ; is generated by a first order method.
Proposition A.2. For every iterate 2, of first-order methods, i.e., æt satisfies
x= Pr(AA)(ro x²),, deg( deg(P.) St. P(0) I,
we have that
dist X²*) ||,0, xt [[[( x²)||
Proof. We start with the result of Proposition A.
dist(x;, X²) [|(I II) x: x²1||
The norm can be split into
[|(T (x: xx" x²) | x0* +
TT3
(x, x²) )12 2// x²)
by (21)
| x= ||
[Tx; x=))|
Since æ; is generated by first order method, we have
2t x= Pa(AA( x²), P.(0) =
11

---

Published as a conference paper at ICLR 2021
Since P(0) 1, the polynomial can be factorized P(A) I + AQi-1(A), Q being polynomial of degree 1. Therefore, |[[( x²)"l reads
[[I({x; x²) x²)l |11 AQ:-1 (zo x²)) x²1
[T x²) IIA Q (2) x12
=0 by (22)
[[] - x²)
which prove the statement.
A.2 PROOF OF THE THEOREM
We are now ready to prove the main result.
Theorem 2.1. Consider the application of a first-order method associated to the sequence of poly- nomials (Pt) (Proposition 2.1) on the problem (NSO). Let μ be the expected spectral distribution of A. Under Assumptions I and 2, we have
Eldist( X²1| R²
|Pl| du.
c(f0)
Proof. We start with the result of Proposition A.2,
dist(æ;, X²) = || x= [[(0 x²)|?
We now write the expectation of the distance function, Eldist(are, )²]
EF | x=1 ||T x=') )|
E [IPI(A) x²)||2 ||1((20) - x²') x1²
[tr (T (0o--==) (30g - tr
(20 [T
x ) - x²)²7]
-EA
(or PI (Io - x0) (000 - x²)² |A]
tr IIE [(ao x x0)(000 - x*)*[A]]
-REEA
[tr P((A)):(A)) - 1r
RIE
P( tr
RE
(P(A) |P(0) [# zero eigenvalues] tr II
DV(
However, P(()) and tr II corresponds to the number of zero eigenvalues of A, therefore,
Eldist(æ;, Xx) RE U (P(A))8s.
R = P())a(A).
B PROOFS OF THEOREM 3.1 AND PROPOSITION 3.1
Proposition B.1. [Block determinant formula] If A, B, C, D are (not necessarily square) matrices,
TA
B
det
detl D) det A BD C))
(23)
C
D
if D is invertible.
12

---

Published as a conference paper at ICLR 2021
Definition 6 (Pushforward of a measure). Recall that the pushforward fuj of measure μ by function f is defined as the measure such that for all measurable 9.
J ((A))((-H)())) = SLS(N)) du(2).
(24)
Equivalently, if X a random variable with distribution yu, then f(X) has distribution f-p-
Proposition B.2. Assume that the dimensions of M E R& xd, fulfill d2 S dy and let r = dz/dg. Let PM be the expected spectral distribution of the random matrix MM E _daadd, and assume that is absolutely continuous with respect to the Lebesgue measure. The expected spectral distribution of A is contained in the imaginary line and is given by
2 (1- ( (1-1+-)
2|
(A(iA)
(o(A)
PMM (A?). T+
(25)
for A E R. df 2 dy, then (25) holds with PM in place of PM and 1/r in place of
Proof. By the block determinant formula, we have that for + O,
sIas M M
det (sIa - A) =
det Idet(sTa, + La,
sIdz
(26)
= d2 dstt L + MM
Thus, for every eigenvalue -X < of - MM T, both iv Á and -iVA are eigenvalues of A. Since rank [M rank(M),, we have rank AA) 2rank Thus, the rest of the eigenvalues of A are O and there is a total 2d = d2 d1 them. Notice that
d1
(27)
d1 + d2
di
1+
Let ff)
and let (f+).MMMT (resp., (f- (--.MMMT) be the pushforward measure of PM T by the function f+ (resp., f-). Thus, by the definition the pushforward measure (Definition 6).
80(A) 1+? (f+). (A) (A(iA) (1-
2 1
1+ -
1
(A)
(28)
We compute the pushforwards (4))-MMMT,((-)) tiv À under the assumption that MASMT (A) PMINT (A)d):
performing the change of variables y
f (+iVX) duMMT (A) { 9 (+iVx) PMMT (A)d)= 3z0
/ +2
PMM (1v)))//))) dlyl,
J820
(29)
which means that the density of (f4)+HMMT (f-)./MMTT at y E -TR is also 2lylPMMT (lvl?).
il20 is 2/yleMre (lv12) and the density of
Proposition B.3.
The condition
=0 YP, Q polynomials (Q()) =0 - = (AP(A), Q(A)) =0
(30)
sufficient for any sequence (Pa)azo of orthogonal polynomials of increasing degrees to satisfy three-term recurrence of the form
() (A) BxPx-2(A).
(31)
where
(A).-1()).PP(A)) (P((A),Pa)))
as (APA-1(2),PP--10)
Bx = (A)
7
Pk-2(1))
(32)
13

---

Published as a conference paper at ICLR 2021
Proof. Since (P)-1(() is polynomial of degree k, and (o)ssss is basis of the polynomials of degree up to kt we can write
XP)-1(A)= = Σ (APk-1, P3) (2(2) (Pg. P3)
(33)
Now, remark that for all j < h: - 2. (Pk-1, = because the inner product of Pk-1 with polynomial of degree at most k - 2. If we make of the condition (30), this implies that (APk-1, Pу) = for all j <
Plugging this into (33), we obtain (31).
Proposition B.4. Let T be the set of polynomials with real coefficients and degree at most t. For t 2 even, the minimum of the problem
I
min
|.:(A)PINPMM (AP)
(34)
PLETT PP(0)
(R)
attained by an even polynomial with real coefficients.
Proof. Since du(it) del [NMмм (1213) is supported in the imaginary axis and is symmetric with respect to O, for all polynomials P. P.Q.
(AP(A),Q(A) = / ((A)Q(A)'d(()) = / P(A))-(())((()))) - (P())))Q()))
.R.
(35)
Hence, (P(A), AQ(A)) = 0 implies (AP(A), Q(A)) O. By Proposition B.3, a threc-term recur- rence (31) and (32) for the orthonormal sequence (0))120 of polynomials holds.
By Proposition B.5, the orthonormal polynomials (0)) of even (resp. odd) degree are even (resp.
odd) and have real coefficients. Hence, for all 2 0 even
Eiso ΦN (A) (0)
E1/2 O2R (A) (0)*
(36)
Ei=o 10x (0)
It/2 (x)
is an even polynomial with real coefficients. By Theorem 2.3, this polynomial attains the minimum of the problem
min P. PP
[((A))]|MPM (A)P)dA)
(37)
and, a fortiori, the minimum of the problem in (34), in which the minimization restricted polyno- mials with real coefficients instead of complex coefficients.
Proposition B.S. The polynomials (á1)z2 of the orthonormal sequence corresponding to the mea- sure p(iA)= = [Λ|PмиT (IAP))(()) have real coefficients and are even (resp. odd) for even (resp. odd) k.
Proof. The proof is by induction. The base case follows from the choice Φu = 1. Assuming that Øk-1 IR XX] by the induction hypothesis, we show that ag 0 (where ag is the coefficient from (31) and (32)):
(Aéx-1 (0))),--100 (z)))) = / ((o (1112)d11
(38)
(A(lox-1(22) (00-1(-1A)) (A2)dx=
Rzo
The last equality follows from (6k (1 1d which holds because (12)*
ó and turn this is true because dx-1 E [ by the induction hypothesis.
Once we have seen that a₁ O, it is straightforward apply the induction hypothesis once again to show that Sa also satisfies the even/odd property. Namely, for even (resp. odd), 7a XP 3y Pt- 2, and the two polynomials in the right-hand side have (resp. odd) degrees.
14

---

Published as a conference paper at ICLR 2021
Finally, 6R must have real coefficients because Φk-1 and Φk-2 have real coefficients by the induction hypothesis, and the recurrence coefficient 5k is real, as
(APx PA)
A0= 101-1(A)04=2(4)11APM)) ((1
0k-1 (1) (A²)dx
J220
(1100)--((1)00-2111)) ( (A3)da R.
R20
(39)
Proposition B.6. Let t 0 even. Assume that on R50, the expected spectral density PM has Radon-Nikodym derivative PMMT with respect to the Lebesgue measure. If
Qi/2 def
arg mig
R20 P1/2(A)2 A2)),
(40)
P1y2El1/2. Pe/2(0)=1
and
P.
def arg min P.l.
P((A)) (1A13) d/ip.
(41)
(R)(10)
P=(0)=1
then P. (A) Q7
Proof. First, remark that the equalities in (40) and (41) are well defined because the arg min are unique by Theorem 2.3. Without loss of generality, assume that d, S dy (otherwise switch the players), and let
def ddyd, 1. Since,
MM
O M
A
(42)
each eigenvalue of T E xRd is an eigenvalue of A2 with doubled duplicity, and the rest of eigenvalues are zero. Hence, we have pL = (1 2/(1 + })) 80 + 2 /(1 + 4)) Thus, for all 2 0,
/ P.(A)>PMM (A)dA
Oi arg min
Pa(A) du dp))= arg min
(43)
JR (0)
P.E.
P.en J
P((0)=1
By Proposition B.4, for & 2 0 the minimum in (41) is attained by even polynomial with real coefficients. Hence,
min P.nn (R)(00) P((0==1
IP(N)) (IAIP) d|j]
min P . (R)(0) P1)2(0)=1
( Prpz(23)>\ (A?)
= min P,zE Rya P1/2(0)=1
PPp(((())))AApMMMTT (13)
min P1 1/2 R.o (0)=(0)=1
min
PMMM))
P, R20 P=)2(0)=1
(44)
Moreover, for any polynomial Q:/2 that attains the minimum on the right-most term, the polynomial
P((A) (=/2(->²)) attains the minimum the left-most term. In particular, using (43), P. (-1)) attains the minimum the left-most term.
def
15

---

Published as a conference paper at ICLR 2021
Theorem 3.1. Suppose that Assumption I holds and that the expected spectral distribution of MM is absolutely contimuous with respect to the Lebesgue measure. Then, the method (11) is average-case optimal for bilinear games when h4, m, are chosen be the coefficients of the average-case optimal minimization of ([) (xx)]
Proof. Making use of Theorem 2.1 and Proposition B.2, we obtain that for any first-order method using the vector field F.
21
"[dist(z;, = R²
((()) = 1+ ())(0)
|.((A) (IA
c1(03
(45)
Let Qi Pt be as defined in (41) and (40). For 1 2 0 even the iteration & of the average-case optimal method for the bilinear game must satisfy
Ze Px- (2o) P7 (Z) - Px (zo)) = Q122(-
Px.((2))
(46)
On the other hand, the first-order methods for the minimization of the function 1 (ax)) make use of the vector field V (=)))(=)11²) = A (Ax + b) = -A²(x - x²). Let A4-A2 be the spectral density of - A By Theorem 2.1, the average-case optimal first-order method for the minimization problem is the one for which the residual polynomial P. (Proposition 2.1) minimizes the functional Ja P. du-A². That is, the residual polynomial is Qi. From (46), we see that the f-th iterate of the average-case optimal method for F is equal to the t/2-th iterator of the average-case optimal method for (z))
C PROOFS OF THEOREM 4. AND THEOREM 4.2
Theorem 4.1. Under Assumption and the assumptions of Theorem 2.1, the following algorithm is optimal in the average case, with y-1 y/0
zo:
y: = 0r + -1- a1) + (y)-(
B₁
3e
8; B. Bt
xt-1 +
B₁ + Be yr
Be = 60), = Br-1,
=o
(16)
where (0))220 can be computed using the three-term recurrence (upon normalization). More- over, (A, .o) "ist(ar,X") converges to zero at rate B/B..
Proof. We prove by induction that
Σx k n dx (A)
x
(xo xx))
(47)
Etzo (x)
The base step holds trivially because do Assume that (47) holds for / 1. Subtracting x² from (16), we have
(0)2
(0))
0= (0)2 (0:-11 x²)
(v. x²)
(48)
El OR (0)2
If
(,()) x²) (A) xz),
(49)
by the induction hypothesis for / and (48), we have
(A) Di k (0)2
(xo x²)+ (A)
Fr. x
(J0 x.)
Σl_0 ox (0)2
(50)
Σ k di (A)
(zo xz))
Ekmo km (0)²
16

---

Published as a conference paper at ICLR 2021
which concludes the proof of (47). The only thing left is to show (49), again by induction. The base
case follows readily from yo = 2g in (16). Dividing by oz()),, we rewrite (49) as
x
(co x') = (A) - xx)),
(51)
Φe (0)
where th is the t-th orthogonal residual polynomial of sequence. By Assumption 4, dh must satisfy the recurrence (15). If we subtract 2, from the second line of (16), we apply the induction hypothesis and then the recurrence in (15), we obtain
yt xx
Ge (yr-1 x²) + (1 a.) -ep--xa, x²) b,
a. (36-111 - x²) + (1 a;) x²) + b, - -x-)
x²) + 21--))))-(((A)))) x²) + (A) - =x") (52)
(A) =000
~A) - x²);
thus concluding the proof of (49).
Proposition C.1. Suppose that Assumption 5 holds with C O. that is, the circular support of μ centered at O. Then, the basis of orthonormal polynomials for the scalar product
(P.Q) J P(A)Q(A)" dp(A) is dx(A) Dx.
A
Vk 2
(53)
where KE.R v 2T Jo (2kd)))())
Proof. First, we will show that if satisfies Assumption 5 with C' = 0, then (A, O with k (without loss of generality, suppose that j > k).
J DRO
= - X 111 dı(A))
(N, ,*)
d((A)
n
25
(re p- do duR()))
1
(
2n
(00)))) ao 1"² rith duR(r) (54)
Jo 2x
0
2n
g2
R
wihh "du(r)= = =0
2 - k)
And for all 1: 2 0,
(*,,**) I
R (R
2 2h de dpR(r)
f( 2x , duu(r). (55)
11 dx())
Jo 2
Da.
Proposition 4.1. If μ satisfies Assumption 5, the sequence of orthonormal polt polynomials (ør) (A) = KRR
(A-C)) where Ki,n V V5at
R 2 dp
(17)
Proof. The result follows from Proposition C.I using the change of variables 2 + 2 + C. To compute the measure un for the uniform measure De,n, we perform change of variables to circular coordinates:
J f()) = n TR f0 {
2x S(C I(C+re"))dddr " 2T S(C + rr do duR(r). J(
D..
duu(r) RR2
dr
(56)
And
1|
R
1 R
22 dpz(())
R2 J
21+1 dr
KG R¹ VT.1.
(57)
21 +2
17

---

Published as a conference paper at ICLR 2021
Theorem 4.2. Civen an initialization 2y zu). Assumption is fulfilled with R C and the assumptions of Theorem 2.1 hold, then the average-cass optimal first-order method is
y: 9 (yyii1)
3: C22 /K
Br Bi-1 + B1-1,
(18)
3t Be + Bt xt-1 +
yt
B, + B.
Moreover, (A. .n) dist(x X²)) converges zero at rate 1/Br
Proof. By Proposition 4.1, the sequence of residual orthogonal polynomials given by ea((A)
(1) = d) Hence, Assumption 4 is fulfilled with 1, by c. v/((a)
( (A). We apply Theorem 4.1 and make use the fact that Φa (0) R Proposition D.3 for the rate on (ist
Ca See
D PROOF OF PROPOSITION 5.2
Proposition D.1. Suppose that the assumptions of Theorem 4.2 hold with the probability measure
MR fulfilling [R((r, RJ) ( r)) Then,
) for in [ro, R) for some TO [0, R) and for some E Z.
K
R²
lim
1
(58)
C
C
K
Proof. Given e > 0, let e, E 2g0 be the minimum such that
1
(1-
R2
S (1 c
(1+6)
(59)
Ei
Limo
77
Define Qt, def n K?
Then,
C
K
1:21
Q2,
QU.
(60)
k=
KE.
C2
Ek=0
Ca
R
Qk.
El_ k=
(C)
R2
1-
Qx.R
Now, on one hand, using that Qú, is an increasing sequence on t,
QLR
1
R²
(61)
Et (BG) 1-
QK.
Eteo
R
1-k
x
R
k
C
C7
k=0
C7
On the other hand, for 2 Ce.
Qun
Qun
Qu.
Elen (12)
QK.
Ei (112) 1-k
QK.
Ei
(62)
(12))=1
1-k
(Qr. - J de Qs ds
(62)
Thus, we want to upper-bound
Sú d de
Q0,R ds. First, notice that
d Q.RR= ds (1,0 R
d
(r) R
duR(r)
So (E) [("())
25 (-log( F)) dpu(r)
(63)
ds
(5OR (R) duR(r))
By concavity of the logarithm function we obtain log( R enough to so that R
< R 1 for E (ro, R.. Choose close
s E/Ce. We obtain that
R
R log
dpn(()) & (.) (F) log
R r
dpvelr)
/
R
(r))² (
20
R
-1) dun(r).
R
ro
(64)
18

---

Published as a conference paper at ICLR 2021
Thus,
Sro (1))²
R
20 ( 1) duR(()
d ds ds 1 [ So (#) log ( duR(r) (Jo (R) djen(r))
2 ds + f"
ds. (65)
(1o (R) 25 ajun(r))
Using that log x x, for lo E [I. Ges 1)
we can bound the first term of (65) as
1 Oo (#) log [) duR(r)
/" Lo (f) 2x-1 duR(r)
ds 1
ds kk (10* (T) 25 dun(r)
(5o (R) djun(r))
2
2
I (t k)
S0² (R)
dduu(r))
2
(66)
T0
2(1-
R
S c
To R
2(1 2(1-6,)-1
(21 + 1)2M (e)
11000 0.
In the last inequality we use that by Proposition D.2, for t large enough, Qr,
R2t
S (2t +
1) /ea For h E it - ce. t), the second term of (65) can be bounded as
Sx
n (f) to
duæz(r)
-1)
ds S (t -()-
1t)
(5o (+) dun((r)
J0" R 2t
dpn(r)
(67)
- -1
R
1
ro
Jo
(#) duR(r)
S QQ...
From (65), (66) and (67), we obtain that for t large enough, for ls E (t - Ce,
Srd ds
Qu S 2EQr.R.
(68)
Hence, we can bound the right-hand side of (62):
Qt
Qun L-k
$
Σl Ekmt-a
R2
(Q.R-
To Qo.
Et
R2
(Qi,R
07
(69)
1 1
R²
1
(1 - 2c) Di=t
(1 (1-20 2c) Eee
C
The last inequality follows from the definition of c, in (59). Since is arbitrary, by the sandwich theorem applied on (60), (61) and (69),
a
K2
R²
1
(70)
C
C
k=
K2
Proposition D.2. Under the assumptions of Theorem 4.2, we have that there exists C₁ such that for large enough,
K2, 2 e1 R2 2 + 1)
(71)
19

---

Published as a conference paper at ICLR 2021
Proof. By the assumption uRs there exist To: C1, > 0 such that
K2,R del 2T !,
Rt y2t dpu(()) = 2T jo {" 12th duu(())
+ 2T [ , dun(r)
R
R (2 r) 1 dr -2sc1 ! /'¹ p n22 ((-r)r r)m-1 dr 2
/
(R.
2 2Tc1
(2 r)r- dr
2 2me Rro + 2 R2t+# B(21 + k,
(72)
where the beta function (ax, v) is defined as
B(x v) def [
dr.
(73)
Using the link between the beta function and the gamma function B(x,y) = [(x) y), and Stirling's approximation, we obtain that for fixed y and large x,
B(x, y) ~ [yy)=
(74)
Hence, for large enough, B(21+ ~ (2 we obtain that there exist ej depending only on & and ro such that for large enough
(k- +1) Hence, from (72)
K 2 Rri + 2TC, R2t** - 1)!(2t++ + 1) (2+
(75)
Proposition 5.2. Suppose that the assumptions of Theorem 4.2 hold with Pr E P((O, R)) fulfilling
"R([r; RJ) - ) for T in (ro, R) for some To [0, R) and for some K. E L. Then, the average-case asymptotically optimal algorithm is, with yo Tp:
y: Y F
(20)
x2 ( x.-1 (1- yt-
Moreover, the convergence rate for this algorithm asymptotically the same one as for the optimal algorithm in Theorem 4.2. Namely, lim E [dist( xx, X²)
Proof. The proof follows directly from Theorem 4.2 and Proposition D.I. See (77) and (79) in Proposition D.3 for the statement regarding the convergence rate.
Proposition D.3. For the average-case optimal algorithm (18),
E dist = -Eap((t) def
(76)
E'=o
O2k KR.R
For the average-case asymptotically optimal algorithm (20),
E (21, = Easymp (t) def For the ierraes yt in (18), i.e. gradient descent with stepsize 1/C, we have
(1
R
2
K2
R
4(t-k)
4
+
(77)
2
C
E Edist( x²) (tD(t) def Ki.
(78)
C2
Moreover, for all 2 we have (t)((() < Earump (1), and under the assumptions of (5.1),
Expe(1)
lim Sope(1) (+000
Earymp (1)
2
lim (-000
Earympp (t)
= 1,
Etv(()
(GD(t)
- T
(79)
20

---

Published as a conference paper at ICLR 2021
Proof. To show (76), (77), (78), we use the expression 2;- x= (r(A)(zu- (oll)uu-="))))) x²) (Proposition 2.1)
and then evaluate ||PPll]. = Sexto) Pa| du (Theorem 2.1).
For (76), the value of || follows directly from Theorem 2.3, which states that the value for the optimal residual polynomial P; is
(80)
Ei [0)2
C
2k=0
K
A simple proof by induction shows that for the asymptotically optimal algorithm (20), the following expression holds for all & 2 0:
R ④
2
2
A b
R
2(t-k)
Vt - xx
+
(0o - x²)
(81)
e
c
1m
Thus,
R
2
R
2
A ))
R
2(c-k)
P((A)
1
Σ
C
C
(82)
=
2
do(A)
+
[
2
Σ
1
KE,R
C
Φz (A)
R
2(t-N)
k=1
which concludes the proof of (77), as
R
2
2
K
R
4(t-k)
R
1
(83)
C
C2k
C
By equation (52),
(1
A
Ke,R C
Yt xx =
(yo x²)
the (h (A)(yo x*)
(84)
C
K²,R Thus, for the yr iterates, [|]1|]] C
and (78) follows.
Now, Etpe(t) S Easymp (t), Vt 2 0 is consequence of (t) being the rate of the optimal algorithm. And
C2
lim (t)
K
R
lim
(85)
EGD (t)
C
C
k=
K
follows from Proposition D.1. To show lim rewrite
(tg(())
R² C2. which concludes the proof,
Easymp (t) =
C (1-
(
21
2
2
Σ
1
R
2(t-k)
+
(86)
C
QK.R
C
C
using that by definition, QU. R26 K22 k.
Now, let ee E Zzo such that
R 2k
Sc.
(87)
C
Amc.
Using the same argument as in Proposition D.1 (see (68)), for t large enough and l E [t ce, t).
S.
d Q. < 2EQu.
(88)
de
21

---

Published as a conference paper at ICLR 2021
Hence, for large enough,
(1 1 -
R
2
2
Σ
(c)
R
2(t=
+ +(c)
2
c
QK.R
= -(1 (o)
=
2
2
Σ
1
R
2((-k)
+
Σ
(c)
R
2(1-k)
+
R
20
c==-cce Qtn-
Sh de Sn
C)
QK.
c
R 2
Σ
2(t-k)
t-
R
2(t-
+
+ E
(1 22
k=t-ce
k=1
c ))
Rt 2
(
1
+(1-
R 2)
(1 ( Qu,
+
t
(89)
which can be made arbitrarily close to (1 ( this into (86), we obtain that we can make Easymp (1) arbitrarily close (1 (1- ( 2)
(
1 by taking > 0 small enough. Plugging
QE.
( Q.a
(1- - (0) (t) by taking large enough.
22


Reviews:
[{"review_id": "y9pb4GSjQR-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n \n \nStrengths:\n\nThe 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.\n\nThe algorithm in (11) is easy to implement in the asymptotic regime -- ex., with (19).\n\nTheorem 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.\n\n\nWeaknesses:\n\nThere are limited experimental results,  but they do succinctly show the expected results from average-case optimization in their setup.  \n\nIt’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?\n\nIt’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.\n \n \nMy 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.\n \n \nThe following point did not affect my score but may help the authors:\n \nIf 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.\n \nIt’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.”\n \nSome 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.\n \nThe 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?\n \nWa¨ıss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Accelerating smooth games by manipulating spectral shapes, 2020.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZXysk_NLlqo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nFor 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.\n\nAs 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JF4kbGhaYEg", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the average-case complexity analysis for bilinear game and normal operator problem.\nInstead of worst-case analysis, they measure the expected complexity with respect to the random inputs, i.e., matrix $A$, points $x^*$ and $x_0$. \nTo 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.\n\nAlthough 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. \nThey 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. \nFor the other difference, the domain of the integral is real or complex. So what’s the benefit of introducing complex instead of real.\n\nOther comments: The writing can be improved by e.g. providing more discussions instead of just stacking the propositions and theorems.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)