Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
main_review: The paper is a follow-up work of the two articles by Paquette et al., 2020 and Pedregosa & Scieur, 2020. 

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

In 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?

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

Finally, 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: -- Strengths:
- The paper is very well written. The problem and the results are stated clearly.
- 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.

-- Weaknesses:
- 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. 
- 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.

-- Minor Comments/Typos:
- 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.
- How does definition 3 generalize the Marchenko-Pastur distribution? The MP has three terms whereas the Beta only has two. Please explain.
- 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. 
- Page 1, Introduction, 3rd paragraph: infinite -> infinity.
- Page 2, paragraph before Section 1.2: $e^{\lambda}$ -> $e^{-\lambda}$
- Page 4, Remark 1: the abbreviation for first order method (F.O.M.) is not defined before being used.

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: -- EDIT: I have updated my scores in response to clarifications --

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

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

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


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. 

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

-- Major issues --

(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?

(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? 

-- Minor issues --

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

Page 5, " "The optimal method w.r.t...." -- why do you speak of a metric $l$?

Page 5 again: can you give examples of random matrices with beta-shaped spectral distribution?

Appendix, section B: some details/pointers on Jacobi polynomials and their recorrence would be welcome. Also, "jacobi" is not capitalized at least in one instance.


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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

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

In Figure 6 and 7 in the appendix, there is no explanation for the blue line.
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.

I consider this paper to be marginally below the acceptance threshold.
review_title: null

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