Parameter-free Clipped Gradient Descent Meets Polyak
Authors: Yuki Takezawa
Han Bao
Ryoma Sato
Kenta Niwa
Makoto Yamada
Venue: NeurIPS 2024 poster (2024)
Keywords: Polyak stepsize
clipped gradient descent
generalized smoothness
Primary area: optimization
TL;DR: We proposed parameter-free methods whose convergence rate is asymptotically independent of $L$ under $(L_0, L_1)$-smoothness

Abstract: Gradient descent and its variants are de facto standard algorithms for training machine learning models. As gradient descent is sensitive to its hyperparameters, we need to tune the hyperparameters carefully using a grid search. However, the method is time-consuming, particularly when multiple hyperparameters exist. Therefore, recent studies have analyzed parameter-free methods that adjust the hyperparameters on the fly. However, the existing work is limited to investigations of parameter-free methods for the stepsize, and parameter-free methods for other hyperparameters have not been explored. For instance, although the gradient clipping threshold is a crucial hyperparameter in addition to the stepsize for preventing gradient explosion issues, none of the existing studies have investigated parameter-free methods for clipped gradient descent. Therefore, in this study, we investigate the parameter-free methods for clipped gradient descent. Specifically, we propose Inexact Polyak Stepsize, which converges to the optimal solution without any hyperparameters tuning, and its convergence rate is asymptotically independent of $L$ under $L$-smooth and $(L_0, L_1)$-smooth assumptions of the loss function, similar to that of clipped gradient descent with well-tuned hyperparameters. We numerically validated our convergence results using a synthetic function and demonstrated the effectiveness of our proposed methods using LSTM, Nano-GPT, and T5.

Parameter-free Clipped Gradient Descent Meets Polyak
Yuki Takezawa 1.2, Han Bao!.2, Ryoma Sato Kenta Niwa*, Makoto Yamada² Kyoto University, 2OIST, NNII, 'NTT Communication Science Laboratories
Abstract
Gradient descent and its variants are de facto standard algorithms for training machine learning models. As gradient descent is sensitive to its hyperparame- ters, we need to tune the hyperparameters carefully using grid search. However, the method is time-consuming, particularly when multiple hyperparameters exist. Therefore, recent studies have analyzed parameter-free methods that adjust the hyperparameters the fly. However, the existing work is limited to investigations parameter-free methods for the stepsize, and parameter-free methods for other hyperparameters have not been explored. For instance, although the gradient clip- ping threshold is crucial hyperparameter in addition to the stepsize for preventing gradient explosion issues, none of the existing studies have investigated parameter- free methods for clipped gradient descent. Therefore, in this study, we investigate the parameter-free methods for clipped gradient descent. Specifically, we propose Inexact Polyak Stepsize, which converges to the optimal solution without any hy- perparameters tuning, and its convergence rate is asymptotically independent of L. under T-smooth and (Lo, I, -smooth assumptions of the loss function, similar to that of clipped gradient descent with well-tuned hyperparameters. We numerically validated our convergence results using a synthetic function and demonstrated the effectiveness of our proposed methods using LSTM, Nano-GPT, and T5.
1 Introduction
We consider the convex optimization problem:
min fxx)
(I)
=ERd
where the loss function convex and lower bounded. In this setting, gradient descent and its variants (Duchi et al., 2011 Kingma and Ba 2015) are the de facto standard algorithms to minimize the loss function. The performance of the algorithm highly sensitive to the hyperparameter settings, necessitating the careful tuning of the hyperparameters to achieve best performance. More specifically, when the loss function is L-smooth, gradient descent can achieve the optimal convergence rate
O -1110 =="""" when set the stepsize to & where To is the initial parameter and x" is the optimal solution [Nesterov] 2018). Unfortunately, parameter L is problem-specific and unavailable in practice. Thus, gradient descent must be executed in many times with different hyperparameters identify the good hyperparameter settings, which a very time-consuming process. Notably, when multiple hyperparameters are under consideration, this hyperparameter search becomes computationally more demanding.
Several recent studies have examined parameter-free methods for tuning hyperparameters the fly
(Berrada et al. 2020; Defazio and Mishchenko, 2023 Orvieto et al. 2022 Jiang and Stich 2023
Ivgi et al. 2023 Khaled et al. 2023 Orabona and Tommasi 2017: Carmon and Hinder 2022
We use parameter-free methods to describe algorithms that provably converge to the optimal solution without any problem-specife. parameters for setting their stepsizes and other hyperparameters.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

These methods automatically adjust the stepsize during the training and are guaranteed to converge to the optimal solution without tuning the stepsize. In other words, the stepsize did not require tuning using the grid search. However, the existing parameter- frreeeer-reeeeeeeee methods only focus on the stepsize, and parameter-free methods for other hyperparameters have not been explored. For example, in addition to the stepsize, the gradient clipping threshold is an important hyperparameter for training language models (Pascanu et al. 2013 Zhang et al.) 2020a
Clipped gradient descent can achieve the convergence rate O -a under the assumption
T
that the loss function is (Lo. L -smoooth when we use the optimal stepsize and gradient clipping threshold (Koloskova et al. 2023). 9. In many cases, Lo is significantly smaller than L (Zhang et al.
2020b Thus, by comparing with the convergence rate of gradient descent O - T = ). gradient clipping often allows gradient descent converge faster. However, we must carefully tune two hyperparameters, stepsize and gradient clipping threshold, to achieve this convergence rate. If the gradient clipping threshold is too large, the gradient clipping fails to accelerate the convergence. Moreover, if the gradient clipping threshold is too small, gradient clipping deteriorates rather than accelerating the convergence rate. Can develop parameter-fre method whose convergence rate is asymptotically independent of L under (Lu, L1) 1 smooothess?
In this study, we investigate parameter-free method for clipped gradient descent. First, we provide the better convergence rate of Polyak stepsize (Polyak 1987) under (To, I. )smmoohnness. We discover that the convergence rate of Polyak stepsize matches that of clipped gradient descent with well-tuned stepsize and gradient clipping threshold. Although the convergence rate of Polyak stepsize is asymptotically independent of L under (Lo, L1) L-m-shothh assumption as clipped gradient descent, still requires the minimum loss value, which is a problem-specífic value. Thus, we make Polyak stepsize parameter-free without losing this property under (Lo, L1) L -smoothhness by proposing Inexact Polyak Stepsize, which converges to the optimal solution without any cobble--specfii parameters. We numerically evaluated Inexact Polyak Stepsize using synthetic function and neural networks, validating our theory and demonstrating the effectiveness of Inexact Polyak Stepsize.
2 Preliminary
2.1 Gradient descent & L-smoothness
One of the most fundamental algorithms for solving Eq. ( represents the gradient descent:
Fz-1 = xy T/ (
where To E Rd is the initial parameter and > 0 is the stepsize at t-th iteration. To ensure that gradient descent converges to the optimal solution quickly, we must carefully tune the stepsize тк- When the stepsize is too large, the training collapses. By contrast, when the stepsize is too small, the convergence rate becomes too slow. Thus, we must search for a proper stepsize as the following theorem indicates.
Assumption 1 (T-smoothhesss). There exists constant I. O that satisfies the following for all x, y E Rd:
[V - vf(y)) S - yyl
(2)
Theorem Nesterov 2018
Corollary 2.1.2)). Assume that is convex and L-smooth, and there
exists an optimal solution x²' satisfies
= arg min f(x). Then, gradient descent with stepsize 17s L.
( [_11200 - xx112)
10000xx111
S So
T
where ā= = ET- x, and T is the number of iterations.
2.2 Clipped gradient descent & (Lo, L, -mmoohhnes
Gradient clipping is widely used to stabilize and accelcrate the training of gradient descent (Pascanu ct al. 2013 Devlin et al. 2019). Let > 0 be the threshold for gradient clipping. Clipped gradient
descent is given by:
Tt+1 2t - Th min {1,
Vf(x.).
(4)
2

---

Many prior studies investigated the theoretical benefits of gradient clipping (Koloskova et al. 2023 Zhang al., 2020a Li and Liu 2022 Sadiev et al. 2023). Zhang et al. (2020b) experimentalyy found that the gradient Lipschitz constant decreases during the training of various neural networks and is highly correlated with gradient norm ||V (a) [|. To describe this phenomenon, Zhang et al. (2020a) introduced novel smoothness assumption called (Lo, sm)-smoohsesss. Then, it has been experimentally demonstrated that the local gradient Lipschitz constant Lg is thousands of times smaller than the global gradient Lipschitz constant L.
Assumption 2 (LLo L >-smoothness). There exists constants Lo 0 and L1 that satisfy the following for all y E Rd with ||æ
yll S :
[V)()) V [())l] S (To + [=]\[())) -
(5)
Note that (Lo, L1)- smmotthessss is strictly weaker than L-smoothness because (Lo, L1 -m)osmhnssssss covers L-smoothness by taking L1 = Using the (Lo. smmsothhssssss assumption, the convergence rate of clipped gradient descent
established as follows.
Theorem 2 (Koloskova al. 2023 Theorem 2.3)). Assume that f is convex, T-smooth, and (Lo, smooohh, and there exists an optimal solution x² == arg min f(x). Then, clipped La satisfies:
gradient descent with q La
1 and e
L1
Lo Do 1012
LL xo x*11+
f(ā) - f(x'(()=)))))))))))) =0 50
(6)
T
where ã = ΣT= 22 and the number of iterations.
When the number of iterations T is large, the first term O -ol|mo-==11 becomes dominant, and the convergence rate of clipped gradient descent is asymptotically independent clipping allows for the use of a larger stepsize, and thus, gradient descent converges faster because of Lo < L. We can interpret L Lo + L1 sup, [[Vf(=)] The stepsize of gradient descent in Theorem is T. sup, [==]] which is typically very small. By comparing with gradient descent, the coefficient multiplied by the gradient of clipped gradient descent in Theorem 2 is min Lo [(= }. which is larger than Lo+L, sup, [=)] Specifically, when parameter æ is is small), clipped gradient descent can use larger stepsize and then reach the optimal solution faster than gradient descent.
Gradient
close the optimal solution x* (i.e., [ [=x) |
2.3 Polyak stepsize
When f is convex, I++1 and generated by gradient descent satisfy || x=11 < ||,; 1=1 2m - f(x)(())))))))))))))))))))))ff + n V /f(x))) By minimizing the right-hand side, we can derive well-known
Polyak stepsize Polyyk 1987)
f(x,) f*
(7)
[2+))1
where ====f(x)) When is L-smooth, gradient descent with Polyak stepsize converges to the optimal solution as quickly as gradient descent with 17- 1
Theorem 3 (Hazan and Kakade (2019) Theorem I)), Assume that f is convex and L-smooth, and there exists an optimal solution
arg min f(x). Then, gradient descent with Polyak
stepsize Eq. 7 satisfies:
L [l x=
f 5
(8)
where o= = = 2, and T is the number of iterations.
In addition to the L-smooth setting, Polyak stepsize is known cause gradient descent to converge to the optimal solution with the optimal rate among various settings, e.g., non-smooth convex, smooth convex, and strongly convex settings HHzan and Kakade, 2019).
3

---

Improved convergence result of Polyak stepsize
Before proposing parameter-free method for clipped gradient descent, in this section, we present new convergence analysis of Polyak stepsize under (Lo, L1)-smmothhesss Surprisingly, our new analysis reveals that Polyak stepsize achieves exactly the same convergence rate as clipped gradient descent with appropriate hyperparameters. A bunch of prior studies established the convergence rates of Polyak stepsize, and it well-known that Polyak stepsize allows gradient descent converge as fast as the optimal stepsize. However, our theorem finds that Polyak stepsize achieves faster convergence rate than gradient descent with the optimal stepsize as clipped gradient descent, and none of the existing studies have found this favorable property of Polyak stepsize.
3.1 Connection between Polyak stepsize and clipped gradient descent
Under (Lg, L1) smoothness, we can obtain the following results. Proposition 1. Assume that f is convex and (Lu, L1) -smooth. Then, Polyak stepsize Eq. 7 satisfies:
[ax)) - 5
min ALo 4LIIVV[(+:)]
(9)
Proof.
Assumption and Lemma
2 iiply
f(x)) 2( + I [(())()))))))))))))))))))))))))) [V
When [IV <
Lo Ey
Polyak stepsize is bounded from below by Tho"
1.
When [V[[
2 L. we
have
1
2(Lo + L[()(()))))
4L1 /f+',)||
Therefore, can conclude the statement.
Under L-smoothness, the lower bound of Polyak stepsize was obtained as follows.
Proposition 2 (Jiang and Stich (2023 Lemma 15)). Assume that f is convex and L-smooth. Then, Polyak stepsize Eq. 77) satisfies:
(xx) - [V+((=))
2L S
(10)
By comparing Propositions 1 and Proposition D shows that Polyak stepsize does not become excessively small when the parameter approaches the optimal solution (i.e., || f(x]] approaches
zero), similar clipped gradient descent. If we choose the stepsize and gradient clipping threshold as in Theorem 2 clipped gradient descent can be written as follows:
D++1 = Iz
min
Lo f Vf(x)).
(11)
Thus, Proposition [iimliis that Polyak stepsize can be regarded as internally estimating the hyperpa- rameters for clipped gradient descent, as shown in Theorem 2
3.2 Convergence analysis of Polyak stepsize under (To, Ta) sm)sshmohsssss
Based the relationship between Polyak stepsize and clipped gradient descent in Sec. 3.1 provide a new convergence result for Polyak stepsize under (Lo, Ia smmootheesss The proof is deferred to A
Theorem 4. Assume that J is convex, L-smooth, and (Io, Im)-smooth, and there exists op- timal solution x= = arg mingera f(æ). Let T be the number of iterations and define T = arg minloger-11 f(x1). Then, gradient descent with Polyak stepsize Eq. (7 satisfies:
f(x,) f(x²) s 00
(Loolll [oo
x
LL
xo
x
(12)
T
T

---

the convergence rate of Polyak stepsize is the same as that of clipped gradient descent. Thus, Polyak stepsize can converge faster than the optimal stepsize given in Theorem [ when To < L. Many prior studies analyzed the convergence rate of Polyak stepsize and discussed the relationship between Polyak stepsize and gradient descent with the optimal stepsize (Polyak) 1987 Loizou et al. [202T] Galli et al. 2023) Berrada et al. (020). However, they only recognized Polyak stepsize as making gradient descent converge with the same convergence rate as the optimal stepsize, and none of the prior studies have found this relationship between Polyak stepsize and clipped gradient descent. Our new convergence result is the first to discover that the Polyak stepsize can achieve the same convergence rate not only gradient descent with an appropriate stepsize but also as clipped gradient descent with an appropriate stepsize and gradient clipping threshold.
By comparing Theorem with Theorem 2
4 Making clipped gradient descent parameter-free
In the previous section, we found that the convergence rate of Polyak stepsize is asymptotically independent of L under (Lg, -moothhsssssss as clipped gradient descent with appropriate hyper- parameters. However, Polyak stepsize requires the minimum loss value f", which is a problem- specific parameter. In this section, we propose a method that can remove the prior knowledge of I' from Polyak stepsize without losing the property of asymptotic independence of L under (1 smsooothsssss
4.1 Inexact Polyak Stepsize
To make Polyak stepsize parameter-free several prior studies have proposed the use of lower bound of f* instead of f* (Loizou et al., 202T] Orvieto et al., 2022 Jiang and Stich 2023). The loss functions commonly used in machine learning models are non-negative. Thus, the lower bound of f trivially obtained as zero and is not a moblem-speciffe parameter. By utilizing this lower bound, straightforward approach make Polyak stepsize independent of problem-specific parameters is replacing f* Polyak stepsize with the lower bound as follows:
f(x)) 1
T/:
(13)
However, the stepsize in Eq. (33) becomes excessively large as the parameter approaches the optimal
solution, and does not lead to the optimal solution [oiizou et al. 2021). This is because |/ f (xx))
approaches zero, while (a:,) - 1' approaches f* 7*(> 0). which makes the stepsize in Eq. (13
excessively large the parameter approaches the optimal solution. To mitigate this issue, DecSPS (Orvieto et al. 2022) and AdaSPS (Jiang and Stich| 2023). which are parameter- free methods based on Polyak stepsize that use |* instead of f*, make the stepsize monotonically non-increasing to converge to the optimal solution.
However, making the stepsize monotonically non-increasing loses the fruitful property that the convergence rate of Polyak stepsize is asymptotically independent of L as clipping gradient descent under (Lo L1) -ss-shooesssss. This is because Polyak stepsize and clipped gradient descent make the convergence rate asymptotically independent of by increasing the stepsize when the parameter approaches the optimal solution. In fact, we evaluated DecSPS and AdaSPS with synthetic function Sec. 6.1 demonstrating that the convergence deteriorates as increases.
Algorithm Inexact Polyak Stepsize
Input: The number of iterations and lower bound [*.
2: phest x best +- f Zg.
3: for t 1.. f(x.)-1-
do
4: I++1 x Iz vT f( Vf(x))
5: if f( i pheat then
6: pbest best 11,
7:
return best
5

---

To address this issue, we propose Inexact Polyak Stepsize, whose details are described in Alg. | As discussed above, we cannot make the stepsize decrease maintain the asymptotic independence of I, under (Lo, sm)-smootsssss. Thus, we set the stepsize as follows:
= f(x+)
(14)
where 7 denotes the number of iterations. Instead of making the stepsize decrease, we propose returning the parameter for which the lowest loss achieved as the final parameter.
4.2 Convergence analysis of Inexact Polyak Stepsize
The following theorem provides the convergence rate of Inexact Polyak Stepsize. The proof is deferred to Sec.
Theorem 5. Assume that is convex, I-smooth, and (Lo, IA) -mm-shothh, and there exists an optimal
solution x² == arg min f(xx). Let T be the number of iterations and o² = - l. Then, æ
generated by Alg. satiiffis::
[ool00
Lo
x" x=1 +
LL
x=
13 LØT
f(x) f(x))
(15)
VT
T
When the number of iterations T is large, only the first term becomes dominant in the convergence rate, which does not depend on L. Thus, Theorem shows that Inexact Polyak Stepsize successfully inherits the favorable property Polyak stepsize under (Lo, L smsoohnensssss In addition to Inexact Polyak Stepsieze, DecSPS (Orvieto et al., 2022) and AdaSPS (Jangg and Stich 2023) have been proposed as parameter-free methods that use I" instead of f in Polyak stepsize. However, these prior methods fail to inherit the favorable property of Polyak stepsize, and their convergence rates deteriorate when is large because these methods decrease the stepsize during the training. In fact, we evaluated DecSPS and AdaSPS with synthetic function in Sec. 6. demonstrating that convergence rates of DecSPS and AdaSPS are degraded when becomes large, whereas the convergence rate Inexact Polyak Stepsize does not depend on L.
Asymptotic independence of L:
0 Lallan ==||="
Removing dependence on Dr: The convergence rates of DecSPS and AdaSPS depend on Dr(:= maxo<est ||,, ()). Thus, strictly speaking, these convergence rates cannot show that DecSPS and AdaSPS converge to the optimal solution because Dr may increase as the number of iterations T increases. For instance, if Dr increase with I(T+), ), the convergence rate of AdaSPS is O(La + T.²), which does not show that AdaSPS converges to the optimal solution. In contrast, the convergence rate in Eq. (15) depends on only || x= Theorem indicates that Inexact Polyak Stepsize converges to the optimal solution.
Convergence rate with respect to T: Inexact Polyak Stepsize successfully achieves the asymptotic independence of T., while slows down the convergence rate with respect to the number of iterations T by comparing clipped gradient descent with proper hyperparameters. The convergence rate of Inexact Polyak Stepsize O Le is not optimal in terms of T, and there may be room to improve this (
rate. For instance, the adaptive methods proposed by Hazan and Kakade (2019) might be used to
Table 1: Summary of convergence rates of parameter-free methods based on Polyak stepsize. All convergence results are the ones under convex, L-smoothness, and (Lo, L1 smmoothness. We define Dr maNogesT
||z, x
Algorithm
Convergence Rate
Assumption
DecSPS Orvieto et al. 2022 (a)
o
max L.n. 1)D? +o"
VT
AdaSPS
Jiang and Stich. 2023 (a)
+
L2
Inexact Polyak Stepsize (This work) O Lallzo
LL wy =0-=011
L Lo L2T
/T
(a) We present the convergence rates of DecSPS and AdaSPS in the deterministic setting to compare DeaSPS, AdaSPS, and Inexact Jndniang and Stich (022)
Polyak Stepsize in the same deterministic setting, Orvicto al. 2022 stochastic setting.
analyzed the the
f L-smooth, (Lo, smowth because (Lo, L1) smoothmess ussumption strictly weaker Lesmoolhness assumption.

---

alleviate this issue. However, the parameter-fres methods for clipped gradient descent have not been explored well in the existing studies. We believe that Inexact Polyak Stepsize is the important first step for developing parameter-free clipped gradient descent.
5 Related work
Gradient clipping was initially proposed to mitigate the gradient explosion problem for training RNN and LSTM (Mikolov et al.) 2010 Merity et al. 2018) and now widely used to accelerate and stabilize the training not only for RNN and LSTM, but also for various machine learning models, especially language models (Devlin et al. 2019 Raffel et al. 2019). Recently, many studies have investigated the theoretical benefits of gradient clipping and analyzed the convergence
Gradient clipping:
rate clipped gradient descent under (1) (Lv, L1 -smsmooths assumption (Koloskova et al.
2023
Zhang al. 2020a b) and (2) heavy-tailes noise assumption (Zhang et al. [2200e] Li and Liu
2022
Sadiev et al. (023). J. (1) Zhang et al.] (2020b) found that the local gradient Lipschitz constant is correlated with the gradient norm. To describe this phenomenon, [Zhang et al. (2020b), Zhang et al.
(2020a), and Koloskova et al. (023) introduced the new assumption, (T-n, [. -smoothhesss, providing the convergence rate of clipped gradient descent under (In, I1 Jsmooothness. Then, they showed that gradient clipping can improve the convergence rate of gradient descent, as we introduced in Sec. [2.2 (2) Besides (Lo, L1) )-smoothness, Zhang al. (220cc) pointed out that the distribution of stochastic gradient noise is heavy-tailed for language models. Then, it has been shown that gradient clipping can make the stochastic gradient descent robust against the heavy-tailed noise of stochastic gradient
(Li and Liu 2022; Sadiev et al. 2023 Zhang et al. 2020c
one of the most canee-onuuminngg tasks for training machine learning models. To alleviate this issue, many parameter-free free methods that adjust the stepsize on the fly have been proposed, e.g., Polyak-based stepsize (Berrada et al., 2020 Hazan
Parameter-free methods: Hyperparameter-tuning
and Kakade 2019 Loizou et al. 202T Mukherjee et al. 2023; Orvieto et al. [022 Jiang and Stich 2023), AdaGrad based methods (Ivgi et al. 2023] Khaled et al. (202)), ) and Dual Averaging-bast based methods (Orabona and Tommasi 2017 2017iDefazio and Mishchenko 2023). However, parameter-fiee free
methods for hyperparameters. except for stepsizes, have not been studied. In this work, we studied the parameter-free methods for two hyperparameters, the stepsize and gradient clipping threshold, and then proposed Inexact Polyak Stepsize, which converges to the optimal solution without tuning any hyperparameters and its convergence rate is asymptotically independent of L as clipped gradient descent with well-tuned hyperparameters.
Numerical evaluation
In this section, we evaluate our theory numerically. In Sec. 6.1 we evaluate Polyak stepsize and Inexact Polyak Stepsize using a synthetic function, varying that their convergence rates asymptotically independent of L. In Sec. 6.2 we show the results obtained using neural networks.
6.1 Synthetic function
Setting: In this section, we validate our theory for Polyak stepsize and Inexact Polyak Stepsize using synthetic function. We set the loss function as f(x) LoL? 2 + Lax" + f*, which is (Lo, -mmoohh for any Lo > 0 and L1 > 0 (See Proposition 3 in Appendix). We set Ly to 1, Zy to
5, f and |* 0 and then evaluated various methods when varying L1.
We show the results in Fig. I The results indicate that gradient descent converges slowly when L, is large, whereas Polyak stepsize and clipped gradient descent does not depend on L1. These observations are consistent with those discussed in Sec. 3 which shows that the convergence rate of Polyak stepsize is asymptotically independent of L as clipped gradient descent. By comparing DecSPS, AdaSPS, and Inexact Polyak Stepsize, which are parameter-fi free methods, the convergence rates of DecSPS and AdaSPS degrade as L1 increases. Thus, DecSPS and AdaSPS lose the favorable property of asymptotic independence of I. under (To, --)osmooth In contrast, the convergence behavior of Inexact Polyak Stepsize does not depend on I,, which is consistent with Theorem and Inexact Polyak Stepsize successfully inherits the Polyak stepsize under (Lo, L1) smoothhess..
Results:
7

---

10a
10a
10
10a
10a
10*
10a
[(zy)
10:2
10-22
10:2
10
10
10
10.4
10
10:0
100
200
100
400
100
200
J00
400
100
200
300
400
500
Iteration
Iteration
Iteration
(a) Gradient Descent
(b) Clipped Gradient Descent
(c) Polyak Stepsize
107
107
10a
10a
10*
Aq
10
1000
107
100
10º
Ray)
102
10
104
1044
10:
104
104
10*
10
10
10.2
10th
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Iteration
Iteration
Iteration
(d) DecSPS Orvieto et al.
2022
(e) AdaSPS (iang and Stich 2023
(I) Inexact Polyak Stepsize
Figure 1: Convergence behaviors of various methods with the synthetic function.
SCD
Clipped SCD
32
Pulyak
1ost loss
To.st loss
AdaSPS
DecSP5
Test
231
Stepsize
Stepsize
Stepsize
(a) LSTM
Nano-GPT
(c)
Figure 2: The final test loss with various hyperparameter settings. For T5, the results of DecSPS and AdaSPS were omitted because their final test loss was much larger than the others, shown in Fig Furthermore, the results of SGD were also omitted when the final test loss became nan or infinity.
6.2 Neural networks
Next, we evaluated Inexact Polyak Stepsize using LSTM, Nano-GPT and T5 Nawrot 2023). For LSTM, Nano-GPT, and T5, we used the Penn Treebank. Shakespeare, and C4 training datasets, respectively. For SGD and Clipped SGD, we tuned the stepsize and gradient clipping threshold on validation datasets. For Polyak stepsize, we showed the results when we set f* zero. For Inexact Polyak Stepsize, Theorem requures the selection of the best parameters. However, we do not need choose this for neural networks because the parameters only reach the stationary point and do not reach the global minima. See Sec. [ for the detailed training configuration. For all experiments, we repeated with three different seed values and reported the average.
Setting:
Results: Figure 4 shows the loss curves, and Fig. shows the final test losses for various hyper- parameters. The results indicate that Inexact Polyak Stepsize consistently outperform DecSPS and AdaSPS for all neural network architectures. Although DoG performed the best for LSTM among the parameter-free methods, the training behavior of DoG was very unstable for Nano-GPT, and the loss values were much higher than those of the other methods. Similar DoG, Polyak stepsize outperformed all parameter-fre methods for T5, but the loss values of Polyak stepsize diverged for L.STM and Nano-GPT Thus, Inexact Polyak Stepsize can consistently succeed in training models for all neural network architectures.
httpps///gthab..cc/aaaraattytt/t

---

Clipped SGD
SGD
12-
12-
AdaSPS
Training loss
DecSPS
Testt loss
Inexact Polyak Stepsize
10000
20000
30000
10000
20000
30000
Iteration
Iteration
(a) LSTM
4.0
4.0
Clipped SGD
SGD
DeG
3.5
ملاا uar! Muyl
3.5
AdaSPS
Training loss
DecSPS
Test loss
Inexact Polyak Stepsize
3.0
2.5-
2.5
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Iteration
Iteration
(b) N
Clipped SGD
DoG
Polyak
Training loss
80
80
6-3
AdaSPS
Test loss
3.0
DecSPS
Inexact Polyak Stepsize
5000E
35000
500ce
05000
55303
40-
20
20000
40000
60000
20000
40000
60000
Iteration
Iteration
(c) TS
Figure 3: Loss curves for LSTM, Nano-GPT, and T5. We plotted the training loss per 100, 10, and 10 iterations for LSTM, Nano-GPT, and T5, respectively. We plotted the test loss per epoch, 100 iterations, and 200 iterations, respectively. For LSTT and Nano-GPT, we found that Polyak stepsize does not converge, and its loss much larger than that of other comparison methods. Thus, to make the figure easier to read, we omit the results of Polyak stepsize and provide the complete results, including Polyak stepsize in Sec.
Conclusion
In this study, we proposed Inexact Polyak Stepsize, which converges the optimal solution with- out hyperparameter tuning at the convergence rate that is asymptotically independent of L under (Lo, L1 -smoothesssss Specifically, we first provided the novel convergence rate of Polyak stepsize under (Lo. L1 L1)-smoothness, revealing that Polyak stepsize can achieve exactly the same conver- gence rate clipped gradient descent. Although Polyak stepsize can improve the convergence under (Lu, smooshhhssss,,, Polyak stepsize requires the minimum loss value, which is problem- specific parameter. Then, we proposed Inexact Polyak Stepsize, which removes the problem-specific parameter from Polyak stepsize without losing the property of asymptotic independence of L un- der (To, T, Jsmoothhness. We numerically validated our convergence results and demonstrated the effectiveness of Inexact Polyak Stepsize.

---

Acknowledgement
Y.T. was supported by KAKENHI Grant Number 23KJ1336. H.B. and M.Y. were supported by MEXT KAKENHI Grant Number 24K03004. We thank Satoki Ishikawa for his helpful comments on our experiments.
References
Berrada, L., Zisserman, A., and Kumar, M. P. (2020). Training neural networks for and by interpola- tion. In International Conference on Machine Learning.
Carmon, and Hinder, O. (2022). Making SGD parameter-free. In Conference on Learning Theory.
Defazio, A. and Mishchenko, K. (2023). Searning-rate-iin learning by D-adaptation. In International Conference Machine Learning.
Devlin, J.. Chang, M.-W., Lee, K., and Toutanova, K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. In Association for Computational Linguistics.
Duchi, J., Hazan, E., and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. In Journal of Machine Learning Research.
Galli, L., Rauhut, H., and Schmidt, M. (2023). Don't be so monotone: Relaxing stochastic line search in over-parameterized models. In Advances in Neural Information Processing Systems.
Garrigos, G. and Gower, R. M. (2023). Handbook of convergence theorems for (stochastic) gradient methods. In arXiv.
Hazan, E. and Kakade, S. M. (2019). Revisiting the Polyak step size. In arXiv.
Ivgi, M., Hinder, O., and Carmon, Y. (2023). DoG is SGD's best friend: A parameter- free dynamic step size schedule. In International Conference on Machine Learning.
Jiang, X. and Stich, S. U. (2023). Adaptive SGD with Polyak stepsize and line-search: Robust convergence and variance reduction. In Advances in Neural Information Processing Systems.
Khaled, A., Mishchenko, K., and Jin, C. (2023). DoWG unleashed: An efficient universal parameter- free gradient descent method. In Advances in Neural Information Processing Systems.
Kingma, and Ba, J. (2015). Adam: method for stochastic optimization. International Conference on Learning Representations.
Koloskova, A., Hendrikx, H., and Stich, S. U. (2023). Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning.
Li, S. and Liu, Y. (2022). High probability guarantees for nonconvex stochastic gradient descent with heavy tails. International Conference on Machine Learning.
Loizou, N., Vaswani, S., Hadj Laradji, L., and Lacoste-Julien, S. (2021). Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics.
Merity, S., Keskar, N. S., and Socher, R. (2018). Regularizing and optimizing LSTM language models. In International Conference on Learning Representations.
Mikolov, T., Karafiat, M., Burget, L., Cernocky, J. H., and Khudanpur, S. (2010). Recurrent neural network based language model. In Interspeech.
Mukherjee, S., Loizou, N., and Stich, S. U. (2023). Locally adaptive federated learning via stochastic polyak stepsizes. In arXiv.
Nawrot, P. (2023). NanoT5: A pytorch framework for pre-training and fine-tuning t5-style models with limited resourees. In arXiv.
10

---

Nesterov, Y. (2018). Lectures on Convex Optimization. Springer.
Orabona, F. and Tommasi, T. (2017). Training deep networks without learning rates through coin betting, In Advances Neural Information Processing Systems.
Orvicto, A., Lacoste-Julien, S., and Loizou, N. (2022). Dynamics of SGD with stochastic Polyak stepsizes: Truly adaptive variants and convergence exact solution. In Advances in Neural Information Processing Systems.
Pascanu, R., Mikolov, T., and Bengio, (2013). On the difficulty of training recurrent neural networks. In International Conference on Machine Learning.
Polyak, (1987). Introduction to Optimization. Optimization Software.
Raffel, C., Shazeer, N. M., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, J. (2019). Exploring the limits of transfer learning with unified text-to-text transformer. In Journal of Machine Learning Research.
Sadiev, A., Danilova, M., Gorbunov, E., Horváth, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtárik, P. (2023). High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In International Conference on Machine Learning.
Zhang, B., Jin, J., Fang, C., and Wang, L. (2020a). Improved analysis of clipping algorithms for non-convex optimization. In Advances in Neural Information Processing Systems.
Zhang. He, T., Sra, S.. and Jadbabaie, A. (2020b). Why gradient clipping accelerates training: theoretical justification for adaptivity. In International Conference on Learning Representations.
Zhang, J., Karimireddy, S. P.. Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. (2020c). Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems.

---

A Proof of Theorem 4
Lemma 1. If Assumption holds, the following holds for any x E 12:;
(V]())) f(x").
(16)
2T.
Proof. See Lemma 2.28
(Garrigos and Gower 2023).
Lemma 2. If Assumption holds, the following holds for any æ E R2:
Vf(x)) < f(x) f(x*).
(17)
2( + -+lV)(())])
Proof. See Lemma A.2 in (Koloskova et al. 2023).
Lemma 3. Assume that f is convex and Assumption 7 and 2 hold. Let T be the number of iterations
and define T == arg mninggtss-11ian Then, gradient descent with Polyak stepsize Eg. 7 satisfies:
8L By
x²1
64LL
x011
f(x+)) f(x=)
T
7
Proof. We have
| 1c-1|=1|aa x²112 (V x²) V
< | - x= x²11 (n:e - f(xx((()))))))) + {[)
where the convexity of f in the inequality.
Case when [V I I,
La Substituting the stepsize, we get
x=1|2 f(xx,) f(x²)
|| x+1 < I
(f(x)) - f(xx))
[V+((x))1
S || x=1
(f(x,) - f(x*))
2(Lo L1 [(xx))l
< | a=11
(f(...) (((n)))((x"))
4T.
where we use Lemma 2 in the second inequality. Unrolling the above inequality, we obtain
((x)) - f(x*) S 4Lo (Ilæ, x01 || - x 11))²
Case when ||V/((;))|
La: Substituting the stepsize, we get I.
| - x= 2 < |ar, x=12 (f(xz) f(x*))²
[V,((1))
| w01 2 f( f(x²) f(x.) f(x")
[V)())))
where we use Lemmas in the last inequality. Then, |[
La implies
L
Lo + L, [[+))
<1.
21 (x))))
Thus, we get
f(xx)
f(x')
f(x1)
f(x*)
Lo + [
|0241
x 212 < ||00 x=1)
2h.
[V](x:)]
2h
f(x))
f(x*)
|
112
4Lg
2L
12

---

where we use Lemma in in the last inequality. Unrolling the above inequality and multiplying Lo on both sides, we get
Lo
[(x) - f(x))) 4Tg (1 -x"
x=" x=112 112
| =21)
L
2L
Summing the two cases: Define TI and T2 follows:
Ti = {
Lo Lı
Lo T2 [[11V)
L1
We obtain
Lo
f(xx) f(x*))
Σ -(x"))
+
4 4holaan 200 ==.
L
21.
LET
LET2
Then, the above inequality implies
4Lo [ - x2112
Σ f(x)) - f((x)) -
T
T
BE
4L1 v 22 x xx $12
Σ
((at)) - (xx) S
T
BET2
Using a² 2 2ab b3, obtain for any E R
4Lo||
x=11
Σ
s(x*)) 62)
T
T
IET1
Thus, when 6 0, we obtain
1
Σ
-f(x)) f(x))
4Loo|a0 x=
+
b
T
26T
2
ET
Choosing / 4Lo Mooll00-- 11
T
we get
AT. aco
xx x011
Σ
(f(z)) f(x*) f(x)) S
T
IET
Thus, we get
4Lo xo x+1
4L v 2L
xnn - x x+1
f(()) f(x²)= <
T
T
1=0
Defining = arg min, f(xt), we get
Vs(z;) - f(x)) 4Lv L2:
120
x
4L1 / 2/L
x=
T
T
Squaring the both sides, and using (a b)2 2a²
262 for all a, b R. obtain
8Lol vo
x11
64LL x
x x+1
f(x,) - f(x))= <
T
72
This concludes the statement.
13

---

B Proof of Theorem 5
Lemma 4. Assume that is convex and Assumptions and hold. Let ' be the number of iterations
and define T == arg giggingggg----ff 1f f(x))
f 2 /T for all t, then gradient descent with
stepsize Eq. satisfies:
f(x,) f 8Lo 2o - x²112 + 202
128L
2 - x= 2²11
0 L
+
VT
T
LoT
where x" == arg ming mig fxx and o² f -r.
Proof. By the convexity of f. we have
01+1 x²1 x x²11 2n
( (
V[(=))
< x2 x=" 22112 ( - -1") + [[
Substituting the stepsize Eq. get
| x=
S || Lt - (f)((a)(((a))) - ff) + 1h (f(x,) - -1m)
VT
< ||,, x²12 12(2 VT (f(x)) - f*) 11o²
1
VT
11:0²
s | x" 101 (f((xx)) f*)
(18)
where we use T 2 1 in the last inequality. Unrolling the above inequality and dividing by 1). we obtain
f(x,) - fr I |10, x²1 - |x x012
(19)
Case when [[:[( < La: From f(xt) p fx² 0²
and Eq. 18).
we obtain
VT
| x² 112 -|| x² 12
(20)
Thus, we get
o²
((x))- 2(Lo + 4, 2(
x012 -111111011111 x²113) [Va: xx'1'=
VT
r²
< ALooT( x= || | x²1
VT
where we use 1 2 1* and Lemma for the first inequality and use [[:{)) inequality. Case when [V/(2:)||
S
for the last
L
Lo 1. From Lemma 2 have
m N f(x,)) f
2
f(1)1( 2(Lo LIIV
Then, we obtain
The 4L Vf(x))l]
4L, /LL(( f*)
where use
f
La for the first inequality, and Lemma for the last inequality. Combining
Eqs. (19 and
20
we obtain
σ²
f(a.) - fr < 44, 2LT(2())(()
f' -0112-1[x:11 x=113) +
VT
14

---

Furthermore, from [ > La and Lemma
we obtain
Ln
Lo
f(zz) - fr
Lo 1
Vf(x)) - ft
2
L
[vf(x:)]1
L1
2L
Thus, we get
f(x)) 5 S 44 A (1T(((()))))))))))))))))(()))))) [1]
L1
|, - x²113) +
(L - (*).
LovT
Li (2(2((((a)-11))
Dividing by
we get
La
Lo
f(x))
-
S 4L0 LLOV,(( -011 x²113) + o²
L1
2L
VT
Summing the two cases: Define Ti and To as follows:
Ti = [=1111//020))11
Lo
1 [ >
Lo
-
To =
T
I
We obtain
Lo
f(x) fr
4L xn - x²1 + 0²
Σ (f(x)) - fr)
T
L1
2L
VT
LET
1ET2
The above inequality implies that
4Lo VD x+1 1 1 0
Σ -()
VT
IE
4b V 2L
Eo x*
LIo2
Σ
-f
T
VT
LovT
1ET
Using a² 2 2ab - 6²,
we obtain for any b E R
1
4Tol 10 - x2 + o²
Σ
2b
((x))( ft -1))
T
VT
BETI
Thus, when 6 0, we obtain
4T [00 x11 + o² b
Σ
Vf(x)) f
T
2bv T
TET
Choosing b
LL. 200 -0 20 1000"
get
VT
4L xo - x=1|2 + o²
-
- fr
T
VT
AET1
Thus, get
|oo|/00 12 o
4L 2L a0n
x012
L102 L102v2L LoVT
2
((())) - - S
+
VT
VT
Defining = arg minn f(x:),, we get
((x))- ALo - x 1 2 0²
4L ALiV2L
x
L
VT
VT
LoVT
Squaring the both sides, and using (a + b)2 < 2a
+ 282 for all a, beb R, we obtain
-xx)- 8Lolloo x²
1 x112
20
1281 x=1 lla
8Li0L
T
L
This concludes the statement.
15

---

Lemma 5. Assume that f is convex and Assumptions Z 2 hold. Let T be the number of iterations and define == arg mingoess---11 ((z,) Then, gradient descent with stepsize Eq.
414 satisfies:
((x)) - f(x=) 50 Lo x²11 +
| 20
x²1
L Li
+
(21)
VT
T
I
where x= arg min (1c) and 0² == -
Proof. If there exists I such that f(xx)) - 8" < o
V we have
f(x,) fr S f(xt) f
Then, f(xz) f 2 vT
for all t, Lemma shows that
f(x,) - 8Lo xo - x=12 [ + 2o²
128LLL1100 - x²11
8L,00L
VT
T
L/T
By combining the above two cases, we have the desired statement.
C Additional theoretical result
Lemma 6. Let I be sunction such that [[V S Lo L (v)(())] holds for any For any æ; y such that || - y) S Lg" we have
IV v((g)) [V))\>]]]] -yl-
Proof. See Lemma A.2 in (Zhang et al. 2020a).
Proposition 3. For any Lo 2 and L1 2 0, f(x)= =
Lot?
x
+
Lo is (Lo, Im)-shooth.
72
1
Proof. Since (xx is twice differentiable, have
L Lo
Lo
x
3 2 |z], obtain Using 4 + 2h.1
L
L
L1 x²
3
v²f(i)
+
|
+ Lo
6
2L1
L1
L
2
Lo
Lo
+
18
2
2
L
Lo
V
+
2
2
From Lemma 6 we have the desired statement.
16

---

D Hyperparameter settings
D.1 Synthetic function
In our experiments, we ran the clipped gradient descent with the following hyperparameters and tuned the hyperparameters by grid search.
Table 2: Hyperparameter settings for clipped gradient descent.
Learning Rate
{1. 1.0 x 10-1 1.0 x 10 10-$ $} {0.01, 0.1, 1, 5, 10, 15, 20, oo}
Gradient Clipping Threshold
Table 3: Hyperparameters selected by grid search.
Gradient Descent Learning Rate
Clipped Gradient Descent
Learning Rate Gradient Clipping Threshold
L1
1.0 10-1
0.1
20
L1 10
1.0 x 10-3
0.1
10
L 100
1.0 x 10-5
0.1
10
L1 1000
1.0 10-7
0.1
10
D.2 Neural networks
In our experiments, we used the following training configuration:
T5: httpe://gthuuoocco//o/otttrrrrrp
We ran all experiments on an A100 GPU. For Clipped SGD and SGD, we tuned the stepsize and gradient clipping threshold using the grid search. See Tables and for detailed hyperparameter settings, and see Table 7 for the selected hyperparameters.
Table Hyperparameter settings for LSTM.
Learning Rate
(100, 50, 10, 011, 0.01} {0.5, 1, ... 4.5, 5, oc} 80
Gradient Clipping Threshold
Batch Size
Table 5: Hyperparameter settings for Nano-GPT.
Learning Rate
{1, 0.3.0.0000 0.1, 0.0000, 0.0001}
Gradient Clipping Threshold
(1, 2, ... ,9, 10, oo}
Batch Size
64
Table 6: Hyperparameter settings for T5.
Learning Rate
(5.0, 1.0, 0.5, 0.1, 0.05] {1, 2, 3, oo}
Gradient Clipping Threshold
Batch Size
128
Table Hyperparameters selected by grid search. Three values correspond selected hyperpa-
rameters for different seed values.
Gradient Descent
Clipped Gradient Descent
Learning Rate
Learning Rate
Gradient Clipping Threshold
LSTM
10/ 10 0.001 0.001 0.001 0.1 0.1 / 0.05
50 / 50 0.001 / 0.001 / 0.001
0.5/1/0.5 00 10/ 10
Nano-GPT
T5
1/ //11
2/2 2
17

---

E
Additional numerical evaluation
14
DoG
18
Clipped SGD
SGD
16-
Polyak
Training loss
AdaSPS
Test loss
10-
DecSPS
12
Inexact Polyak Step
10000
20000
30000
10000
20000
30000
Iteration
Iteration
(a) LSTM
Clipped SGD
SGD
DoG
Polyak
Training less
AdaSPS
Test loss
DecSPS
Inexact Polyak Stepsize
1000
3000
4000
5000
1000
2000
4000
lteration
Iteration
(b) Nano-GPT
Figure 4: Loss curves for LSTM and Nano-GPT. We plotted the training loss per 100, 10, and 10 iterations for LSTM, Nano-GPT, and T5, respectively. We plotted the test loss per one epoch, 100 iterations, and 200 iterations, respectively.
18

---

4.0
4.0
Clipped 5GD
DoG
3.5
AdaSPS
Training loss
DecSPS
Wo الlly war y
Test loss
Inexact Polyak Stepsize
3.0
1500
2000
2500
Iteration
Iteration
(a) T 2500
4.0
Clipped SGD
SGD
3.5
AdaSPS
Training loss
DecSPS
Test loss
Inexact Polyak Stepsize
3.0-
3.0
2.5-
2.0
2500
5000
7500
2.0
2500
5000
Iteration
Iteration
(b) T = 7500
Figure 5: Loss curves for Nano-GPT with different
19

---

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:
Our main claims are clearly discussed in Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Sec.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and faimess.
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?
Answer: [Yes]
20

---

Justification:
All proofs are provided in Sec. and
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: 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)?
Answer: [Yes]
Justification: All training configuration and hyperparameter setting are provided in Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are 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 a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to 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 all 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 to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
21

---

Answer: [Yes]
Justification:
Our code is contained in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeeee //nips.com htte://alllllgiiiee///oeeeuaaass ssiniiiiccypyy for more details.
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. If 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 supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
Our training configuration is provided Sec. D
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, 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: [No]
Justification: We repeated the experiments in Sec. 6.2 with three different seed values and reported the average, while we did not report error bars to make the figure easy to read.
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 enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
22

---

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 error 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 figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it 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
Answer: [Yes]
Justification:
The authors read and complied with the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The motivation and its impact of our study are clearly discussed in Sec.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
23

---

The conference expects that many papers will be foundational research and not tied 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 an 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 a 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our study does not provide any new dataset or pre-trained models.
Guidelines:
The answer NA means that the paper poses 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 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. Lieenses for existing assets
Question: 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?
Answer: [Yes]
Justification: See Sec.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it 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: [Yes]
Justification: Our code is provided in the supplementary material with MIT license.
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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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 details about compensation (if any)?
Answer: [NA]
Justification:
Our experiments do not use any crowdsourcing service.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our experiments do not use any crowdsourcing service.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "2PSuHsnE0h", "reviewer": "Reviewer_rinC", "summary": "This work made an interesting observation regarding the polyak stepsize. \nIn particular, the main observation is that the polyak stepsize can be interpreted as doing a gradient clipping.\nWith this observation, this work presents a new convergence guarantee of the polyak stepsize under the L_0,L_1 smoothness", "questions": "- If you don't use the polyak step size, perhaps the parameter-free method should still achieve O(1/T) convergence rate? I'm asking this because the price to pay for parameter-freeness with the polyak stepsize seems to be quite significant. The convergence rate becomes O(1/\\sqrt{T}) insteand O(1/T). Could you clarify this? Also, is there any lower bounds for this?\n\n- It's quite nice that the authors interpret the polyak stepsize as doing some kind of clipping. However, in practice, another popular method is coordinate-wise clipping. Does the polyak stepsize approach lets us do coordinate-wise clipping too?\n\n- Based on your experiments, when would you recommend practitioners to use the polyak stepsize instead of gradient clipping?\n\n- Perhaps, from a practical perspective, the fact that the algorithm needs to maintain the best iterate so far might be a little impractical. For NN training, computing f is too costly and you can only compute the mini-batch loss. This is just a minor point. How did you guys implement this for NN training experiments?", "limitations": "See above. Overall, I appreciate the clean presentation of this work.\nBased on the overall scope and the main results, my recommendation for this paper is a \"weak accept.\"", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Interesting observation, and nice literature survey.\n- Theoretical results seem interesting.\n- Nice presentation and it's quite easy to follow.\n- Nice set of experiments.", "weaknesses": "I have several questions below, but overall, the main scope and results are well-presented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your positive evaluation and constructive feedback on our paper.\n\n> If you don't use the polyak step size, perhaps the parameter-free method should still achieve $O(1/T)$ convergence rate? [...]\n\nWe will add the discussion we replied to for all reviewers to the revised version and clarify this point.\n\nBesides Polyak stepsize, DoG [2] is also a well-known parameter-free method for stepsize.\n[2] analyzed the convergence rate of DoG in the convex and deterministic setting, showing that DoG achieves the convergence rate $\\tilde{\\mathcal{O}} ( \\frac{L D_T^2}{T})$ where $D_T  \\coloneqq \\max_{0 \\leq t \\leq T} \\| x_t - x^\\star \\|$ (see page 36 in [2]).\nThus, it is still unclear that DoG converges to the optimal solution with rate $\\mathcal{O}(\\frac{1}{T})$ because $D_T$ may increase as the number of iterations $T$ increases.\nDoG is a parameter-free method for stepsize, whereas we study parameter-free methods for stepsize and clipping threshold, which is even more challenging than the parameter-free methods for stepsize.\n\nWe are not aware of the lower bound for parameter-free clipped gradient descent. \nIt is one of the most promising directions for future research.\n\n>  It's quite nice that the authors interpret the polyak stepsize as doing some kind of clipping. However, in practice, another popular method is coordinate-wise clipping. Does the polyak stepsize approach lets us do coordinate-wise clipping too?\n\nThank you for the comment. It is unclear whether Polyak stepsize approach can also be interpreted as coordinate-wise clipping as well as non-coordinate-wise clipping.\n\nFirst of all, it is still an open question why coordinate-wise clipping works well in practice.\n[1] analyzed the convergence rate of non-coordinate-wise clipped gradient descent, showing that non-coordinate-wise gradient clipping allows gradient descent to converge faster under $(L_0, L_1)$-smoothness. However, no prior papers have provided a similar convergence analysis for coordinate-wise clipping.\nTherefore, it is difficult to discuss the relationship between Polysk stepsize and coordinate-wise clipping at this moment.\nIt is one of the promising directions to explain why coordinate-wise clipping works well from a theoretical perspective and investigate the relationship between coordinate-wise clipping and Polyak stepsize. \n\n> Based on your experiments, when would you recommend practitioners to use the polyak stepsize instead of gradient clipping?\n\nFigure 4 indicates that Polyak stepsize with $f^\\star=0$ is very unstable for LSTM and Nano-GPT.\nPolyak stepsize is very sensitive to the hyperparameter $f^\\star$, by comparing with the sensitivity of hyperparameters in clipped gradient descent (see Figure 3).\nTherefore, we do not recommend practitioners use Polyak stepsize instead of gradient clipping.\n\n> Perhaps, from a practical perspective, the fact that the algorithm needs to maintain the best iterate so far might be a little impractical. For NN training, computing f is too costly and you can only compute the mini-batch loss. This is just a minor point. How did you guys implement this for NN training experiments?\n\nIn our experiments with neural networks, we used the final parameters instead of the best parameters.\nAlthough Theorem 4 requires selecting the best parameters, we found that, in practice, it is unnecessary for neural networks because the norm of the stochastic gradient does not reach zero in practice (see Sec. 6.2.).\nWe will revise the manuscript so that readers understand it more clearly.\n\n## Reference\n\n[1] Koloskova et. al., Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In ICML 2023\n\n[2] Ivgi et. al., DoG is SGD’s best friend: A parameter-free dynamic step size schedule. In ICML 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pcFOalBFXf", "reviewer": "Reviewer_bj1n", "summary": "The paper proposes a version of the Polyak step size when the optimal value is not known. It analyses the proposed method in the convex, $(L_0,L_1)$-smooth setting, and draws a connection to gradient clipping.", "questions": "Many plots (e.g. Figure 2 and 3) are very hard to read, due to inadequate color palettes, too thin lines, missing log scales etc.\n\nTo make the experiments reproducible, please specify for each hyperparameter and problem the actual value that was used, and not only the set of values among which it was tuned (see Tables 3-5).", "limitations": "See above.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The analysis of Polyak step sizes under $(L_0,L_1)$-smoothness seems to be novel, and the connection to clipped gradient descent is interesting.", "weaknesses": "* Comparing Thm. 2 and 5, the convergence rate drops from $1/T$ to $1/\\sqrt{T}$. Comparing convergence results of Alg. 1 to those of DecSPS, AdaSPS is somewhat unfair, as those are **stochastic** methods, and Alg. 1 is not! Thus, Table 1 is a misleading comparison.\n\n* Having the $1/\\sqrt{T}$ in the step size in Alg.1 has several disadvantages: one needs to determine the number of iterations before training, and for long runs the step size will become very small. A numerical analysis how the choice of $T$ affects the performance of the method is missing.\n\n* Algorithm 1 is a deterministic method (that is, it uses the full gradient). The comparison in section 6.2 suggests that you compare to stochastic methods (SGD,SPS,..). Which batch sizes were used for the methods? Did you use Algorithm 1 as is, or a stochastic version of it? This part of the experimental setup needs to be clarified - further, comparing deterministic to stochastic methods is somewhat problematic, as the per-iteration cost is different, and it obfuscates if any observed (dis)adavtanges are only due to the noise when running a stochastic method.\n\n* Finally, the neural network results are not really convincing, as the proposed Inexact Polyak stepsize is only competitive for one out of three settings (and the experiments are still quite small-scale compared to standard LLM benchmarks).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your comments and criticism of our paper.\n\n> Comparing Thm. 2 and 5, the convergence rate drops from $O(1/T)$ to $O(1/\\sqrt{T})$. Comparing convergence results of Alg. 1 to those of DecSPS, AdaSPS is somewhat unfair, as those are stochastic methods, and Alg. 1 is not! Thus, Table 1 is a misleading comparison.\n\nIn the revised manuscript, we will add the footnote in Table 1 and mention that the prior studies also established the convergence rates of DecSPS and AdaSPS in the stochastic setting.\nHowever, the convergence rates listed in Table 1 are in the deterministic setting, and the comparison of those is fair. Under the deterministic setting, Inexact Polyak Stepsize can converge to the optimal solution faster than DecSPS and AdaSPS because of $L_0 \\ll L$.\n\n> Having the $1/\\sqrt{T}$ in the step size in Alg.1 has several disadvantages: one needs to determine the number of iterations before training, and for long runs the step size will become very small. A numerical analysis of how the choice of $T$ affects the performance of the method is missing.\n\nThank you for your suggestion. \nWe conducted the experiments with Nano-GPT by varying the number of iterations $T$ and showed the results in Figures 5 and 6 in the attached PDF.\nThe results indicate that Inexact Polyak Stepsize outperforms DoG, DecSPS, and AdaSPS for all $T \\in \\\\{2500, 5000, 7500\\\\}$.\nWe have not finished experiments with SGD and Clipped SGD yet since we do not have sufficient time during this rebuttal.\nWe will add these results along with those for SGD and Clipped SGD in the revised manuscript.\n\n> Algorithm 1 is a deterministic method (that is, it uses the full gradient). The comparison in section 6.2 suggests that you compare to stochastic methods (SGD,SPS,..). Which batch sizes were used for the methods? Did you use Algorithm 1 as is, or a stochastic version of it? [...]\n\nWe used the stochastic gradient with the same batch sizes for all methods, including our proposed method, in the results shown in Figures 2 and 3.\nSpecifically, we set the batch size to $80$, $64$, and $128$, for LSTM, Nano-GPT, and T5, respectively.\nFor the results with the synthetic function shown in Figure 1, we used the full gradient for all methods.\nWe will clarify these experimental settings in the revised manuscript.\n\n\n> Finally, the neural network results are not really convincing, as the proposed Inexact Polyak stepsize is only competitive for one out of three settings.\n\nWe would like to highlight that parameter-free methods should be featured with stability across different models and datasets, i.e., different problem-specific parameters $L$, $L_0$, etc., instead of achieving the best performance.\nFor instance, as the reviewer mentioned, DoG achieved the best performance for LSTM among parameter-free methods.\nHowever, the training curve of DoG was very unstable for Nano-GPT, which is problematic for a parameter-free method.\nTherefore, we can conclude that Inexact Polyak Stepsize, which successfully trained all neural networks, is a desirable parameter-free method.\n\n> Many plots (e.g. Figure 2 and 3) are very hard to read, due to inadequate color palettes, too thin lines, missing log scales etc.\n\nWe will revise these figures to improve the readability.\n\n> To make the experiments reproducible, please specify for each hyperparameter and problem the actual value that was used, and not only the set of values among which it was tuned (see Tables 3-5).\n\nThank you for your suggestion.\nWe will report the hyperparameters selected by grid search in the camera-ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ugG5hF9jND", "reviewer": "Reviewer_zAFh", "summary": "The work extends the convergence results for the Polyak stepsize to ($L_0$, $L_1$)-smoothness (and convex), showing a rate of $\\mathcal O(\\tfrac{L_0}{T} + \\tfrac{LL_1^2}{T^2})$. To remove the dependency on knowing the optimal function value $f^\\star$, they introduce a horizon dependent stepsize factor $1/\\sqrt{T}$. Not surprisingly, this comes at the cost of \"deaccelerating\" the rate, specifically to $\\mathcal O(\\tfrac{L_0+\\sigma^2}{\\sqrt{T}} + \\tfrac{LL_1^2}{T}+\\tfrac{LL_1^2\\sigma^4}{L^2_0 T})$ where $\\sigma$ is the error for the guess of $f^\\star$.", "questions": "See weaknesses.", "limitations": "A couple of important points are not discussed:\n\n- The theoretical results are only for deterministic even though stochastic experiments are considered. One should expect only convergence to a neighborhood. If this is not formalized in a theorem, I suggest at least making this theory/practice gap explicit (especially in contrast with the baseline like AdaSPS that have been developed for the stochastic case).\n- The $1/\\sqrt{T}$ factor in the stepsize deteriorates the rate should be discussed", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "It is interesting that Polyak stepsize can recover the rates of clipped GD under  ($L_0$, $L_1$)-smoothness, thus removing the need for tuning the clipping parameter and stepsize in this setting as long as $f^*$ is known. It is not too surprising that Polyak stepsize converges for ($L_0$, $L_1$)-smoothness and convex (Polyak stepsize is Fejer monotone under star-convexity alone after all), but the fact that the rate matches those of clipped GD seems interesting.", "weaknesses": "- The horizon dependent stepsize $1/\\sqrt{T}$ (to relax knowledge of $f^\\star$ to knowledge of a lower bound $l^\\star \\leq f^\\star$), leads to a slow $\\mathcal O(1/\\sqrt{T})$ rate, which is problematic. Since the work are also assuming knowledge of a lower bound on $f^\\star$, why not use the successive halving strategy originally used for Polyak stepsize in [Hazan and Kakade 2019](https://arxiv.org/pdf/1905.00313) (Alg. 3)? I imagine it should be able to show a similar result to their Thm. 2, which only suffers a logarithmic factor in the complexity (instead of deaccelerating the scheme). Instead of comparing with parameter-free stochastic Polyak methods in l. 172-178, why not compare with the more appropriate deterministic strategy of [Hazan and Kakade 2019](https://arxiv.org/pdf/1905.00313) (Alg. 3)?\n- The connection with gradient clipping seems largely misleading. The paper makes it seem as if the results are concerning gradient clipping (e.g. the paper title, the title of section 4, l. 237). Instead the results directly concern Polyak stepsize, why not simply present it as such?\n- Stochasticity is not treated or discussed even though it seems like a major motivation from the experiments.\n\nThe main contribution seems to be showing rates for Polyak stepsize under ($L_0$, $L_1$)-smoothness (and convexity), which does not seem sufficient in itself. The direction is interesting, but in its current state the paper has too many either unnecessary of misleading parts (as mentioned above).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your constructive criticisms of our paper.\n\n> The horizon dependent stepsize $1/\\sqrt{T}$ (to relax knowledge of $f^\\star$ to knowledge of a lower bound $l^\\star \\leq f^\\star$), leads to a slow $O(1/\\sqrt{T})$ rate, which is problematic. Since the work are also assuming knowledge of a lower bound on $f^\\star$, why not use the successive halving strategy originally used for Polyak stepsize in Hazan and Kakade 2019 (Alg. 3)? [...]\n\nThank you for the suggestion. We will add the following discussion in the revised manuscript.\n\nOur paper focused on the deterministic setting for theory, while Inexact Polyak Stepsize also works in practice for neural networks, as demonstrated in our experiments.\nIn contrast to Inexact Polyak Stepsize, Adaptive Polyak [2] requires computing the loss value, which is not immediately extendable to the stochastic setting.\nThus, Adaptive Polyak is not applicable in the stochastic setting due to its methodological issue.\nThough our theory only holds in the deterministic setting, our ultimate goal is to develop methods that also work for training neural networks.\nThus, we utilized the idea of DecSPS and AdaSPS instead of Adaptive Polyak, proposing Inexact Polyak Stepsize in our paper.\n\n> The connection with gradient clipping seems largely misleading. The paper makes it seem as if the results are concerning gradient clipping (e.g. the paper title, the title of section 4, l. 237). Instead the results directly concern Polyak stepsize, why not simply present it as such?\n\nWe wonder if the reviewer misunderstood our motivation to study Polyak stepsize.\nLet us clarify that our paper attempts to propose a parameter-free clipped gradient descent method and leverages the Polyak stepsize as its basis.\nHere, we briefly summarize the motivation of our paper.\nBy slightly changing the notation,\nclipped gradient descent can be reformulated as follows:\n\\begin{align*}\n    \\mathbf{x}_{t+1} = \\mathbf{x}_t - \\tilde{\\eta}_t \\frac{\\nabla f (\\mathbf{x}_t)}{\\| \\nabla f (\\mathbf{x}_t) \\|},\n\\end{align*}\nwhere $\\tilde{\\eta}_t = \\eta \\min\\\\{ \\| \\nabla f (\\mathbf{x}_t)\\|, c \\\\}$.\nThis reformulation allows us to consider parameter-free methods for $\\tilde{\\eta}_t$ instead of $\\eta$ and $c$ in clipped gradient descent.\nThe gradient norm $\\|\\nabla f(\\mathbf{x}_t)\\|$ in the denominator is reminiscent of Polyak stepsize, which motivated us to analyze Polyak stepsize under $(L_0, L_1)$-smoothness.\nThen, we uncovered that Polyak stepsize achieves the same convergence rate as clipped gradient descent.\nWhile clipped gradient descent uses two hyperparameters $\\eta$ and $c$, Polyak stepsize requires only one hyperparameter $f^\\star$.\nWe explored parameter-free methods for Polyak stepsize (i.e., $f^\\star$) to study parameter-free clipped gradient descent, leading to our proposal of Inexact Polyak Stepsize.\nWe will revise our manuscript to make this motivation clear to readers.\n\nWe are also wondering if the paper title may have misled the reviewers.\nWe will change the word order in the title and the paper title to \"Parameter-free Clipped Gradient Descent Meets Polyak\" to better reflect our motivation and avoid misunderstandings.\n\n> Stochasticity is not treated or discussed even though it seems like a major motivation from the experiments.\n\nWe will add the following discussion on stochasticity to the revised manuscript.\n\nWe agree that the stochastic setting is important, but we would like to emphasize that parameter-free methods for clipped gradient descent are already challenging even in the deterministic setting. Furthermore, clipped gradient descent does not converge to the optimal solution in the stochastic setting (see Theorems 3.1 and 3.2 in [1]), which makes it more difficult to develop parameter-free clipped gradient descent.\nOur paper focused on the deterministic setting, but we believe that our findings will be helpful in future studies of parameter-free clipped gradients in the stochastic setting. \nSee also the reply to the next question.\n\n> [...] One should expect only convergence to a neighborhood. If this is not formalized in a theorem, I suggest at least making this theory/practice gap explicit [...]\n\nWe would like to note that even the convergence analysis of clipped gradient descent has not been established in a stochastic and convex setting [1]. \nThus, we first need to establish a novel proof strategy for analyzing clipped *stochastic* gradient descent to analyze Inexact Polyak Stepsize in the stochastic setting, but it is out of scope in our paper.\nWe believe that it is one of the promising directions to analyze Inexact Polyak Stepsize in the stochastic setting, while we left this problem as a future work.\n\nMore technically, the analysis of clipped gradient descent first derived the upper bound of $\\sqrt{f(x_t) - f^\\star}$ and then derived the upper bound of $f(x_t) - f^\\star$ by squaring both sides (see page 13 in [1]).\nIf we extend this proof strategy to the stochastic setting, we get the upper bound of $\\mathbb{E} \\sqrt{f(x_t) - f^\\star}$ and obtain the upper bound of $(\\mathbb{E} \\sqrt{f(x_t) - f^\\star})^2$. However, the upper bound of $(\\mathbb{E} \\sqrt{f(x_t) - f^\\star})^2$ is not a desired one because we would like to obtain the upper bound of $\\mathbb{E} f(x_t) - f^\\star$.\nTherefore, we need to establish a different proof strategy to analyze the clipped *stochastic* gradient descent.\n\n\n> The $1/\\sqrt{T}$ factor in the stepsize deteriorates the rate should be discussed\n\nThank you for the suggestion. \nWe promise to discuss in the revised version the convergence rate of Inexact Polyak Stepsize being deteriorated to $O(\\frac{1}{\\sqrt{T}})$ by the $\\frac{1}{T}$ factor in the stepsize.\n\n\n## Reference\n\n[1] Koloskova et. al., Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In ICML 2023\n\n[2] Hazan et. al., Revisiting the Polyak step size. In arXiv 2019", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xQYQIRdlis", "reviewer": "Reviewer_JWAj", "summary": "I think this is a solid paper, interesting and relevant to the community. As somebody who has worked and published on Polyak step sizes in the past, I find the new results interesting regarding the convergence of the Polyak step under the $(L_0,L_1)$-smooth condition. That helps explain some of the surprisingly fast practical convergence of Polyak step sizes. The new inexact Polyak step size is also interesting. It has clear limitations - it's 1/sqrt(T) rate - but given it's convergence rate holds without knowledge of f*, it is still very interesting. The holy grail here is log dependence on f* misspecification, so there is still some ways to go.\n\nThe experiments are inline with my expectations, to DoG method is know to be unstable on many problems and that's seen here. I always like to see more and larger experiments but I think these are sufficient, they cover some main problem classes and use multiple seeds.", "questions": "N/A", "limitations": "See above", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Clear and well explained theoretical results.\n- Puts results into context well.\n- Clear legible and relevant experiments.", "weaknesses": "- Some awkward or ungrammatical wording in places.\n- Inexact Polyak Step-size convergence rate is somewhat slow.\n- Dependence on estimate of key estimated parameter (f*) is not as good as D-Adaptation/T-DoG.\n- Stochastic case", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your quite positive evaluation of our paper.\n\n>  Some awkward or ungrammatical wording in places.\n\nWe will revise them in the camera-ready version by using an English proofreading service.\n\n> Inexact Polyak Step-size convergence rate is somewhat slow.\n\nAs the reviewer pointed out, Inexact Polyak Stepsize slows down the convergence rate to $\\mathcal{O}(1 / \\sqrt{T})$ compared with the clipped gradient descent with appropriate hyperparameters (Theorem 2).\nHowever, the study for parameter-free clipped gradient descent is a new research topic, and the lower bound for parameter-free clipped gradient descent remains unclear. We believe our discovery and proposed method will benefit future research for parameter-free clipped gradient descent.\nEspecially, revealing that the convergence rates of clipped gradient descent and Polyak stepsize are the same allows us to reduce the number of hyperparameters to be considered from two (i.e., stepsize and clipping threshold) to one (i.e., $f^\\star$), which will be quite useful for future studies.\n\n> Dependence on estimate of key estimated parameter (f*) is not as good as D-Adaptation/T-DoG.\n\nD-Adaptation and DoG try to estimate $\\| x^{(0)} - x^\\star \\|$, while Polyak-type parameter-free methods, including our proposed method, try to estimate $f^\\star$ by utilizing the lower bound $l^\\star$.\nThe study of parameter-free methods is still a nascent topic in the optimization community, and it is yet unclear which estimation is easier. Therefore, we believe it would be useful for future research to study methods other than DoG and D-Adaptation.\n\n> Stochastic case\n\nWe agree that the stochastic setting is important, but even the convergence analysis of clipped gradient descent has not yet been established in a stochastic and convex setting [1]. \nThus, we first need to establish a novel proof strategy for analyzing clipped *stochastic* gradient descent to create parameter-free clipped *stochastic* gradient descent, but it is out of scope in our paper.\nWe believe that it is one of the promising directions to analyze Inexact Polyak Stepsize in the stochastic setting, while we left this problem for future work.\n\nMore technically, the analysis of clipped gradient descent first derived the upper bound of $\\sqrt{f(x_t) - f^\\star}$ and then derived the upper bound of $f(x_t) - f^\\star$ by squaring both sides (see page 13 in [1]).\nIf we extend this proof strategy to the stochastic setting, we get the upper bound of $\\mathbb{E} \\sqrt{f(x_t) - f^\\star}$. Therefore, we get the upper bound of $(\\mathbb{E} \\sqrt{f(x_t) - f^\\star})^2$, which is not a desired upper bound because we would like to obtain the upper bound of $\\mathbb{E} f(x_t) - f^\\star$.\nThus, we need to establish a different proof strategy to analyze the clipped *stochastic* gradient descent.\n\n## Reference\n\n[1] Koloskova et. al., Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In ICML 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers and AC for their efforts in reviewing our paper.
We appreciate all comments and criticisms for improving our paper.


All reviewers point out that reducing $L$ to $L_0$ in Inexact Polyak Stepsize comes with the cost of slowing down the convergence rate to $\mathcal{O}(\frac{1}{\sqrt{T}})$ compared with the clipped gradient descent with appropriate hyperparameters (Theorem 2).
However, we would like to emphasize that asymptotic independence of $L$ can also considerably improve the convergence rate because $L_0$ is thousands of times smaller than $L$ in practice [1].
Here, we would like to provide the summarized comment at this point.
Detailed replies were provided to each reviewer separately.

Our paper studied parameter-free clipped gradient descent, and the main focus is to reduce the dependence of $L$ to $L_0$. 
Since $L_0$ is much smaller than $L$ in practice [1], reducing this dependence can significantly enhance the convergence rate.
To study the parameter-free clipped gradient descent, we analyzed Polyak stepsize under $(L_0, L_1)$-smoothness, revealing that Polyak stepsize can also reduce the dependence on $L$ to $L_0$ as well as clipped gradient descent.
Thanks to this discovery, we can reduce the number of hyperparameters to be considered from two (i.e., stepsize and clipping threshold) to one (i.e., $f^\star$).
Then, we proposed a parameter-free method for Polyak stepsize, called Inexact Polyak Stepsize, without losing the asymptotic independence of $L$.

Inexact Polyak Stepsize successfully achieves the asymptotic independence of $L$ and reduces the dependence of $L$ to $L_0$, while it slows down the rate with respect to the number of iterations $T$, as the reviewers pointed out.
We agree with the reviewers that the convergence rate of Inexact Polyak Stepsize $O(\frac{L_0}{\sqrt{T}})$ is not optimal in terms of $T$, and there may be room to improve this rate.
However, we believe our discovery and the proposed method are the important first steps for developing parameter-free clipped gradient descent.
Especially, uncovering that the convergence rates of clipped gradient descent and Polyak stepsize are the same allows us to reduce the number of hyperparameters to be considered from two to one, which will be pretty useful for future studies. 
We are grateful that all the reviewers found this discovery novel and interesting.
We will carefully discuss the above point in the revised manuscript.

Again, we thank the reviewers for examining our paper. We would like to respond to any of your comments if you have any concerns about our feedback. We value your feedback and welcome discussion.

## Reference

[1] Zhang et. al., Improved analysis of clipping algorithms for non-convex optimization. In NeurIPS 2020

Meta-review: This is a solid paper, interesting and relevant to the community. The new inexact Polyak step size suffers from a 1/sqrt(T) rate but its convergence rate holds without knowledge of f*. We recommend acceptance as a poster.

To authors: Following the discussion with Reviewer bj1n, make sure the comparison in Table 1 is as fair and explicit as possible regarding stochastic vs. deterministic regime. One way would be to add a column "Regime" with values "Stochastic" or "Deterministic" depending on the analysis. Another way would be to delete Table 1 altogether. Please also improve the color palette in the plots, as the yellow color is really hard to read.
Decision: Accept (poster)