Only tails matter: Average-Case Universality and Robustness in the Convex Regime
Authors: Leonardo Cunha
Gauthier Gidel
Fabian Pedregosa
Courtney Paquette
Damien Scieur
Venue: ICLR 2022 Submitted (2022)
Keywords: optimization
average-case
first-order
random matrix theory
nesterov

Abstract: Recent works have studied the average convergence properties of first-order optimization methods on distributions of quadratic problems. The average-case framework allows a more fine-grained and representative analysis of convergence than usual worst-case results, in exchange for a more precise hypothesis over the data generating process, namely assuming knowledge of the expected spectral distribution (e.s.d) of the random matrix associated with the problem. In this work, we show that a problem's asymptotic average complexity is determined by the concentration of eigenvalues near the edges of the e.s.d. We argue that having à priori information on this concentration is a more grounded assumption than complete knowledge of the e.s.d.,  and that basing our analysis on the approximate concentration is effectively a middle ground between the coarseness of the worst-case convergence and this more unrealistic hypothesis. We introduce the Generalized Chebyshev method, asymptotically optimal under a hypothesis on this concentration, and globally optimal when the e.s.d. follows  a Beta distribution. We compare its performance to classical optimization algorithms, such as Gradient Descent or Nesterov's scheme, and we show that, asymptotically, Nesterov's method is universally nearly-optimal in the average-case.

Under review as a conference paper at ICLR 2022
ONLY TAILS MATTER: AVERAGE-CASE UNIVERSAL- ITY AND ROBUSTNESS IN THE CONVEX REGIME
A Anonymous authors Paper under double-blind review
BSSTRACT
Recent works have studied the average convergence properties of first-order optimization methods on distributions of quadratic problems. The average- case framework allows more fine-grained and representative analysis of convergence than usual worst-case results, in exchange for a more precise hypothesis over the data generating process, namely assuming knowledge of the expected spectral distribution (e.s.d) of the random matrix associated with the problem. This work shows that a problem' 's asymptotic average complexity is determined by the concentration of eigenvalues near the edges of the e.s.d. We argue that having a priori information on this concentra- tion is a more grounded assumption than complete knowledge of the c.s.d. basing our analysis on the approximate concentration is effectively a middle ground between the coarseness of the worst-case scenario convergence and the restrictive previous average-case analysis. We introduce the Generalized Chebyshev method, asymptotically optimal under hypothesis this con- centration, and globally optimal when the e.s.d. follows a Beta distribution. We compare its performance to classical optimization algorithms, such Gradient Descent or Nesterov's scheme, and we show that, asymptotically, Nesterov's method is universally nearly optimal the average-case.
INTRODUCTION
The analysis of the average complexity of algorithms has a long story in computer science. Average-case complexity, for instance, drives much of the decisions made in cryptography (Bogdanov & Trevisan, 2006).
Despite their relevance, averago-cast case analyses are difficult extend other algorithms, partly because of the intrinsic issuc of defining a typical distribution over problem instances. Recently though, Pedregosa & Scicur (2020) derived framework to systemically evaluate the complexity of first-order methods when applied on distributions of quadratic minimization problems. This done by relating the average-case convergence rate to the expected spectral distribution (e.s.d) of the objective function's Hessian, which is well-studied object random matrix theory. Having access to this object in practice is a much stronger hypothesis when compared to the worst-case analysis that relies only on the values of the edges of this distribution.
Paquette ct al. (2020) extended the averago-casc framework by introducing noisy generative model for the problems. They further derived the average complexity of the Nesterov Accelerated Method (Nesterov, 2003) on a particular distribution. They showed the strong concentration of the metrics around a limiting value as dimensions go to infinity.
Scieur & Pedregosa (2020) showed that for a strongly convex problem with eigenvalues sup- ported on a contiguous interval, the optimal average-case complexity converges asymptotically to the one given by the Polyak Heavy Ball method (Polyak, 1964) in the worst-case.
1.1 CURRENT LIMITATIONS OF THE AVERAGE-CASE ANALYSIS
When analyzing the state of the art of average-case methods on quadratics problems, observe significant. limitations that we address in this paper. First, little is known

---

Under review as a conference paper at ICLR 2022
about the convergence rate convex problems. Also, optimal average-case algorithms require an exact estimation of the e.s.d to guarantee an optimal convergence rate, their convergence rate under inexact e.s.d. is not known. Finally, the non-smooth is also discussed in (Pedregosa & Scieur, 2020), but with little details.
Convex problems. The minimization of non-strongly convex problems is drastically slower than their strongly convex counterpart, as Gradient Descent presents worst-case convergence in + and Nesterov is ((²). In the strongly convex case, both the worst-case and average- case are asymptotically equal. However, little is known on optimal average-case rates for convex problems, well the average-case complexity of classical methods such as gradient descent or Nesterov's method, see (Paquette et al., 2020).
Exact estimation of the e.s.d. In (Pedregosa & Scieur, 2020), the theoretical study of optimal algorithms in the average-case requires an exact estimation of the e.s.d. of the problem class. Such estimation may be hard, nor impossible to obtain in practical scenarios. Despite showing good performance when the e.s.d. is estimated with empirical quantities, there are no theoretical guarantees on the performance
the method when the e.s.d. poorly estimated. There is therefore a need to analyze the algorithm's performance under different notions of uncertainty on the spectrum. This allows a practitioner to choose the best algorithm for practical problem, even with imperfect priori information.
Non-smooth. Pedregosa Scieur (2020) briefly introduce average-case optimal rates on non-smooth problems, when the c.s.d. is the Laguerre distribution e-> In this paper, extend the analysis to the gencralized Laguerre distribution - a -1.
1.2 CONTRIBUTIONS
Our main contribution is a fine-grain fine-grained analysis of the average-case complexity on convex quadratic problems: we show that a problem's complexity depends on the concentration of the eigenvalues of e.s.d. around the edges of their support. From this perspective, we propose family of optimal algorithms in the average-case, analyze their robustness, and finally exhibit a universality result for Nesterov's method. More precisely,
(Optimal algorithms). In Section 3, we propose the Generalized Chebyshev Method (GCM, Algorithm 1), a family of algorithms whose parameters depend on the concentration of the c.s.d. around the edges of their support. If the parameters of the GCM method are set properly, the algorithm converges an optimal avcrage-case rate (Thcorem for smooth problems, Theorem 6 for non-smooth problems), rate that show is faster than worst-case optimal methods like Nesterov acceleration. We show these rates be representative of the practical performance of the algorithms in Fig. 6, and retrieve the classical worst-case rates as limits of the average-case (see Table 1).
(Robustness). Developing an optimal algorithm requires the knowledge of the exact c.s.d. However, practical scenarios, we only have access to an approzimation of the c.s.d. In Theorem 2 in Section 4 we analyze the rate of GCM in the presence of such mismatch. We also analyze the optimal average-case rates distributions representing the smooth convex, non-smooth convex, and strongly convex settings and compare them with the worst-case rates (Table 1).
(Universality). Finally, in Theorem 4, we analyze the asymptotic average-case conver- gence rate of Nesterov's method, We show that its convergence rate is nearly optimal (up to logarithmic factor) under some natural assumptions over the data, namely concentration of eigenvalues around similar the Marchenko-Pastee measure. This contributes to the theoretical understanding of the numerical efficiency of Nesterov's acceleration.
AVERAGE- CASE ANALYSIS
In this section, we recall the average-case analysis framework for random quadratic problems. The main result is Theorem 1, which relates the expected error to the expected spectral
2

---

Under review as a conference paper at ICLR 2022
Regime
Worst-case
Iverage-Case
Strongly conv. (1 ((/5))
(1 (((=))
Smooth conv.
1/22
1/204
Convex
1/v1
1/002
Table 1: Comparison between function value worst- case and average-casc convergence. is the condi- tion number in the smooth strongly convex case. In the smooth convex case & > -1 is the conceutration of eigenvalues around (see Assumption 1) and in the non-smooth case consider du x X
Figure 1: Representation of different spectra with different concentrations of eigenvalues around the edges of the sup- port. The average-case rates for non- strongly problems are determined by these concentrations
distribution and the residual polynomiial The one-to-one correspondence between the residual polynomials and first-order methods applied to quadratics will allow us to pose the problem of finding an optimal method as the best approximation problem in the space of polynomials.
We define random quadratic problem:
Problem 1. Let H E Raxd be random symmetric positive-definite definite matria independent to xt' E Tedd, a random vector that is the solution to the problem. We define the random quadratic minimization problem
min =ERd
( (x-x") H at)}
(OPT)
We interested minimizing the expected errors [x] - f(xx))l, the expected function- value gap, and V fxx))l?, the expected gradient norm, where æe is the t-th update of a first-order method starting from zu and E is the expectation over the random variables H, zo and x².
The expectation we consider is over the problem and not over any randommess of the algorithm.
In this paper, we consider the class of first-order methods (F.O.M's) to minimize (OPT).
Methods in this class construct the iterates a, as Vf(xx-1)) [
2t E Zo + span
(1)
That is, I, belongs to the span of previous gradients. This class of algorithms includes for instance gradient descent and momentum, but not quasi-Newton methods since the preconditioner could allow the iterates to go outside of the span. Furthermore, we will only consider oblivious methods, that is, methods in which the coefficients of the update are known in advance and do not depend on previous updates. This leaves out some methods such as conjugate gradient or methods with line-search.
From First-Order Method to Polynomials. There is an intimate link between first- order methods and polynomials that simplifies the analysis quadratic objectives. The next proposition shows that, with this link, we assign to each optimization method a polynomial that determines its convergence. Following Fischer (1996), we will say polynomial P. is residual if Po( = 1.
Proposition 1. (Hestenes et al., 1952) Let w, be generated by first-oddrr method. Then there erists a residual polynomial P, of degree I, that verifies
Dt xx P. - x²)
(2)
3

---

Under review as a conference paper at ICLR 2022
Remark 1. If the first-order method is further momentum method, i.e. a+++ = Dt + ( + mi(a; - Tt--)). We can determine the polymomials by the recurrence Po =1 and Pa+1(A) = P((A) + h(PP((A) + mm(P((A) Pa-1(A)).
We note that while most popular F. P.O.M's can be posed as a momentum method, the Nesterov method cannot.
A convenient way to collect statistics on the spectrum of a matrix is through its empirical spectral distribution.
Definition (Expected spectral distribution (e.s.d)). Let H be a random matrix with eigenwabues Aa)) The empirical spectral distribution of H, called pH, is the probobility measure
P =- -
2 Ox.1
(3)
where dx, is the Diruc delta, a distribution equal to zero everywhere except at X and whose integral over the entire real line is equal to one.
Since random, the empirical spectral distribution μи is a random variable in the space of measures. Its expectation over H is called the expected spectral distribution and we denote
:= [
(4)
We can link the e.s.d. of H to the convergence of a first-order method on the distribution of H. In the following we will consider In xx and H to be independent, with To sampled isotropically.
Theorem Let a, be generated by a first-order method associated to the polynomial P.. the measure is the e.s.d. of H, and [[[ x=" (xa x=") x²²²²= R²I for some constant R. Then we can write the convergence metrics at time step t as
E|[| x 11 11= R2 (P(())d(A),
[[J(x: - [ax')\ = R² (((())du())
(5)
( R2 (P(()))a(())
and
This shows that polynomials are powerful abstraction they allow us to write all of our convergence metrics within the same framework For simplicity, we set R²2 = and we will refer directly to the polynomials associated to given method. We will refer to objective [ as the one associated to the added X' term, i.c. the function-value is objective l= 1.
This framework is linked to the field of orthogonal polynomials by the next proposition. We construct an optimal method w.r.t. a given distribution through a family of orthogonal polynomials associated to it.
Proposition 2 (PPedregosa & Scieur, 2020)). Let P! be defined
P arg / P((A))dv(A)).
(6)
Then (P!) is the family of residual orthogonal polynomials w.r.t. X dv.
This theorem further implics that the optimal first-order method is momentum method as Favard's theorem Marcellán & Álvarez-Nodarsee (2001) tells us the orthogonal polynomials w.r.t. a given distribution are related through a three term recurrence,
(A) a, P.(A) + (A) + (1 Pt- Following Remark 1, the optimal method is derived from this recurrence as
(7)
Ft++1 2t
(a+ 1)(xt 2z-1) 1) by V.V/ fax)).
(8)
4

---

Under review as a conference paper at ICLR 2022
3 METHODS
Being able to write the rates in terms of the expected spectral distribution ties the average-case framework to the field of random matriz theory. Indeed, because of results from this field, certain e.s.d's are considered more natural than others. Indeed, it can be shown that the same distribution arises when we take the gram matrix of random centered i.i.d. features with variance o²: the Marchenko Pastur distribution.
Definition 2 (MP distribution). The Marchenko Pastur distribution associated with the parameter and with scale o² is given by
1
V(* 1)(1 X-)
(pM = 2TO²
(9)
with A+ A+= = o2 VT) , A = = ma (1))))))
The Marchenko Pastur distribution parp can considered a natural first model for e.s.d's as it arises universally from matrices with i.idd. endries, mild low moment assumptions, there no specific distribution of the matrix to be considered. can be seen as a model for the white-noise in the data. When 1, i.e. n d, we have duMp & X -
Pedregosa Scieur (2020) first derived the optimal method w.r.t. РMP, and Paquette et al. (2020) derived Nesterov's rates under the distribution. As are concerned with being robust, a natural step is to consider the Beta weights.
Definition 3. The (generalized) Beta weights with parameters T, and scale are given by the (non-normaliied) pdf
de(A) (T A)T.
(10)
This family distribution generalizes the MP distribution, and both have similar concentra- tions near 0 when & ~ 1/22.
The optimal method w.r.t. a and objective is associated to a shifted Jacobi polynomial pa. with B = + 1,a = T. When a = 3 = -1/2, we retrieve the Chebyshev Method (Flanders & Shortley, 1950)- As such, name proposed methods the Generalized Chebyshev Method (GCM).
Algorithm GCM(a,
Inputs: Initial vector 2n, function f, smoothness parameter estimate L x- < 0, + 0
for I,...,T do
a: 2(
2( 214+)]64-04334)
4 + (2+00 [(t+1](++++++1
7t <- (t+k))(+-2)(
8, 4- ort710111
Dt Æt-1 (8:4 1)(1-11-1-1)) -
bebe V (x
We'll consider the Nesterov's method used Paquette el. al. (2020), which defined by the iterations:
Lt+1 = y: I ff(,))
(11)
t
M1+1 31+1 + 1+3 (2 xt)
(12)
re We also consider the Laguerre method, which is optimal w.r.t. du(x)) = M(+t)) taking a as a parameter. This method is proposed to optimize non-smooth functions. Both these methods generalizations of ones that have been proposed in Pedregosa. &

---

Under review as a conference paper at ICLR 2022
Scieur (2020). We show that Algorithm corresponded to polynomials P. and derive the Laguerre method in appendix B.
Remark 2. The Generalized Chebyshev takes the largest eigenvalue L as a parameter, but the rales we will show are robust to an overeslimation of L.
ROBUST AVERAGE-CASE RATES
We will state our assumption over the spectral distributions. Tt. effectively allows us to parametrize all of our distributions of interest in way that characterizes the asymptotic convergence, diving them into equivalence classes.
Assumption We will write Vr,g for continuous distribution supported in (0, LJ s.t. (x) 0 for x E [0, L), dv+, = @(x5) near and dvr.s (((L-)) near L.
Assumption quite nonrestrictive, in that, the spectral distribution of the Hessian for any smooth convex problem can be identified with some T. in this class. It is milder assumption than (1) assuming complete knowledge of the spectrum of the Hessian or (2) the specific distribution on the entries of your data. Moreover the assumption encompasses the frequently used MP (e.g. Martin & Mahoney (2021); Pennington Bahri (2017)) and Uniform distributions We note there's s need to consider eigenvalues situated at 0 as they do not contribute to the optimization process.
The & works measure of how close -1. Samples in finite dimension of distributions with high values of & will work as strongly convex functions in practice.
to the worst-case scenario, as it approaches
We show that Vr,& indeed bohaves like an equivalence class when considering the asymptotics of the convergence of the methods: only the concentrations the edge matter. We do this by singling out from each of these classes the beta distributions for which we can compute the rales, then show the rates to be the same inside Vr,g-
Theorem 2 (GCM average-case rates). A Generalized Chebyshev Method with parameters (ax, B) applied to a problem with e.s.d. as in Assumplion has average-cas rales
1-2
ifa < r + 1/2 and 3 < E 3/2
E[f(x;) f(x*)] L C
2(5 2) logt (max (a- - --,,---1)--
= and 8 = { 3/2
ifa 1/2 or { +
(13)
1-28
ifa < fa<<+1//> and $ (
f( L Ca.
t 215+3) log (mmax -B
if - 1/2 and 8 5/2
if + 1/2 3 > 5/2
(14)
where Cg.8 is distribution dependent constant.
Theorem 2, which is illustrated by fig. 2 shows that overest 3, and underestimating will still leave us with the optimal asymptotic rates, so a good rule of thumb for calibrating the algorithm is to use high 3 and low a.
Theorem shows that a proper choice of B can indoed make the Jacobi polynomial asymptotically optimal w.r.t. to any Vr.g-
Theorem 3 (Optimal Rates). Let v follow Assumption 1. The optimal asymptotic averuge- case rates for (x)) f(x))] and [[]l[(((,)))) are atfoined by the GCM with parameters (T, E + 2) and (T. E + 3), respectively, and read
(. f(x') 2(E-22)))
E f ((E-33))))
For the function value (1 = 1), we find rates that approach - as & - 1, showing the worst-case limit. (over the considered distribution) on the average-case.

---

Under review as a conference paper at ICLR 2022
3.0
5
2.5
Parameters (T, 5)
Method
2.0
3
( 2
2. 2
1.5
2
1.0
1
GCM(a 3.
21
6-
0.5
0
GCM(a 2.
0.0
Nesterov
logt
-0.5
-2
Gradient Descent
1
-1.0
-1
0
Figure 3 & Table 1: The figure illustrates the robustness of the Generalized Chebyshev Method with parameters (o, B) for fized problem corresponding (T= 5.6 - }) The color represents the exponent a of the average-case rate O(t") the method for different values of a and B. The white star represents the optimal tuning and the blue area the set of parameters for which the method converges. Note we have large of region that guarantee the same optimal asymptolic rate. The table compares the asymplotic average-case rales for the function-vale for different methods with different (7, E) values.
the Marchenko-Pastrn distribution
We remark that the above theorems imply that, at least asymptotically, the GCM is robust for suboptimal choice of parameter / up to 1/2 below the optimal choice and infinitely above.
For completeness, we also derive worst-casc rates for the GCM:
Proposition (GCM worst-casc rates). Let f be conver, L-smooth quadratic function. Then, for the Generalized Chebyshev Method with parameters (a, (), we have worst-case rules
(a)-8) 8)
if a > 8-1
f(x,) - ((x))
2- 20 a $ 8 -1
if
$
(15)
1-2
a a
821
((
if a> 8-2
[V]((x)) - f(x")11 S C²T.²
1-22
if
a 858-2 3
(16)
6-
a58-2 B 3/2
For a reasonable choice of a, 3, i.e. 32 theoretical lower bound of 2
21 a $
1
1. the function value achieves the
We now analyze the convergence of the Nesterov method. Nesterov (2003) has shown that matches up to a constant factor lower bound on the worst-case complexity non strongly convex problems. A natural question is if this performance would translate to good average-case rates. To do so, we will extend Paquette et al. (2020) proof for the Nesterov method rates under the MP distribution.
Theorem 4 (Nesterov average-case rates). Let as in Assumption 1. Then for the Nesterov method, we have average-case rates
2(E+2) 3 logt B[f(x))) [xx')] C.,,
i < -1/2
if -1/2 if > -1/2
|[[[V C2 (17)
1 (6+7/2)
The difference between the asymptotic average-case rates of Nesterov and the optimal ones are f-+1 when & + 1/2, log when + 1/2 and 0 otherwise. This shows that Nesterov is almost optimal when the concentrations near are relatively high, i.e low &
Theorem 5 (Gradient Descent average-case rates). Let v as in Assumption 1. Then for gradient descent
(lf( f(x=' ((+)))
E B/ ((+-3))))
(18)
7

---

Under review as a conference paper at ICLR 2022
CIFAR
MNIST
R11 II
300
10-
104
12/1000
022
10
Figure 4: Above: Empiriaal spectrum for the covariance matrix of the features. Below: Gradient norms throughout iterations. Left: CIFAR-IO Inception features Right: MNIST features. Here we choose to compare gradient norms as the minimum function value is not known. The properly tuned GCM achieves remarkable performance under these nyn-synthetic spectrum's.
Observe for the function value that the rate for Nesterov is t-2 and the rate for Gradient Descent t-1 when -1.
Lastly, consider the optimal rates for Gamma distribution.
Theorem 6 (Laguerre method rates). Let a > -1 and Pas a > -1 be a Gamma distribution, Lee. (x)) x"e g= The optimal rales are given by the Laguerre method of appropriate luning and M[++1].
(()(x)) - f(xx) ((1
(19)
Note that this result does not have the same universality as the others because of the non-compacity of the distribution's support. These rales are contrasted the worst-case lower bound on the optimization of non-smooth functions by first-order methods, which gives
f(xx) f(x") f(x))
VE
These rates are not found when a + 11 indicating that the worst-case is especially pessimistic in this scenario.
Remark All of the expected rates we state are almost deterministic on the high dimensionnl setting per the concentration results shown in Paquette et al. (2020)
5 EXPERIMENTS
We simulate the e.s.d's 's in two ways. The Marchenko Pastur distribution, which we sample by taking H = xxx where X has i..d. gaussian samples. This enables us to simulate (r,E) values of (1/2, 1/2). Other values of (r.{) are simulated by sampling A E Rd from the corresponding Beta distribution and taking H U diag(A)U", where U is an independently sampled orthonormal matrix.
We let. x=
and sample 2o from centered Gaussian distribution, the dynamics are the same as in the general case. In all experiments use the problem's instance largest eigenvalue to calibrate each method (e.g. Gradient Descent's stepsize is I/L). Our theoretical rates in Theorem 5 and Theorem 4 respectively for the Nesterov method and Gradient Descent are procise under the approximate range -1 < & < as we show Figure 6. Distributions with higher & need many samples otherwise they behave strongly convex functions.
The same is not true for the Generalized Chebyshev Method. < 3* or E is low the empirical findings diverge from the theoretical. We believe this is due to numerical instability
8

---

Under review as a conference paper at ICLR 2022
10a
10'
[[ [(a)]
10
10-1
f(x)
10-14
10-5
GOML
10
10-7
Nederoo
10
10
10a
Figure Rates for synthetic problem, simulating the Marchenko Pastur distribution. Note that both tunings of the GCM achieve performance in function value very close to the one of Conjugate Gradient, which optimal for every draw of the problem.
under these regimes the metrics also have much larger variance than in the other regimes. We've not been able though to pinpoint the exact source of this supposed instability. This is shown in appendix D)
The GCM with 3 >> 3r performs corresponding to the theory, and it's non-asymptotically very close to the performance of 3*. High values of also perform very well on non-synthetic data, suggesting in practice we should use these values.
Nesterov
Gradient Descent
10a
10a
10
E- -3.9
10-
10-2
[=000
Theomiica
10
Regress Asssym
10
10
10a
10a
100
10a
10a
10a
Chebyshev
102
10"
10
10
10
5-601
E.50
10-6
Crestial
Asyrpp
10-10
10a
10a
10a
10a
Figure 6: Comparison between experiments run synthetic Beta distribution and theoretical asymptotic. Y-axis the function value
CONCLUSION AND FURTHER WORK
In this paper, we've 'vve established that the assymptotic convergence of first order methods on quadratic problems in the convex regime depend on the concentration of the Hessian's cigenvalue near the edges of the spectrum's 's support We further contributed to the theoretic understanding of the Nesterov's method performance and established the contrast between the worst-case and average-case in the main regimes considered in Optimization.

---

Under review as a conference paper at ICLR 2022
BIBLIOGRAPHY
Andrej Bogdanov and Luca Trevisan. Averago-case complexity. arXw preprint cs/ es/0606097, 2006.
Bernd Fischer. Polynomial based iteration methods for symmetric linear systems. SIAM, 1996.
Donald A Flanders and George Shortley. Numerical determination of fundamental modes. Journal of Applied Physics, 21(12):1326-13 1032, 1950.
Magmus Rudolph Hestenes, Eduard Stiefel, al. Methods of conjugate gradients for solving linear systems, volume 49. NBS Washington, DC, 1952.
Francisco Marcellán and Renato Alvarez-Nodarse. On the "favard theorem" and its extensions. 254, 2001.
Journal of computational and applied mathematics,
Charles H Martin and Michael W Mahoney. Implicit seffrregularization in doep neural networks: Evidence from random matrix theory and implications for learning. Journal of Machine Learning Research, 22(165):1 73, 2021.
Yurii Nesterov. Introductory lectures on conver optimization: A basic course, volume 87.
Springer Science & Business Media, 2003.
Courtney Paquette, Bart van Merriënboer, Elliot Paquette, and Fabian Pedregosa. Halting time is predictable for large models: A universality property and average-case analysis. arXi preprint Xrx::20006. 201:22006.0429, 2020.
Fabian Pedregosa and Damien Scieur. Acceleration through spectral density estimation. In International Conference Machine Learning, pp. 7553 7562. PMLR, 2020.
Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In International Conference on Machine Learning, pp. 2798 2806. PMLR, 2017.
B.T. Polyak. Some methods of speeding up the convergence of itcration methods. USSR Computational Mathematics and Mathematical Physics, 04, 1964.
Damien Scieur and Fabian Pedregosa. Universal average-case optimality of polyak momentum. ar preprint Kki::2002.04664 2020.
Gabor Szegö. Orthogonal polynomials, vol. 23. American Mathematical Society Colloquium Publications, 1975.
Walter Van Assche. Weak convergence of orthogonal polynomials, Indagationes Mathematicae, 6(1):7-23, 1995.
10

---

Under review as a conference paper at ICLR 2022
A PROOFS OF SECTION 2
Theorem 1. Let wa be generated by first-order method associated to the polynomial Pe, the measure the e.s.d. of H, and El((o - x² (xo x²)² R&I I for some constant R. Then we can write the convergence metrics at time step t
E|||, - 201 R² / (P(())d(A))
B[f(x+) - f(x')|= R² P((A)adp(A)
(5)
and
B = n22 PP(A)APu(A))
Proof. We remark that by the definition of the expected spectral distribution of H, we have for continuous g
(r]g((r(HH)) ((A))
((A)))(())
(20)
We know that x² = P x²). We can write || - x=11 in terms of trace and use the independence of H and 2g xx to connect it to the e.s.d.:
E||a, - x x=1 = Eitr((z0 - x xx ( - x=))]
(21)
EH 20 x [tr (Pi H
( (20 x²)²1
(22)
[P
E 20 - [ x²')x")) (at x= x²)²
(23)
RR (2r H)
R² P,(A)² du(A)
(24)
For the gradient and function value the reasoning is the same by noticing that
B[f(x: f(xx)] E[[r(((00 P(H))) x" x²))]
(25)
[Ex(()))((T((H)))
(26)
where XPc is also a polynomial. As vf(xx) = H(x - -.).
B[V E[(r((a00
xx') x²)))
(27)
=E
(28)
Proposition 2 ((Pedregosa & Scieur, 2020)). Let P! be defined as
pf = arg mi /
P((A))
(6)
Then (P!) the family of residual orthogonal polynomials w.r.t. X+1
Proof. We differentiate the expression for the metrics w.r.t. to the coefficients of the polynomials:
d. (JNP(S)dUCN) day
= /
d (aNtRCA) du(A) =
dax K
=2 =2*(AANRR(NNCN)) =0
This means that P((A) is orthogonal to any polynomial of degree t w.r.t to the intern product (.--)x44dd
11

---

Under review as a conference paper at ICLR 2022
B GCM AND LAGUERRE METHOD DERIVATION
We will first state two lemmas that allow to construct the optimal polynomials. With them in hand the procodure is trivial.
Lemma 7. Let (Pi) be family polynomials following
Pa(A) (ar + P.))P:-1)A) TePo-(()),
with Po a constant polynomial and P. + 0, Vt. Then
P(()) = (a, + by P(- + (1 (22
(29)
is the recurrence for P((A) Pc(A)/ P:()). With:
0₂ 8:00
(30)
b. 6r,3t
(31)
6 (ar + r1
(ō0 = 0)
(32)
The proof of this is presented in Pedregosa & Scieur (2020). Further, we know how to compute the recurrence for the polynomials of shifted distribution:
Lemma 8. Let (Pt) be family polynomials orthogonal w.r.t following
Pa(A) (ar + 3,A)Pt- + +
(33)
and define polymomials P, s.l.
(=(m(A))= P:(A),
with m(A) aA + b non singular affine transform. Then Pt follows recurrence like in eg.
(33), with:
df at b,3c
(34)
3 aB8
(35)
(36)
The lemma is self-evident by considering eq. (33) with argument m m=)(A)
These results
enough to get the recurrence relation for the residual polynomial w.r.t x IL - =x)a. We begin by the standard Jacobi polynomials, which are orthogonal w.r.t
- x1=)((1+++ x) and follow recurrence according to at, Ya below Szegö (1975):
ar (2n + (2n 8
(37)
2n(n+a+
(a² - (2n
3. 2n(n + a (2
(38)
- a
76 2n(n+ aa 2-
(39)
We then shift the distribution according nTxx,, and then transform the residual ones. We slightly simplify these computations and use remark 1 to get Algorithm 1.
We know (Szegö, 1975) that the Laguerre polynomials LT, with usual normalization, follow the recurrence
(A) = 21 a
t 12) (A)
1 a (A)
(40)
t
As we don't have to shift the domains, we have only to apply lemma 7 to get the Laguerre method. method,Purther, get explicit expression for d, o simplifying the expression.
12

---

Under review as a conference paper at ICLR 2022
Algorithm 2: Laguerro(a)
Inputs: Initial vector 2o, function f
æ-1 f-
for t = I,..., T do
2t + 2t-1 + [-1
( x2-2) zta
1 Vf(xz-1)
ita
C PROOFS OF SECTION 3
In the following will consider shifted versions of the spectral distributions. This shift is writlen as an alfine transform m()): [0, LJ > [-1,1] because most results in the theory of orthogonal polynomials are stated in terms of distributions supported in [-1,1].
This can be seen as an additional layer of abstraction because the quantities evaluated with
the shifted distributions and polynomials are proportional, i.e. if P.(x) Pt(m(x)) and (((x) (mm(x))):
J (((s))'(s)dd x (f))))
(41)
So all the asymptotics are the same. The Jacobi polynomials Pp are those orthogonal w.r.t
dp(x) = (1 - x)) + x) Most works use the normalization Par. (-1) = (-1)² (++²). We will write pa. for this normalization and pa.. for the residual polynomials
Theorem 2 (GCM averago-caso rates). Generalized Chebyshev Method with parameters (a, 3) applied to a problem with e.s.d. as in Assumption has average-cass case rates
-1
if < 1/2 and 3 < < 3/2
B[f(m)) [x=')] ~ L C%.0
2(5 2) logt (o 8--
ifa = 1/2 and B = - 3/2 ifa> T + 1/2 or $ { 3/2
(13)
1-28
f and 8 < +
[[[[)(=>)11)) ~ I22 -2,
2(5+3) log (a
and 8 = f
ffa>++1/2 or 8> 5/2
(14)
where C is distribution dependent constant.
Proof. We will prove that for any a and 8, E, > -1, 1> 0 and v following Assumption 1, we have
1-29 29
if < T 1/2 and < if = = and 8 5 if fa>>+1122 or 8>
I pr (o L'
2(++1) logt 2(max((---7,-6
We will first show this result for the Beta weights, then show that distributions with the same concentration behave similarly.
The normalization of pa.3 is s.t.[ Szegö (1975) (4.3.))):
{ p. (1))) dr= 2n an+a+++11
20+B+1
I(n + () + (n -B+11 O(t=l) (42)
() + + 1)+1)
Further, the residual polynomials are s.t. 1
) from the definition of the
classical normalization. We state the result. (Exercise 91, Generalisation of 7.34.1) from Szegö (1975):
13

---

Under review as a conference paper at ICLR 2022
Lemma 9. We have
! (1 T (x) ((11))
(43)
f( ifa>
1G t- logt 1
(44)
1
Noting that Pa.0 (-1)t (-x), can write:
[ P = (S.
(f. ()) (x) (w)) +0 (f( pp (x)
(45)
We can then show our result for du, ( = - x)a by carefully considering each of the cases on Lemma 9 and the maximum of each term in eq. 45, and an added 2-23 from the different normalization. With this, we have the wanted result for the Beta weights It remains to show:
Le (x) (e))))))))))))) ( (x)
(46)
And the rest follows from the same arguments. We do this with the help of this lemma shown in Van Assche (1995) relating the weak convergence of the orthogonal polynomials:
Lemma 10. Let μ be measure and (pt) it's family of orthonormal polynomials s.t. Pe follow the recurence:
xp)(2) (xP:+1(x) bepr(x) + at at- (x)
and a, be converge respectively to b. Then for any f continuous and bounded:
/ [ + π [ f(x) dr
(47)
v1 x2
Let c s.t.
x x2 1 |dv,, A(1 2)1 S B(1 - x)
(48)
dur is bounded. We observe that for 0 < x < 1-66 e, f(x) (1+x) We get from application of 10, and the observation that pa.. Nip. a.9 (/2-)/
with Ag.
[ (1 x) pa. (x)² dr
1- (1 (1-x)*
x) P. p. (x)) dx + J1-
[ (1 x)" p. (x:) (49)
@(hp)
0(1-1)
{" (1 - x)" pa. (x)=
(50)
1--
L' pan (x)2 ddrg(r)=
pa.3 (x) (()) dx)
8( 1)
(51)
θ
)²) pa. (2))² (x)) dr
(b1
14

---

Under review as a conference paper at ICLR 2022
Theorem 3 (Optimal Rates). Let follow Assumption 1. The optimal asymptotic average- case rates for (x) f(x")] and (z)Vl are ottained by the GCM with parameters ( and (T, + 3), respectively, and read
(x)( f(x" = Ot -(t 2()+))))
[ = Ot
f ++++1 (i.e., are optimal), the Proof. We will prove that for T, > 1 Ifa= and $ = rate of convergence reads
P((ANNMMA)))) - ( P((0)=1
min
O(t - (()-(()+
(52)
Showing the second equality is easy by considering theorem 2, and that is further the minimum asymptotic rate for the Beta distribution jr.g-
By setting Pt and PV" = Pi (0] the optimal orthonormal and residual and polynomials w.r.t.
show that P must have the same rate on fr, it does on v, thus the optimal rate of v cannot be lower than the optimal rate of jr,. Indeed, setting é1, 62 as in eq. 48:
(0) J 1-22
(z))
Pr ()(x))dpT.((x))
(53)
1-62
1ta
(L
Ita
(x) = =
Pl
(54)
(x) (
Pe (x)
=
(55)
Pe (-1)
1+c
(56)
Where the first two equations come from the fact that ((U+,) near and and the third from lemma 10.
This effectively upper bounds the rates on v because the rates of Pe on pr, can't lower than 2( + + 1).
O
Proposition 3 (GCM worst-case rates). Let J be a conver, L-smooth quadralic funclion. Then, for the Generalized Chebyshev Method with parameters (a, B), we have worst-case rotes
((0-0) -1-23
if a > B
f(x1) - f(x)) S SCL
if
a S 3- -
3
(15)
2-
a as
82
(a
if a> 3-2 2 a aSB-2 B < 3/2
[V)()z)) - f(x")) s COL2
1-1
(16)
t-
as -
B 2 3/2
Proof. rates] We will prove that: sup=e 2' pa. (x) O(L').(....)).
Where:
2(a - B)
if a> 8-1
vaa, B,1,
-1 23,
if
a 8 351 321
(57)
-21,
if a a
From Szegö (1975), Theorem 7.32.2, < ;
((t-1/2) (
if a a< if a >
p. (cos 0)
2: a
ct
(58)
0 1-2-1/20(t11)
if 2
1, at
We observe that, from the symmetry of the Jacobi polynomials:
sup a' pm (x)² = Q max sup p =E[o.1]
(z) sup (1 - x) > (z)) P()
(59)
zE|o.1]
The (1- - 2 term, corresponds to sin ())) in the variable 6, which is O(82)). The rest follows from carefully considering the expressions given by eq. 58.
15

---

Under review as a conference paper at ICLR 2022
Theorem 4 (Nesterov average-case rates). Let as in Assumption 1. Then for the Nesterow method, we have average-case rates
2-((+2)
if -1/2
(
logt if -1/2
/
C22 C220 (5 (17)
1 (6+7/2)
i -1/2
Proof. We will prove:
1 2(6+1)
if < if = 1/2
S. P.Nes (2)2X (2)2) durg-I Cf t 3 logt
(60)
(6+5/22
if > 1/2
Paquette et al. (2020) has shown that the nesterov polynomials Pe are asymplotically, in t:
P.(A) 2J1(tVaX) ax)
20//2
(61)
tax
In the sense that:
S.'v (P(()) 4JZ(1V ut lu
4dump(() = ((--(142/112))
(62)
The arguments can be casily used to show that such an integral is O O(t-(a+4+31/12) when evaluated wrt general du s.t μ' = ((x)) near 0.
We can thus consider our integral of interest substituting pNes by it's Bessel asymptotic
and dividing it into three regions, ie. [0. 1] = [o, U l I corresponding to two
different regimes for the Bessel function. The first region will give us the asymptotic and the others we will bound.
We consider first, for some >> 0:
(t](tv/)) uc
c e- ut du
(63)
2u
We note the asymptotic for J7:
ff(Vt))
(1 cos(2/te + 2n))
(64)
π T
Doing the change of variable u tu, and identifying the upper limit of the interval, which is ct 1/2 to co:
Vi c
4.7((vu)) du A 1-2- {
of-1
((tv)ee
de
(65)
Bu
2- 100
25-1 1 _ - de
0
(66)
TVto
= 1i-
c de
(67)
π bv
T(E-2.e)
Where the cosinus term goes to 0 from the Riemann-Lebesgue lemma and T is the incomplete Gamma function.
The term corresponding to the interval [et-1/2, is exponentially small. Indeed, because of the exponential e- it is Oce-rvt). This shows that the integral concentrates in region that is closer and closer to 0 and that only the behaviour of the distribution near 0 malters. We have for the [0, {] region, doing the change of variables
Pu:
(J t2 e at du θ ( (1-21551)
(1-2166))
1dh PiVD) 88
e de
(68)
16

---

Under review as a conference paper at ICLR 2022
And the e is (1). We have the following Bessel asymptotics:
[((v))
w 0
(69)
4'
J((v)) O00
0 00000
(70)
So divide this integral aswell:
2-221))) fdh ue (((vV) c du = (-2((tt)) f y dv) = ) (I((())
(71)
1 1-2(6t1) S wy Ji(V du (22(6)1) [ 1
=6 (1226)11))
(72)
Where 1t(t) = logt i 1 and 1 otherwise. The nesterov rate is then Ig Et 3 if g 2 and t 2 if <<<
Theorem 5 (Gradient Descent average-case rates). Let v as in Assumption 1. Then for
gradient descent
[l)()))) - 0(((((2))
B B = -((()))))))(((())))))))))))))))) (E-
(18)
Proof. Considering that ((nD()) = =(1 (1 2² we will prove
L (1-
(1- x)
d= - 0(t-(5+++))
(73)
We know, for the Beta weights, that:
[. (11- (1 aP = T( + +T+
T(2r + O(1 ((-(6)))))
(74)
We can indentify this asymptotic to the interval f for any because:
a=== [( (1 0 - 2)
(75)
Then:
S: (1 (1-x)21X dus.duug--- 0(11 2
(76)
|0(1- 1)2CX (1(1-))2'' d θ (//0 (1 11(1- 2220t NSHL du) ((t-(4+++))
(77)
Thcorem (Laguerre mothod rates). Let a > -1 and Has a > -1 be a Gamma distribution, i.e. dua(22 (z) F(a+13' The optimal rates given by the Laguerre method of appropriate
luning and
B[f(x,) - f(x*)] (a+2)).
(19)
Proof. Let Le be the Laguerre polynonials with the usual normalization Szegö (1975):
/ L(())duaax))= = L7 n2 + a
(78)
We further now [Szegö (1975) (5.1.13)]J:
Σ -)(=)= 0=0
(79)
17

---

Under review as a conference paper at ICLR 2022
Thus, letting Pt be the residual laguerre polynomial, consider:
22 tt (++++))
/
Blf(2))) - [[x01] =
Li L
t
t (t+a+2
Σ
Li aa+1 (x)dd(())a+(())
k=0
(80)
1 a 2
h + (itatt)
(++a+2) - 2
)
k=0
( (+ a 2
= O (tt (a+2))
D ADDITIONAL EXPERIMENTS
{=
10a
104
10a
10
10"
10-2
10
10-3
10
10-3
10-1
20
60
80
100
120
140
0
20
00
100
120
140
Figure 7: Empirical Theoretical function-value performance for GCM(a", ,8)) Red lines are given by numerical integration, shades are minimum and maximum values under 10 runs and the blue line is the mean
9=1.50
A 0.500
10
10
10
10a3
Figure 8: Empiriaal vs Theoretical function-value performance under Marchenko Pastur distribution. Red lines given by numerical integration,shade minimum and maximum values under 10 runs and the blue line the mcan
We note that in the regimes where the empirical average performance doesn't match the thcoretical one, we can still find samples problems who do match. This and the much larger variance the function-value, this discrepancy is due to numerical unstability in these regimes.
18


Reviews:
[{"review_id": "rDWi_rWWwUa", "reviewer": "Reviewer_KTu2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "-- Strengths:\n- The paper is very well written. The problem and the results are stated clearly.\n- The average case convergence rate for a large class of quadratic problems is established for GCM and Nestrov method and further it is shown that GCM with appropriate parameters is optimal.\n\n-- Weaknesses:\n- The main concern I have is that the setting considered is rather limited. Being limited to quadratic problems, though encountered frequently in practice, is very restrictive. \n- The paper only talks about convergence rate of expected loss, expected distance to the optimal point and so on. It would be interesting to see if something can be said about the variance of these quantities as well. Referring to the motivating example of the paper, the Quicksort algorithm, we know that the average case complexity is $O(n\\log n)$ but we also know that the complexity concentrates around its mean, i.e. with high probability it terminates with a complexity close to the average. In the absence of such high-probability bounds, knowledge of the variance might be the next best thing and it could give us an idea of how close to the mean we expect these values to be. It would be interesting to consider this in the future.\n\n-- Minor Comments/Typos:\n- Even though it is clearly stated in the Contributions Section, when I read the paper it was not clear to me at first that Algorithm 1 is a contribution of the paper. It would be helpful to make the contributions clear throughout the text.\n- How does definition 3 generalize the Marchenko-Pastur distribution? The MP has three terms whereas the Beta only has two. Please explain.\n- The numbering of Theorems is not consistent. E.g. we have Theorem 2.1 or Proposition 2.1 but then later the numbering format changes to Theorem 3, etc. \n- Page 1, Introduction, 3rd paragraph: infinite -> infinity.\n- Page 2, paragraph before Section 1.2: $e^{\\lambda}$ -> $e^{-\\lambda}$\n- Page 4, Remark 1: the abbreviation for first order method (F.O.M.) is not defined before being used.\n", "summary_of_the_paper": "The paper considers the problem of average convergence rate of first order methods on a given ensemble of quadratic problems. The authors propose the Generalized Chebyshev Method (GCM) and show that it is optimal when the e.s.d. is beta distribution. They also show that so long as we know the behavior of e.s.d. near the edges of its support, GCM still achieves the optimal rate. The authors finally consider the Nestrov method and derive its asymptotic average-case convergence rate.", "summary_of_the_review": "The paper analyzes average case convergence rate of first order methods on quadratic problems and establishes very interesting results for different e.s.d.'s and knowledge of the e.s.d. only around the edges of the support. The main concern is the limited application of the results as only quadratic problems are considered. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "htkatiMAnfM", "reviewer": "Reviewer_VZRV", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper is a follow-up work of the two articles by Paquette et al., 2020 and Pedregosa & Scieur, 2020. \n\nI feel that the authors tend to oversell their work. For example, the authors claim to have \"a complete analysis of average-case convergence in non-strongly convex problems.\" I think the results require restrictive conditions such as Assumption 1 and an asymptotical view. \n\nIn particular, I wonder why the authors claim to have \"established that the asymptotic convergence of first-order methods on quadratic problems in the convex regime...\" Is there a clear correspondence between conditions like Assumption 1 and the convex regimes?\n\nThe paper also stated that the methods and their guarantees are more practical. I feel that asymptotic guarantees are rarely helpful for high-dimensional problems in practice. Also, I wonder how the authors are going to estimate the characteristic values in Assumption 1? \n\nFinally, I don't understand how the authors show that the rates presented in those theorems are optimal. For example, could the authors please explain to me why Theorem 4 gives optimal rates? Its proof in the appendix is relatively brief and presents a list of claims. The only justification for these claims, like equations 50, 51, 52, and 53, seem to be the phrase \"we argue.\"", "summary_of_the_paper": "The paper analyzes average convergence rates of random quadratic optimization problems. The authors attempt to characterize the rates via the expected spectral distribution (e.s.d) of the random matrix (objective's Hessian) and show that the proposed algorithms work well asyptotically. ", "summary_of_the_review": "Overall, I don't find the paper very exciting as a follow-up work of some recent publications. The results' proofs seem to be oversimplified. And the convergence rates are only in the asymptotic sense. The assumptions also make the paper a mismatch for several of the authors' optimality and universality claims.   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "P9IMwZkNfkb", "reviewer": "Reviewer_poH2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The main strength of the paper is to go beyond Pedregosa/Scieur and consider the case where the limiting spectral measure is not assumed fully known. I agree with the authors that tail-type assumptions like the ones they make are more reasonable in practice. Moreover, they provide results that relate the parameters used to define the method to the convergence rates, and allow for comparisons. \n\nThere are three main weaknesses to the paper. One is that there is no significant new theory developed; all results essentially follow the same proof ideas as Pedregosa/Scieur. The second is that the paper is not at all impressive in terms of experiments, which would have helped because the theory is not that surprising. The third weakness is that the writing is unclear at at least two important points (1 and 2 below). The ideas in those places seem incorrect or contradictory. I'd still like to see these points better explained.\n\n-- Major issues --\n\n(1) It is nice that the authors give a full analysis of their \"generalized Chebyshev method\" under their e.s.d. assumption. However, I would have thought that the rate-optimal way to choose $\\alpha,\\beta$ would be the one given in the paragraph starting with \"The optimal method w.r.t....\" in page 5. This would align with the fact that orthogonal polynomials are optimal. However, it does not seem to be the case. What did I not understand?\n\n(2) It is never true that a discrete spectral distribution equals a Beta, a Laguerre law, or satisfies Assumption 1. It seems to me that you need all of these to work asymptotically, but this is not mentioned in the paper. Given this, I am not sure of how exactly the proofs should be carried over: there may be difficulties with the recursion, maybe? \n\n-- Minor issues --\n\nThe use of QuickSort in the introduction as an example of average-case analysis is a bit unfortunate, as it is completely unrelated to the paper at hand. Perhaps there's no need to give an example at that point.\n\nPage 5, \" \"The optimal method w.r.t....\" -- why do you speak of a metric $l$?\n\nPage 5 again: can you give examples of random matrices with beta-shaped spectral distribution?\n\nAppendix, section B: some details/pointers on Jacobi polynomials and their recorrence would be welcome. Also, \"jacobi\" is not capitalized at least in one instance.\n\n", "summary_of_the_paper": "-- EDIT: I have updated my scores in response to clarifications --\n\nThe problem of optimizing a convex quadratic function via first order methods is considered. This is a well-understood problem from the worst case point of view, and its complexity will depend on the largest and smallest eigenvalues of the associated Hessian matrix. However, a nice recent average-case analysis by Pedrogosa and Scieur gives the following result: if the spectral density of the Hessian converges to a \"nice\" probability measure (such as the Manchenko-Pastur law), then first-order methods that are tailored to this density may converge faster. In fact, such methods can be obtained from the three-term recurrence for the orthogonal polynomials of the measure.\n\nThe present manuscript follows up on the Pedregosa/Scieur, but departs from in two specific ways. Firstly, it considers the case where the limiting spectral law is a beta distribution, and derives the corresponding iteration. Secondly, the authors analyze the performance of this iteration under \"mispecification\": that is, they allow for more general spectral measures than the beta, and only specify how these measures behave near the extremes. In spite of this, they are able to derive bounds of the same order as in the beta case. \n\nA few other theoretical results are presented: worst-case rates for the method derived from the beta distribution; an analysis of Nesterov's method under conditions on the tail of the spectral measure, and a result on Laguerre spectral measures. These results generalize other theorems obtained in the Pedregosa/Scieur paper. The theory is complemented by a small numerical study.\n\n", "summary_of_the_review": "The contributions of the paper are probably correct. However, the mathematical contribution is too closely tied to previous work. Moreover, the experimental contribution is not significant. Finally, there are the writing/correctness issues mentioned above. When put together, these observations justify my low score for this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A8UXp9_vW3c", "reviewer": "Reviewer_Tq5M", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper seems to be a direct following paper of the two papers by Pedregosa and Scieur and the main technical difficulty is in the calculus part in the appendix. I don't consider this to be something very novel.\n\nMinor problem: The definition of Marchenko Pastur distribution does not mention the point measure at 0. I guess it is because this point measure probably won't affect any rate derived in this paper because it gives an integral of 0. The authors can add some explanations to make this clear.\n\nIn Figure 6 and 7 in the appendix, there is no explanation for the blue line.", "summary_of_the_paper": "This paper is a theoretical work concerning the convergence rate of random quadratic optimization problems. The authors provide a detailed analysis of the relation between convergence rate and ESD of the Hessian.", "summary_of_the_review": "The paper is well-written and everything is explained clearly. But I don't think the paper contains enough technical and empirical novelty.\n\nI consider this paper to be marginally below the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the average convergence rate for first order methods on random quadratic optimization problems. Specifically it is a follow-up to work of Pedregosa and Scieur. They study the expected spectral distribution (e.s.d.) of the objective's Hessian and show asymptotic guarantees that work under some assumptions. In comparison to Pedregosa and Scieur, the main takeaway is that you only need to know the distribution at the edges as opposed to the entire spectrum in order to get the same improved convergence. However some reviewers felt that the contributions were oversold, and for example that Assumption 1 is quite restrictive.
Decision: Reject