Characterizing linear convergence in optimization: Polyak-Łojasiewicz inequality and weak-quasi-strong-convexity

Authors: Foivos Alimisis, Bart Vandereycken
Primary area: optimization
Keywords: gradient descent, linear convergence, Polyak-Łojasiewicz inequality, weak-quasi-strong convexity

Abstract:
We give a complete characterization of optimization problems that can be solved by gradient descent with a linear convergence rate. We show that the well-known Polyak-Łojasiewicz inequality is necessary and sufficient for linear convergence with respect to function values to the minimum, while a property that we call "weak-quasi-strong-convexity", or WQSC, is necessary and sufficient for linear convergence with respect to distances of the iterates to an optimum.

Decision: reject
Reviewer scores: 8, 3, 3, 6

Reviews and discussion:
<thread>
creation date:
1729795026653

thread_type:
official_review

<thread_object>
creator: reviewer_1jsr

<content>
summary:
The paper studies the linear convergence of gradient descent when applied to minimizing a smooth but possibly nonconvex function. The main contribution is two theoretical results characterizing the convergence rate of gradient descent under the PL inequality or Weak-Quasi-Strong-Convexity (WQSC) inequality.

The first result shows that the PL inequality is both necessary and sufficient for linear convergence of gradient descent, with convergence here meaning in terms of the function values f(x_k) - f*. Of course the sufficiency of PL inequality for this result is well-known but the reverse implication, that linear convergence implies the PL inequality, seems novel.

The second result shows something similar for functions satisfying the (WQSC) property and linear convergence with respect to the distance of the iterates to the set of solutions.

In this way, the authors seem to have solved the search for a "weak PL" condition that will ensure linear convergence - the PL inequality is necessary.

Some applications to neural networks are considered but no numerical investigations are done.

strengths:
- The arguments appear to be correct and the results are stated clearly and precisely.

- The results are novel in the sense that previous results of this nature considered (slightly) narrower function classes. The characterization of linear convergence in terms of PL inequality is significant.

weaknesses:
- The results in this paper are, on the whole, incremental in nature. They mostly extend known results to the case where the set of optima is a convex set rather than assuming that it's a singleton. While it's no doubt an important distinction, the analysis involved is hardly changed.

- The paper is purely theoretical, without any investigations into whether these results hold or give insight in practical scenarios. Although some effort is made in the appendix to discuss neural networks that may satisfy the hypotheses of the results here, they are under assumptions like Lipschitz-continuity of the gradient which is actually not typically satisfied by neural networks.

- The related work is underdeveloped, with no mention of the Kurdyka-Łojasiewicz inequality or the associated results about error bounds and convergence rates. I think there is certainly a connection here that is at least worth referencing, if not developing further.

questions:
- To your knowledge, is the work by Abbaszadehpeivasti et al. the only other result that shows necessity of PL for linear convergence? I was surprised that this has not been examined before given the large amount of literature on the PL (and KL) conditions.

- Are there notable functions covered by your relaxed assumptions that are not covered by the weak convexity assumptions in  Abbaszadehpeivasti et al. ? Their curvature lower bound can have a negative constant so it covers a pretty broad class of functions, c.f. Drusvyatskiy and Paquette 2019, if I am not mistaken.

- Similar question to the above - are there actual modern deep learning problems whose set of minimizers is convex that are not toy problems? It seems a bit exaggerated to consider the work of Alimisis 2024 in line 182 as having unrealistic assumptions for assuming that the minimizer is unique. While it is indeed unrealistic, from the point of view of realism/modern deep learning, I don't see why it's any more unrealistic than assuming that the set of minimizers is convex - as far as I know this is simply not the case in modern deep learning. Furthermore, from the point of view of theory, the difference between having a singleton minimizer or a convex set is small - you have many of the same inequalities just by taking the projection onto the set of minimizers, as is done in the current submission.

*References*

Efficiency of minimizing compositions of convex functions and smooth maps
Drusvyatskiy and Paquette 2019
</content>
</thread_object>

</thread>
<thread>
creation date:
1730328120744

thread_type:
official_review

<thread_object>
creator: reviewer_jpve

<content>
summary:
This paper characterizes the necessary and sufficient condition for the GD to have a linear convergence for smooth (possibly non-convex) functions with respect to the function value and the distances between the iterate and the optimum (that is a projection of the iterate to the solution set). The PL and WQSC conditions are known to provide a linear convergence for GD, and this paper shows that they are also necessary conditions.

strengths:
See Weaknesses.

weaknesses:
Theorems 5 and 7 are the main contributions of this paper, but they appear to be either equivalent or nearly identical to the closest results in Abbaszadehpeivasti et al. (2023) and Alimisis (2024a) mentioned by the authors.

- Theorem 5: The authors mention that Abbaszadehpeivasti et al. (2023) assumes extra assumption (see line 177), but I found that this is just a corollary of the Lipschitz gradient assumption. Theorem 5 in Abbaszadehpeivasti et al. (2023) therefore essentially assumes the same condition as Theorem 5 in this paper, so I should say that there is nothing new in Theorem 5.

- Theorem 7: The only difference between Theorem 7 of this paper and Theorem 5 in Alimisis (2024a) is the assumption on solution set; the former assumes that the solution set is convex, while the latter assumes that the solution set is a singleton set. Although I agree with the authors that their assumption is indeed weaker, I do not see this as a significant advancement, especially given that lines 346-347 were only required to address a non-singleton convex solution set.

Apart from the above, I do not find this paper's contributions sufficient for publication in ICLR. I recommend that the authors address the questions raised in the Conclusion to better motivate this work for the machine learning community.

questions:
See Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730531132873

thread_type:
official_review

<thread_object>
creator: reviewer_ty5u

<content>
summary:
The paper presents the necessary and sufficient conditions for the linear convergence of the gradient descent (GD) method. Specifically, the authors prove that the Polyak-Łojasiewicz (PL) condition is a necessary and sufficient condition for the function values to converge linearly to the minimum. In contrast, the weak-quasi-strong-convexity (WQSC) condition is a necessary and sufficient condition for the sequence of iterates to converge to the minimizer.

strengths:
The authors clarify the necessary and sufficient conditions for the linear convergence of GD, including both the convergence of function values and the convergence of the sequence of iterates.

weaknesses:
1. This paper lacks a clear comparison with existing work. Additionally, I am uncertain whether the authors are the first to suggest that the Polyak-Lojasiewicz (PL) condition is necessary for the linear convergence of function values in gradient descent.
2. According to Definition 2, there is only one global solution. If there were two distinct global solutions, the inequality in Definition 2 would not hold. Therefore, the WQSC condition proposed by the authors is essentially equivalent to the weak-strongly convex condition in (Alimisis (2024a) ). Am I correct in this assessment? If so, it should be noted that linear convergence under the weak-strong convexity property has already been established.

questions:
Line 42: Should the stepsize $\eta$ be in the range $(0,2/L)$ or $[0,2/L]$?
Line 46: The authors should reference original or classic sources. Additionally, they cite too many papers from arXiv, raising concerns about the reliability of the results in these papers.
Lines 269 and 346: Should we consider the step length $\eta$ as a constant, or as a variable that can converge to 0? I believe these two cases should not be conflated. Therefore, I suspect there may be an issue with the relevant proof.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730636950684

thread_type:
official_review

<thread_object>
creator: reviewer_n8tc

<content>
summary:
In this paper authors study the linear convergence conditions for gradient descent algorithm. They prove that well-known PL-condition is not just sufficient, but also necessary for gradient descent to have linear convergence in terms of functional residual. Additionally, authors introduce a new class of problems, that they call weak-quasi-strongly-convex. Authors claim, that on this class of problems gradient descent has linear convergence rate in terms of distance to the solution necessary and sufficiently.

strengths:
The authors introduce two novel theoretical results. Firstly, they show that PL-condition is not just sufficient, but also necessary for linear convergence of gradient descent on smooth function. Secondly, the authors introduce the definition of weak-quasi-strongly-convex (WQSC) function. Moreover, the authors prove that the WQSC condition is necessary and sufficient for gradient descent to converge linearly in terms of distance to the solution. The WQSC condition is less strict than strong convexity, which broadens the class of problems, where we can obtain linear convergence with respect to distance to the solution. 
Overall, the result seems significant for the community while being very simple. In theory, it allows researchers to connect theoretical results for linear convergent methods and problems that satisfy the PL condition (see Theorem 10 in Appendix). In practice, the WQSC condition, while being a relaxation of the strong convexity condition, broadens the spectrum of problems, where GD has linear convergence in terms of distance to the solution.

weaknesses:
Lack of experiments. It would be beneficial to provide some experiments on WQSC problem, which show linear convergence of GD on this problem.

questions:
When you mention an equation, please, change \ref to \eqref, since it is a bit confusing.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731931640648

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response to all reviewers / part 2

comment:
### Added value in a technical level: 
We do not claim that our results are groundbreaking in terms of technicality. We prefer though to see their simplicity as an advantage rather than as a disadvantage, as they can be understood by a very wide audience, broadly interested in optimization.

#### Theorem 5:
Abbaszadehpeivasti et al.(2023) show the necessity of PL in their Theorem 5 under the assumption of lower bounded curvature (only), making the proof almost trivial (see also our new Proposition 7 for a slightly more general version). This is because, the lower bound for the curvature (in combination with the choice $1/L$ for the step size) provides the important inequality $$ f(x)-f(\tilde x) \leq \frac{2L - \mu}{2 L^2} \| \nabla f(x) \|^2, $$
where $\tilde x$ is an iterate of gradient descent starting from $x$ with step $1/L$.

We noticed that in the case of gradient descent, deriving such a bound can be obtained only using $L$-smoothness and the specific structure of the algorithm (lines 233-258 in the new version of our paper). This by no means implies that, in general, an upper bound for the curvature is the same as a lower bound for the curvature. For twice differentiable functions, the first corresponds to an upper bound for the eigenvalues of the Hessian, while the latter to a lower bound for them. Recall also the examples in the previous section.

#### Theorem 9 (previously 7):
The main technical backbone of Theorem 9 (previously Theorem 7) has been developed in Alimisis (2024(a)). The technical contribution of our work is a neat way to extend its result in the case of a problem with multiple optima, by making a more restrictive (but totally natural) assumption (line 373 in the new version) on the contraction rate of gradient descent (must be proportional to the step size) and work things in the limit of arbitrarily small step sizes (lines 424-431 in the new version). We believe that such an argument is not trivial.

To conclude, we believe that sometimes it is easy to label a result as incremental, when it is seen written down clearly. While our community certainly suffers from a high supply of incremental results, we are confident that our results are quite important and novel and we give plenty of evidence in our previous discussion. We admit though that certain aspects of these results were made clearer to us after receiving your reviews, and we thank you for that.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731931724393

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response to all reviewers / part 1

comment:
We thank the reviewers for their time and energy. Their efforts mean a great service to us, as they encouraged us to look our results and related ones in greater detail and make valuable conclusions. We address here some topics of criticism that seem to underline many of your concerns and we also respond to each one of you individually. We have also revised our paper, with changes highlighted in blue.

### Presentation: 
We have made an honest effort to discuss related work to the best of our knowledge and we think that the comparison with our work reflects the best of our understanding. We have added some related work about the Kurdyka-Łojasiewicz inequality and its relationship to error bounds as suggested by reviewer 1JSR (lines 172-175 in the new version). It is surprising also to us that such a natural question on necessity of weak convexity notions has not received more attention in the literature. We kindly believe that reviewers' uncertainty over previous work should result in lower confidence score and not in lower presentation score for our paper.

### Added value in a high level:
#### Theorem 5:

An instance of our Theorem 5 can be found in Theorem 5 of Abbaszadehpeivasti et al.(2023), under the assumption of bounded curvature from both above ($L$-smoothness) and below (even by a negative $\mu$). After a closer inspection, we figured out that in Theorem 5 of Abbaszadehpeivasti et al.(2023) only the lower bounded curvature assumption is used to show the necessity part of the result, while $L$-smoothness is used only for the sufficiency part of the result. Their result confused as because it is stated as an "if and only if" statement. We have added a slightly more general version of the necessity part of Theorem 5 of Abbaszadehpeivasti et al. in our revised version of the paper as Proposition 7.
The assumption of lower bounded curvature is in general not standard, in the sense that such assumption cannot be used in the sufficiency part of the result (i.e. to guarantee a linear convergence rate starting from a PL condition as in Proposition 1). In contrast, our result (Theorem 5) derives the necessity of PL condition assuming $L$-smoothness and utilizing the very structure of the gradient descent algorithm. We have added an "if and only if" statement in our revised paper as Theorem 8, where the lower bounded curvature assumption is completely absent.
There are notable functions that are lower bounded, $L$-smooth, but do not have a lower bounded curvature. Here are some examples of such functions $f: \mathbb{R} \rightarrow \mathbb{R}$. This means that they fit the assumptions of our results (Theorems 5 and 8), but not the assumptions of Abbaszadehpeivasti et al.:
>- $f(x)= (x^2-x^{1/3}\sin(x))\frac{1}{1+x^2} $
>- $f(x) =(x^4 - x^{1/5} \sin(x)) e^{-x^2} $
>- $f(x) = x^2 - x^{1/7} \left(x-\frac{x^3}{6} \right) e^{-x^2}$


These functions are all lower bounded, differentiable everywhere, and twice differentiable everywhere except at $x=0$. $f''(x)$ is always upper bounded, thus the curvature is always upper bounded by some $L>0$. Close to $0$ though, it holds $\lim_{x \rightarrow 0} f''(x) = -\infty$. This means that the curvature at $0$ is $-\infty$. We have included the first function as an example in the new version of our paper (lines 288-302).

Even in the case that the curvature does not become $-\infty$ but it is still negative with a very large magnitude, the result by Abbaszadehpeivasti et al. suffers, as the constant with which their derived PL inequality holds is of the order $\mathcal{O}(-1/\bar \mu)$ (line 333 in the new version), where $\bar \mu$ is a lower bound for the curvature.

An overview of the previous discussion can also be found in the new version of our paper in lines 178-193.

#### Theorem 9 (previously Theorem 7):

Regarding Theorem 9 (Theorem 7 in the old version), the added value compared to the result of Alimisis (2024(a)) is that our result holds in the case of multiple optima which form a convex set (in contrast to a singleton). 

>- The first reason that we took the time to work in the case of multiple global optima is that the usual definition of WQSC (or whatever various authors choose to name it) involves the possibility of multiple optima and the projection to their set, see Necoara et al. (2019) (Definition 1) and Karimi et al. (2016) (end of page 11). In all these works, one needs to assume that the set of optima is convex, in order to guarantee the uniqueness of the projection.
>- The second reason is that allowing multiple optima, even forming a convex set, is strictly more general than allowing a unique optimum. A prominent class of functions that have convex set of optima is the class of quasi-convex functions (all level sets of a quasi-convex function are convex, thus also the set of global optima). It is our bad that this example was missing from the original paper and we added it in the revised version (lines 196-198).
</content>
</thread_object>

</thread>


Metareview: