New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results

• it remains unclear whether the connection to surrogate function is useful beyond proving negative results.

This is exactly our main point: In light of our negative results, proposing yet another stochastic variant of the Polyak stepsize in the case where the optimum value of $f$ is unknown is not a promising direction. Judging from the number of papers that ignore this issue, this seems a very much needed point for this community. So, our negative results are not a minor point, but very much an essential part of our contribution. In turn, as recognized by the reviewer, these results are a consequence of our surrogate view.

• the conclusion says that the neighborhood of convergence is unavoidable without interpolation

This is not what we meant. We wrote “We demonstrate that this neighbourhood is not avoidable and a fundamental issue beyond interpolation causing instability”. So, what we mean is that the neighbourhood of convergence is not due to the lack of interpolation, as commonly believed, but instead on the fact that the minimum of the surrogate loss is not zero. This condition is formally expressed in Eq. (5) in Section 6. We believe that this is a very important point that is possibly misunderstood by many people in this field.

• it seems that only convex function are considered

Correct, we will make it more clear.

• Typos in Lemma 1

You are correct, we will fix them.

• Rate for sharp functions

As the other reviewers also found, there is a typo, a missing “1/2" in the first two terms of the inequalities

• Which properties do not hold if $\psi(x^*)\neq 0$?

In this case, the function $\psi$ is only approximately LSUC (Lemma 2) instead of being LSUC. This implies an additional term in Lemma 3. As discussed in Section 6, we show that the consequence of this extra term cannot be avoided.

• Convexity of h in Theorem 3 is only required for x

Correct! We will add it.

• second part of Remark 1

Sorry that is a weird typo, we meant $a = \sup_\xi f(x^*,\xi)$.

• the paper by Loizou et al. has results for the nonsmooth setting in the Appendix C.1

At the end of Section 5 were we discuss the non-smooth results in Loizou et al we are referring to $SPS_{\max}$, as mentioned in the following sentence [225-226], and implied by the context of our Theorem 3 (using stepsize from Algorithm 1). In [1] there is no result for $SPS_{\max}$ in the non-smooth case. In [1] they only have a nonsmooth result for SPS in the easier interpolation case. This is not a minor difference: They claim that “Using the proof techniques from the rest of the paper one can easily obtain convergence for the more general setting”, but this does not seem to be true. The technical reason is that the min function would introduce a non-convexity that would not allow the use of Jensen’s inequality. We show how to go around it, by lower bounding it with a convex function in line 805 in the supplemental material. So, a proof is indeed possible but not with the same tools they use. We will be more precise on this point and make it clear that we are referring to $SPS_{\max}$

• Where is Proposition 5?

Typo, it should be Lemma 5 (as you can see from the hyperlink in the pdf).

• "the last iterate will converge". I think it is more accurate to say "the function values converge to zero" (here the optimal value of is zero)

Thank you for the clarifying question, in this case we do in fact we do have convergence of the last iterate to a point in the solution set. This question was also asked by reviewer qnH4 and we provide a similar response below. We will also include this discussion in the Appendix.

The result follows from a classic argument with Fejér monotone sequences. From Lemma 1 we have that the distance to any solution is decreasing, that is, $\\{\boldsymbol{x}_t\\}$ is a Fejér monotone sequence with respect to the solution set. Since we have that $\phi(\boldsymbol{x}_t)\to 0$ and $\phi$ is continuous then we have that every limit point $\\{\boldsymbol{x}’\\}$ is within the solution set since $\phi(\boldsymbol{x}’=0)$. Therefore we can use the fact that if $\\{\boldsymbol{x}_t\\}_t$ is Fejér monotone with respect to the solution set and the set contains all the limit points of the sequence then the sequence must converge to a point in the solution set (see Theorem 8.16 in [Beck 17]).

[Beck 17] Beck, Amir. First-order methods in optimization. Society for Industrial and Applied Mathematics, 2017.

We thank the Reviewer for carefully going over our paper. In particular, we will fix all the typos and minor mistakes in our notation. In the following we answer to the Reviewer’s questions

1. Lack of practical algorithmic improvement, this perspective is of only theoretical interest.

Actually, writing a paper of “theoretical interest” was exactly our aim. Moreover, the call for papers of NeurIPS explicitly says “We also encourage in-depth analysis of existing methods that provide new insights in terms of their limitations or behaviour beyond the scope of the original work.” We agree that reviewers have freedom to interpret the reviewing guidelines, but we would still appreciate a more faithful interpretation.

1. Could you provide an example of a nonsmooth function that satisfies Definition 2?

An easy example is in line 108: $f(x)=|x+2|+x^2/2$. We have that $\partial f(x) = \\{1+x\\}$ for $x+2>0$, $[-3,-1]$ for $x=-2$, and $\\{-1+x\\}$ for $x+2<0$. Also $x^{\ast}=-1$ and $f(x^*)=1.5$. One can verify, for example by plotting the inequality, that this function is self-bounded for L=9 and not-smooth. In the same way, one can also show that f is L-LSUC with the better constant L = 2. Note, that one must also consider the worst case subgradient at $x=-2$.

2. On line 140, could you elaborate more on $\phi(\boldsymbol{x}_t)\to 0$ why implies the last iterate converges?

Thank you for the question, the result follows from a classic argument with Fejér monotone sequences, we will add the details in the appendix. Briefly, from Lemma 1 we have that the distance to any solution is decreasing, that is, $\\{\boldsymbol{x}_t\\}_t$ is a Fejér monotone sequence with respect to the solution set. Since we have that $\phi(\boldsymbol{x}_t)\to 0$ and $\phi$ is continuous then we have that every limit point $\boldsymbol{x}’$ is within the solution set since $\phi(\boldsymbol{x}')=0$. Therefore we can use the fact that if $\\{\boldsymbol{x}_t\\}_t$ is Fejér monotone with respect to the solution set and the set contains all the limit points of the sequence then the sequence must converge to a point in the solution set (see Theorem 8.16 in [Beck 17]).

3. On line 152, the quadratic growth condition misses a constant

Correct, it is a typo.

4. What are the conditions on h in Section 5?

The observation that $h = 0$ “works” is correct. In this section we focus on bounds to the minimizer of the surrogate $\psi$ (line 167) which also coincides with the minimum of $h$ (since h is non-negative). To establish a rate on $f$, one needs to establish a connection between the minima of $h$ and $f$, which would not be possible if one were to take a constant function $h =0$. Because many variants are picking different h’s it makes sense to break up the analysis this way since, as we show, they are equivalent to subgradient descent on $\psi$ and so we should only expect these variants to converge to a minima of $\psi$ not $f$. Furthermore, having a separation reinforces the fact that there is a tradeoff between designing an “$h$” that is nice (e.g. $H(x^*) =0$) and one that connects to the original objective function $f$.

5. [1] has results for the nonsmooth case

In line 225 we are referring to $SPS_{max}$, as mentioned in the following sentence [225-226], and implied by the context of our Theorem 3 (using stepsize from Algorithm 1). In [1] there is no result for $SPS_{max}$ in the non-smooth case. In [1] they only have a nonsmooth result for SPS in the easier interpolation case. This is not a minor difference: They claim that “Using the proof techniques from the rest of the paper one can easily obtain convergence for the more general setting”, but this does not seem to be true. The technical reason is that the min function would introduce a non-convexity that would not allow the use of Jensen’s inequality. We show how to go around it, by lower bounding it with a convex function in line 805 in the supplemental material. So, a proof is indeed possible but not with the same tools they use. We will be more precise on this point and make it clear that we are referring to $SPS_{max}$.

6. Example from [2]

The example discussed in [2] (Example 5.13) uses the functions $h(x) = e^{|x|}$, and $h(x)=e^{||x||^2/2}$. Both of which are lower bounded by 1. The technique used there is by calculating T explicitly and observing that it is not quasi firmly non-expansive.

[1] Loizou, N., Vaswani, S., Laradji, I. H., & Lacoste-Julien, S. (2021, March). Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics (pp. 1306-1314). PMLR.

[2] Bauschke, H. H., Wang, C., Wang, X., & Xu, J. (2018). Subgradient projectors: extensions, theory, and characterizations. Set-Valued and Variational Analysis, 26, 1009-1078.

[Beck 17] Beck, Amir. First-order methods in optimization. Society for Industrial and Applied Mathematics, 2017.

We thank the reviewer for the feedback and for recognizing the value of our paper.

• Would it be possible to derive an algorithm that outperforms gradient descent with the Polyak stepsize by applying an accelerated gradient method to the surrogate function?

We are currently working on this question! Indeed, our surrogate view immediately suggests a way to make an accelerated version of Polyak stepsize, which would be difficult following the usual derivation. In fact, one can think of just using an accelerated scheme on the surrogate loss, using the LSUC constant instead of the global smoothness to set the stepsizes. That said, it is unlikely that we can get an accelerated result in all cases because that would imply a better convergence rate in the non-smooth case (see lines 145-146) that is impossible due to the known lower bound. Instead, we currently believe that one could obtain an algorithm whose rate is never worse than the Polyak one and it accelerates only when possible. We believe that our unifying view can open the door to many results of this form.

We thank the reviewer for the feedback and for recognizing the fact that our unifying surrogate view is “memorable” and “it should be more widely known”.

• Is there hope of getting improved convergence results for Polyak in some situations where $\phi$ is convex, but $f$ is not?

Yes! In fact, we wrote about it in Remark 2: We consider a stochastic optimization problem where one of the functions is non-convex, yet the surrogate of the function is convex. As far as we know, this is the first guarantee of this kind for Polyak stepsizes.

• Rates for Hölder-smooth functions

We can add them, they are an immediate corollary of Theorem 7 in the Supplemental Material.

• Inequality at the end of section 4

It’s a typo, thanks for pointing it out. In particular, quadratic growth implies the presence of a factor 1/2 on the first two terms of the chain of inequalities. With that term, we only need $s^2/G^2\leq 1$, that is true.