Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work derives a new lower bound for the class of first-order methods applied to minimize $L$-smooth functions satisfying the Polyak-Łojasiewicz condition with parameter $\mu$. In particular, the authors derive $\Omega\left(\left(\frac{L}{\mu}\right)^{1 - \alpha}\right)$ lower bound for finding $\varepsilon$-solution (for small enough $\varepsilon$ and large enough dimension of the problem that depends on $\alpha$). This closes a long-standing open question about the optimality of Gradient Descent for this class of problem.
strength_and_weaknesses: ## Strengths

1. **Long-standing open question is resolved.** The contribution of the paper is fundamental: the question about the lower bounds for smooth PL functions has been open for a long time. PL condition gained a lot of interest in the optimization and ML communities during the recent few years, but the question remained open. This indicates the non-triviality of the derived result. 

2. **Elegant worst-case example.** I find the constructed "worst-case" function quite elegant: it is a sum of Nesterov's "worst function in the world" function and piece-wise quadratic function (along each component). The first part is standard and provides nice properties such as zero-chain property, which is the key property of literally all existing lower bounds. The second part is non-standard and makes the problem non-convex but not too much, i.e., PL-condition holds. Therefore, the proposed worst-case function is very intuitive and quite simple. I believe that providing simple solutions (especially for old problems like the one that this work addresses) is highly valuable for the community.

## Weaknesses

1. **Inaccuracies and gaps in the proofs.** Unfortunately, the proofs are hard to read due to multiple inaccuracies and gaps. Most of these issues can be fixed (I have double-checked), but a few of them are not obvious to me (though I did not try to think about them too long -- this is the authors' responsibility to make the proofs as clear as possible). See them in the list of comments.

2. **Issues with English.** Some sentences end abruptly and some parts of the text are not polished well (especially in the proofs; because of that some parts are hard to comprehend). I provide some comments related to this issue. I suggest the authors make a thorough pass through the paper and correct all issues with English.

## Detailed comments

1. **Numerical experiment request.** The main result of this work is more than sufficient for publishing at top optimization/ML conference/journal (if the inaccuracies mentioned below are not fatal mistakes). However, I am curious to see how accelerated methods like Nesterov's one or momentum methods like the Heavy-ball method of Polyak behave on the constructed worst-case smooth PL function. It would be great to see the comparison of these methods with GD and with the theoretical lower bound for different dimensionalities of the problem.

2. "The PL condition may be originally introduced by Polyak": if I am not mistaken it was introduced by Polyak and Łojasiewicz independently.

3. "any $\hat \mu$-strongly convex function that admits": this sentence is a bit confusing because during the first reading one can think that the authors mean a particular subset of strongly convex functions. However, after this sentence, they provide a definition of differentiable strongly convex function. To prevent confusion, I suggest removing "that admits" (or replacing it by ", which by definition satisfies").

4. **Discussion about $\alpha, T, c$.** I believe that this discussion should be added somewhere in the text. In particular, $\alpha$ can be chosen arbitrarily small. However, in this case, $c$ has to be also small. This implies that $T$ should be large enough (according to (31) and (32)). In particular, $T \to \infty$ when $\alpha \to 0$. Therefore, the dimensionality of the worst-case example depends on $\alpha$. I believe, the paper will benefit from such kind of discussion.

5. Section 2 requires proofreading in terms of English: some sentences end abruptly.

6. The fonts in Figure 1 are too small. The authors should increase the fonts and also add markers to the curves (to make the plots easier to comprehend).

7. Formula (14) appears between two sentences. It should be a part of a sentence, e.g., "Next, we define $v_{T,c}$ as follows:"

8. Formula (14), the first row (condition on $x$), the second row (last term), the third row (the last term): one should add $\frac{1}{32}$ in front of $T^{-c}$.

9. Formula (19): what is the role of $D$? This parameter is never introduced.

10. Page 7, "for any $0 < a < 1$": one should also add that $\frac{a}{6(a-1)} < 0.01$ (otherwise the the condition on $c$ from Theorem 2 does not hold).

11. Proof sketch of Lemma 1: I think, this proof sketch does not improve the understanding of the proof. I believe it would be better to provide just the full proof of Lemma 1: for me it was easier to check the full proof than to parse the sketch.

12. Pages 8-9: "the smooth constant" --> "the smoothness constant"

13. Lemma 2, page 11: it is worth saying in the statement of the lemma that $T^{c} \geq \frac{1}{2}\sigma^{-1}$ and $\sigma < 1$.

14. Formula (43): the union is over $k$, not over $i$

15. Page 12, "Lemma 3 then follows from Proposition 2 in Carmon et al. (2020)": I guess one needs Proposition 1 to get the result. Moreover, it is formally about the slightly larger class of methods (so-called zero-respecting algorithms). As Carmon et al. (2020) write, this class is strictly larger than the class of the linear-span methods. However, the proof of Lemma 2 is valid even for zero-respecting algorithms, so, one can replace everywhere in the text "linear-span methods" by "zero-respecting methods" (and introduce zero-respecting methods instead of the linear-span ones).

16. Formula (48): $E_{T,T}$ is not defined. I guess it is $T\times T$ matrix having zero elements everywhere except the element $(T,T)$ that is equal to $1$.

17. After (49): I guess $e^{(i)}$ is a column of $I$, not a row (to have the right size).

18. After (50): one should exclude $k = 0$.

19. After (52), "From $x_k = \max |x_i|$": this sound a bit informal. Better to change to: "For $k$ such that $x_k = \max |x_i|$..."

20. Formula (53): in the fourth step one can get $\frac{1}{32}$ instead of $\frac{1}{64}$. Also the constant in the end should be different since $A + \sigma I \preceq (4+\sigma) I$ (see my comment 31).

21. Above (57): why $x_1$ cannot be larger than $1 - \frac{1}{32}T^{-c}$? It seems that the current proof requires $x_1$ to be smaller than $1 - \frac{1}{32}T^{-c}$.

22. Formula (57), the last step: if my calculations are correct, one can get $\sigma^2$ in the end (which is slightly better).

23. "The last inequality above holds because $||(A + \sigma I)x|| \leq 6\sqrt{T}$": my derivations give slightly better bound ($4$ instead of $6$). Moreover, the authors should provide the full derivation since it is not the readers' responsibility to fill the gaps in the proofs.

24. Formula (58): the authors should provide the complete derivation. I have double-checked this part myself, everything seems to be correct. However, as I already mentioned, this is the authors' responsibility to provide complete and clear proof.

25. Above (59), "If (56) holds for $i = n$": this is not a sentence. The authors should reformulate this part.

26. The last step of (59): I do not understand the last step. In particular, it is equivalent to $- \frac{1}{1 + \sigma/2}\tilde{x}_n \geq 0$. But this is not true. **I think this is an important gap in the proof.**

27. Formula (61): I do not understand how the fourth and sixth inequalities were obtained. Complete derivations are required. **I think this is an important gap in the proof.** Also I guess $\theta$ should be replaced by $\sigma$. Next, the final step also requires the full derivation (though this particular step is correct). 

28. Formular (63): $b_{T,c} \to b_{T,c}(x)$.

29. The sentence after (63): I think it is better to add some details, e.g., $b_{T,c}(1) = 1$, which implies that $(\nabla g_{T,c,\sigma}(x))_j = (A(1-x))_j$ for $j \geq i$.

30. Formula (65): one should have factor $1 + 32T^c$, since $b_{T,c}$ does not depend on $\sigma$.

31. "Consequently, $f_{T,c,\sigma}$ is $(3 + 32\sigma T c)$-Lipschitz because $A \preceq 2I$": in fact, $A$ has eigenvalues larger than $3$, so, $A \preceq 2I$ does not hold. Instead, one can get $A \preceq 4I$ implying that $f_{T,c,\sigma}$ is $(4 + \sigma + 32\sigma T c)$-smooth (not Lipschitz)

32. Formula (66), the last step: one should add $\inf_{x\in \mathbb{R}^T}$ in front of the expression and also multiply $b_{T,c}(x)$ by $\sigma$.

33. Formula (68): I have double-checked this part, but the authors should provide a complete derivation. Also above (68) and everywhere in this proof one should replace $\max_{i=0,\ldots,T+1}\tilde{x}_i$ with $\max_{i=0,\ldots,T+1}|\tilde{x}_i|$.

34. Formula (69): I have double-checked this part, but the authors should provide a complete derivation.

35. After (69), (c): one should have $1 - \frac{1}{32} T^{-c} \leq \max_{i=0,\ldots,T+1}|\tilde{x}_i| \leq 1 + \frac{1}{32} T^{-c}$.

36. After (70), "consequently ...": the norm sign is in the wrong place.

37. Formula (71), the second step: according to my derivations, one should have $5$ instead of $3$ in the denominator of the second term. The authors should provide the complete derivation.
clarity,_quality,_novelty_and_reproducibility: **Clarity.** Up to the end of Section 4.1 the paper is clearly written, though there are some minor issues with English. However, the proofs are hard to read due to many unexplained parts.

**Quality.** The quality of the paper is good given the strengths of the result (if the inaccuracies in the proofs are not fatal). Nevertheless, I encourage the authors to apply the necessary corrections. It will increase the quality a lot.

**Novelty.** The results are novel.

**Reproducibility.** Not applicable.
summary_of_the_review: Overall, the main result of the paper is very good and significant, if the mentioned inaccuracies are not fatal mistakes. I will increase the score if the authors fix at least the issues with the proofs (otherwise, I will have to decrease the score and recommend rejection). Moreover, the paper will benefit, if the authors provide the results of the numerical experiments requested in my review.



**UPDATE after rebuttal:**

I thank the authors for their effort and improvement of the lower bound. However, a lot of new content was added: original submission was 15 pages (with appendix), not it has 26 pages. These extra pages are quite technical and I can say that the changes are too significant. Therefore, the paper needs another full round of review. Unfortunately, I have to take this into account, that is why I am changing my score to 3.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a lower bound on gradient oracle complexity for optimizing smooth PL functions. Their result establishes that gradient descent method is worst-case optimal for this class of functions. 
strength_and_weaknesses: Strengths:

- I think the problem is very natural and it was surprising (to me) that a result of this sort was not known. Also, the finding that gradient descent is optimal is interesting as well. This is because in (some parts) of the literature, PL functions are basically used as a class of non-convex functions in which typical analysis with strong convexity applies. However, this paper shows that unlike smooth strongly convex functions, it is not possible to accelerate gradient descent for this class. This establishes an interesting separation between the two classes.

- I think the paper is written well; it presents a good overview of the existing tools in lower bound constructions and gradually builds up towards the main result. Also, the main text contains sufficient details of the proof.

Weaknesses: 
I think the main weakness is that the scope of the paper is rather limited. Moreover, I think that there are still some loose 
ends which would have been good to resolve (or comment on its difficulties) given the limited scope. One such aspect is that the lower bound is only established for constant error -- while this is sufficient to argue that no acceleration is possible in this class; it would be good to show that the oracle complexity of gradient descent is tight even with regard to its dependence on $\epsilon$. Another aspect, unclear to me, is whether these lower bounds extend to randomized methods? If yes, the authors should comment on that; if not, it would be good to incorporate it (perhaps using techniques of [WS17]) or discuss challenges towards it.

[WS17]:  Lower bound for randomized first order convex optimization

I read parts of the proofs and have corrections and questions about how some of the steps follow. It would be helfpul if the authors response help address these.

- Don't understand why the inequality before Eqn. 53 holds. If the lower bound on $m$ in the statement is used, then there should be no $m$ in the right hand side.

- Proof of Lemma 5: I am little confused about the first few lines in the proof of this lemma. What if all coordinates of $\tilde x$ except the first (which is 0) are negative. Then the assertion that there exists $k,l$ such that $\tilde x_i>0.5$ for $i=k..l$ is not true. It seems that the proof should thus use the absolute values of these.

- I am not sure about what happened in inequality in Eqn. 59.

- Statement of Lemma 6: It seems that the assumptions stated in the lemma statement is not sufficient to get the final result -- say $x_l$ is $-\infty$, $x_{l+1} = 1- \frac{1}{32}T^{-c}$ and $x_{l+2} = 1+\frac{1}{32}T^{-c}$, then $(\nabla f_{T,c,\sigma} (x)){(l+1)} = -\infty$ The premise thus needs to be strengthened. Also, I dont understand some parts of the proof here:
(a). Third inequality -- how? what if $\tilde x_{l+1}$ is negative?
(b). What happened in the fourth inequality; the statement has no lower bound on $\tilde x_l$ in terms of $\tilde x_{l+1}$, right?

- Typo: It seems $1/32$ missing from definition $v_{T,c}$?

- Typo: $\sigma$ missing in front of $b_{T,c}(x)$ in inequality after Eqn. 66 and henceforth.

- Typo: after Eqn 70, inequality should be outside the norm.

- Typo: should be $1+\frac{T^{-c}}{32}$ in the rhs in the first sentence of part 4(c) of proof of Lemma 1.

- Typo: Should be $\tilde x_k$ (as opposed to $\tilde x_m$) at the end of base case in proof of Lemma 5

- Typo: In the proof of Lemma 2, the last inequality should be $\geq$.
clarity,_quality,_novelty_and_reproducibility: I think the paper is well-written and is of good quality. The constructions, though inspired from prior works had to be modified in order to be applied in this context. Reproducibility: Does not apply.
summary_of_the_review: I think the studies a very natural problem and provides an interesting result. The only downside is its limited scope.

Edit: Post author response, I have increased my score from 6 to 8.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studied the lower bound of minimizing PL functions. It provided an $\Omega((L/\mu)^{1-a})$ (arbitrary small $a>0$) lower bound for finding the optimal solution. It reveals a fundamental difference between PL functions and strongly convex minimization, also it shows that GD is already nearly optimal for solving PL functions.
strength_and_weaknesses: Strength:
1. First specific lower bound result for PL functions
2. Reveals the fundamental difference between PL function and strongly convex functions
3. The paper is well-written.

Weakness:
1. The lower bound comes without the dependence on $\epsilon$, which is different from the strongly convex counterpart.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, the flow is very clear. Also it is a rather concise paper without lengthy proof, appreciate it.

The main technique is still the zero-chain argument which is common in lower bound literature, but the proposed hard instance reveals novelty.
summary_of_the_review: To be honest, I am in a dilemma on evaluating the significance of the result. I am excited on the result concerning it is the first result for PL functions. But the lower bound here is just $\Omega((L/\mu)^{1-a})$, which is kind of "constant" level, rather than the $\Omega(\sqrt{\kappa}\log(1/\epsilon))$ in the strongly convex case, or maybe the lower bound here can be further rewritten as ($\kappa=L/\mu$):

$\Omega(\max(\sqrt{\kappa}\log(1/\epsilon), \kappa^{1-a}))$

So I believe that the result in the submission should not be tight enough (maybe the final tight lower bound should be $\Omega(\kappa\log(1/\epsilon))$?), which makes me skeptical on the significance of the result. So I hope to learn more from authors on the insight of the result, also the difference on the technical part compared to the lower bound of strongly convex minimization. Thank you for the effort.

---------Update---------

I appreciate authors' effort for revising the result, and there is a significant change in the new version, which took me a long time to read it beyond the regular review time frame. I think it is a pretty nice result revealing high importance, but I would say it is almost another new paper and I agree with Reviewer a1uz that it may require another full round of serious review, so I will keep my score here. Thank you very much.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors derive a new lower bound for first-order methods applied to functions satisfying the PL (gradient dominance) condition. While I find lower bound results important and significant, I do not believe the paper could be published in its current form. This is due to some of the reviewers catching technical issues in the proofs. Although the authors have tried to address this, I believe the paper should go through a rigorous review process rather than a short rebuttal type of patching the technical shortcomings.
justification_for_why_not_higher_score: Technical issues in the proofs.
Decision: Reject