Non-Uniform Smoothness for Gradient Descent
Authors: Albert S. Berahas
Lindon Roberts
Fred Roosta
Venue: Accepted by TMLR ()

Abstract: The analysis of gradient descent-type methods typically relies on the Lipschitz continuity of the objective gradient. This generally requires an expensive hyperparameter tuning process to appropriately calibrate a stepsize for a given problem. In this work we introduce a local first-order smoothness oracle (LFSO) which generalizes the Lipschitz continuous gradients smoothness condition and is applicable to any twice-differentiable function. We show that this oracle can encode all relevant problem information for tuning stepsizes for a suitably modified gradient descent method and give global and local convergence results. We also show that LFSOs in this modified first-order method can yield global linear convergence rates for non-strongly convex problems with extremely flat minima, and thus improve over the lower bound on rates achievable by general (accelerated) first-order methods.

Published in Transactions on Machine Learning Research (02/2024)
Non-Uniform Smoothness for Gradient Descent
Albert S. Berahas
albertberuhas
Department of Industrial and Operations Engineering
University of Michigan
Lindon Roberts
lindon.robert edu.
School of Mathematics and Statistics University of Sydney
Fred Roosta
fred. roostro Brg.. edu
School of Mathematics and Physics
University of Queenslond
ARC Training Centre for Information Resilience
Reviewed on OpenReview: https: // openreview. net/ forum? id= 17ESE)E76P
Abstract
The analysis of gradient descent-type methods typically relies on the Lipschitz continuity of the objective gradient. This generally requires expensive hyperparameter tuning process to appropriately calibrate stepsize for given problem. In this work we introduce a local first-order smoothness oracle (LFSO) which generalizes the Lipschitz continuous gradients smoothness condition and is applicable to any twice-differentiable function. We show that this oracle can encode all relevant problem information for tuning stepsizes for a suitably modified gradient descent method and give global and local convergence results. We also show that LFSOs in this modified first-order method can yield global linear convergence rates for non-strongly convex problems with extremely flat minima.
1 Introduction
In this work, consider gradient descent-type algorithms for solving unconstrained optimization problems
min f(x),
(1.1)
#ERd
where f Rd - I is continuously differentiable. Gradient descent-type methods for 1.1 have seen renewed interest arising from applications in data science, where d is potentially very large Bottou et al. 2018 Wright 2018). When analyzing such methods with fixed stepsize, it is most commonly assumed that Vf is Lypsiicchitz continuous and assume a stepsize of order 1/L,, e.g. (Wrighl 2018 Section 4). The key reason
behind this smoothness assumption is the resulting bound
Ly lly x (f()) - f(x) Vf(x) x)1
Va,y E Rd
In practice, however, Ly is usually not known. The simplest approach in this situation is to try several
stepsize choices as part of (possibly automated) hyperparancter tuning process (Snock et al. 2012). That said there are often benefits to changing the stepsize at each ileration, with common approaches including linesearch methods (Nocedal Wright 2006), Polyak's stepsize for convex functions [Polyak] 1969 (although this requires knowledge of the global minimum of f) and the Barzilai-Borwee 1988) (although global convergence theory exists only for strictly convex quadratic functions, and does not converge for some (non-quadratic) strongly convex functions without modification (Burdakov al. 2019)
stepsize (Barzilai Borwein,

---

Published in Transactions on Machine Learning Research (02/2024)
In the setting where L is known, this approach is still limited pessimistic, the stepsize is chosen to be sulficientll small to ensure decrease throughout the domain, as it reflects the global smoothness of f- In an iterative method it suffices to ensure decrease from one iterate to the next, and so of greater relevance is the local smoothness of f in a neighborhood of the current itcrate.
There are two natural ways that local smoothness could be used to modify the stepsizes in gradient descent. First, we could dynamically estimate Ly by looking at how rapidly f is changing near the current iterate. This approach is followed in (Malitsky & Mishchenko/ 2020), where Ly is estimated based on fxxx) ff(xx-1)l22/ (aa_-)))ll/lxx==---111 -2--1l22 This estimation procedure allows for global convergence of a hyperparameter--ie variant of gradient descent for convex functions. An alternative approach for convex problems is to estimate
the distance from the starting point to the minimizer ||:0- -xr'xr and use this to construct hyperparameter--in
methods |Carmon& & Hinder 2022 Defazio & Mishchenko 2023 Mishchenko & Defazio 2023). Alternatively,
we could assume the existence of an oracle that gives us a suitable local Lipschitz constant for V (Mei et al.
2021). There, it is assumed that one has access to an oracle L(x) that satisfies
L(x) 2
If(y) - V(=) x)1
ll - 21/2
Vy E R.
(1.2)
Although some useful propertics arise when allowing a stepsize of 1/(( for gradient descent (at current iterate oxk) for example faster convergence than gradient descent with fixed stepsizes the oracle L(x) has limitations. For example, if we want. to exploit extremely flat regions around minima, we may want [xx) - 0 as + x², but for (1.2) to hold with L(x") = requires f be a constant function.
In separate line of work, (Zhang et al. isfying a smoothness condition of the form | [1=)l22 v Tug + I, [<x)]], which was empirically motivated by training deep neural networks and also applies to some distributionally robust optimization problems (Jin
2020 considers gradient clipping methods applied to functions sat-
et al. 2021). This condition was slightly relaxed in (Xie et al., 2023) to the generalized Lipschitz condition
[V - fx & (Ta + [[IVS(x)112) llv x/|2, Va ERd, Vy E B(x,1/In)
(1.3)
noting in particular that the inequality only needs to hold for x and y sufficiently close.
In this work, we consider a more general and localized form of the approach from (Mei et al. 2021]. b where our oracle only requires bounds similar to (1.2) to hold for y E B(x, R) for some R> 0. Such local first- order smoothness oracle (LFSO), gives a local Lipschitz constant over explicitly defined neighborhood. Such LFSOs exist for any C2 function (not just those with Lipschitz continuous gradients), including those satisfying the weaker smoothness condition from (Zhang et al., 2020: Jin et al., 2021] mentioned above. Given the availability of a LFSO, we show how this can be used to construct a convergent gradient descent- type iteration that does not require any hyperparameter tuning. Similar to the case of 1/L., stepsizes, this parameter-free result comes from the LFSO capturing all the relevant problem information.
To show the promise of this approach, we demonstrate in Section 4 how the incorporation of a LFSO allows gradient descent to achieve global linear convergence rate to arbitrarily flat minima of convex functions. We do this by considering a class of objective functions which include f(x) = ||=1|"" for p + co, where (x) is extremely flat near the minimizer x² = O. This is achieved by the LFSO allowing larger stepsizes as I + x", counteracting the degeneracy of the minimizer. These functions are known to be difficult for gradient descent iterations, and in fact provide the worst-case lower bounds for accelerated gradient descent (Attouch et al., 2018 2022) | Further, in Section 5 we show that our LFSO approach gives global linear convergence rates for objectives of the form f(x) very degenerate minimizers. Our numerical results in Section G show the global linear rate achieved in practice by the LFSO approach for both types of objective functions, compared to the (expected) sublincar rate for standard gradient descent. We note that the objective f(x) = ||= can alternatively be minimized in 1 iteration using iterativoly reweighted least-squares (IRLS). IRLS only has local convergence guarantees for problems of the form f(x) = || blbp
2r for p - xo, an alternative set of objectives with
22 when p < 3/2 and can diverge for larger p without careful
modification Addi et al. 2019).
Of course, LFSO requires more problem information than these methods to achieve this result.
2

---

Published in Transactions on Machine Learning Research (02/2024)
Compared to the similar methods mentioned above, LFSO is the only method with global and local conver- gence theory for general C² nonconvex objectives. By comparison, (Malitsky & Mishchenko/ 2020 Carmon
& Hinder 2022 Defazio & Mishchenko] 2023 Mishchenko & Defazio 2023) only have global convergence
results for convex objoctives" [ and (Mci et al. 2021 only considers global convergence for nonconvex func- tions the presence of a specific non-unilorm Eojasiewicz condition. Our numerical results for specific convex functions in Section show that the method from (Malitsky Mishchenko 2020) gives fast global linear convergence on the samn problems, but this is not proven. We also note that the LFSO approach is potentially more suited for adaptation to stochastic optimization than (Malitsky & Mishchenko 2020 as it does not require taking differences of (stochastic) gradients.
In the general nonconvex case with Lipschitz continuous gradients, LFSO recovers the standard O(e-²) iteration complexity required to find an c-optimal point. The per-iteration cost LFSO is one gradient evaluation and up to two LFSO evaluations. In terms of scalability, the practicality of this approach depends on how efficient an LFSO evaluation is; identifying general settings where LFSOs are casily computable is important direction for future work. However, for all the example problems considered in this work, the computational cost of evaluating the LFSO is similar to (or cheaper than) the cost of single gradient evaluation. Our approach also avoids the need for any expensive tuning of learning rates (and in some cases achieving global linear convergence rates).
This introduction and first analysis LFSO methods demonstrates it to be a promising avenue for future work, by giving an explicit mechanism to decoupling stepsize selection from objective smoothness (and hence avoiding hyperparameter tuning), and in some specific circumstances being able to adapt to extremely flat regions of the objective function. The LFSO approach requires more complex oracle and a choice of initial radii R& (for examples in Sections and 5 Rs | f (=x)lle is used), and so an important starting point for future work would be the efficient construction of such oracles (and indeed it would be useful to know when such oracles are easy to compute), and developing a systematic understanding of suitable values for Rg. This future work would enable a thorough numerical evaluation of the LFSO approach on more realistic problems.
2 Algorithmic Framework
We now introduce our new oracle and show our algorithmic framework which incorporates the LFSO oracle into a gradient descent-type method.
Definition 2.1. Suppose f Rd + IR is continuously differentiable. A function L : Rd x (0, o0) + [0, oo) is
a local first-rrder smoothness oracle (LFSO) for J is
L(x, R
If(g) - f(x) f(x)= (y -y-x)1 =
2 by x112
(2.1)
for all x Rd, all y E B(x, R) and for some R > 0, and L is non-decreasing in the second argument R.
For example, if f is Ly-smooth-ic. Vf is Lipschitz continuous with constant Ly-then L(x, R) = Lg defines an LFSO for f. Treating this as an oracle rather than a problem constant encodes the common algorithmic assumption that Ly is known. However, LFSOs exist for much broader class than Ly-smooth functions.
Lemma 2.2. I is CR(R)), then L(x, R) max 2 [y)il is an LFSO for J.
Proof. It is straightforward that L is non-decreasing in R. In this case, the property 2.1 is well-known, for instance (Cartis et al., 2022 Corollary A.8.4 & Theorem A.8.5)
Another common smoothness class is the case of C2 functions with Lipschitz continuous Hessians. In this case, Lemma 2.2 gives a simple, explicit form for LFSO.
Furthermore, [Carmon Hinder 2022 requires uniformly bounded (stochastic) (sub)gradients, and Defazio Mishchenko
2023 Mishchenko & Defazio 2023) require f to be Tipschitz continuous.
3

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma 2.3. If f is (RR) and f is Lи LipLiscchitz continuous, then L(x, R) [2=] L is LFSO for f.
Proof. This follows from Lemma 2.2 and that | I [V2 La LaI yll for all y B R).
S
A useful property that will use to get explicit formulae for LFSOs the following straightforward consequence of [2.1p.
Lemma 2.4. Suppose I. is LFSO for and Mar, R) Mx, R) for all Rd and all R > 0. Then L. is LFSO for f if and only if L is non-decreasing in R.
To incorporate an LFSO into gradient descent-like iteration, natural step would be consider ileration of the form
7 V (x(x),
2k++1 3k L(rk. R&)
(2.2)
for some appropriately chosen values of Rg > 0 and 1 0. In the case where f is Ly-smooth, standard convergence theory (e.g., (Wright] 2018 Theorem 4.2.1)) would suggest that value such as is appropriate. This shows that the LFSO notion encapsulates the problem-specific aspect of choosing a suitable stepsize.
However, the choice of R& not so straightforward: for property 2.1 ((*++1) < f(xx) would need Fx41 B(x,, Rx). This is not guaranteed if Rg is chosen too small, as the following example illustrates.
be useful typically to prove that
Example 2.5. If d and f(x) = x4 then a suitable LFSO is
L(x, Rt) = 24r² 24R2,
using Lemmas 2.2 and 2.4 as well as
max 12y² = 12 max ((x RT)2, (ar + R)}} < 12(22² + 2 s
from Young's inequality. Suppose z4 and 1) 1, then from 2.2
we may compute
[x++1 Fkl
6 + 6R
and so J&+1 & B(Ik, R&) whenever R3 is smaller than R x 0.16238, the unique real root of p(R) =
6R3 + GR
To avoid this issue, first pick an arbitrary value for R2, then possibly increase it to sufficiently large value that 2z41 is in the required neighborhood of rę- The resulting method is given in Algorithm | Note that it requires one evaluation of V and possibly two evaluations of L (oracle calls) per iteration.
Computational Cost of LFSO Evaluation In practice the computational cost of L (performed poten- tially twice per iteration of Algorithm D will depend on the specific problem being analyzed. However, for the examples this work the cost of one LFSO evaluation is small, of the same order as single gradient evaluation (or potentially cheaper the gradient has already been evaluated).
In Section 4 where f() hgg()), the dominant cost of the LFSO 4.2 is the evaluation of [Vg(()] but Vg(x:) has already been evaluated when originally computing fz)).
In Section 5 for linear regression problems, provided quantities only depending on the problem parameters A have been pre-computed, the LFSO (5.3) dominated by one residual calculation Az - b. This residual is computed when evaluating the gradient, so the LFSO cost dominated by evaluating || bll when Ar b is already known, of cost O(n) for a problem with n residuals. This is cheaper than the cost of a gradient evaluation, which also requires matrix-vector product not present in the LFSO evaluation.
4

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm Gradient Descent with LFSO.
Input: Starting point 2o E Rd, stepsize factor > 0.
for k= 0, ..... do
Choose any R3 3: Set
Ra max Re, L R
(2x))
(2.3)
Iterate
2k+1 26
Vf(xx).
(2.4)
L R
end for
In Appendix A we also derive LFSO for 2-class logistic regression and show the same cost. Section the dominant cost of evaluating the LFSO is an extra (nn) for training data of length (beyond information already computed in a gradient evaluation), plus gradient evaluation requires extra matrix-vector product not present in the LFSO evaluation.
3 Convergence Analysis
In this section provide global convergence results for the general nonconvex and PL/strongly convex cases, and also local convergence rates to non-degenerate local minima. To enable these, we prove a descent lemma (Lemma 3.2 suitable for Algorithm
Assumption 3.1. The function f I& R continuously differentiable and bounded below by f and L is an LFSO for f-
Lemma 3.2. If Assumption 3.1 holds, then Algorithm produces iterates satisfying
f(x+11) f(xx)) L(æx, R&) (1 (1-/) - [V
(3.1)
for all 0, I,...
Proof. Since R% 2 R& and L is non-decrcasing in R, we have that
| skll
[ S I( Rτ)
"
Vf(xx)l s Rk.
(3.2)
L L( Rs)
and 2.1 can be used. That is,
| [V(xx)]12 + L(øx,Ra) Ra))
n²
((x+1)- - ((xx)) S L(aR, Ra)
| [1x)))1)
2
L(x,, R2,
(1-2) | [V[(x))
L(xk, R&)
which gives the desired result.
Since the LFSO captures all the necessary problem information, the requirements on the stepsize factor 7 are straightforward.

---

Published in Transactions on Machine Learning Research (02/2024)
3.1
Global Convergence
Theorem 3.3. If Assumption 3. holds and 0 2, then either
lim inf V [xxx)l = 0, or
lim R
L RA) = oc.
8000
Proof. From Lemma 3.2
we have
[(xk) - (( 2 (12 1)
[[(x))]]
(3.3)
2L(EK, RE)
By summing over k we get
[f((x)]1 2]f(xo) - fr1
< 00,
(3.4)
L(rk, Rx) 1/2 11)
k=0
hence lim3-
R&) = 0, and the result follows.
Of course, this is not quite a convergence proof, as we need to be concerned about the risk of L( R&) growing unboundedly, which could occur in cases such as f() = sin(=²) if || + co during the iteration. One simple situation where this behavior does not occur the following.
Corollary 3.4. Suppose Assumption 3.1 holds and 0 < n < 2. If the sublevel set {x E Rd f(x) s f(xo)) is bounded, L is continuous in I, and the choices Rg are bounded, then limg [[(x) 0.
Proof. If R2 R for all k, then L( RR) L( From Lemma 3.2 know z& {o E Rd f(x) < f(x0)} for all k. Then we know that RR, [[x)) and L( R&) are all bounded, and so R4 is bounded too. Finally, this means L(z,, R is bounded, so limx-400 [V L(x,, Rx) = (derived in the proof of Theorem 3.3 gives the result.
In fact, under the assumptions of Corollary 3.4 3.4 actually gives us the common O worst-case iteration complexity rate for nonconvex problems (c.g., (Cartis et al. 2022| Chapter 2)). We note that these assumptions are weaker than assuming L Ly-smoothness everywhere, as we only care about the LFSO in the initial sublevel set.
Remark 3.5. The above (in particular (3.2 still works if we replace |/ [V(xx) in (2.3) with any upper bound C& 2 f=(x))] This will be useful in Section
In the case where f satisfies the Dolyak-Lojasiewiee (PL) inequality with parameter p >> for example if f is y-strongly convex we can achieve convergence even in some cases where L(x,, Rx) + co, provided it does not increase too quickly.
Theorem 3.6. Suppose Assumption
3.1 holds and 0 < 2. If is u-PL, that is
f(x) - fr < 24
Va V Rd
(3.5)
and
L(ok, Rx) = oc,
k=D
then limg-ro ff
3 Ste. the maximum number iterations before [[ first attained.

---

Published in Transactions on Machine Learning Research (02/2024)
Proof. From Lemma 3.2 and 33. get
f(x++1) - f f(xx)= -5 L( R&)
(1-2) |V ((x))
(3.6)
12 - 11)
(f(xk)- -
(3.7)
L Rx)
By summing over & get, by the assumption in the theorem statement,
pm 17) oc,
(3.8)
Lirk R&)
and so the result follows from (Bertsekas
2015
Prop A.4.3).
We should note that if f is coercive (e.g. f is strongly convex) then the sublevel set fa f(x) - f(2o)} is bounded, and so Corollary 3.4 guarantecs convergence (provided the R2 are bounded).
3.2 Local Convergence Rate
Encouraged by the result in Theorem 3.6
we now consider the local convergence rate of Algorithm to
non-degenerate local minimizers.
Theorem 3.7. Suppose Assumption 3.1 holds and 0 < 7 < Suppose also that f is also C²(R") and x² is local minimizzr of I with Amin (V' fxx)) sufficiently close x² in the sense that
0, is continuous v, and Rg 0 for all k. If xo is
||50- -011 Ri (where B(x", BI) is a region where f is p : Amiu (V2 (V2 convez), and [(xo) - f(x)) S R22/2 (where R2 S R1/2 and [[V[(x)] S pR2 whenever E B(x", R2)
then Ik + xx R-linearly, with
| - x x= Linax (1-
12 - 11) k Temax
||:00 x=1
(3.9)
for conslant Lmmax > 0 (defined in 3.10 below).
Proof. Since f is C22 There exists neighborhood B(x",Ri) within which f is j-sttrongly convex for = Amiu 2 (x*))) Given this neighborhood, define
Lmax
max BEB(2" B1) OSRER:
max L(x, R).
(3.10)
Hence, whenever || x*1l R1, we have L( R&) S Lmax- Strong convexity also gives
- f()) f())(((((())))
x)> ~ - x||
for any x, y E B(x", R1), and so it follows that L(x, R) 2 p for all B(x* R1) and R > 0.
Since is C there exists" R2 I RI/2 such that [x())] < nR (2n) for all B(x" R2). Then if
|| x²1 < R2, we have
[ - -
S [2 x²1l n
Vf(xx)] S Rg +
R < Ry 2
L( RA)
SSince Vf is continuous, there ball B(x" R2) such that [[ all B(x", R2) (with arbitrary, such (21/(2n) above). Then take R2 min( R2/2,

---

Published in Transactions on Machine Learning Research (02/2024)
Now, for any E B(x", R1), by strong convexity in this region, it follows that if f(x) - f(x²(((++))))))))))) S pR
then | x"I I R2. Given this, suppose that zo is sufficiently close to x" in the sense that E B(x", R1) and f(rn) - f(x²) & 2R2/2 /2. We then have that zo E B(x", 3(*x, and so 21 E B(xx,Ri from the above. Lemma 3.2 implics that (x11 I (zo) and so in also satisfics f(x1) f(=)=(==))))))))))))r()))) ) - pR which in turn implics #1 E B(x", Rg).
By induction, we conclude that za B(x", R1) for all k (and also that IN B(x", R2) for all k). Then, by the same reasoning as (3.7). since (35 holds in B(x", RI) and L( Rx) S Lmax: we have
((041))((z')) S (1 1m 1
(f(x))-(xa))
1 f(x)))
Timax
and we have a linear convergence rate of f(xx)= + f(x*). Finally, we use the strong convexity result that Nesterov
2004
Lemma 1.2.3 & Theorem 2.1.7)
M 2 || - 1- s f(x) -s(x))
L Lmax | - x: xx111
to conclude that
2 (f(xx) f(x²))
s 2 2(1 1nn22 - (f(zo) - f(x"))
20k x²1 5 1
4
Lmxx
Lmax
(1 1 1m7(2 117(2-111 11) m)
||:00 x²11?
Lmax
p
giving 3.9
4 Global Rates for Compositions of Functions
Motivated by problems with very flat minima, we now consider the performance of Algorithm T when the objective function has specific compositional structure. Assumption 4.1. The objective is f(x) = h(g(z)) where:
The function g Rdd + is lwice continuously differentiable, Vg is Lápscchcl continuous, and g is PL with minimizer satisfying g(x*)=
The function h: [0, oo) + R is twiice continuously differentiable, strictly increasing, strictly convex, h² is non decrescre,,,g, and ht(t) = O(t)) as t - 0+, for some 2
We note that the assumptions on imply that
2 g(z) < [Vg(+)] < 2Lg g(x), Vr E Rdd
(4.1)
where the rinht-hand inequality follows from (Wright 2018 eq. (4.1.3)), and that x² (the minimizer of g) is also a minimizer for f with f(x*) h(0).
The function g could be, for example g(z) = |A bl2 for some consistent linear system Ar b, but in general need not be convex. We are most interested in Assumption 4.1 when the outer function h is very flat near 0, such as h(tt) = (P for p > 2, although other functions such as h(t) = t are also allowed. In general, this means that f is not PT,, as shown by the case g(x) = x² and l((1) = 12.
Even though f not PL, we will show that the iterates generated by Algorithm D exhibit a global lincar convergence rate, which is typically only seen for PL functions (for standard GD-type methods). To show this, we will need the following technical results.
8

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma 4.2. Suppose Assumption 4.1 holds and we perform the iteration
xs+1 = 2/ Th Vg(xx),
where there erists E Lg) such that e 1k S 2/ bu for all k. Then
g(ax) - (1 Uge(2 Lgt))* g(zo).
Proof. This gencralization of (Karimi al. 2016 Theorem 1), which proves the case where c = 1/Lg (i.e. M/s bu for all k). Since g -ggsmmohhh have
Lg
g( S g(xx)) mh Volx)(
Vg(xx)]
2
g( 1p Lig'ti
[[Vg(z))
(((x)) - 7 (1- T.g711: g(0x))
where the last incquality holds from 4.1 and so
g( $ (1
[
2 (1- T )) g(xx),
or
g(Fx)) S (1 Mg/l T.gg)))) g(
The termn (2 Lynk) is positive for all 17 (0, 2/ Lg) and maximized for = 1/Lg. in which case (m - [ight)= = /g/ Ly I 1. Hence, m E [c, 2 Ln c), then
0 myc(( Tncc) My Tg uh/ Lgg 1.
The result then follows.
Corollary 4.3. Suppose the assumptions of Lemma 4.2 hold. Then [V + 0, R-lineorly.
Proof. Since Vz(z) = (((g(=)) we use 4.1 to get
\f(x*)) = N ()(x)))
[g(+=)] s /2Lg N'' N((g(x))) V((=)).
noting that N (((((x)) since strictly increasing. Then by Lemma 4.2 we get g(xx) S g( and so
[ s 22 (l(((z)) (1 uye(2 - Lge)) 8/2 Vg(zo).
where we have used that W is increasing (since h is increasing and convex), and [V/(())] - 0 R-linearly with rate (1 p2 - 2/2
Now for the objective given by Assumption we have
Vf(x) = Vl(g(z))VV((z)) and v²f(2) = [((( +((g()))V'(()))
and for the purposes of calculating L(x, R) we estimate
max 2 f(x + 8)(l < h² (g(( -
+ b))
Using 4.1
and Vg(x s)ll | |=(())| we get the LFSO
[L [Vo=)1l
[L,R+ [V9(2)]11
L(x, R) =h²
[LgR R + [V +
Lg
(4.2)
2
2
9

---

Published in Transactions on Machine Learning Research (02/2024)
Note that L is non-decreasing in R follows since h and h" are non-decreasing, and h" > 0 (Assumption 4.1
By observing the form of L(x, R) 4.2 it is natural to consider R3 = [[g(z))] since these two quantities (i.e. R and [[Vg(z)])) always appear together and it is a computable/ known value. It is this choice that will give the fast global convergence rate Algorithm [
Lemma 4.4. Suppose Assumplion 4.1 holds and we choose Rs = [|Vg(aa)] and any v > 0 in Algorithm
(with LFSO 4.2 Then RR = D& (g(xx)) for some Dae [1, max (1, n/ Lg)]-
Proof. Substituting our choice of R2 in
4.2 we get
ny (((((<=))
Rs = max
[V
h"
(6a+1)21VVoe+>)1l (Lg + 1)2[Vv(==>11 W
Vg Lg
2ph
2pg
n/h!
[Valoa)ll") [[/((a>))]
< max [[Vg(z))]]
2pg
(Lo+t))11Vg(ee) L.g
2110
{1, 1, Tog
< maxx
[Vg(aa]]
where the last line follows from h strictly convex (so h is non-decreasing). This gives Dr S max (1,7/T.g) That D& 2 follows from RA Rg (by definition of Ry).
We can now show our global lincar rate for Algorithm I for this specific problem class.
Theorem 4.5. Suppose Assumption 4-1 holds and we choose R2 = [[/g(*)]] and v E (0, in Algorithm
(with LFSO 4.2 ). Then [[ + R-linearly.
Proof. From Lemma 4.4
we have
L[rK, Rx)= 11 (LyDz + 1)² 1)²1 (V([)))))
(T.g 1)) 1/ (LyDs + 1))"|V T.g.
2/1
2/1g
Our iteration can be expressed
(1((((k)) Vg(xx).
Fk-1 Ik
T(rks Ra))
Since h is convex, have h" 2 and h' is non-decreasing, using 4.1 get
Lg 1' (Tng DT Dr + 1) 1)
[V Ly 1'(g(xx))
[(rK, RR) 2 K/
2
2p4
which gives
n (g((g()))) < n
(4.3)
L(rk, R2)
Lg
Separately, since h/ > 0 and h² is non-decreasing, have (for any t 2 0)
t-) S J.¹
< 12(2t),
and so
h" (LgDs - 1)2 192
(L + 1
(L,Dr + +))1 < 2
2p
10

---

0. Published in Transactions on Machine Learning Research (02/2024)
Since h' is non-decreasing, we then conclude
L( Rs) S (2pg + Lgght (LyDDe + 1) +1)VVo((=>))
M9
From 4.1
we then have
Lgg + 1)2 (())))))
Mæx. Ra) S (2pkg + Lig)t
Mg
Denoting Cs = (Tg Dr 1)2 /pg, this means
hh' (g(x))
(g(((()))
L [ R&)
(2 + (C
We note that S C2 < Cmax == 2Ly max 1, 17 Lg) 1)2 from My S Lg and Lemma 4.4 respectively.
Also, since Algorithm| 1 is monotone (Temma 3.2 noting Assumption 3.1 implied by Assumption 4.1 we have f(xx) S (xo) and so g(xx) S g(xo) since increasing.
Now, since (t) (tt)) as t 0t, there an interval [0, ö] constants 0 C1 S C2 for which
Citº s (1)( S C2t,,
vt e [0,60
If Ckg(za) s 8, then we have
H((((x))) 2 Cig(zx)" h((Ckg(Iz)) C2C%g(Zu))
Ci
C2Chnax
By contrast, if Cag(ZN) > 5, then g(xo) 2 g(xx) 5/Cmax. Since h' is contimuous and strictly positive for all t 0, we have
11(t)
6D = min
8/Cmer Staa(aa) hi (C(Cmaxl) 0,
and so this case we have
l'(((x)) N((Cug((x))
1(g(ax))
2 ED
((Cmmxx((Ea))
In either case, have
17 h1 (g(aa))
C2Chaax , E0 50))
C1
min
> 0.
(4.4)
L(Tx R4)
2/g + Lg
The result then follows by combining
and 4.4 with 1 E (0, 2) and Corollary 4.3
We reiterate that this result is a global linear rate, and does not require 2g to be sufficiently close to x (although the actual linear rate does potentially depend on zo). This applies to functions with extremely flat minima, such as f(x) ||= 2 for any (by taking g(z) || and h(t) tt).
5 Global Rate for Linear Regression
Another important problem class where Algorithm can achieve a global linear rate (at least in some cases). is the case of lincar regression with an Ep loss function:
min f(x) || b1129 ZE3d
(a 6.)
(5.1)
for some e gaxd with rows a, E dd for I...., n, and b R", and p E N. The choice norm here avoids any issucs of non-smoothness the objective, but taking p - so again recovers situation with extremely flat local minima. Our theoretical results will hold in the case where A is sufficiently well-conditioned, which 2p
in particular includes the case f(x) ||00|| 2p
11

---

Published in Transactions on Machine Learning Research (02/2024)
Assumption 5.1. The matrix A has full rank, S d, and x(A)* < nn(nn 1), where x(A) is the 2-norm condilion number of A.
Observe that Assumption 5.1 implies the system Ar = is consistent. We also note that Assumption 5.1 is quite restrictive, especially when n is large, requiring the rows of to be almost orthonormal. Given this, we delegate the technical details of this section Appendix B
For
5.1
we have
Vx(x) 10pAA(A:: b)2p-1 and (²)())= 2p(pp-2p2p1111) 1)A" diag(Ar b)2p-2 2A,
where (Ar b) is understood to represent element-wise powers. We now need to provide an LFSO for f(x) 5.1 In the case p = 1 that is, typical linear least-squares regression- we have (²x(x) 2p(2p - 1)A7 and so we automatically get
Lix, R) = 21
(5.2)
valid LFSO. In the case p 2,3, 4, valid LFSO for (5.1 is
(z. 2p(2p - 1)]1-113 2 || - 20120-2
max i=L....
10:112
2p-2 R
(5.3)
as derived in Appendix B.1
We note that substituting p = into 5.3 recovers 5.2 and so 5.3
a valid
LFSO for all p e N. Observing the form of (5.3) a natural choice for RA is RĄ = A bll.o.
Theorem 5.2. Suppose Assumplion 5.1 holds, and we choose Rg | -1000 and 11 E (0, 1] in Algorithm 7
(with LFSO 5.3
Then for any p N, the residual ||ræl| - 0 Q- 2-linearly.
Proof. See Appendix B.2
The above gives a global linear rate under some restrictive assumptions the problem 5. satisfied if A = I, for example, which gives us the objective f(x) = || [2r for any p.
They are
6 Numerical Experiments
In this section, we provide some brief numerical experiments confirming the global linear rate for Algorithm 1 (with an appropriate choice of Rg and no tuning of the fixed stepsize = 1) for objectives of the form f(x) = ||>11"" as in Section and f(x)= = ||~|| 2p
2p as in Scction 5 In all cases, we use d 10 dimensional problems and starting point zo = (1,...,1) 1)T and p = 1,...,., 5. For both objectives, the = 1 case gives the strongly convex objective f(x) = ||<1 but for p > we only have (non-strong) convexity and a flai neighborhood of the global minimizer x² 0. In all cases we plot the normalized gradient decrease [VV
as function of iteration k, for up 10a iterations.
For standard gradient descent with fixed stepsize, fast convergence, some mild tuning of the stepsize v was required. For both objectives, we see that gradient descent achieves a global linear rate for = 1 as expected, but a clearly sublinear rate for all > 1, again in line with expectations.
get the results shown in Figure To see sufficiently
When running A Algorithm 1 we use R2 [|Vg(=))]2 = 2||0||a for f(x) = ||- (based on the framework
of Section 4 and R4 = || for f(x) = || ? (based on the framework of Scction 5). The corresponding results are given in Figure 2 Here we see the expected global linear rate for all values of p, not just the strongly convex case p 1. We do note however that the rate of convergence is faster for smaller values of p.
By comparison, A Appendix C.1 shows the same results for the adaptive gradient descent algorithm of (Malitsky & Mishchenko 2020) (using the recommended starting stepsize 7/o = 100 10 which is automatically adjusted after the first itcration). This method outperforms both standard gradient descent and Algorithm ] and indeed appears to show global linear convergence rate for all problens. However, this result is not proven, and no convergence results for this method are known for nonconvex objectives.
12

---

Published in Transactions on Machine Learning Research (02/2024)
10
(y 0.01)
10
0.001
00000)
1.5x 06
10
10
10-+
10-4
10.5
10000
2000
6000
Irerationn
Iberation
(a) f(x) = ||>| 2P (varying y values)
(b) f(x) = |=1 (all use 7 = 2)
>> 0 achieved by gradient descent with fixed stepsize for non- strongly convex functions with flat minima. Plots show [/ as function of k.
Figure
Global sublinear rate [(x)]l
10-
10-
10 1-
10-1
[
10-1
10-7
10-7
10-1-
10-
10-3:
10-11
10-11
10
10-11
2000
6000
10000
4000
8000
1000
Iteration
(a) f(x)
1|=11/"
(b) f(z) = ||||
Figure 2: Global linear rate [V achieved by Algorithm 4 for non-strongly convex functions with flat minima. Plots show ||V (2=))l2/1V(( as function of k.
Runtime Performance Since Algorithm is computationally expensive than gradient descent per-iteration basis (from up to two evaluations of the LFSO per iteration), the above results are shown in terms of runtime (rather than iterations) in Appendix C.2 We see that Algorithm [ is slower than gradient descent, but not significantly (within a factor of for the slower problems p = 3,4,5).
Mis-specification of Rs The above results for Algorithm | assume that Rd is chosen according to the theoretical results in Sections and In Appendix C.3 we consider the impact of significantly mis-specifying R& (i.c. by changing the order of magnitude, not just adjusting by a constant) Algorithm 1 We see that using Rg too small appears to have minimal impact on the convergence rate and Rş too large worsens the convergence rate to sublinear.
7 Conclusions and Future Work
We have introduced new oracle for local first-order smoothness, which exists for wide range of functions and encodes all of the problem information relevant for selecting stepsizes for gradient descent-typs type methods. Using the LFSO, we introduced practical gradient descent-type method, and showed global and local
13

---

Published in Transactions on Machine Learning Research (02/2024)
convergence results under reasonable assumptions. We then showed that this method gives global linear rates for some specific (non-strongly) convex functions with degenerate local minima.
There are many potential directions for future study of LFSOs, including automatic differentiation techniques for building LFSOs and understanding how to pick the forcing sequence Rg- This would enable more extensive numerical testing of the LFSO approach to ascertain its usefulness on problems of more practical interest. Additionally, the use of LFSOs in broader optimization settings, such as constrained, bilevel, nonsmooth and/or stochastic optimization is an interesting direction for future work.
Acknowledgments
FR was partially supported by the Australian Research Council through an Industrial Transformation Train- ing Centre for Information Resilience (IC200100022). Albert S. Berahas was partially supported by the Office of Naval Research under award number N00014-21-1-2532.
References
Deeksha Adil, Richard Peng, and Sushant Sachdeva. Fast, provably convergent irls algorithm for norm linear regression. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceeddngg wtt.:ggs.wrrrrr.ceeeeeeee httpp//ppppp.eeeeppppeeee///eeee files//ppeee/211///1ee #6C77558873777022555555766866888
paf
Hedy Attouch, Zaki Chbani, Juan Peypouquet, and Patrick Redont. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming, (61(1)):12331175 2018.
Hedy Attouch, Zaki Chbani, Jalal Fadili, and Hassan Riahi. First-order optimization algorithms via inertial systems with Hessian driven damping. Mothematicnl Programming, 193(1):133-11) 155, 2022.
Jonathan Barzilai and Jonathan M. Borwein. Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8(1):141 148, 1988. doi: 10.1093/imaae immaum/8.1.144
Dimitri Bertsekas. Conver Optimization Algorithms. Athena Scientific, 2015.
Léon Bottou, Frank E. Curtis, and Jorge Nocodal. Optimization methods for largo-scale machine learning. doi: 10.1137/16M1080173.
SIAM Review, 60(2):223-31) 311, 2018.
Oleg Burdakov, Yuhong Dai, and Na Huang. Stabilized Barzilai-Borwein method. Journal of Compulational Mathematics, 37(6):916699) 2019. doi:
Yair Carmon and Oliver Hinder. Making sgd parameter-fres
Po-Ling Loh and Maxim Raginsky (eds.): Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learn- ing Research, pp. 2360-2389. PMLR, 02-05 Jul 2022. URL httts::/ htt..ceeeddna.......er.////1.. press/v178/ carmon22a. html
Coralia Cartis, Nicholas T. M. Gould, and Philippe L. Toint. Evaluation Complerity of Algorithms for Nonconvez Optimization: Theory, Computation and Perspectives. Number 30 in MOS-SIAM Series on Optimization, MOS/SIAM, Philadelphia, 2022.
Aaron Defazio and Konstantin Mishchenko. Learning rate--rtt-----e learning by d-adaptation. The 40th Interna- tional Conference Machine Learning (ICML 2023), 2023.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. In 35th Conference on Newral Information Processing Systems, 2021.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Lincar convergence of gradient and proximal-gradice methods under the Polyak-Lojasieviez condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795 811, 2016.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity in first- order non-convex optimization. In Proceedings of the 38th International Conference on Machine Learning. 2021.
Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free learner. arXiv preprint (xXi:2206.06100) 2023.
Kevin P. Murphy. Machine Learning: Probobilislic Perspective. MIT Press, 2012.
Yurii Nesterov. Introductory Lectures on Convez Optimization. Springer US, 2004. ISBN 978-1-4020-7558-7.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering, Springer, New York, 2nd ed edition, 2006.
B.T. Polyak. Minimization of unsmooth functionals. USSR Compulational Mathematics and Mathematical Physics, 9(3):14 29, 1969. doi:
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning al- gorithms. In NIPS'12 Proceedings of the 25th International Conference on Neural Information Processing Systems, volume 2, pp. 2951 2959, 2012. doi: 10.5555 10.5555/2999325 229992299 22999444..
Stephen J. Wright. Optimization algorithms for data analysis. In Michael W. Mahoney, John C. Duchi, and Anna Gilbert (eds.), The Mathermatics of Data, volume 25 of IAS/Part City Mathematics Series, pp- 49-97 American Mathematical Society, Providence, Rhode Island, 2018. doi: ww.10000pemm//225
Chenghan Xie, Chenxi Li, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. Trust region methods for nonconvex stochastic optimization beyond Lipschitz smoothness. orXiv preprint arXiv:2310. 17319, 2023.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In Proceedings of the 8th International Conference on Learning Representations ICLR, 2020.
A LFSO for Logistic Regression
Here derive LFSO suitable for 2-class logistic regression. Following (Murphy 2012 empirical risk minimization problem is
Chapter 8), the
n ly log(us(w)) + (1 -11--0 - y:) log(1 (s(w)))),
min ((w) Σ wERd
i=1
where (w(w) (w x;) for (1) = 1/(1 + e) and we have features Is E Rd and labels yi E (0, The associated gradient and Hessian may be written as
X =
(m(w) XT((ww
v), and v²f(w)= XT
where X E Raxd and y E R" contain the training data and labels, p(w) E R has entries (ı(w), and 5(w) = diag(o' (aagg(a(vii (wTTaa)
ax)) E Raxn.
Since dt(t)= E 00, 1/4] for all t, we automatically have | f(w)ll < || Thus Vf is Ly-smooth and Algorithm with 77 1 can reduce to standard gradient descent with learning rate 1/L
If we want to get tighter LFSO, we start by noting that o'(t) (t) at)) and so a²(1) 20)3) 3a + at), (t),, and since ott) E [0, 1] we have (o"(t) < /3/18 for all t. Hence by Cauchy-Schwarz and Taylor's Theorem, we have
/3 /3
o'(w + x))) < o'(wFxx))
18
15

---

Published in Transactions on Machine Learning Research (02/2024)
whenever ||s||2 & R. Hence more precise LFSO for this problem is
|| max min { ('(("Tx:) xx) i=l...
v3 R|jaall2 1
L(w, R)
(A.1)
18
If the data X is separable, then near the optimum w" it is likely that all w xs far from zero, and o'(w"x;) 24) < 1/4, and so taking this LFSO with small R may improve on the simpler L(w, R) = 1 | from Lipschitz continuous gradients.
The computational cost of evaluating Vf(w) is one evaluation of (u(w) = o z;) for each and one matrix- vector product with X. If [ and |æv]|2 have been pre-computed, then since o' d'(w"a x4) = (; computing the LFSO (A.1 requires the evaluation of each (4(w) plus ((n) in extra calculations. Thus LFSO evaluation is actually computationally cheaper than one gradient evaluation.
B Technical Details for Section 5
B.1 Derivation of LFSO
Here we derive the LFSO 15.3 for problem
5.1 with p= 2, 2,3,4, 4,...
Lemma B.1. For any 21; -... Fm E IR and
z we have
Σ
T
Proof. If = 1, this is the triangle inequality. For 1> 1, we use Hölder's inequality to get
TTTel' < (|==l|llelle)/c==)))
where x = (#1,...,,a E Rm and e= (1,....11 1) E R". The result then follows from |ell = m 0
Using Lemma
B.1
we get
(af x b, + of s)2-2 < 2 [(a x 2-) + (a 2)20-2]
for any p 2,3, 4.... Noting that || diag(Ar (Ax 6)20-2112 112 = ||A -113822 2, for this range of we get
V fy)ill = max 1
|/ (x+ + s)1l2:
max (x,
max 2p(2p 1)||_|12 max (a x - b: + at 5)20-2 :=I....?
R
2 (a/'s)20 s)00-)3 max max 2p(2p || ||2 22r-3 3(a? x
i=l..... ||=
< max 2p(2p 1)11 A| 22r 3 x b,) 2 1|a:122" 2p- p22p-2). 2),
and 5.3
is valid LFSO.
B.2 Proof of Theorem 5.2
Given the choice Rg = -IA blloo, and noting that Algorithm I works if [ in 2.3 is replaced by any upper bound for [[x]( we have for 2 2,
2pm |All /nl / 6112p-1
R = max
[llA. bl1
2p(2p 1)[[A|B
22p-3
|| - b1128 2g + (maxi= l1s1120-2) || 61128
17 Ti
Ar blloo
= max
||Axx - -blloo:
(2p- 1)|2||2 - 1
max;=11...,. n ||a: 1a:112"" 22)-22
-i c1, n, 1)ll -bblo,
16

---

Published in Transactions on Machine Learning Research (02/2024)
where
1/n
G1 (A,,,,,,y) = max 1,
(2p 1)]|_|12 2
1+ max;=1.....
|| 11:00
Thus we have
L( Ra) 2p(2p-1)jlAAf 1)]1-112 22p-3
max i=1..... ||AR b112--2
1a:12
1a=12"-2 cA
6
6112-2
=2 (A, n, 1))l A.xx b1120-2
(B.1)
where
C2(A, n, = (2p -2p- 1)11 2 1+
max i=...... ||:112002 ( 1 ca(A,m...))
again for p= 2,3,4..... For since L(x, R) is independent of R, always have (xx Rx) 2p|1A112 equivalently [.I with 02 (2,A, 1, = || Finally, our ileration is
7
A (Arı b)2p-1
Jk+1
2h C2 (2 n, P. Ar bl
Since we assume our lincar system consistent, we know [5.1] has a global minimizer at f(x") = 0, and suitable error metric the residual, 1k Ar b. Written in terms of the residual, our iteration
Tk+1 = rk
c2 n, m.))lll 2--2-0 AA rx 2p-1
(B.2)
In the case p= = 1, the residual iteration
B.2
becomes
Tk+1
||
AAT
rk.
and so ||rx|| + lincarly for all E (0, 1], as expected.
Instead, p 2 2, suffices to consider the case rk # O. Here,
B.2
may be written as
2p
Tk+1
02
7 AAT
Fk +
02
AAT ть
||
2-
(B.3)
dropping the arguments 02 = c2(A, n,,, n) for brevity. To handle the nonlinearity in the second term, we first look at the difference
Ch F
|
2p-2
Looking at en in terms of each component separately, and writing [[rx]d = ||rx|oo//a,, for some assi 2 1 (with ag,, = oo [rx]s- = 0), we get
-1--
[en]
2p-2
K,
Note specifically that ag,i 1 for the index i for which [[ra]al || Then for any M > 1, we have
lep 1
Σ
[rali
+
1
1
[r
2
2p-2
ki
(1-
2
Σ
Ira]? +
Σ
[rxl?:
2
200,2M
2
=||rx|
[ra]]
M2p-2
ta K
17

---

Published in Transactions on Machine Learning Research (02/2024)
Since M > 1, there is at least one i with ag2s M (the index corresponding to ||rx So,
Σ Indl 2 1| 2
|
Bock RM
using standard norm equivalences. All together, we have
F 1 1 n M2p-2 2 M )
2
1
||xx12.
Md - 1 in this case. So by taking M for any M > 1. This bound is tightest as M- + 1t, with May sufficiently close to 1, we get
F S (1 10--0 (1-x))/1)r22l.
for any < 1/n. Returning to B.3 we get
|ra+il22 v
1
71 AAT
(1 - 1// 1|rlll2.
C2
C2
| nB 2 + 1/
B/1BB11(1 -)1/2) ||<||22,
where B = /c2 has |B I 1 since C2 2 || Thus ||ri|12 + 0 Q-linearly provided || - 1/ l|2 + B|| c)//3 <.
Defining 0; > 0 as the ith singular value of B E T= since | & 1 and B is full rank (since A is full rank and n S d) we know 0 < 0₂ S o S 1. Since E (0, 1] by assumption, we have
|| - B + nl1 Bl2 - e) = max [|1 - no nonl + m(1 - 1)
(1 non) + 17(1 <) 1/201.
This factor is in (0, 1) provided
170 - 17(1 - e)1/201 E (0,1).
Since 71,0, nn < 1, this holds if on (1 (1-6)1/201 1)1 Since x(A)² s(B) 01/0m; this is equivalent to
x(A)* < 1/(1 e). Since < 1/n is arbitrary, this holds from s(A)* < nn(n 1) (Assumption 5.1
C Additional Numerical Results
C.1 Adaptive Gradient Descent
The below shows the convergence adaptive gradient descent (Malitsky & Mishchenko 2020 on the same
test problems as Scction 0
10
60
10:1
10
1005
00
10-9
68 50
000
20
Iimation
(a) f(x) = ||0||
(b) [(x) ||
2p
Figure 3: Convergence [x)] 0 achieved by adaptive gradient descent Malitsky & Mishchenko 2020 for non-strongly convex functions with flat minima. Plots show [V
function of k.
18

---

Published in Transactions on Machine Learning Research (02/2024)
C.2 Runtime Performance
In the below we compare the gradient decrease achieved by gradient descent (fixed 17) and Algorithm as Section 0 but measured by runtime (total CPU time) rather than iterations.
E1 (E--))
20"7
14"
10"*
0100
241
0.2
0.10
2.01
11.00
0.06
0.00
000
1133
5:01
045
0.06
0.07
0.00
CPT cinee (e)
CPU
Lane
(0)
(a) f(x)
| (varying 7) values)
(b) f(x)
| (all use 10-3)
Figure 4: Convergence rate [+x()) achieved by gradient descent with fixed stepsize for non-strongly convex functions with flat minima. Plots show [//f function of CPU time.
10
10-
10
11-
30
18-13
10
18'15
(a) [(x) = ||00
(b) f(x) = || 3p
Figure 5: Convergence rate Vf((x)) + O achieved by Algorithm for non-strongly convex functions with flat minima. Plots show [|V/(rr)]le//ll / as function of CPU time.
C.3 Sub-optimal choice of Rs
The results for Algorithm 1 presented in Section 5 use the choices of Rs given in Sections and (namely Reptimal [|Vg(=))]2 = 2 2212 for f(x ||>|1/" and R the performance Algorithm when R₁ is significantly mis-specified (i.e. change in the order of RR, not just. constants).
paptimal || for f(x) = ||>|||2) Here we consider
19

---

Published in Transactions on Machine Learning Research (02/2024)
10
00
10-7
10000
9031
30030
linaties
(a) ((x 1 Ra R
poptimal
(b) f(x) = || 1lp Ra.
Roptimal
Kk
1074
10
10"
10
10
10:4
10"
10:13
1011
10-0
(c) f(x) = ||=122 Rs = (R
poopiimlly 2
(d) f(x) || Rs
(12
(Hopttmaly
Figure 6: Performance of Algorithm with sub-optimal choices of Rg. Plots show [V/(ma)ll//VV/fooll as a function of k.
In Figure bc for p E (3),, we note that the significant reduction in convergence rate is likely because the new R& is initially significantly too large. For p {1, we are in the regime where Rg is too small (as > 0), and this appears to have minimal impact on the speed of convergence.
20


Reviews:
[{"review_id": "6GRNMBWo58", "reviewer": "Reviewer_wNUz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. (Strength) The algorithm given by the paper is quite simple, and its analysis is straightforward. The new condition is a clear generalization of prior work.\n2. (Strength) The obtained rate only depend on the local smoothness constants rather than the global constant, therefore they can be significantly tighter than the standard rate for GD. Although how much tighter they are is not clear.\n3. (Weakness) The points queried by algorithm 1 always happen to be queried at nondecreasing radiuses $R_k$-- this means that, for example, if the smoothness near the optimum is very small, we may still end up getting a large value for it from the oracle because our query radius $R_k$ is very large and has never decreased.\n4. (Weakness) It is well-known that regression problems of the form $\\sum_{i=1}^n (a_i^{\\top} x - b_i)^p$ can be solved by Iteratively reweighted least squares (IRLS) for any $p$. IRLS has the same per-iteration cost as gradient descent. Moreover, it does not require any access to a local smoothness oracle or global parameters. There should both a comparison in theory and in experiments between the proposed algorithm and IRLS for solving this problem.\n5. (Minor point) While it is true that the algorithm is technically hyperparameter-free, this information is baked into the (strong) assumption of access to such an oracle. Are there any examples where this oracle is available, other than for standard linear regression?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of non-convex optimization with a local smoothness oracle. The paper relaxes the local smoothness assumption of [1] to only hold over a ball of a radius $R$ rather than pointwise. This introduces the problem of choosing which radius value $R$ to query the local smoothness oracle at. The paper gives an algorithm (Algorithm 1, p. 4) in which they set the radius $R$ by following a simple rule (eqn. 2.3).  The authors prove global convergence (with the ordinary $\\epsilon^{-2}$ rate) in Corollary 3.4, and give a similar result for functions satisfying the PL condition in Theorem 3.6. They show the algorithm converges linearly if initialized within a small neighborhood of the minimum in Theorem. 3.7. They also give a result for a composition of a PL function and a strictly convex function with monotone second derivatives (see Assumption 4.1) in Theorem 4.5. Finally, an important application of this algorithm is given in Section 5, where it is applied to linear regression of the form $f(x) = \\sum_{i=1}^n (a_i^{\\top} x - b_i)^{2p}$. Under the assumption that the data matrix is well conditioned, Theorem 5.3 gives linear convergence for Algorithm 1 on this function class for any value of $p$. \n\n[1] Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. In Proceedings of the 38th International Conference on Machine Learning,2021.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address my concerns above, particularly in point (4).", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DP1w1HUlFe", "reviewer": "Reviewer_Rqa4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Adaptive and parameter-free algorithms are critical to obtain easy-to-use algorithms for practitioners.\n\nWeaknesses:\n- It seems that Parts 3 and 4 are not correlated with the experiments: experiments only show linear convergence of the proposed algorithm on $l_p$ linear regression. To be more explicit, I do not see the theoretical or practical advantage of the proposed algorithm for functions satisfying the PL hypothesis.\n\nQuestions:\n- Can you ensure that the theoretical rate obtained in Thm 3.6 under the PL condition is better than the one of gradient descent? Or that the step size is larger than $1/L$ at each step?\n\n- What's the point of Thm 3.7?\nThe two main convergence results are under PL (Thm 3.6) or strong local convexity (Thm 3.7). I was wondering if the authors knew the relationship between the two hypotheses. Is PL weaker or stronger than strong convexity?\nIf the goal of Thm3.7 is to obtain linear convergence on the iterates, it seems that the PL condition is sufficient; see, for instance, Thm. 4.1 of [1]\n\n- Does Assumption 5.1 imply local strong convexity? PL?\n\n- What is the exact computational complexity of the proposed algorithm? The only sentence I found is rather vague: \"it requires one evaluation of $\\nabla f$ and possibly two evaluations of $L$\".\nWhat is the cost of evaluating $L$? Could you add these computational costs more transparently directly in Algorithm 1? There is no mention of how to tune the hyperparameter $\\eta$ in the experiments: do you have to tune it in practice?\nHow costly is the computation of $L$ in practice? Could you add the same graph with the wall clock time?\n\n- I am not asking for exhaustive SOTA experiments, but adding other adaptive algorithms, such as those mentioned in the introduction, would significantly strengthen the paper.\n\n- A setting where adaptivity is very much needed is bilevel optimization, which has significant similarities with compositional optimization. Could you imagine extending your results to this setting?\n\n[1] Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose an adaptive and parameter-free algorithm based on the on-the-fly estimation of the local Lipschitz constant. They show linear convergence of the proposed algorithm under the Polyak-Lojasiewicz (PL, Thm 3.6) and local strong convexity (Thm 3.7). These results are then extended to compositional functions $f(x) = h(g(x))$ (Thm 4.5) and extended to the specific case of $l_p$ linear regressions with lighter hypotheses (Thm 5.3).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Clear cost per step of the proposed algorithm\n- Clear explanation of how $\\eta$ is tuned\n- Comparison with other adaptive algorithms: theoretically on the rates and empirically (again I am not asking for SOTA algorithm, just a fair scientific comparison for insights, it is OK if the proposed algorithm is slower) \n- Wall clock time for the experiments, or fair computational comparison \n- Make experiments and theory match: either remove Parts 3 and 4, or add experiments in these settings", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gZXvejO4MX", "reviewer": "Reviewer_F8Co", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. The smoothness condition and algorithm are new.\n2. The analyses are simple yet effective. \n\n## Weaknesses\n\n1. In practice, evaluating $L (x, R)$ can be challenging. This limits the applications of the algorithm. While the paper provides some examples such as the problems of minimizing $f$ and $g$ defined above, these problems are not very relevant in practice. More realistic examples would be beneficial.\n2. The proposed algorithm does not specify how to choose the radii $R_k$, yet the convergence and rate guarantees assume specific conditions on $R_k$ and $L ( x_k, R_k )$. Please either demonstrate the difficulty of efficient optimization when these conditions are not met, or provide a rule for selecting $R_k$ (possibly with modifications to the algorithm) that ensures these conditions are met.\n5. Assumption 5.1, which requires the condition number of the matrix $A$ to be very close to $1$, is highly restrictive. While the authors explicitly acknowledge this limitation, it does not fully justify the significance of the example.\n6. The problem setup, unconstrained differential convex optimization, is fundamental. Please consider generalizations to the constrained optimization setup, composiptimization setup, and possibly mirror descent-type methods. \n7. Minor comments: \n    - Emphasizing that the problem of minimizing $f$ provides the worst-case bounds for accelerated gradient descent can be misleading, because this paper considers a different oracle model.\n    - Coercivity is sufficient to ensure boundedness of the level sets.\n    - Theorem 3.7 needs a clearer statement. Please define explicitly how close $x_0$ should be to $x^\\star$ and provide the explicit convergence rate (as in the last equation of the proof).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Consider the problem of unconstrained convex differentiable optimization. This paper proposes a \"local first-order smoothness oracle,\" a \"trust-region\" generalization of model proposed in Mai et al. (2021). The paper then proposes a gradient descent method and analyzes its global convergence and local convergence rate. As a result, for instance, a linear convergence rate is achieved for minimizing $f (x) = \\Vert x \\Vert_2^{2p}$ and $g (x) = \\Vert x \\Vert_{2p}^{2 p}$ when $p$ is large.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses above and make necessary modifications to the paper.", "broader_impact_concerns": "N/A. This is an optimization theory work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SpVphnqVEh", "reviewer": "Reviewer_GZSs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- LFSO allows for the construction of a convergent gradient descent-type iteration without requiring much hyperparameter tuning.\n\n- The LFSO method demonstrates promise in achieving a global linear convergence rate to arbitrarily flat minima of convex functions\n\n- It also presents global convergence results for both nonconvex and PL/strongly convex cases\n\n\nWeaknesses:\n\n- It needs discussion or analysis on the potential limitations and practical considerations of implementing the LFSO method in real-world applications. The current numerical experiments are not so convincing since only toy examples are used while not considering real experiments\n\n- It could benefit from a more extensive comparison with existing methods, particularly in addressing the trade-offs and potential challenges in using the LFSO approach. It lacks such comparison with other competitors, which is one of its major drawbacks of this submissions\n\n- It would also be valuable to provide insights into the computational complexity and scalability of the proposed method, especially in comparison to other state-of-the-art algorithms", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission presents Local First-Order Smoothness Oracle (LFSO) for gradient descent-type methods. The LFSO allows faster convergence to arbitrarily flat minima of convex functions. The paper demonstrates the effectiveness of the LFSO approach through theoretical analysis and numerical experiments.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "see the weakness part above", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: See above
Decision: Accept (poster)