New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
Authors: Francesco Orabona
Ryan D'Orazio
Venue: NeurIPS 2025 poster ()
Keywords: Convex Optimization
Stochastic Optimization
Primary area: optimization
TL;DR: We provide a unified analysis and new insights of the Polyak stepsize and its stochastic variants via a surrogate loss.

Abstract: The Polyak stepsize has been proven to be a fundamental stepsize in convex optimization, giving near optimal gradient descent rates across a wide range of assumptions.
The universality of the Polyak stepsize has also inspired many stochastic variants,
with theoretical guarantees and strong empirical performance. 
Despite the many theoretical results, our understanding of the convergence properties and shortcomings of the Polyak stepsize or its variants is both incomplete and fractured across different analyses. 
We propose a new, unified, and simple perspective for the Polyak stepsize and its variants as gradient descent on a surrogate loss. 
We show that each variant is equivalent to minimize a surrogate function with stepsizes that adapt to a guaranteed local curvature.
Our general surrogate loss perspective is then used to provide a unified analysis of existing variants across different assumptions.
Moreover, we show a number of negative results proving that the non-convergence results in some of the upper bounds is indeed real.

New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
Francesco Orabona
King Abdullah University of Science and Technology (KAUST) Thuwal, 23955-6900, Kingdom of Saudi Arabia
francesco@orabona.com
Ryan D'Orazio
Mila Québec Al Institute, Université de Montréal
Montréal, QC, Canada ryan. dorazio mila.quebec
Abstract
The Polyak stepsize has been proven to be a fundamental stepsize in convex opti- mization, giving near optimal gradient descent rates across wide range of assump- tions. The universality of the Polyak stepsize has also inspired many stochastic variants, with theoretical guarantees and strong empirical performance. Despite the many theoretical results, our understanding of the convergence properties and shortcomings of the Polyak stepsize its variants is both incomplete and fractured across different analyses. We propose a new, unified, and simple perspective for the Polyak stepsize and its variants gradient descent on surrogate loss. We show that each variant is equivalent to minimize a surrogate function with stepsizes that adapt guaranfeed local curvature. Our general surrogate loss perspec- tive is then used to provide unified analysis of existing variants across different assumptions. Moreover, we show number of negative results proving that the non-convergence results in some of the upper bounds is indeed real.
Introduction
The iterative optimization of complex functions forms cornerstone of modern machine learning, scientific computing, and engineering. Among the most foundational first-order methods is gradient descent, which iteratively refines solution by moving in the direction opposite to the function's gradient. A critical aspect of gradient descent is the selection of an appropriate stepsize (or learning rate), as it dictates both the speed of convergence and the stability of the algorithm. The wrong choice of the stepsizes can lead to slow convergence or, conversely, to divergence, making the tuning process significant practical hurdle.
In this landscape of stepsize selection strategies, the Polyak stepsize, proposed by Polyak (36] stands out for its theoretical elegance and convergence properties. Starting from an arbitrary 21 E R2, the Polyak stepsize is defined as
f(xx) f 1
Et+1 Et
11g,1
9.:
(1)
where * 9, E af(x)) and / min f(x) If g, then 31+1 Ft- This update rule can achieve linear convergence for strongly convex and smooth functions, (1/TT) rate for convex smooth functions, and (I)VTT) rate for non-smooth convex ones. This is particularly interesting because all of these rates are achieved with a unique stepsize and without knowledge of smoothness
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

or curvature constants. In other words, this update rule is adaptive to the geometry of the functions to optimize.
Recently, the Polyak stepsize has seen a resurgence in the machine learning literature, with a plethora of variants. However, despite the big number of papers on this topic, one essential research question seems still to be missing: What makes the Polyak stepsize adaptive and when can it fail?
Contributions. This paper aims to provide a novel framework to understand the Polyak stepsize, providing a clear geometric explanation of its adaptivity. In particular, we show that the adaptivity is due simple but powerful observation: The Polyak stepsize minimizes surrogate objective function that is always locally smooth. As for standard smooth functions, we will show that the knowledge of the local smoothness constant is enough to obtain the correct rates. In addition, the local smoothness will depend only on the gradient itself, removing the need to estimate it. Furthermore, we show that minimal curvature of the surrogate is inherited from the original function as well. We also use this framework to extend its core idea to a family of algorithms. Then, we will show a number of negative results when f f(x") is not known and for its use in the stochastic case. These negative results complete our understanding by showing that some non-vanishing terms in existing upper bounds are necessary.
Related Work
In the pionnering work of Ermol'ev [1] stepsizes of the form x 1/1ss.1f were proposed for non-smooth optimization. Despite the many convergence guarantees enabled by Ermol'er 'v [44's framework, in Polyak (36] it is noted that linear convergence is not possible with such stepsizes. As an alternative, Polyak suggests the stepsize ( which is shown to converge favourable rates with non-smooth convex functions, and strongly convex and smooth functions. In fact, contrary to common belief, Polyak (36) was the first to show linear convergence with a rate comparable to gradient descent in the smooth and strongly convex case. Furthermore, the case where f is estimated was also studied, showing convergence to level set if f* is overestimated, and best-iterate convergence to a neighboorhood if it is underestimated. The Polyak stepsize has since been extended and studied across several applications and domains.
Non-smooth convex. In non smoth convex optimization, several schemes have been developed to estimate f* on the fly 6 16 41 31 27). In the finite-sum case with interpolation. | and variants
have been studied as an incremental subgradient method [3 27
Non-expansive operators. In the context of non-expansive operators, the update ( has also been studied as special case of the subgradient projector [2] g [0]: where it can be shown that subgradient descent with T) (f(x)=c)+/Il9.) is quasi-firmly non-expansive operatof] if f is convex and с 2 f*, and æ - x* if f is continuous [2]. Moreover, in the finite-sum setting, interpolation can also be viewed as iterating different quasi-firmly non-expansive operators with common fixed point. For example, applying subgradient projector sequentially (i.e., cycling through the different component functions) in a way such that each function eventually gets visited guarantees that + {f()) < c} g Example 5.9.7]. For survey on this topic see Censor [9].
Deterministic. In modern optimization, 11 has been shown achieve similar rates gradient descent in various common assumptions (e.g., Lipschitz, smoothness and strong convexity) [22], and more recently with other assumptions such as weakly convex functions 12), (Lg, L, -smooth functions [42 [7], and directional smoothness [30].
Stochastic. The Polyak stepsize has also been extended to the stochastic case with emphasis on
applications to machine learning [39] 29, 38). The ALI-G method (5) and SPS 229 use stochastic estimates via the sampled function f(x E) and its gradient f E) to perform Polyak- like stepsize. SPS in addition uses inf f far E) as an estimate to f*, and is shown to converge at fast rates without neighbourhood under interpolation. Folowing SPSmax max many variants have been proposed for SGD: StoPS (24), DECSPS and SPS max (35. SPS, [15. Beyond SGD, other extensions include: mirror descent
[ with preconditioning (1. with line-search 25 and with
momentum
non-expansive if for all fixed points x", [[[(w) 2=1 < || x²122_ 2- [[)) 20| Note that furily non-expansive operators also referred to cutters.
An operator 7' is

---

Neighbourhood of Convergence. For SPSmax. Loizou et al. (29 proved that the suboptimality gap only guaranteed to shrink up to factor that depends on the loss themselves. As we will explain in Section 5.T this is equivalent to the guarantees in online learning where the regret is proportional to the cumulative loss of the competitor, typically denoted by T.* Hence, these kind of guarantees are usually called in online learning I.* bounds [see, e.g., 34] Section 4.2].
Surrogates. Gower et al. [9 show that the Polyak stepsize equivalent online gradient descent with fixed stepsize on a sequence of adversarially chosen self-bounded surrogate losses. Differently from our framework, the adversarial nature of their losses does not allow to show that the algorithm is minimizing a fixed function. In comparison, our surrogate approach considers a fixed surrogate loss with local smoothness, where the Polyak stepsize is chosen be the inverse of the local smoothness.
Surprisingly enough, despite the adaptivity of the Polyak stepsize across various assumptions without modification, in previous literature there is clear explanation why this is the case.
3 Definitions and Notation
We will use the following notation and definitions. All the norms in this paper are L.2 norms and will be denoted by || Il. For a function / R2d - R, we define a subgradient of f in E Re as a vector g E IRd that satisfies f 2 f(x) + (g.y- y-.y-2. x), Vy E Rd. We denote the set of subgradients of f in æ by 0f()). For differentiable function we have that 0f(x) = {V)(x))
A function f V + R, differentiable in an open set containing V, is L-smooth w.r.t. || fly S f()) + (Vf(z). - x) + 1 2 x - yll? for all x, y E V. Definition 1. We say that a function f has a s-sharp minimum in xx if
f(x) f(x") s|1 -x"
x²|l
Note that if f has sharp minimum then it is not differentiable at xx 37 and if the function is also convex and G-Lipschitz we immediately have G 2 Definition 2. We say that a function f T + R.. is L-self-boundee if
||g|| (z)(()) inf [())), Vg E af(x).
It is known that L-smooth functions are L-self-bounded [see, e.g., Lemma 4 in 28). but this definition strictly weaker because it does not assume differentiability.
Polyak Stepsize is Gradient Descent on a Surrogate Function
Let f be convex and xt E argmin, f()). Consider the following function:
<(x)
- -
Instead of viewing the Polyak stepsize 1 with respect / propose view it equivalently as a subgradient method with respect to Φ. By the chain rule of subgradients [[Coolllyry 16.72], subgradient descent with the Polyak stepsize [I] equivalent subgradient descent on with |o This perspective may seem superfluous, howerever, we will show that _ is strongly related certain notion of local curvature of é, local star upper curvature.
stepsize
Definition (Local star upper curvature (LSUC)). We say that a function with minimizer x" has Xy local star upper curvature (LSUC) around there exists Xy > 0 such that
f(x") f(y) - (gy x= - - 2
1g
2 Vg, Eff
Note that if the function is LSUC everywhere, then must be convex since we assume the existence of a subgradient It is also immediate to show that convex L-smooth functions are also L-LSUC. Indeed, for convex I-smooth functions we have that 32 Theorem 2.1.5]
f(x) - f(y) - (V/(v), x >
2T. [
(3) Væ, E IRd
II g, is subgradient but directional derivative then would be guaranteed to be star-convex 266.

---

8-
f(x) = +|
[( 6
2-LSUC
4-
Figure 1: The function f(x) 21 2 non-smooth 2-LSUC as demonstrated by blue curve. f(x*) (g. x² - 2) - 1/4 being larger than f(x) for all and g E 0f(z). Similarly, f is self- but with larger constant
So, it is enough to set æ = xx to obtain the above definition. However, the inclusion is strict, because there exist functions that
smooth and still satisfy the above definition. For example, as shown Figure 1 one can easily verify that f(x) = je + + = is 2-LSUC and 9-self-bounded but not differentiable
2, hence it is not smooth.
Finally, if the war-upper-curvattee holds globally, i.e., there exists show that this condition is equivalent to the upper quadratic growth condition in Guille-Escuret et al. 21 This observation was first made by Goujaud et al. [88 Theorem 2.6]. we include the precise
Xy for all y, then we can
statement and proof in the Appendix B
The key observation in the next Theorem is that & is always locally star upper curved, regardless of the curvature (or lack of it) of the function f. Moreover, it will inherit additional curvature from f. The proof can be found in Appendix A
Theorem 1 (Curvature of the Polyak surrogate). Les [(x be convex and define xx E argmin,, f(x)..
Define ((x:) (x) (z)) f(x Then, have
o is 1o, -SSUC around any y for any 9y E Of(y).
If f s-sharp, then & has s² -q-quarraicc growth.
If f has u-quadratic growth and L-self bounded, then à satisfies local quadratic growth:
1 /llgg/|
((z)
|| x= =11 Agg 0f(x).
2 2L
This theorem tells us that, regardless of the curvature of f. we can always construct the function ó that is locally curved. It is well-known that for L-smooth functions one can use the stepsize 7) and achieve a rate between (1/TT) and a linear one, depending on the presence of strong convexity. Here, we show similar result: GD can use stepsizes that depend on the local star upper curvature in all cases. Note however, unlike GD with a constant stepsize and smoothness, we do not have a descent lemma with o. Indeed this not possible as it would guarantee O1/TT) rate for the last iterate which was shown to be impossible by Goujaud et al. [18 for QG + (L) functions (i.e., I-LUSC functions).
Lemma 1.
Let & convex and define x" argmin, Φ(x). Assume & to be ASLLSUC around any guarantees
point æ. Then, using subgradient descent with stepsizes T)t Aus
Th. (d(x.) ((x*)) - - x012
| x=
(3)
2
Summing this inequality over time, we also have
||0|| - -1=112
d (TTT
m))( <
(4)
A function satisfies the ju-quadratic growth condition if f(x) f(xx" 2 1/2l/z x=1

---

where or
Eis tt 2t or Tr argmin (m)....... o(x))
Proof. From the classic one-step analysis of GD [see, e.g. 34 we have
Te (g De - x²) = = Ila x=1 2++1 x= w=1
+
111 2
9
for any 9x, E =))(zz). Now, we use the fact that ø LSUC and the definition of 17, we obtain the stated bound. Summing from / = 1 to T and discarding the negative term on the right hand side concludes the proof.
The above discussion can be summarized in the following theorem.
Theorem 2. The Polyak stepsize in (T is equivalent to subgradient descent on the function & in 22. when using stepsizes тソt equal to the inverse of the local-star-upp upper curvature of ó in æt.
This theorem and Lemma 1 do not give a rate, however we can immediately observe that if Σ th +00 we also have (x,) + 0, implying convergence of the last iterate (see Remark ( for more details).
To obtain known rates for the Polyak stepsize, we can use additional assumptions on f. However, to stress that, differently from prior results, explicitly get convergence rate for the surrogate function Ø, the function actually minimized by (T). The rates on the original function f are immediate by just taking the square root.
G² | x= 112 So, If is G-Lipschitz, then Ei=1 The 2 T/G². Hence, the final rate is ((xT) S 27 the surrogate loss converges as O(1/T), as expected by loss with upper curvature.
Now, instead let's assume that the function f is L-self-bounded. Using inequalities between harmonic and arithmetic means, we have
T
T
8L (L))(x;)))))))
8L2
19 11
a1
x x=1
E 11mm
T
9
9
T
where in the last inequality
This implies
4L
((āT) <
|
x=
x=
1
x
x=
2 2 T/e
2
72
9=,
Similarly, it is equally easy to obtain rates for Hölder-smook functions, see Theorem 7 for more details.
We can also assume that f is s-sharp and G-Lipschitz. So, from 3 and the fact that & has s² quadratic growth from Theorem then by Lemma we have
1
2 ar, 111 S 5² s²m æt x²1 11? < ()(((x))) d(x*)) < a. x²1 | 2
Using the fact that : S this immediately gives a linear convergence rate.
5 Generalizing the Polyak Stepsize: More Surrogates and Stochastic Setting
We have shown how the Polyak stepsize is just GD on a particular function with stepsizes adapted to the local curvature of the function. In this section, we show that construct entire family of surrogate losses with similar guarantees, while also preparing ourselves for the stochastic setting.
Instead of the function
2 we consider more generally the surrogate
v x = (=)==>>(()) hxx)
where h R + R=0 is convex. As special case we can recover 2 with h(x) f(x) f*, however, in general we not need to know f For example we can take (f(x)) a)+ for any Intuitively, the role of h is to transform into positive function. We show that và generally has an approximate local-star-upper curvature, where the approximation stems from à potentially being strictly positive in "
5

---

Definition (Approximate local-star-uge upper curvature), We will say that function f with minimizer x' has e-approximate Xy- sy-str-uuper-curee around y if there exists such that
11 e, 4g, E 0f(y)) - -x)))f(()) (gy. xx yy) 2
Since we do not make explicit assumptions h with respect convergence to the minimum of h or vb. So, from here onward we denote xt as as minizer of vh.
we can only hope to achieve
Lemma 2.
Let h F - Rz0 be convex. Define ib hh² Then, vb is (2 (zx((((==") +xx*)) approximate [[g|| for any g E @h(x)).
Proof. Given that the function (x)) might not be differentiable, we have to be careful in the calculation of its subgradients. We have
(v) 1 h2
1 (1)(x) h())(((()))) h(x)]
2 2 (x) + hg) x) (xx) + (h(#)g. x),
where g E (a())) and the first inequality is due the fact that (.2 is convex function. Hence, we see that g == hx(2)gg is a subgradient of &b in æ. Hence, for any u E Rd we have
(ar) (g. x u) 2||@|| 1اا12 = 1 1=)()) h(x)) (g, x u) + h(x))²
1
h((z)) (h(æ) (g, u))
h((z) (h(æ)) - h(u)) (g. x - u) + h(u))
S h(x=) h(u) (2
where the inequality is due to the convexity of h and the fact that h(x) Setting x², we have the stated bound.
With approximate local curvature, a generalization of Lemma is immediate.
Lemma 3. Assume tb IRd + R to be e-aaproxxmmatel >--star-upper-curee around x,, Then, for any nh O, any 9. (v..). and 0141 24 11:9. we have
(v(())))) - (xxx)) s Ix= 2r11
|
x++1
1) 2
1 Xx 11) |19.11 + m.c.
+
2
The last two lemmas tell us that the properties the surrogate functions breaks if <b(x*) ) * O. Hence, will not be able to prove convergence results, but only that, for example, the suboptimality gap will converge up to a floor that depends on v(x*). However, Section we will show that this is construct simple one-dimenstonal functions where the
not an artifact of the proof. Indeed, generalized Polyak stepsize does not converge.
5.1 Stochastic Approximation Setting
Consider now the case that we are minimizing F(x) Eg~D E)], where f S I, that covers both the stochastic approximation and finite-sum settings. We do not know the distribution D, but we assume that we can sample & i.i.d. from D.
In this setting, we argue that the Polyak stepsize makes sense only in restricted settings. In fact, the interpretation of the Polyak stepsize minimizing surrogate function implies that in the stochastic setting we will minimize the function Eg-D[; 1 ( E)], where the function h((,&) depends on the particular variant of the stochastic Polyak stepsize. is clear that in general argmin, lE [x, E be completely different from argmin, Eg- h2 2 E)]-
Here, starting from ALI-G [S] and SPS (29] that use the idea of limiting the stepsizes, we propose generalized Polyak stepsize algorithm. The proof is in Appendix

---

Algorithm Generalized Polyak Stepsize
Require: h: RR + R, æ1 E Rd
1: for t =l....,. do
2: Sample &. from D
3: Tranform far E.) into M( Et)
4: Receive E E.)
5: if 9t # 0 then
6: 2t+1 2t n E.)g: where n min |s &(
7: else
8: 1t++1 24
9: end if
end for
Theorem Let R x - Rz0 be convex in its first argument. Denote by H(x)
EE-D E)]. Then, setting R): = min |Io Mank.) Algorithm we have
Ef.)( is sele bounded, we have
T
21 xx" x0
min
[[H():)
27/1(x"))
T
2L
T
and
T
Σ min
27) B[H(a:)) -7 Σ H(x*)
||0
x x0112+
Σ
7
2 g. (2)
2
t=1
If ( E.) is G-Lipcchitz then we have
Σ B[H(x.) < | x011
T
IT + (x²x)) + G - x01
VT
hf, is L-self- belldbouudded and (xx) has p-quadratic growth, then
T+1 +
E [| x=1 $ E [ xx 113] a T+1
1 1 H(x"),
where min (1,,7) 7) and 2y min 1 7).
Choosing the function h, the above theorem covers and extends number of results in previous papers, for example:
SPSmax
29
h(x, {) f(x, {) inf f(x, E), so H(x)) E[f {) inf f(x, E)] M1x,,, {) = (ax è) - q(E), where g(E) is lower bound to inf [(x, E). In
SPS
35
max
this case,
H (((=') = Exf(x" E) -(E)]-
SPS 15] h(x, {) (s( {) f(x ()) In this case, H(x*) 0 so can also safely set ? = Jo. Moreover, H (xx) 2 F(xx) F(x*), ), hence any bound on H(x) translates
to a bound on the suboptimality gap.
Remark 1. 1f"("", (())=="))))=))")")))))" 0 for all i, then ||++| x=1| S || x²1|. Hence, in this case only need to consider all the properties of h in the bounded domain {x E RR | x² S || x+1l []] This well-known via the subgradient projector perspective, as æ; is guaranteed approach the Netx h(x,, E) 0} at each iteration if it is non-empty. This property was observed in Gower et al. (20] for SPS.. (15), but here it holds more generally. For example, hix E) (f(x E) a)+ where 2 sup, f(xx", E), would also have no neighbourhood of convergence and satisfies the assumption of the theorem.
7

---

Remark 2.
The above theorem also applies to the case where some of the f(,,E) are non-comvex
functions. while still guaranteeing the convergence to the global optimum of F. For example,
2| We have consider F(x) = (..f((x)) + 0.5ff(2)), where f = - (non-convex) and f2 = 0 and h2(x)) = that F(x) = 2/21 so x² = Now, choose (1) = max (1'))
(2 - () 2/ Hence, the hypotheses of the theorem are verified. Moreover, (x) =
2 F(x) and H Hxx*) = 0, so the theorem implies a convergence rate for the minimization of F(x) F(x") by using SPS..
Remark 3. In the proof of Theorem if one stops before taking expectations. one obtains a regret guarantee on a sequence of arbitrary losses h.). Such regret scales as the sum of the loss in x². This exactly the I.* bound that we mentioned in Section 2 Indeed, this kind of updates and guarantees were already obtained in the online learning literature for the special case of linear predictors by the Passive-Aggrent Aggressivee family of algorithms T.V.
Besides covering a number of previous algorithmic variants, we also extend the previous known guarantees. In particular, Loizou et al. [29] only studied SPS in the non-smooth setting but did not include SPS [4] Theorem 3 shows for the first time that SPSmax is adaptive to the entire range of upper curvature of the function, from Lipschitz to smooth functions. In Appendix D we also show additional results. Moreover, the second result in the smooth case is new, and it allows to recover the SGD guarantee H when y is sufficiently small. For example, we include precise statement for SPS when (a, {) is L-self-bounded, that recovers the guarantee in Gower et al. [20] Corollary 2.3].
6 Neighbourhood of Convergence and Instability of the Polyak Stepsize
In Section we demonstrate that a generalized version of the Polyak stepsize and existing variants can be viewed as GD on function with approximate local curvature, with convergence to a neighbourhood of the optimal solution. This neighbourhood of convergence appears in our analysis just like in all existing variants, therefore suggesting it is unavoidable if
(5) In this section, we demonstrate that this neighbourhood of convergence is not artifact of the analysis and indeed cannot be avoided in general. We also show that the positivity condition (5) can fundamentally change the dynamics of Algorithm [T] even in the deterministic setting, thus posing challenge that is not just associated with interpolation.
H(x)= = Ee-n(h(<,, c)] > 0 for all x
Condition 5) occurs with SPS (29 without interpolation, or in the deterministic setting when the optimal value is underestimated, (xx) = f(x) - c where 1 > e. Convergence under this condition was first studied in the deterministic case in Polyak's 's original paper (36), where it is shown that if infz (zx)= = h²* > O then lim miniçase h((x;)= - h- - htt That is, the best iterate eventually enters a neighbourhood of the minima where the size of the neighbourhood is dependent much h is underestimated by O. In the stochastic case, convergence of the average iterate to a neighbourhood when understimating the minimum was also studied by Orvieto et al. [35] under SPS However, we demonstrate the consequence of condition (5) is far greater than existing results suggest, with instability of fixed points, potential cycles, lower bounds in the sub-optimality gap, and lack of convergence regardless of initialization.
how
Deterministic Setting. We first demonstrate that in the deterministic setting, for different classes of h, if h- min, h(x)) > 0, then the fixed points of
h(w,)) Il, 9t>
if gt E ah(x),, 0 & ah(z)),
x = T(x:)
(6)
De,
otherwise
are unstable. Intuitively, this can be explained via our surrogate function view: In fact, denoting the local curvature constant of the surrogate 1 [h(xz) h+ around o; as d we see that the stepsize ne in update (6) can be equivalently written as
M(x:)) T) = (xx))) hr X
1
"Although Loizou et al. (29) state that SPS analysis can be readily extended to SPSmax this does not seem to be the case due to the non convexity of the min function, as demonstrated by our different proof technique in Appendix(C
8

---

20
10
2
-10-
0.10
1.00
20
60
Figure 2: Trajectories under T' for h(()) = + with an unstable fixed point at Lack of convergence observed for different values a as predicted by Proposition
If h is Lipschitz or self seff-boundd then then #t-1 may move further away from x" within neighborhood of x². Indeed, in Proposition we show that for all self-bounded functions with quadratic growth condition, the fixed point of T in (6) is unstable, similar result can also be shown is L-Lipschitz and has sharp mininum (see Proposition 6 in the Appendix).
+00 as - x'. Therefore, if h possesses curvature,
Proposition (Unstable fixed point). Suppose h is convex, strictly positive, L-self-bounded, and satisfies the quadratic growth condition h((r)- h² 2 - x 1| where xx = arg mill. h(()) is the only fixed point of T, defined in (6). Then, for any point E (y y o x" ,oy)) h-
h 88 } we have
(T(x) x=1l
x
Note that this reinforces the need to clip the stepsize as proposed in ALI-G and SPSmax- However, clipping will not remove this behaviour unless the maximum value is taken to be small enough. In Proposition we show there always subregion where the stepsize bounded, and this subregion can be made arbitrarily large within the unstable region; therefore, if the clipped value is too large instability is unavoidable.
The importance of h > 0 in update (6) has also been studied in Bauschke et al. 3 where they demonstrate with examples that 7 can fail to be quasi-firmly non-expansive if h- 0. Propositions [ and provide extra insight on this phenomenon as they automatically prove T cannot be quasi-firmly non-expansive and therefore have the following remark.
Remark If and either of the following conditions hold:
h is convex, self-bounded, and satisfies the quadratic growth condition,
h is convex, Lipschitz, and has sharp minimum,
then T from is not quasi-firmly non-expansive.
While Propositions I and establish that minima can be unstable, this property may not fully describe the dynamics of update 6). In fact, instability admit convergence in the average iterate last iterate if the local critical neighborhood is skipped. So, in Proposition 2 we provide an example of a function h. which satisfies the assumptions of Proposition[] [ where the iterates cycle and never reach the minimum in best Heerte or on average.
Proposition 2 (Cycling and failure to converge). There exists a strictly positive smooth and strongly convex function h, and initial point æ, such that iterates from update (6) cycle and satisfy the inequality h(} Ei=
h" 2 8 >> for all
Note that since the cycle in Proposition 2 consists of finite number of points, clipping will not necessarily remove this behaviour (e.g. the clipped value is taken to be larger than any of the seen stepsizes). In Proposition 2 specific initialization was chosen to construct cycle that would not converge. However, in Proposition [ we show that for 1-d quadratics the lack of convergence true for all initializations and values of h up set of measure zero.

---

Proposition: 3 (The set of good initializations can have measure zero), Let h R RR defined as hxx) 2
h(zz) O, where It-1 I2 IV Vh(ri), and æı randomly initialized. =² + a for Then, P(lim:-<ce 21 = = = O. In other words, the set of initializations that can converge to the optimal solution has measure zero.
Proof. Note h is I-smooth and I-strongly convex and therefore satisfies the conditions of Proposition
1 with L = and an unstable unique fixed point. Let T be such that 2 T(x)). T(x)
2 if o O and 0 otherwise. With inverse (S) {ir = Vx² + 2a z E S}. Therefore,
T ((x""))
}) has most 2 points which has measure zero for all k. By Lemma 5 in Appendix E the result follows.
Proposition 3 can be extended much more generally if from (6) is shown to satisfy the Lusin (N-1) property (see Definition| 7 123 Definition 4. 12].
Remark Note that, by Lemma
In the stochastic case with SPS, condition 5 is due to lack of interpolation, and Orvieto et al. [35 show that it can change the expected fixed point. In contrast, in the deterministic setting we have shown lack of convergence despite the fixed point being x². Therefore the issue here stems from the instability of the method due the underestimation of h² and not the bias of the expected update.
Stochastic Setting. In the stochastic setting, the positivity condition (5) can occur despite ming h(x, <) = 0, such as in SPS (h(z, {) f(x) ming fxx <)) without interpolation. Orvieto et al. (35) demonstrate that without interpolation SPS can fail to converge in a 1-d quadratic and has an expected fixed point different than ming F())) min [f E)l. Similarly to the deterministic setting, we can show that SPS can have a random walk between finite number of points.
Proposition 4 (Failure to converge). There exist fi and fz quadratic 1-d functions and a starting point 1 such that SPS on F(x) 0.5((i (x) + f2(x)) satisfies [[F(x:)) min F(x)= 2 2/3, Vl.
Proof. Let fi x² 2r + 5 and f2(2) 2x 4x 10. Let's start from 21 where F(r1) = 8. If we draw fI, x2 = -1 while if we draw f2 then 22 1 because (1) = O. Hence, 9. Iterating, have that 2g has equal probability to be equal to and 2 Hence, again we have [F((a)))] 9. So, we have that this holds for any I. Moreover, have that ming F(x) 44/6.
B[F(x2)] 0.5 (11)(())))(1)1)))) + +0.5 0.5
7 Discussion and Limitations
We have shown that the design, properties, and failure of the (variants) of the Polyak stepsize can be easily derived through the lens of the minimization of a surrogate objective function. This framework also provides a new and natural explanation on the adaptivity of the stepsize via the local curvature of the surrogate. We believe this framework has the promise to design new variants, by simply designing surrogate functions with the required properties. Furthermore, with our perspective we have provided new insight on the challenge of controlling neighbourhoods of convergence that often appear in variants of the Polyak stepsize. We demonstrate that this neighbourhood is unavoidable and fundamental issue causing instability. Moreover, we show that this issue is not due to the lack of interpolation, as commonly believed, but instead because the minimum of the surrogate loss is not zero more generally.
The limitations of our framework include the assumption of convex in the generalized surrogate that must be assumed apriori. It is unclear if this framework can be extended to the more general case of noncovex surrogate functions. The class of such surrogates that admit fast rates and tight neighbourhoods of convergence remains an open question that we leave to future work.
Acknowledgments
We acknowledge the use of Gemini 2.5 in developing the proof of Proposition We also thank Mehdi Inane Ahmed for helpful discussions. Ryan D'Orazio's 's work is funded by loannis Mitliagkas' CIFAR chair.
10

---

References
[1] Farshed Abdukhakimov, Chulu Xiang, Dmitry Kamzolov, and Martin Takáč, Stochastic gradient descent with preconditioned Polyak step-size. Computational Mathematics and Mathematical Physics, 64(4):621-633 634, 2024.
[2] Heinz H Bauschke and Patrick I. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2017.
[3] Heinz H Bauschke, Caifang Wang, Xianfu Wang, and Jía Xu. Subgradient projectors: extensions, theory, and characterizations. Sel-Valued and Variational Analysis, 26: 1009-1078 2018.
[4] Amir Beck. First-order methods in optimization. SIAM, 2017.
[5] Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Training neural networks for and by interpolation. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 799-809. PMLR, 13-18 Jul 2020.
[6] Dimitri Bertsekas. Nonlinear Programming, volume 2. Athena Scientifie, 1999.
[7] Ulf Brännlund. On relaxation methods for nonsmooth convex optimization, 1993.
[8] Andrzej Cegiclski. Iterative methods for fixed point problems in Hilbert spaces, volume 2057. Springer, 2012.
[9] Yair Censor. Iterative methods for the convex feasibility problem. In M. Rosenfeld and J. Zaks, editors, Annals of Discrete Mathematics (20): Convexity and Graph Theory, volume 87 of North-Holland Mathematics Studies, pages 83-91, North-Holland, 1984.
[10] Patrick L. Combettes. Fejér monotonicity in convex optimization, pages 1016-1024. Springer US, Boston, MA, 2009.
[11] Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. Online passive-agreesive algorithms. Journal of Machine Learning Research, 7(19):551-585, 2006.
[12] Damek Davis, Dmitriy Drusvyatskiy, Kellie J MaePhee, and Courtney Paquette. Subgradient methods for sharp weakly convex functions. Journal of Optimization Theory and Applications, 179(3):962-965 982, 2018.
[13] Ryan D'Orazio, Nicolas Loizou, Issam Laradji, and Ioannis Mitliagkas. Stochastic mirror descent: Convergence analysis and adaptive variants via the mirror stochastic Polyak stepsize. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
[14] Yu. M. Ermol' ev. Methods of solution of nonlinear extremal problems. Cybernetics, 2(4):1-14, July 1966. ISSN 1573-8337. doi: 10.1007/BF01071400
[15] Guillaume Garrigos, Robert M. Gower, and Fabian Schaipp. Function value learning: Adaptive learning rates based on the Polyak stepsize and function splitting in ERM. arXiv preprint vrxiv:2307.14528 2023.
[16] Jean-Louis Goffin and Krzysztof C. Kiwiel. Convergence of simple subgradient level method. Mathematical Programming, 85(1):207-211 May 1999. ISSN 1436-4646. doi: 10. 1001 1101070050053.
[17] Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for convex (Lo. -smoohhh optimization: Clipping, accel- eration, and adaptivity. In The Thirteenth International Conference on Learning Representations, 2025.
[18] Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Optimal first-order methods for convex functions with quadratic upper bound. arXiv preprint arXiv:2205. /5033, 2022.
[19] Robert M Gower, Aaron Defazio, and Michael Rabbat. Stochastic Polyak stepsize with moving target. arXiv preprint 21Xiv:2106.11851, 2021.

---

[20] Robert M. Gower, Guillaume Garrigos, Nicolas Loizou, Dimitris Oikonomou, Konstantin Mishchenko, and Fabian Schaipp. Analysis of an idealized stochastic Polyak method and its application to black-box model distillation. arXiv preprini P.XXi::504001880 2025.
[21] Charles muille-Escuret, Manuela Girotti, Baptiste Goujaud, and Ioannis Mitliagkas. A study of condition numbers for first-order optimization. Arindam Banerjee and Kenji Fukumizu, edi- tors, Proceedings The 24th International Conference Artificial Intelligence and Statisticy, volume 130 of Proceedings of Machine Learning Reseurch, pages 1261-1269, PMLR, 13-15 Apr 2021.
[22] Elad Hazan and Sham Kakade. Revisiting the Polyak step size. arXiv preprint arXiv: 2022.
[23] Stanislav Henel and Pekka Koskela. Lectures on mappings of finite distortion, volume 2096. Springer, 2014.
[24] Samuel Horváth, Konstantin Mishchenko, and Peter Richtárik. Adaptive learning rates for faster stochastic gradient methods. arXiv preprint arXiv:2208.05287 2022.
[25] Xiaowen Jiang and Sebastian Stich. Adaptive SGD with Polyak stepsize and line-search: Robust convergence and variance reduction. In shirry-seventh Conference on Neural Information Processing Systems, 2023.
[26] Pooria Joulani, András György, and Csaba Szepesvári. modular analysis of adaptive (non- Jconvex optimization: Optimism, composite objectives, variance reduction, and variational bounds. Theoretical Computer Science, 808: 108--08,,, 2020. ISSN 0304-3975. Special Issue on Algorithmic Learning Theory.
[27] Krzysztof C. Kiwiel. Convergence of approximate and incremental subgradient methods for convex optimization. SIAM Journal on Optimization, 14(3):807-88) -440, 2004.
[28) Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 983-992. PMLR, 16-18 Apr 2019.
[29] Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1306-1314. PMLR, 13-15 Apr 2021.
[30] Aaron Mishkin, Ahmed Khaled, Yuanhao Wang, Aaron Defazio, and Robert M. Gower. Di- rectional smoothness and gradient methods: Convergence and adaptivity. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[31] Angelia Nedic and Dimitri P. Bertsekas. Incremental subgradient methods for nondifferentiable optimization. SIAM Journal on Optimization, 12(1):109-134 2001.
[32] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer, 2004.
[33] Dimitris Oikonomou and Nicolas Loizou. Stochastic Polyak step-sizes and momentum: Con- vergence guarantees and practical performance. In The Thirteenth International Conference on Learning Representationss 2025.
[34] Francesco Orabona. modern introduction to online learning, arXiv preprint arXiv:1912.13215
2019. Version 7.
[35] Antonio Orvieto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of SGD with stochastic Polyak stepsizes: Truly adaptive variants and convergence to exact solution. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 26943-26954. Curran Associates, Inc., 2022.
12

---

[36] Boris Teodorovich Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physies, 93):14-29, 1969.
[37] Boris Teodorovich Polyak. Introduction to Optimization. Translations Series Mathematics and Engineering. Optimization Software, Inc., 1987.
[38] Mariana Prazeres and Adam M. Oberman. Stochastic gradient descent with Polyak's learning rate. Journal of Scientific Computing, (9)1):25, Sep 2021.
[39] Michal Rolinek and Georg Martius. 14: Practical loss-hased stepsize adaptation for deep learning. Advances in neural information processing systems, 31, 2018.
[40] Fabian Schaipp, Ruben Ohana, Michael Eickenberg, Aaron Defazio, and Robert M Gower.
MoMo: Momentum models for adaptive learning rates. In International Conference on Machine Learning, pages
PMLR, 2024.
[41] Hanif Sherali, Gyunghyun Choi, and Cihan H Tuncbilek. A variable target value method for nondifferentiable optimization. Operations Research Letters, 26(1):1-8, 2000.
[42] Yuki Takezawa, Han Bao, Ryoma Sato, Kenta Niwa, and Makoto Yamada. Parameter-free clipped gradient descent meets Polyak. In The ehirty- Annual Conference on Neural Information Processing Systems, 2024.
[43] Xiaoyu Wang, Mikael Johansson, and Tong Zhang. Generalized Polyak step size for first order optimization with momentum. In International Conference on Machine Learning, pages 35836-35863. PMLR, 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: To the best of our knowledge our framework in Section that both generalizes and analyzes the Polyak stepsize is novel. Additionally, we have included novel negative results in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our framework and assumptions in Section 7
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: All theoretical statements outline assumptions used in their respective proof. Complete proofs are either presented directly in the main body or in the appendix. We do not provide proof sketches for proofs not in the main body but do provide intuition and discussion such cases.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
We do include any experiments in our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
We do not include any experiments in our paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccgguieeeeeeeeeeee/eeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
We do not include any experiments in our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We do not include any experiments in our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
We do not include any experiments in our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:////auurrr..ccpo/aaa//cctaa
Answer: [Yes]
Justification: As our paper is theoretical we do not have any concerns regarding: research with human subjects, and data concerns. Nor do foresee any societal impact.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Due to the fundamental research of our paper we do not foresee broader societal impacts as per the guidelines below.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not use nor provide any models or data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No assets of the kind are used.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
We do use or release any such assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No human subjects are used.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects are used.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: An LLM was used to help derive result but not our core results or analyses.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
20

---

A Proofs for the Surrogate Ø
Theorem 1 (Curvature of the Polyak surrogate). Let (xx be convex and define x² E argming f(x).
Define Φ x (f())) - (f(=))f((")) f(x"))² Then, we have
Φ is 1 -SSC around any for any 9y @f(y).
If f is s-sharp, then & has 8² -quadraati growth.
If f has u-quadratic growth and L-self bounded, then 6 satisfies local quadratic growth:
1 gll
((x) 2 2 2L
1|
x=1 Ag E (f()).
Proof.
1
((v) - x(x*)( - (Vo(y), x x²)
2
2 (f(()) - f(xx))² (f(y) f(z")) )) y - x²) + 2 12 Vo(y)
(((()) f(a)))² (f(y) f(a))) y x²)) (f(y) f(x)))²
2
(f(y) f(x')) (s(y) f(xx' (g y x²))
s 0,
where the inequality is due to the convexity of and the fact that f(y) f(xx)((+++)) 2 O. For the second property, we have
a²
f(x) - f(x*) 2 alx - x' =111=(()) - x(xx))
2
|| x x x2
2
For the third property we have
Φ(x) 1 (f(x)) f((x))²2
| (f(x) f(x")
1 1 1
2
|| x=11
2
2L
2L
Remark 6. Convergence of the last iterate follows from classic argument with Fejér monotone sequences. From Lemma 1 we have that the distance to any solution is decreasing || x= S ||x, -x*l for any minimizer xt
that is, {xx, ] 120 is Fejér monotone sequence with respect to the solution set. Since we have v(xx)) - O and & is continuous then for every limit point x' of the implying x' is also a minimizer of 6. Therefore we can use the fact that if {x: J120 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 (see Theorem 8. 16 in Beck (4).
sequence it also holds that d(x')=
B Relationship between Star Upper Curvature and Upper Quadratic Growth
For function f. denote by X = {x: f()) = ming [(x)]. In Guille-Escuret et al. [21] they define the following function class.
Definition 5. A function f is L-quadratically upper bounded (denoted L-QG*) ifr all Rd:
L min x
f(x) f 2
x x= 2
We now show that convex T-QG+ are globally L-star upper curved, while the other direction true for the local version of the two definitions.
21

---

Theorem 5. Let f be a corvex L-QG* function, then f is globally L-star upper curved. On the other hand, let f be L LSSC, then for all we have
Lx
[(x) - 1 S
min 2 2 Ex
a
x= x2
Proof. Assume that f L-QG+ Then, we have
L min x'ER
f(y) + (g. x - y) S f(x) S
x x 22122.
2
where the first inequality is due to convexity and E 0f(y). Now, set x = xx + tg for any xx E X², to have
1 f(y) fr S xg x²
L
1
2
1 y) 119
1
6
v)
2
min x'EX
x²
1
x¹
I (g. x²
2L
2
-g. x²) 2T. g
Now, assume that is -LSUC and set g E 0f(x). For any x* e argming f(x), using Cauchy- Schwarz's 's inequality, we have
1
A
f(x) f(x") (g. x²)
1 1g]la|<
x0112
x
x²
2
2
2
Given that this holds for all x² E x it implies
f(x) f S Am
min EX
| 1o--x'1 x'13
C Proofs for the Stochastic Surrogate Vb
Theorem 3 Let h : Rdd x + R2o be convex. Denote by H(x) = (M< E)}. Then, setting
? = min
7 [1 E(). in Algorithm we have
-f.((-).) is I-self bounded, we have
| 11 2-11(x))
min 2 B[H(x:))
and
T
T + Σ
T
Σ min
7)
B[H(x:)) < ||لج 1
B + > H(x*)
t=1
t=1
hf E.) is G-Lipschitz, then we have
T Σ [H())
[ x=1
7T + 2x"x)) + Gl - x=1
+
G H(x"))
VT
hf () is L-self-borl bounded and H (xx) has p-quadratic growth, then
T+1
E [[|TT+1 - x =1" < [ x
x01] a T+1
+ 1
H (xx)
where min [ ( 7) and 27 min (+ 7)
22

---

Proof. For simplicity, denote by hx(x) = h(0, Et).
From the Lemma
T 3 have
T
Σ ((
- / [1 x²11 7h
1
l1g. h2))))))))))
Σ nehy he (z)))(()))
||
For the last term the r.h.s., we have
(x,)(()))) = min
7
(x((xs))((=²) S -he(2*).
|g hx(a))))
Observe that if he is L-self bounded then || - (1)(((a))) inf 1x(x)) S 2Lhx(x)). Therefore, we have
min (5::7) he((xr)) S min
(1r(2z) he(0rs) (x))
(1g,1 12 11
Now, since 1/: S 1/ the second term on the r.h.s can be discarded because it's negative. Taking expectations, we have the first stated bound.
Ytt (3r.) Taking expectations, we have the stated For the second result, bring on the l.h.s. the terms bound.
2
For the third result, first of all observe that for any a, we have
1
min(a,b) maxx(1/a11/b) 1/a + 1/b"
Hence, we have
(he( 11g,1
(xx
11 (xxt)
(a))( min
1|2 17) 1e he( 2 hax))))) + 7 >|
7 (x(()))) + 7
Now, observe that the function B(x) = xウン02 is convex x 2 O, because (²(x) = [162 So, summing over time and using Jensen's inequality, we have
G²
B
T
be(
1 Σ T
B(h((x:))
1 T
Σ
((()))) 7G
[x] x ||
2
he(w")
he(
7T
*+ / < Gv
Note that B- B-1(x)
that is an increasing concave function for 2 0.
2
So, inverting B and taking expectation, we have
1
Σ
T
EH
E
B
[1
x="
112
2 T
ha(x²)
T
TT
1=1
x=
1|2
G
x²
2H(x*)
+
+ G
GG/271l(x*).
7T
VT
For the smooth and quadratic growth case, we have
1 (x:) S (x:)
min
2L 7)
< 12 x= 1|2 | x=1/2 2- 2m (2t)
< [ - x' x11 112 - ||0 - x" x²1 + (x="
Taking expectations and using the quadratic growth assumption on H, we have
min
E ||
x x=
< min
27. E(H(z,)) -x)))]
2
2T.
1 21:7) H H(x*).
< EE 022 x - EE [1] [| x0 + 22 min
Ussin the inequality
V /2 Vy V2,y 2 O.
23

---

Hence, we obtain
E [1 -
-x x01² - (1 - a)L [||e, x²1 -b,
where a = min (2T, () and (2 - -min 1 7)) Hxx)). Note we have S a - 8/4L - 1.
From this inequality, it immediate to obtain
I [| - x x=1 a T-1 + T+1
|| x"
a
D Additional Convergence Result for Generalized Polyak Stepsize
Corollary 1. Let f Rd x S convex and L-self-bounded. Define x* argmin, (B-DDf((a E)] := F(w)). Let h(x,E) (f(x,E) f(x", .))). Then, running Al- gorithm with y = oc, we have
[[F(@T)] F(x*) 2L 11 1
BIy 2l/22(((>*)>> [inf sæx <) x*1l
T
VT
where Øт = Et Dt or æт argmin (e F(x).
Proof. Given the definition of h, have that ((x") O. Moreover, h(,, 2 f(x,E) (() hence (x:)) 2 E[F(x;)] - F(x*) for any t.
We have that
()((x.)),
if f(; f(x",E) if f(x, < f(x'g() if f(x, f(x'
@h(a, E)
(0),
(ag: a (0,10 (f(x,)))
Hence, for all 9, E Öhh(x,, E,) we have
| < 2L(f E,) inf f(x, Ei)
-_( f(x", &.) + f(x" E.) - inf f(x E.))
$ 2L(h(x, E.) f(x", E.)) inf f(x Ex))
So, using this inequality Lemma gives
12 AL(h.(w., fe(x)) fi)
T
h
x
T Σ t=1
hx Th
1 S 2 x - ==11
(8)
2
2
Now, from Cauchy-Schwarz Schwarz inequality, for any non-nege non-negative random variable and random variable
X, have [[ (E[X))² /E Denote by fr inf, f(x Given that f 2 0. Se (xx" - ft = O with probability 1, i.e., l...s. of the previous inequality is (2(h(xx)) Otherwise, if we assume F(x*) Blinf, f(x + > we have
fax E)] = O, then the expectation the
h7(x1) (L) + (a ft)
(x[h())))))
(x. - Elinf f(x E))
Hence, in all cases we have the last expression a lower bound the l.h.s. of (8). We now can proceed as in the proof of the Lipschitz case in Theorem to have the stated bound.
We now extend Theorem 31o Hölder-self-boundde functions. Definition 6. We say that f is (Lv,v) foölder-self-boundde if there exits [0, 1] and L, such That
|| < (1 1 -
1-0 L
I+v (f(x) f(x')( 3i, Vg E 0f(x).
24

---

This definition is weaker than both Lipschitz and smoothness and it is easy to see that L-smooth functions satisfies this condition with v 1 and L1 L.
The following theorem generalizes both the Lipschitz and the smooth case, recovering both bounds up constant factors.
Theorem 7. Let h : R x S + R2o be convex. Denote by ((x) = Egg-D/h(2 E)]. Assume that Mc Ee) is (Lv, U)Höldde----- bounded. Then, setting 1)t = min |1g, k(m). in Algorithm
have
|00 |01--x01 112
T Σ [[H())))
=Q
+ 2H 21(2)))
Ty
where Q(y) = 2y + L, 2 (1 -1-
Proof. For simplicity, denote by he(x)= h( Et).
From the Lemma 3 we have
T
T
Σ T
- / | x=1 112
Te 1)-
1
llg. (h)
Σ
nch (x, (xx))
For the last term in the r.h.s,, we have
(a:)(xa)) = min
7
he (e( S >he(2²))
|1g.1 ha
Observe that if h4 is (Le, Holde---ee-----eouudeee then
AT L (he(2) inf inf hz)))) to S {Khh(æ)) =
|1 v 1 +
x
where K, (1 + 1) Arr L.t Therefore, we have
h4 K, .7 ho(( S min
(xx)
(he(zze)
min
(1..1 >)
he(wxs) = (1111((0.))
As before, we lower bound the minimum with the convex function B(x) x
IIT K
h (xx) r
The (I.)
min
he he())) 2
B(((h(zz))
Kv
h
(ara) + +YKe
As before, this allows us to use Jensen's 's inequality:
B
1 T
Σ h((a))
s Σ
T
B(h((x))
|2]| x2
2
he(2")
TT
T
For simplicity of calculations, now lower bound B(x),
T 2
x 1 x, yK,
C(x) = 0.5 min
< B(x).
max fr 1+" >kr}
Note that C(x) is invertible and its inverse is
if y 2 (y 1+"
c- 2y. (2 Kyy)
14"
if y < (イ 1-
< 2y + (2 (vyKy)) 11
2y + Ly (2T 1 11 1
Taking expectations and using Jensen's incquality gives the stated bound.
25

---

E
Proofs for Section 6
Lemma Let f m - R+ where f inf fxx) Then for any 2 the following are equivalent:
-(x)) - ft < <ef,
f(x)) - pr (x)
Proof.
f(x) - f < cf e f(x) < ((+
f(x) <s
(c+1)
+ f(x) -f (1- c+1 f(z) f()
11-41)
Proposition Suppose is conver, strictly positive, L-self-bounded, and satisfies the quadratic growth condition h(æ)) - ht* 2 + - x²11² where x² = arg min h(x)) is the only fixed point of (y h(y)) h < ht* 8 we have
T (6). Then for any point
(T()) x01| > x x=11
Proof. Let xy be in then by definition of we have
x²11²- = 2 ||,, x=11² Th (gr tz x²) + Ti
0t+1
|1g, 12
2
2
n 11 11
||0, x I12
Th All
[x
xx11 || +
h(xx))
h h(x,)²
| 11?
x= +
|gg.1
2 1
h(r,,)
h(aa)))
2 |
x" 112
+
||00 - x011
||
|gg.
2|1g,1 ||
h(x:)) h² h st-pp then we have by Lemma 4
(1/01-1)+11 +
8L (h(x))) h²))
M(xx))
(h((2s)) - -1))
1
Consequently,
h(xz)
4L (h(x;; - h(xx))
|0 x= x=12
22
[
x=11
2|1g.1
P
I9el
Igel
Where the last inequality follows from h being self-bounded and convex,
1
27. g. 12 < h(xx)) h²* < (g., x. x²) S |1
x=1|
Proposition 6. Suppose h is convex. strictly positive, L-Lipschitz. and has a p-sharp minimum h(x)) h* u|| x=I| where x² arg ming h(x)) is the only fixed point of T (6) Then for any point x E S = ty y # x h(y) h < h" 2L-p we have
(T(x) x01
x
Proof. Let E S then by following similar steps to Lemma we have
1(xx))
(((x)))
2 a1+11
x=1 2 2 ||=,
2=1
||
2=11
9g.1
2 2
26

---

By Lemma we have
h(x))) 11" < h1"
21.
1112L-1) +1
2L (1())))) hh))
h(()))
(1(#4)) h:)
4/(21.-w)
Therefore, by sharpness and Lipschitz property of h, we have
((x,))
L(h(x,) h²)
L|
x"1l 1 x
2 2
1l1g.11
9
Proposition (Cycling and failure to converge). There exists strictly positive smooth and strongly convex function h, and initial point æı such that iterates from update (6) cycle and satisfy the
inequality h Ei= (x) h" 2 for all
Proof. The proof is constructive: consider h - R. update is
+ so h- 1. Observe that the
27
+
1
-1
11+11
2x5
2xz
Now, we want to choose 2 so that we oscillate between possible values.
Set æ1 = cot where has to be determined. The update becomes
x7 -111 cot 0 cot
J2
201
2 cot 0
where in the last equality we used the identity for cot. Hence, have col(2 Given that we want to oscillate between values, we want 2443 = Wt, that is, (2)(2)))) = (2'). We can achieve it if we select / π 777. Indeed, we have
T1 coT(TT/)
12 cot(22//7)
Σ3 cot(44/77)
I4 cot(8 cot(T + 7/7) (oT(TT/7)
Finally, one can verify numerically that f( Ei= x4) f > 0.77.
Proposition 8. There exists subregions within the unstable regions in Propositions 7 and o where the stepsizes are upper bounded.
Proof. By convexity of h we have h- S "g < |1 ||| - x so 11 h(#)-4"
Tæ,-0"
By assumption in Lemmas and the unstable region = {a h(x)) - h" ch*} where depends on the properties of h. Therefore, for æ E S and denoting ah(x)) as any subgradient at æ, we have
h(x)) |g (h(x) ht)²
M[)]|< - x²11 (c+ 10+1)h"m I x²1
(h(x) ht)²
has a sharp minimum, h())) h² /a|l: x²1|, then have h(w) stepsizes are always bounded within S.
c+1 h². Therefore, the a²
|l
Now consider the subregion S₁ {æ: 1((x) ル Eh*} for some k > 1. Consider x E Sk.
that + h)h < h(x)) S (1 + c)h". If statisfies the quadratic growth condition h((x)) h 2
[ 21 then
h(x)) I ?
(c + 1)h 1| x
2 1)h² (h((z) - h*) <
2k(c+1)
99)
(h(x)) h+)a
/AC
Where the last inequality follows since a & Sg. Therefore, stepsize is bounded within Ss. and grows increase k.
D
27

---

Definition 7 (Lusin (N-) condition). Let R - RR. We define T- over set S S R as
(S) {a: T(x) E S}.
We say that T satisfies (N condition for every set E of measure zero we have that T TT((-EE))) (E) also has measure zero.
Lemma 5. Let I R R with unique fixed point x² If xx is unstable, that is, there exists such that x + x² and 1 x=1 S 6, then (T) - x:" > || - x='l- Define T-1 over a set
C R as (S) = (x Txx) S}. If (1x*) is of measure zero for any k, then
lim Hz = x =0 1+000
In other words. the set of initializations that can converge to the fixed point has measure zero.
Proof. We divide IR" into sets, 5 - points that can exactly reach the unique minimizer w². If T* since the countable union of null sets is null set.
}), and its compliment S S represents the (T*(((0))) ({x*) }) is null for every then so
Now we show that for all initializations in 2i E S ! cannot converge to x². Suppose the contrary, lim;-x 3t x². Let B = fy y # x², | x= < 8}. Since 2t + xx there exists a step n where (xth C B. Similarly, there exists n' This is contradiction as we have that || - 2*1 < ||x+11 x*I| < .... < || - x*1|. Therefore, the initializations that allow for E, xx coincide exactly with the null set S.
where | x² | -x==x= for all 2 n'.
28


Reviews:
[{"review_id": "evxbBlB9ZX", "reviewer": "Reviewer_fAec", "summary": "The authors study the Polyak method for optimizing a convex function f.  The authors note that from prior work, the Polyak method has qualitatively different convergence guarantees under various assumptions: for instance when f is convex/smooth convex/smooth strongly convex previous work showed 1/sqrt(T), 1/T, and linear convergence rates respectively.  These convergence guarantees look different, and use somewhat techniques.  The authors ask whether these convergence results can be unified under a single framework.\n\nSuprisingly, they can be.  Specifically, they consider the \"surrogate\" function phi = (f - f^*)^2. When f is convex, they observe that phi has the $\\|g_y\\|^2$-LSUC property around $y$, so that the Polyak step size from y is just the inverse of the LSUC constant at y. Now using a simple convergence lemma that they prove for such step sizes (Lemma 1), they are able to deduce a variety of convergence results under various assumptions on f.\n\nThey also show how to extend their results to both the stochastic setting, and where only a lower bound of f^* is known.  Finally they prove a variety of lower bounds for Polyak methods, for example showing that the fixed points are unstable when the lower bound on f^* is not tight, and the step sizes are not appropriately clipped.", "questions": "1. It seems that the current approach is mainly using properties of phi, rather than f.  Is there hope of getting improved convergence result for Polyak in some situations where phi is convex, but f is not? (This might be a bit a niche, but I am not aware of such results.)\n\n2. “Similarly, it is equally easy to obtain rates for Hölder-smooth functions. ”\nI think it would be nice to state this explicitly in the main text.\n\nInequality at the end of section 4.  As a sanity check, the stated bound seems to imply that $(s^2/G^2 - 1/2)\\|x_t - x^*\\|^2 \\leq \\|x_{t+1} - x^*\\|^2,$ which woiuld mean that $s^2/G^2 \\leq1/2.$ I’m likely missing something, but I don’t see why this should be true without extra assumptions.  Can the authors clarify? \n\n------- minor comments ------\n- adaptiveto -- missing space\n- Eq 1 -- this is the Polyak step rather than the stepsize\n- \"pionnering\"\n- Definition 1 -- should add a quantifier for x.  Is this a local condition, or for all x?\n- Definition 2 -- check notation; x is doubly overloaded and g isn't defined.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Overall, I thought that this was a nice paper that sheds some interesting light on the Polyak method.  The main observation of the paper is that the Polyak method can be viewed as gradient descent on the surrogate function phi(x) = f(x)^2.  On the one hand, this is a fairly straightforward obsevation.  However it's memorable, and I think it should be more widely known, since it's a nice organizing principle for Polyak.\n\nThe main point of this observation is to streamline the convergnece anlayses for Polyak under a variety of assumptions of f.  The successfully achieve this by analyzing convergence of phi with step size given by 1/(LSUC constant).  This main result is given in their Lemma 1.  I suspect that a version of Lemma 1 could be rewritten directly in terms of f, and that this would give a similarly general result that could be applied for various f to obtain the main results.  So I'm not completely clear on whether considering the surrogate is entirely crucial here.  With that said, I think Lemma 1 is more naturally applied to phi, so I like the results as stated.  Working with phi is just perhaps more of an organizing principle than something that will lead to new convergence results that couldn't easily be obtained otherwise.\n\nI thought the negative results were nice.  These really seem to be an improvement over existing work.", "was_revised": true, "final_justification": "The authors gave a reasonable response and my general assessment of the paper remains the same after reading the other reviews.  I think the observation that Polyak can be analyzed as gradient descent on a surrogate fuction is nice, and seems to unify various convergence results.  I think that this would be broadly interesting to an ML audience.", "rebuttal": "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”.\n\n- Is there hope of getting improved convergence results for Polyak in some situations where $\\phi$ is convex, but $f$ is not? \n\nYes! 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.\n\n- Rates for Hölder-smooth functions\n\nWe can add them, they are an immediate corollary of Theorem 7 in the Supplemental Material.\n\n- Inequality at the end of section 4\n\nIt’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."}, {"review_id": "hWoLJ7We15", "reviewer": "Reviewer_xpPF", "summary": "This paper investigates the Polyak stepsize, a stepsize selection rule that has recently gained attention in the context of (stochastic) gradient descent. The authors point out that the gradient method with the Polyak stepsize can be interpreted as a simple gradient method applied to a surrogate function incorporating local curvature. Based on this perspective, they provide a unified analysis of (stochastic) gradient descent with the Polyak stepsize under various assumptions on the objective function. This analysis encompasses many existing results in the literature. In addition, the paper presents some negative results, such as the failure of the Polyak stepsize when the optimal value is inaccurately estimated.", "questions": "This is a question driven purely by personal curiosity: 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?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**  \n- The paper addresses stepsize selection, a fundamental and important topic in this field.  \n- The perspective is novel and thought-provoking. While the proofs appear simple, the idea of introducing a surrogate function is likely nontrivial.\n- It provides a unified analysis that encompasses many existing results.  \n- It clearly shows that the failure of the Polyak stepsize under violated assumptions stems from intrinsic limitations of the stepsize itself, rather than from shortcomings of the analytical technique.\n- The manuscript is well-written and easy to follow.\n\n**Weaknesses**  \n- Although the paper offers a new interpretation that may serve as a foundation for future developments, it does not appear to provide techniques that are directly useful in practice.", "was_revised": true, "final_justification": "- While the proofs appear simple, the idea of introducing a surrogate function is likely nontrivial.\n- It provides a unified analysis that encompasses many existing results.\n- Although the paper offers a new interpretation that may serve as a foundation for future developments, it does not appear to provide techniques that are directly useful in practice.", "rebuttal": "We thank the reviewer for the feedback and for recognizing the value of our paper.\n\n- 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?\n\nWe 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."}, {"review_id": "hFkyalM8vi", "reviewer": "Reviewer_qnH4", "summary": "**Summary**\n\nThis paper establishes a new perspective on the Polyak stepsize in convex optimization. The idea is to consider a transformation of the original objective $\\frac{1}{2}[f(x) - f(x^\\star)]^2$, which inherits convexity from $f$ and naturally satisfies certain local curvature conditions. The authors demonstrate that gradient descent using the Polyak stepsize can be viewed as gradient descent on the transformed objective. The convergence analysis of the Polyak stepsize is established using this transformed objective in different settings, and some connections with previous literature on stochastic Polyak stepsize (SPS) are also discussed. Some negative results, including counterexamples, are presented to demonstrate the cost of not knowing the optimal value $f^\\star$.", "questions": "**Questions**\n\n1. Could you provide an example of a nonsmooth function that satisfies Definition 2?\n2. On line 140, could you elaborate more on why $\\phi(x_t) \\rightarrow 0$ implies the last iterate converges?\n3. On line 152, the quadratic growth condition misses a constant $\\frac{1}{2}$; if you take $s = G = 1$ (e.g. $f(x) = |x|$), then the inequality becomes invalid.\n4. In section 5, the function $h$ is defined as a general convex function. Is it necessary for $h$ to take the form of $(f(x) - a)_+$?  I did not find any restriction that $h$ should be relevant to $f$ at all, except that it is a nonnegative convex function. For example, taking $h(x) = 0$ would be a valid choice according to the discussion, but it does not yield a meaningful convergence guarantee.\n5. It is claimed on line 225 that \"[1] does not prove a guarantee for the nonsmooth setting\". However, in Section 3.7 of [1], it is mentioned that results for the nonsmooth case are established in the appendix. \n6. On line 269. Could you be more detailed about the mentioned example from [2]?\n\n**Minor issues**\n\nPlease carefully proofread the paper.\n\n1. Line 29\n\n   adaptiveto => adaptive to\n\n2. Line 87\n\n   The definition of $L$-smoothness is not correct. Nonsmooth concave function also satisfies the bound.\n\n3. Line 116\n\n   Please be consistent with $f$ and $f(x)$ in the theorem statement.\n\n4. Line 102, 120, 166\n\n   Please be consistent with $g \\in \\partial f(x)$ or $g_x \\in \\partial f(x)$\n\n5. Line 129\n\n   \"Let $\\phi$ convex\" is not clear; $\\phi$ is convex by the composition rule of convex functions. \n\n6. Line 131\n\n   \"summing this inequality over time\" is not clear\n\n7. Line 133\n\n   $g_t$ and $g_{x_t}$ are inconsistent\n\n8. Line 134\n\n   \"Now we use ... we obtain\" is not clear\n\n9. Line 161\n\n   positive => nonnegative\n\n10. Line 164\n\n    The wording in definition 3 and 4 are inconsistent: e.g., say/will say; star-upper-curvature/star upper curvature\n\n11. Line 173\n\n    Missing $($\n\n12. Line 175\n\n    Why not directly use $x^\\star = \\arg \\min \\psi(u)$?\n\n13. Algorithm 1, Line 3\n\n    Tranform => Transform\n\n14. Line 177, around Line 250\n\n    $\\lambda_t$ => $\\lambda_{x_t}$ according to definition 4\n\n15. Line 179\n\n    tells => tell\n\n16. Line 213\n\n    $\\xi$  and its bold face are inconsistent\n\n17. Line 250, Line 305\n\n    Paragraph titles are inconsistent\n\n18. Line 263\n\n    $T$ is used for both the operator and the total iteration count\n\n19. Line 264\n\n    The concept of clipping has not been introduced here\n\n20. Line 243\n\n    $x$ should be bold face\n\n21. Line 291\n\n    Inconsistent bold face issue again\n\n22. Line 300\n\n    The Lusin$(N^{-1})$ property only appears once in the paper without proper definition\n\n23. Line 304\n\n    under estimation => underestimation\n\n24. Line 306\n\n    $\\min_x h(x, \\xi) = 0$ is not clear\n\n25. Line 763\n\n    Bold face issue \n\n26. Appendix\n\n    $f^\\star$ is inconsistent  with $f(x^\\star)$ used in the main paper\n\n27. Line 779\n\n    functions => function\n\n**References**\n\n[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.\n\n[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.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\nThis paper is overall well-written and provides an interesting new perspective on the Polyak stepsize. The results are supported by theoretical analysis. The motivation of the paper is clear, with theoretical results also connected to previous literature on SPS.\n\n**Weaknesses**\n\nAlthough I believe that the results in the paper provide new insights into the Polyak stepsize, I find the paper's presentation to be unsatisfactory:\n\n1. Lack of practical algorithmic improvement\n\n   Although the paper provides new insights into the Polyak stepsize and provides Algorithm 1 as a general template for new algorithmic variants, it lacks an in-depth discussion on whether these new variants are practically competitive. I recommend that the authors consider providing at least one instance of Algorithm 1 that has not appeared in the literature before and test it on toy examples. Otherwise, this perspective is of only theoretical interest.\n\n2. There are a number of notation inconsistencies and typos in the paper. See minor issues and questions for more details. \n\nOverall, I think the paper provides valuable insights into Polyak stepsize. However, given the issues above, I recommend borderline rejection, and I'm willing to raise my score if my concerns are addressed.", "was_revised": true, "final_justification": "Overall, I raise my score to 4 given that the authors fix the typos/notation issues in the revision. But I'm still concerned that the paper fails to demonstrate new algorithmic improvements/variants. In particular, the counterexample does not rely on this new perspective, so the importance of the first part of the paper is not clear. I'm willing to raise my score further if the authors make (even preliminary) attempts in this direction, otherwise this paper remains borderline to me, \n\n**Other minor issues**\n\n1. Last iterate convergence\n\n   This is more a consequence of Fejér monotonicity rather than just $\\phi(x_t) \\rightarrow 0$. Please clarify in the revision\n\n2. In the revision, please add additional clarifications on 1) the requirement on the design of $h$ 2) the nonsmooth result compared to the SPS literature.", "rebuttal": "We thank the Reviewer for carefully going over our paper. In particular, we will fix all the typos and minor mistakes in our notation.\nIn the following we answer to the Reviewer’s questions\n\n1. Lack of practical algorithmic improvement, this perspective is of only theoretical interest.\n\nActually, writing a paper of “theoretical interest” was exactly our aim. \nMoreover, the call for papers of NeurIPS explicitly says\n“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.”\nWe agree that reviewers have freedom to interpret the reviewing guidelines, but we would still appreciate a more faithful interpretation.\n\n1. Could you provide an example of a nonsmooth function that satisfies Definition 2?\n\nAn easy example is in line 108: $f(x)=|x+2|+x^2/2$.\nWe 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$.\nOne can verify, for example by plotting the inequality, that this function is self-bounded for L=9 and not-smooth.\nIn 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$.\n\n2. On line 140, could you elaborate more on $\\phi(\\boldsymbol{x}_t)\\to 0$ why implies the last iterate converges?\n\nThank 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]).\n\n3. On line 152, the quadratic growth condition misses a constant\n\nCorrect, it is a typo.\n\n4.  What are the conditions on h in Section 5?\n\nThe 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$.\n\n5. [1] has results for the nonsmooth case\n\nIn 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}$.\n\n6. Example from [2]\n\nThe 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.\n\n\n[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.\n\n[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.\n\n[Beck 17] Beck, Amir. First-order methods in optimization. Society for Industrial and Applied Mathematics, 2017."}, {"review_id": "k6fmKfMAao", "reviewer": "Reviewer_AKhF", "summary": "This paper sheds light on the Polyak step size by relating it to gradient descent with curvature-inspired step sizes on a surrogate function. This connection is used in order to provide negative results for Polyak step sizes, for example in the stochastic setting without interpolation, or when the optimal value is underestimated.", "questions": "- From the definition of the subgradients, it seems that only convex $f$ are considered, but the introduction remains unclear on this.\n- I think the statement of Lemma 1 is unprecise: first, the LSUC assumption is actually needed for $\\phi$ and not $f$ as stated. Second, the Lemma also uses the fact that $\\phi(x^*)=0$, but this assumption is not mentioned. Finally, the proof uses the notation $g_t$ and $g_{x_t}$ which in my understanding denote the same vector.\n- line 153: I get to the linear rate $1-\\frac{2s^2}{G^2}$ which somehow could be negative if $s^2 = G^2$. What am I missing?\n- line 179: \"The last two lemmas tells us that the properties of the surrogate functions breaks if $\\psi(x*) \\neq 0$.\" Which properties are meant here exactly? Can you elaborate how this can be seen from the Lemmas?\n- Theorem 3: Do you need to assume that $h$ is jointly convex in the two arguments? Convexity in $x$ should be sufficient.\n- I am not sure if the second part of Remark 1 is correct: consider $\\xi$ having two possible values and $f_1(x)=|x-1|$ and $f_2(x)=|x+1|$. Then $a=0$ satisifies the condition, but if $x^* $ is the minimizer of $1/2 (f_1 + f_2)$, then for one of the two $\\xi$ we have $h(x^*,\\xi) > 0$. \n- line 225: This is not correct; the paper by Loizou et al. has results for the nonsmooth setting in the Appendix C.1. (However they only have results where the SPS step size is not capped at $\\gamma$).\n- line 266: I could not find a Proposition 5 neither in the main text nor in the appendix\n\nMinor:\n\n- line 29: \"adaptive to\" missing space\n- line 60: Incomplete sentence\n- line 83: \"they will BE denoted\"\n- line 89: \"Note that IF\"\n- line 97: \"chain rule of subgradients\". Maybe better to say \"chain rule of convex subgradients\" as there are notions of subgradients that do not follow a chain rule.\n- line 140: \"the last iterate will converge\". I think it is more accurate to say \"the function values converge to zero\" (here the optimal value of $\\phi$ is zero, see above)", "limitations": "NA", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- The results of Section 6 are interesting, showing that the negative results are not an artefact of the analysis. They shed a lower-bound-type insight on the empirical observations that Polyak step sizes are less powerful for non-interpolating problems.\n- The connection to the surrogate function could explain the adaptivity of the Polyak step size (see also Weaknesses below). \n\n**Weaknesses:**\n\n- Some of the formal statements of the paper need to be formulated more precisely in order to avoid confusion (see below for details).\n- From the connection to the surrogate function, some points remains open: why is it seemingly beneficial to adapt to the curvature of the surrogate function? Does it explain the dynamics of the Polyak stepsize in practice (for example, it has been observed that the Polyak step size often warms up and then decays for ML problems)?\n- On the conclusion:\n\t>  We believe this framework has the promise to design new variants, by simply designing surrogate functions with the required properties.\n\nThis sounds promising, but in fact all surrogate functions discussed in the paper have been previously proposed (which is also mentioned in the paper). No attempts are made to explore new surrogate functions beyond the existing ones. The paper would benefit a lot in my opinion from such explorations (which could be tested by experiments); currently, it remains unclear whether the connection to surrogate function is useful beyond proving negative results.\n\n- The paper makes a few considerations which could be analyzed beyond the theory: for example, it mentions that non-convex problems are harder to analyze theoretically. However, it could be investigated through experiments if the presented limitations of Polyak step sizes can be observed also on non-convex problems (e.g. cycling behaviour due to underestimation in the deterministic case). Another interesting direction would be the proposed rule of $a= \\sup_\\xi \\inf_x f(x,\\xi)$. How does this rule perform in a practical setup (constructed such that $a$ can be computed)? Can we estimate $a$ somehow on the fly? In short: I am not proposing to add experiments for the sake of having experiments, but because they could clarify and complete the story of the paper. \n\n- If I understand correctly, the conclusion says that the neighborhood of convergence is unaviodable without interpolation. This is not accurate: the paper [17] shows that the convergence rates are achieved in the smooth and non-smooth case even without interpolation, but assuming that we know $f(x^*,\\xi)$ for all $\\xi$ (which of course is a very strong assumption, but it is not the same as unavoidable).", "was_revised": true, "final_justification": "In the discussion period some smaller points of confusion have been clarified. However, I remain the borderline score as the main weaknesses mentioned in the initial review remain open: it is far from obvious how to use the framework of this paper to design better practical Polyak stepsize variants. Can the surrogate function viewpoint explain the Polyak stepsize dynamics that occurr for the problems of interest (i.e. ML training problems)?", "rebuttal": "- it remains unclear whether the connection to surrogate function is useful beyond proving negative results.\n\nThis 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.\n\n- the conclusion says that the neighborhood of convergence is unavoidable without interpolation\n\nThis is not what we meant. We wrote “We demonstrate that this neighbourhood is not avoidable\nand 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.\nWe believe that this is a very important point that is possibly misunderstood by many people in this field.\n\n-  it seems that only convex function are considered\n\nCorrect, we will make it more clear.\n\n- Typos in Lemma 1\n\nYou are correct, we will fix them.\n\n- Rate for sharp functions\n\nAs the other reviewers also found, there is a typo, a missing “1/2\" in the first two terms of the inequalities\n\n- Which properties do not hold if $\\psi(x^*)\\neq 0$?\n\nIn 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.\n\n- Convexity of h in Theorem 3 is only required for x\n\nCorrect! We will add it.\n\n- second part of Remark 1\n\nSorry that is a weird typo, we meant $a = \\sup_\\xi f(x^*,\\xi)$.\n\n- the paper by Loizou et al. has results for the nonsmooth setting in the Appendix C.1\n\nAt 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 \n $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}$\n\n- Where is Proposition 5?\n\nTypo, it should be Lemma 5 (as you can see from the hyperlink in the pdf).\n\n- \"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)\n\nThank 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. \n\nThe 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]).\n\n[Beck 17] Beck, Amir. First-order methods in optimization. Society for Industrial and Applied Mathematics, 2017."}]

Author rebuttal:

Meta-review: The paper at hand proposes novel theoretical perspectives on (stochastic) Polyak stepsizes. The paper is pleasant to read, and the authors take us step-by-step into an interesting correspondence between PS and direct optimization of a surrogate function with the same minimizer, but interesting curvature properties to which PS directly adapts. 

All reviewers agree that the paper is correct and interesting for the optimization community, and hence I recommend accepting this for the conference. 

However, I believe the authors should take the following points into account for the camera-ready:

1) As suggested by Reviewer AKhF, I would strongly recommend placing illustrations and toy simulations in the paper to guide the reader through the text and the derivations. Especially, this would enhance the intuition around the curvature adaptations claims. I also agree with Reviewer AKhF that exploring new surrogate functions and understanding the effects of choosing such functions would be highly desirable. The authors may be able to expand a bit on this in their revision.

2) I would include a few more citations linking the Polyak stepsize to surrogate functions (e.g., squaring the loss), in particular [A,B] below.

3) Improve clarity: I think it might be helpful to actually structure a bit more the contribution section, to better guide the reader in the exploration of your work.

[A] Chen, Pei. "Hessian matrix vs. Gauss–Newton hessian matrix." SIAM Journal on Numerical Analysis 49.4 (2011): 1417-1435.
[B] Orvieto, Antonio, and Lin Xiao. "An adaptive stochastic gradient method with non-negative Gauss-Newton stepsizes." arXiv preprint arXiv:2407.04358 (2024).
Decision: Accept (poster)