Are Convex Optimization Curves Convex?
Authors: Guy Barzilai
Ohad Shamir
Moslem Zamani
Venue: Accepted by TMLR ()

Abstract: In this paper, we study when we might expect the optimization curve induced by gradient descent to be \emph{convex} -- precluding, for example, an initial plateau followed by a sharp decrease, making it difficult to decide when optimization should stop. Although such undesirable behavior can certainly occur when optimizing general functions, might it also occur in the benign and well-studied case of smooth convex functions? As far as we know, this question has not been tackled in previous work. We show, perhaps surprisingly, that the answer crucially depends on the choice of the step size. In particular, for the range of step sizes which are known to result in monotonic convergence to an optimal value, we characterize a regime where the optimization curve will be provably convex, and a regime where the curve can be non-convex. We also extend our results to gradient flow, and to the closely-related but different question of whether the gradient norm decreases monotonically.

Published in Transactions on Machine Learning Research (06/2025)
Are Convex Optimization Curves Convex?
Guy Barzilai Aei- University
guyborzilail @mail. Smail.tau.ar tau.ac.
Ohad Shamir Weizmann Institute of Science
oktd.ehhamirruccimam..ccm
Moslem Zamani
moslem. mostem..amaanii Sateem.caamanni@@uulooouui be
U'Louvain
Reviewed on OpenReview: https: // openreview. net/ forun? id= T2tppse eX2
Abstract
In this paper, we study when we might expect. the optimization curve induced by gradi- ent descent to be convez precluding, for example, initial plateau followed by sharp decrease, making it difficult to decide when optimization should stop. Although such unde- sirable behavior can certainly occur when optimizing general functions, might it also occur in the benign and well-studied case smooth convex functions? As far as we know, this question has not been tackled in previous work. We show, perhaps surprisingly, that the an- swer crucially depends on the choice of the step size. particular, for the range step sizes which are known to result in monotonic convergence to optimal value, characterize regime where the optimization curve will be provably convex, and regime where the curve can be non-convex. We also extend our results to gradient flow, and to the closely-related but different question of whether the gradient norm decreases monotonically.
1 Introduction
We consider the well-known gradient descent algorithm with constant step-size, which given a function f: - R. an initial point xn E R. and step-size parameter r > O, generates a sequence of points (x following the recurrence relation
Yn E J2, In-1 /
This sequence of points induces an oplimization curve, which is the linear interpolation of ((n, (xx))) in I2 (see Figure for an example).
Our motivating question is to understand the properties of this optimization curve. For example, if the function f is convex and smooth, then choosing the step size appropriately, it is well-known that the curve decreases monotonically to the minimal value of f (Nesterov) 2018). However, other properties might also be of interest. For example, an undesirable phenomenon concerning the optimization curve is when it plateaus for a while, and after that substantially decreases. This phenomenon undesirable, since it can cause the user to terminate optimization prematurely, thinking that a minimum has been reached, where fact continuing the optimization would have resulted in significant improvement. An important property that disallows this undesirable phenomenon is converity of the optimization curve: Namely, that the slope of the curve (or oquivalently, {f(..) - f (= decreases monotonically. Morcover, convexity of the optimization curve occurs very often in practice, in wide variety of problems. However, to the best of our knowledge, no previous work attempted to rigorously study when we might expect the optimization curve to convex.
To begin this investigation, we first note that for general non-convex functions, we have no hope of guaran- teeing convex optimization curve. For instance, if we initialize gradient descent. close to maximum of a

---

Published in Transactions on Machine Learning Research (06/2025)
Gradient Descent on fx) = x²
Optimization Curve of Gradient Descent on f(x) = x²
fx) x
GD steps
f(x)
flxm)
Figure 1: Gradient descent on (xx x²2 with step-size 1 0.1 and initial point 20 3.
smooth locally concave function, it is easily seen that the optimization rate will increase over time, leading to a concave optimization curve. Moreover, even we consider the more benign case of convex functions, it is well-known that the optimization curve gradient descent may not monotonically decrease general (and certainly not be convex), as shown in the following simple example:
Example Consider the conver 2- 2-Lipschilz function
f(x) = |x] + max (0,x)
on R, which minimized O. For any step size n > 0, suppose we initialize gradient descent zo By definition of gradient descent, have
3 and x2 nf 4 2n
3
21 :ff
+ 4"
hence f(zo) J. 3. f(a1) zn f(z2) = 2n. Therefore, the optimization curve first increases and then decreases, and thus is neither convex nor monotonically decreasing.
This observation motivates us in focusing on the class of L-smooth convex functions, where the gradient is L-Lipschitz. This is an extremcly well-studied class for gradient descent procedures, and in particular, it is well-known that for any 7 E (0, Zt), the optimization curve of gradient descent will monotonically converge to the minimal value (whereas for larger value of 1), gradient descent may diverge; see Nesterov (2018) Theorem 2.1.14)). Thus, we will be interested in whether the optimization curve of gradient descent is convex, when optimizing such functions and in this step size regime. As far we know, this question has not been addressed in previous literature.
In this paper, we provide an answer to this question, which is (perhaps unexpectedly) somewhat subtle: On the one hand, for any 1) E (0, 1.751 (which includes the worst-case optimal step size 1/L), we prove that the optimization curve indeed convex. On the other hand, we prove that for r) E (173 2) the optimization curve may not be convex even though the curve is still monotonically decrcasing and gradient descent is guaranteed to converge to minimal value. In other words, there exist step sizes that ensure monotonic convergence of gradient descent, but do not ensure convexity of the induced optimization curve.
As another contribution, we consider a closcly-related but different question: Namely, whether the norm of the gradients (<>)(( monotonically decrease, for L-smooth convex functions. This question is related, as the gradient captures the local slope of the function, which correlates with the magnitude of the objective function decrease after a single gradient step, assuming smoothness and that the step small enough (in fact, this intuition used more formally in our proofs). Although one might suspect that the behavior of gradient norm decay will be similar the question of optimization curve convexity, prove
2

---

Published in Transactions on Machine Learning Research (06/2025)
that the answer here is different and more positive: The gradient norm is decreasing, for any n E (0, žl Finally, we extend our analysis to gradient flow (the continuous-time analogue of gradient descent), and prove that for smooth convex functions, the gradient flow optimization curve is always convex, and that the gradient norm is monotonically decreasing.
2
Preliminaries
We will need the following simple lemma, which essentially states that the integral of a non-decreasing function is convex:
Lemma 1. Let R + R be a Riemann integrable function on every closed sub-interval of R. Define
f:R- - R such that for every x E I:
f(x) = l g(t)dt.
If g is non-decreasing, then f is convex.
Proof. Let t be real numbers. By definition of convexity, it is enough show that
f(u) f(s) f(t) f())
(1)
s
We note that by definition of f, it holds that f(u) f(s) S" g(x)dx, and by the monotonicity of g, it therefore holds that (u - s) g(s) I f(u) - f(s) 1 (u 8) g(u). Thus,
g(s) < f(u) [(s < g(u) and similarly s(u) s f(1) (()) S g(l)
(2)
Obviously, implies
completing the proof.
As discussed in the ion, we consider an optimization curve induced (f(r))) to be convex, if the curve formed from the linear interpolation of the discrete points ((x))) is convex (in the standard sense, e.g. its epigraph is a convex set). This formalized the following definition:
Definition 1. Let {a, Jm be a sequence of real numbers. Then we say that the mapping n + a, is conver over Zzu, if the function g [0, oc) + R defined as
g(t) = ale + (t (1-(())aaa ape
is conver.
By Lemma and the Newton-Leibniz theorem (as appears, for instance, in Bartle & Sherbert 2001 The- orem 7.3.1)), we see that a real valued sequence )2= is convex over Σzo if and only if the sequence {an - oa+1 1 is non-inereasing (actually, the "only if" part follows from elementary properties of convex functions). shall often be convenient to use the latter characterization rather than the former.
3 Gradient Descent
In this section, we shall investigate the optimization curves induced by gradient descent on convex L-smooth functions. For such functions, it is well-known that for any E (0, 7)), the gradient descent optimization curve monotonically decreases to the minimal function value (see Nesterov (2018) Theorem 2.1.14)). In the following theorem, we prove that in the more restricted regime r E (0, convex:
the optimization curve also
Thcorem 1. Let f R
R + R be a conver L-smooth function, and let {x be the sequence of iterates produced by gradient descent, starting from some Zo E RR, using a step size nj E (0, 1.73. Then the mapping n. - (xxa is conver (equivalently, the sequence (f(m) (x 1) 1 is non-increasing).
3

---

Published in Transactions on Machine Learning Research (06/2025)
Proof. Arguing by induction and using the fact that 20 is arbitrary, it suffices to prove that
f(z2) f(x1) 2 f(z1) (((11)=13) f(zo).
(3)
By convexity and by L-smoothness of f, we have (see Nesterov 2018
Theorem 2.1.5)):
2o - 21) + (f ff (zo) f(zo) f(x1) 2 (Vf (0
2L
T222 f(x2) - f(a)) z (V/ ( - f(z2) f(x0) z (V x2 zo)
+ 21.
[V V (x1)1²
1
22
+ 2L
(22)
Vf (zo)]l
Due to gradient descent update rule, we have 21 Substituting these values into the inequalities, we obtain:
V f (2o) and 22 ro V (V
f(0o) f(x1) 2 (V (x1) Vf +
2L |V (z1) vf(=)))
[w22 - ((x)) 2 - V 2 + 2T.
V (m2) - V
1
f(x2) - f(x0) 2 ー VV (2.) ( (m)) Vf (z1) 2L
(x2) Vf (mo))²
Multiplying the above inequalities by 3.2 and 1 respectively and summing them up, we obtain:
-(02)-((x1) (f(11) - f(xo)) 2 3n (Vf (21), Vf (2o)) + |V (2)) Vf (#x)]l
3
4L
|V (=))) + 1 (z)) (=))l
71
IVV (=o) 2 (VF (zo) V (x1))
|V (x2) - Vf (xo)1
(4)
4L
Rearranging terms, the right-hand side equals
3 vf +
IIV - v (xo)))
4L
4L
4L
7 d
1V, (x1) - v (=))
=
78 2
|V (x1) - v (zo))l + (x²) v (z))) V/ (z²) - vf Vf (zo))
+ 41
2
7 -17) 8L
7
(12) - ク / (z1) - 1 v (zo)
- v (2o))1 + 2L
=
where the last transition is by the elementary equality - I|b al + c|c bll + ||c al
O||c _bb _all
which can be easily verified via expansion. Overall, we have shown that
8L - ") (Vf (2o))1
f - -f(x) f(xo)) 2
+ 2L V Vf v/ -
The first term is non-negative (since we assume 5 1. 1.75) ) and so is the second term. This implics (3) and concludes the proof.

---

Published in Transactions on Machine Learning Research (06/2025)
We note that the theorem applies for step sizes in the range (0, 1,77], which is more restrictive than the regime (0, 2) where gradient descent is known to monotonically decrease to optimal value. Thus, one may wonder whether this restriction is necessary, or perhaps Theorem I can be extended for a broader range of step-sizes. In the following thcorem, we prove that preciscly this restriction is indeed necessary namely, for any step size E (Z 2): gradient descent will converge and the optimization curve will monotonically decrease, without necessarily being convex:
Theorem 2. For every L > 0 there evists a conver L-smooth function f - R and To E R such that for every step 17 E 1175 2t the mapping n + f(xn) is not convex.
Proof. We note that without loss of generality, it suffices to prove the theorem for L = 1. To see this, suppose our thcorem holds for 1. This means that there exists a convex 1-smooth function f R + R and æp E IR, such that for every step-size v E (1.75, 2); the optimization curve of gradient descent on ʃ with initial point Ty and constant step-size isn't convex. Now, define g : R such that for every R: so and define z. The reader may verify that g is convex and L-smooth. VL
g(t) ft),t, define ão Now, for n E N, define
In =n-1 71 (2n-1) in = -n-1 r/g (2)()
En. Arguing by induction, we claim that for n Zzo it holds that In. VL" by definition, and if the claim holds for n E Zz0, then
Indeed, the base case 0 holds
In 1 VTT In Int1 = In - nngg (Tn) VL - VL
VL
1 VI VI( (In - non-nn((cn (In)) Int1
vL
It obviously follows by the definition of g that g(ūx) ((x)) for all n E Z2o- Thus, the optimization curve corresponding to g, žо and n is the same as the optimization curve corresponding to f, xo and r - which shows why it suffices prove the theorem for ==
We now turn to prove the theorem for == 1. Specifically, consider the function f RR - R defined as
112 151 1(1) 1
t- 2 t>1.
It fairly obvious and easy check that indeed a convex 1-smooth function.
Now, set 2p -1.8 and let there be 17 (1.75.2). 2). We have
Φ = To nf (xo) = (n - 1)(-zz) = 1.8(1 - 1).
and due to the fact that 1) > 1.75, have x > 0.75 1.8 1.35. This implies that
32 = 21 - n (21) xι - 1] = 1.8 + 0.8 < - 1.8 0.8 -0.2
where in the last equality we recalled that 17 < 2. Thus:
1
f(xo) - < < f(x)(())))))))) + 0.5( (1.87 1 -1. 0.5) < (1.81 1.8 0.5) - 0.5(-1.8 + 0.8n)²
f(x2) -
2 -00 (r)
2) < (21 2) 2"2
Rearranging the terms, we get the equivalent inequality 7/2 15.75m + 24.5 < 0, which easily verified to be equivalent to 1.75 < r < 14. This holds due to the assumption that r) E ().75,2). Thus, f(x)) - f(x)) < f(x1) f(zz) holds, which means that the relevant optimization curve not convex. This concludes our proof.
5

---

Published in Transactions on Machine Learning Research (06/2025)
So far, we have considered the convexity of the optimization curve induced by gradient descent. A re- lated property of interest is how the sequence of gradient norms (IIV/(*)) behave. It is well-known (see Nesterov (2012) ) that for convex smooth functions, the minimal value after N iterations, namely minngN x I| is upper bounded by a function monotonically decreasing to 0 (as should be expected when the method converges lo global minimum). However, does the sequence (I.V(( itsell decay monotonically? The following theorem establishes that this true, for any Tj the regime where gradient descent converges:
Theorem 3. Let f IR" + R be conver L-smooth function, and let { be the sequence of iterates produced by gradient descent, slarling from some To IK", using slep size (0, E1 Then the sequence (IV)(()) is non-increasing.
Proof. Arguing by induction, and using the fact that zo is arbitrary, it suffices to show that |/ fz)))l > [xr))l
Theorem 2.1.5)), we have Using a standard inequality for convex L-smooth functions (see Nesterov 2018
that for all x, E R.:
--)) 3) 2 1 |V5(2) vf(i)]|
(5)
-
Plugging To, into 5 we have
(Vf(21) V 21 -2) 2 [Vf(z)) (=
b (Vf(x1) - f((o)), - 2 , [V/((=)) (-(1) vS(00))11
= - 1 ((((()))) V/(aa)) - /| (V/(a)))) N / (IVS - (VI())) Vf(a))) (x0))
- 1 -n) (1)). (V) Vf(x)))
2
2 1 n) [Vf()))] |+
(6)
Now, if 17 2, then by substituting for 7 and rearranging the terms, get from 6 that
1 L | [Vf(m=))
which obviously implies the desired result. Otherwise, we have & --1 17 0 by assumption. Using Cauchy- Schwarz, (6) implics
2 - (V- -VV(=))) 2 - (v)
|Vf(m)))
Rearranging the terms, we get the equivalent inequality
( 1 [ 0.
([>v(=>))] - (V
(7)
Now, [Vf((=]]] 0 then we are obviously done. Otherwise, assume for the sake of contradiction that [[V[(m)]] [x]](= Then, splitting to the cases v E (0, 1) and 17 E [ 2); it is easy to verify that
(17 (11 + |+)()م)) + (V)()))) > 0.
Together with [Vf(())) |VV < this results
(IVf((z))] - (17 - 1 [ 1 (IV/Ga2)) < <0,
which contradicts
Therefore, in any case, have |V/(())]| 2 [[V[()))] as required.

---

Published in Transactions on Machine Learning Research (06/2025)
4 Gradient Flow
In this section we extend our results to the optimization curve induced by gradient flow, and prove that it is always convex (when optimizing smooth convex functions).
First, we recall that given a function f C (IR", , IR) (namely, differentiable with a continuous gradient), and some 2g E R", the gradient flow (z(t))(2o defined by the differential equation
(1) (v((x()) x(0)) To
Assuming L-smoothness of f for some L is sufficient condition for this differential equation to have unique, well-defined solution globally all of t 2 0 (this follows from the Chcard-Lindelöf theorem). We can then define the optimization curve induced by gradient flow as follows:
Definition 2. Given a function f E (IR", IR) for which gradient flow (starting from some xn) is uniquely defined, the associaled oplimization curve g [0, 00) + R is defined as g(l) f(x(() for all t E [0, oo).
Before discussing the case smooth convex functions, let us first consider the simpler case of convex C² functions. In that case, one may verify that there exists unique solution defined for 2 0 for the gradient flow differential equation (again, this can be shown to follow from the Picard-Lindelöf theorem and the fact that the gradient norm is decreasing, due to the function's smoothness and convexity). Morcover, in that case convexity of the optimization curve is easy to establish:
Theorem 4. Lel R - I be conver function such that E CR", RR) and E R Then the resulling gradient flow optimization curve is convex.
Proof. Recall that the optimization curve is defined as g(t) = f(x(t)) for all t 2 0. By elementary results, a sufficient condition for convexity of g is that it is twice differentiable, with a non-negative second derivative.
By the definition of the gradient flow differential equation, we have for all 2
x'(1) = (s(((())
(8)
Therefore, x(-) is differentiable for all t 2 0. Now, using the chain rule we have:
g((t) = (V (z(1)) o' =() | (x(t)))
(9)
Owing to the fact that E C2 (R", R), we can differentiate again using the chain rule to get:
(t) -2 -2 (x(t). H x'())))((t)) 2Vf Hy (z(()) Vf (z(t)))
(10)
where H is the hessian matrix of f. We note that f convex and f e (R R). Therefore, for all 2 E R" it hold that Hz(2) is positive semi-definite (see Nesterov 2018
Theorem 2.1.4)). Specifically, for all 2 0,
(Vi (x(t))) Hy (a(t)) V (x(t)) 20
and therefore by 110 g"(t) 2 0 for all t 2 0. This implics that g is twice differentiable [0, oo), and that its second derivative non-negalive, which concludes the proof.
We now turn to discuss the case of convex and smooth functions (which are not necessarily twice- differentiable). The theorem below implies that the resulting optimization curve is always convex:
Theorem 5. Let f R. + R be a conver L-smooth function for some L E c0), and zo E R", Then the resulting gradient flow optimization curve is connex.
The proof the theorem (which is a bit involved and appears in the appendix) builds on a variant of the proof of Theorem D and the fact that gradient descent can be seen as a discrctization of gradient flow.
Furthermore, from Theorem one concludes the gradient flow equivalent of Theorem

---

Published in Transactions on Machine Learning Research (06/2025)
Theorem 6. Let f: : 1R" R be conver L-smooth function for some E (0, 00), and 2o E ER. Let x(-) be the unique solution for the corvesponding gradient flow differential equation. Then the map + | (x(())] is non-increasing over oo)
Proof. Recall that the optimization curve is defined as g f(x(t)) for all & 2 0. From Theorem 5 is convex, and by the monotonicity of gradients of convex functions, it follows that g is non-decrcasing over [0, oc). From the definition of the gradient flow differential equation, for t E [0, oo) it holds that:
z'(t) = - (x(t))
Therefore, by the chain rule, for E [0, oo):
(t( = - VV
Hence, it follows that ++ V (xl is non-decreasing on E [0, oo), and the result follows.
5 Conclusion and Discussion
In this paper, we studied the convexity of optimization curves induced by gradient descont, focusing on convex L-smooth functions. For step sizes that assure monotonic convergence merely v (0, 4), we identified the regime that ensures convexity of the induced optimization curve, namely 1) E (0, 1.79]. Moreover, we showed that in the complementary regime of ( L 2), the induced optimization curve may not be convex, even though the gradient descent still converges monotonically to minimum. In addition, close connection between gradient. descent and gradient flow to show that the optimization curve induced by gradient flow is convex as well. Finally, we studied the closely-related question of whether the gradient norms decrease, and showed that here there are no separate regimes: For both gradient descont and gradient flow, the gradient norms decrease monotonically.
used the
Our work leaves several open questions and directions for future research. For example, the proof of non- convexity in Theorem relies showing lack of convexity between two consecutive steps i.e, we showed that fz0) f(11 < f(1 f(22). One may ask whether there exist cases where more steps fail to be convex i.e, f(xx) f( < f(*a+1) - ((x+2) holds for multiple n E Zzo. or whether the optimization curve might be concave for several consecutive steps. Another obvious direction for research is to consider other optimization settings where the optimization curve is convex or non-convex, or consider this question for other optimization methods.
References
Robert Gardner Bartle and Donald R Sherbert. Introduction to Real Analysis. Wiley, 4th edition, 2011.
Arieh Iserles. A First Course in the Numerical Analysis of Differential Equations. Cambridge University Press, 1996.
Yurii Nesterov. How to make the gradients small. Optima. Mathematical Optimézation Society Newsletter, (88):10 11, 2012.
Yurii Nesterov. Lectures on conver optimization, volume 137. Springer, 2nd edition, 2018.
8

---

Published in Transactions on Machine Learning Research (06/2025)
A Proof of Theorem 5
In order to prove theorem 5 recall the well-known fact that gradient descent can be seen discrete approximation of gradient flow, namely the solution of its differential equation:
Definition 3. Let f E (R", R) be conver function, and zo R such that the gradient flow differentiol equation has unique solution x(-)) (as function on [0, oo)). Let 1) > 0 be fized.
As in gradient descent, for E N define: In In-1 1) (zn-1). Define Euler's approcimation with slep-size yj to be (()) [0, xo)
+ IR such that for all l. E ()),
x. (1) = = t
1
Vf + (14)
1
The reader may have already observed that in fact, the points generated by gradient descent with step-size > are exactly the points (1n() where xf()(.) (.) the corresponding Fuler's approximation. other words gradient descent with step-size vj > O, is the Euler discretization (with step-size 7) associated with the gradient flow differential equation.
Another important property will need is that n converges to 0, the Euler approximation generally converges to the solution of the differential equation. Proofs of this fact may be found in most textbooks differential equations. However, for the sake of completeness we shall present such proof, adapted to our specific assumptions and needs, and similar to the one that appears in Iserles (1996 Theorem 1.1):
Theorem 7. Let L 0, R + R be conver L-smooth function and RR For every n > let (-) be the corresponding Euler's approzimation, and let xx-)) be the unique solution for the corresponding gradient flow differential equation. Then for every R > 0
(1) 7= x
uniformly [0, R).
Proof. Fix R > 0 and < 17 < 1. is L-smooth, and thus x(-) (as a solution to the corresponding gradient flow differential equation) is uniquely defined on [0, 20). Morcover, from the definition of gradient flow, for all t [0, oo) it holds that:
<'()) (((((()))
Therefore, xr(-) differentiable on o0), and therefore continuous on oz). Now, by the fact that S is L-smooth (and particularly Vf E C(IR", ((I", holds that the map + fV((x(t) is continuous on 10, oc), mcaning that C¹ ([0, oo), R") (and particularly E C ([0, oo), R")). Therefore, 2²-) is bounded [0, R+ there exists M > 0 such that ||x((]]| S M for all L E [0, R+
Now, from the fact that Vf E C(R", IR",, it holds that f is bounded on {w E R"; ||l||| < <M}. It therefore holds that z²-) has a bounded derivative on [0, R 1], and therefore is Lipschitz on [0, R ++ ++]]iic there exists K > 0 such that for all t1, t2 E [0, R + 1],
| - x(t2)) S K [t t2l
Now, for Zzo denote en = ( (mn)) - x((n). By definition of the differential equation and of Euler's
approximation, it holds that Cu = O. Denote n
R +1. Becanse 0 < < 1, it holds that n n² < R+1.
Fixing some n E n0 -1,, we have
(x+1
Cn+1 = (1) ((n h + 1)m) - x((n+ + 1)m) = - n/
- (x(m))
V vf(x(s))ds
(n+1)y
(n+1)n
- (VI((
V)(((s)) - (5(a(0000) ds
= =6
en
nn
9

---

Published in Transactions on Machine Learning Research (06/2025)
and
(n+1)g
((-1))
len+1
$ |eel +
[[(c(+)) - ( ds s ||eall + L nn
(<(s) 2000 ds
((nlin
$ |le + L
(I1(()) x((n))l + (m(n)) x(0) (nn) ds
Inn
(n+1)
=(1+ + Ln) ||enll
+
[|x(|) - x(nn)]l ds
(x+1)n
(1 + Lnj) ||elll
LK
1s - nrild
m
LK (1 + Lm) |lnll
2 17.
Thus, arguing by induction, we gel that for n E {O....,"" "..
LK n-1
|eal S 1/ Σ (1+ Lnjs
1=0
Furthermore, a similar calculation implies that in fact, for every t E [0, R).
[z)0(()) z(0)|| s s Lm) 1| [4)
LK
11²
and thus for every [0,
LK
LK n²
LK (1 + Ln)
(0)((t)) 10---16 x(t)
(1+ Ln) <
n
Σ j=0
(1 (m)
=
2 17²
2
Ln
Kn (1 + Laj)"
(+) K1 Lyp"
(ca) Kn 1(R+1)
$ 2
S 2
In the above, (+) is due to the fact that for all 8 E IR it holds that + S e², and (*+) is due to non-" S R+1. Now, we notice that:
Kn ((++)) 200
2
which concludes our proof.
To apply this result in the context of optimization curves, we have the following immodiate corollary:
Corollary 1. Let L > 0, f RR + IR be a convez L-smooth function and xo E 1R" For every 1j > lef x-))() be the corresponding Fuler's approzimation, and let xx-) be the unique solution for the corresponding gradient flow differential equation. Then for all 0:
f (1) (1)(()) 2 f (x(1))
Proof. Theorem obviously implies that for all 2 0 we have:
z (1) ~ x(t)
The result now follows from the continuity of f.
Now, we would like to use the convergence established by this corollary, along with the results of Theorem prove that the optimization curve of gradient flow is convex as well. However, one should note that Theorem ] establishes the convexity of the optimization curve of gradient descent (which is defined to be
10

---

Published in Transactions on Machine Learning Research (06/2025)
the linear interpolation between the points
rather than the convexity of the mapping
I ++ [(a((0()) discussed in the corollary. Therefore, we shall need variant of Theorem [ which concerns the convexity of the mapping + (t)( For technical reasons, we will utilize a rather different proof technique to prove the result. The aforementioned variant is formalized as follows:
Theorem 8. Let : +
R be convex L-smooth function, and lel xo E R" For every > 0 let xl0))) be Euler's approzimation of the corresponding gradient flow differential equation with step size n, Then for all 17 E (0, + the map t + f (t)) is conver (over [0, oo)).
Proof. By the definition of I-smoothness, if follows that f is also I'-smooth for all 1/ 2 L. Therefore, for ") s-smooth. Therefore, without loss of generality, it is sufficient to prove the all E (0, +l it holds that f is
result for 17 = +.
Looking at ( it is easy to notice by its definition that for all n E Z20, slt) E C( " Thus, it holds that t( E Cp (R), .ft) and the fact that f E C' (R",R,, it holds that the mapping t f (zlt)(t) is in C²([E, "t"] R) for every n E Zzo, and thus, is a C² piece-wise function on o0).
is piece-wise Ca curve on (0) Thus, by the chain rule
Now, define g: [0, 00) + R as
s(1)= = ( V (x) (m+/L) (1 (1- m,/L) Vs (m//)))))) - (xltt (m//t)
where we denote n4 [tL]. It is easily verified that wherever the map + f (z) is differentiable, its derivative is exactly g()). Considering the fact that this mapping is differentiable at [0, (c) \ (2) and
that is easily seen to be piece-wise continuous function (and thus it is Riemann integrable on every closed sub-interval of [0, oo), we have by the Newton-Leibniz theorem (see the exact form in Bartle & Sherbert
2201 Theorem 7.3.1)) that
f {xbtt)()) f((u)= = ʃ g(s)ds
for all t 2 O. Now, by lemma 1 proving that g is non-decreasing shall suffice, it shall imply that the map t + f (t) is convex over co).
To that end, we shall prove the following:
(i) For all Σz0: g is non decreasing on 7 *+)).
(ii) For all N, lim,- ((t) S ())
Along with the fact that g is piece-wise continuous (with discontinuities at (-)) these two properties are casily seen to imply that g is non-decreasing. Thus, proving them will conclude the proof.
Thus, we now turn to prove
ii) Let there be n E Zzo and let there be 4,,42 I
n+l) such that l2 > 4
L
Denote y(t) x i (
(t
-
1 Vf (x ( for t E [t. at Then
- (0(tt))((t))0000)) ((t))) = (V (V)(((ta)) vf(((t))), v(t2) - y(t1)) 2 0, CR(I,,,
where the inequality follows from convexity of f (and the fact that it is in Cº (I²", " R)). It obviously follows that g(tz)= 2 g(t1), as desired.
Turning to prove
fii let there be n E N and denote 2g = x(tt) (a=²) 21 = = (g)
Obviously we have:
1 Vf (V((30) -Ff(2))
lim g(t)=
Vf 20
11

---

Published in Transactions on Machine Learning Research (06/2025)
We now notice the following:
9 I L-
11
lim = -/tp::/-------------------------
v/(=1))
(Vf(2z), (f((2)) -
-
(Vf(z1) - - -V(aa
T. ((V/(a)) - v/(=a), -
1 |V[(2t) -(ffa))-Jlll -V
= (VVS(()))) - =1 -0) + (7f(z)-v((a)) 20,
where the inequality holds since f is convex and L-smooth (see (Nesterov 2018 Theorem 2.1.5)). Thus, lim+- 2- g(t) S ( as desired. As mentioned above, this concludes the proof.
Now, having these results, we just need one more technical lemma order to prove theorem 5 Lemma 2. Let A C IR" be a conver set, f : : + R and 20) x A + IR such that:
1. For every A: g(5,z) = f(z).
There crists > 0 such that for all (0,6) the map a + g(s,2) is coneea over A.
Then f is conver function.
Proof. Fix some 2, A and À E (0, 1). Then for every (0, 8), by convexity of x + g(s, x), it holds that
g(8, A + (1 Aly) s x) + (1 A)g(s,y)
Now, taking the limit in both sides of the above inequality, and using the first assumption in the lemma statement, we get
f(Ar + (1 A)y) s *f(x)+ (1-+((11))))) A)f(v).
Since I, y, are arbitrary, the result follows by definition convexity.
Now we are ready to prove theorem 5
Proof of Theorem As usual, for every > we denote the corresponding Euler's approximation as ( By theorem we get that for every 77 (0, }), the map + f (t) is convex over [0, oo). Corollary implics that every 0,
(z)
p 70 f (x(t))
Combined with Lemma 2 we get that the map t + f (z()) is convex over [0, 00), required.
12


Reviews:
[{"review_id": "Ws48ZfuqFk", "reviewer": "Reviewer_UXUq", "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.**\n1. The problem formulation is interesting. The notion of \"convexity of an optimization curve\" is novel, to the best of my knowledge. \n2. I appreciate the authors' effort to provide a complete solution to when the optimization curve of gradient descent is convex for the standard convex and smooth case. \n2. The proofs are simple and easy to check. \n\n**Weaknesses.**\n1. The paper motivates this study by stating that the convexity of an optimization curve is sufficient to prevent the “plateau phenomenon.” This motivation is somewhat weak, given the obvious fact that convexity is not a necessary condition. It is unclear whether convexity is the appropriate notion to study.\n2. The “plateau phenomenon” is perhaps more relevant in the context of non-convex optimization. Nevertheless, the authors exclude the non-convex case using a counterexample (Example 1), which corresponds to the third result I mentioned above. The counterexample is somewhat weak, as the paper primarily considers smooth functions, whereas the counterexample is Lipschitz continuous and non-smooth. Strictly speaking, the counterexample does not rule out the possibility that the optimization curve can be convex in non-convex smooth optimization.\n3. The authors use another counterexample to show that the convexity of the optimization curve does not generally hold for step sizes exceeding $1.75 L$ (Theorem 2). However, since only one counterexample is provided, the significance of this negative result remains unclear.\n3. The second result I mentioned above, which establishes the monotonicity of the gradient norm along the optimization curve (Theorem 3), is not closely related to the title.\n4. The results for gradient flow are not very interesting. Gradient flows are not implementable, and the step size selection issue does not arise in this case.", "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 proposes an interesting notion of \"convexity of an optimization curve\"—a sequence of numbers $\\set{ v_i }$ is called convex if the linear interpolation of the sequence $\\set{ ( i, v_i ) }$ is convex. Consider minimizing a function using gradient descent with a constant step size. The paper proves the following results:\n1. If the function is convex and $L$-smooth, then the corresponding optimization curve is convex for step sizes between $0$ and $1.75 L$, and may become non-convex if the step size exceeds $1.75 L$.\n2. If the function is convex and $L$-smooth, then the gradient norm of the objective function is non-increasing along the optimization curve.\n3. If the function is non-convex and Lipschitz continuous, then the corresponding optimization curve can be non-convex for any constant step size. \n\nThe paper also proves that for gradient flow applied to a convex function, the optimization curve remains convex and the gradient norm is also non-increasing.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please try to find a counter example for the non-convex case that is smooth. \n2. Please try to argue for the significance of Theorem 2. It might be helpful to provide a counterexample involving a commonly used loss function in machine learning.\n3. Please clarify the connection between Theorem 3 and the title.\n1. In the proof of Theorem 6, please either remove the uninformative phrase “by elementary results” or replace it with something more specific, such as “by the monotonicity of gradients of convex functions.”", "broader_impact_concerns": "I believe there is no such concern, as this is a theoretical work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "aoWgLst3XN", "reviewer": "Reviewer_SbwR", "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": "**Weaknesses**:\n\n1. I think the settings where the trajectory is convex are very limited. I guess it is only possible to guarantee GD on deterministic smooth and convex functions. This property easily breaks down if considering stochastic setting with gradient noise, nonconvex functions, nonsmooth functions, accelerated GD, etc.\n\n2. The case where the trajectory is not convex is not necessarily bad. For example, GD/SGD works for minimizing deep neural networks, where the trajectory is likely not convex. For the smooth and convex function this paper considers, although GD achieves convex curves, GD is not the optimal algorithm for solving it. The optimal algorithm, accelerated GD, adds some extrapolation/momentum step and likely breaks down the convex curves, but it brings faster convergence. Based on 1 and 2, the problem to study whether curves are convex seems to be meaningful and interesting only in math, it does not necessarily result in anything. Nonconvex curves do not necessarily hurt anything either.\n\n3. All examples where convex curves fail in this paper are caused by overshooting. For this, I mean the trajectory passes the optimal point. For Example 1, $x_0=-\\eta/4$ and $x_1=3\\eta/4$, and the curve from $x_0$ to $x_1$ passes the critical point $0$. The example in Theorem 2 has $x_0=-1.8$ and $x_1=1.8(\\eta-1)$, which passes by the critical point $0$. Therefore, it seems to me a more interesting problem is to see which stepsize does not overshoot. The same motivation and the same set of results still work, but it allows more instances. Overshooting is also hurting more as it causes oscillations and unnecessary additional optimization steps.\n\n4. It is not fully clear to me why studying curves for gradient norm is related. At first glance, a more meaningful result would be also studying whether the curve is convex or not instead of just non-increasing according to the title. Although there are some links between convex curves of loss and non-increasing curves of gradients similarly to Lemma 1, it is not fully clear in the high-dimensional case. Also, GD is not optimal in making gradients small. The (near) optimal algorithms \"GD after AGD\" and \"AGD with regularization\"discussed in Nesterov's book not necessarily results in non-increasing curves as well.\n\n**Other questions** (These are questions (potential future work) I think about when reading the paper. These are not necessarily something claimed or studied by the paper):\n\n1. The current paper looks at fixed constant stepsize. What happens if the stepsize varies? I think it is easy to design a diminishing stepsize where it converges with a convex curve. Also, there is a recent line of work studying acceleration of GD using large stepsize [1,2], where the stepsize varies.\n\n2. Quotation marks in latex is produced using `` and ''.\n\n3. Why does the following equation on page 6 (after equation (7)) hold? We can choose $\\eta=0.5/L$ and the first term is negative, so it is not obvious to me why this is always true when $\\Vert\\nabla f(x_1)\\Vert>0$.\n\n$$(\\eta - 1/L) \\Vert \\nabla f(x_0)\\Vert + 1/L\\Vert \\nabla f(x_1)\\Vert >0$$\n\n4. The paper said on page 6 that the gradient flow has a unique global solution (before Definition 2). What does global solution mean?\n\n5. As the paper also mention in Section 5, I think it is more interesting to study examples beyond convex smooth functions. To me, convexity of curves is not super interesting. It is good to also think about other behaviours. For example, in low rank matrix factorization $\\Vert XX^\\top - A\\Vert_F^2$ problems, as it contains saddle-point and many local minima, the curves often behave like step-wise functions. This might be a suitable prototype to study optimization trajectories.\n\n**References:**\n\n[1] Provably faster gradient descent via long steps. SIAM OPT. 2024.\n\n[2] Acceleration by stepsize hedging: Silver Stepsize Schedule for smooth convex optimization. Math.Program. 2024.", "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": "The paper studies when the trajectory of gradient descent results in a convex function on a smooth and convex function. For gradient descent (GD) $x_{n+1}=x_n - \\eta \\nabla f(x_n)$ where $\\eta$ is the stepsize and $f$ is $L$-smooth and convex, standard analysis tells that it converges monotonically when $\\eta\\leq2/L$. However, little is known whether the trajectory $(n, f(x_n))$ is convex. The contribution can be summarized below.\n\n1. When $\\eta\\leq1.75/L$, the trajectory of GD is always convex. When $\\eta\\in(1.75,2)/L$, although GD always converges with $f(x_n)$ monotonically decreasing, there exist examples where the trajectory of GD is not convex.\n\n2. When considering the $\\Vert\\nabla f\\Vert$, the trajectory is always non-increasing.\n\n3. These two results are extended to gradient flow when $\\eta\\to0$. The trajectory $(t, f(x_t))$ is always convex, and the trajectory $(t, \\Vert\\nabla f(x_t)\\Vert)$ is non-increasing.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My biggest concern is on the motivation of studying the considered problem.\n\n1. Optimal algorithms, AGD, for smooth convex functions do not produce convex curves, but they achieve the best convergence rate.\n\n2. The only example of convex curves is GD applied to smooth convex functions.\n\nIt seems that whether curves are convex is not super relevant to whether the algorithm is good or not. There are not too many examples where we can guarantee convex curves as well. The question why we should look at convexity of optimization curves is not clear. It is also not motivated enough why we should focus on non-decreasing gradient norm as well. I mentioned one alternative to study what stepsize overshoots. This appears to be a more relevant and interesting problem for me.\n\nI hope the points I mentioned in the weakness section and this biggest concern I summarized above could be resolved in the next version.", "broader_impact_concerns": "Not applied. No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FxEiCLiW3i", "reviewer": "Reviewer_MKfE", "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": "The paper addresses an interesting problem in geometry and calculus. Reading the paper is a pure mathematical joy. The techniques are simple yet clever, and the proofs are correct. \nThe paper definitely deserves to be accepted to TMLR.", "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": "The paper studies whether the iteration/function value curves of gradient descent (GD) and gradient flow (GF) are convex. In particular, it examines whether the sets $\\{n, f(x_n)\\}$ (piecewise linearly connected) and $\\{t, f(x(t))\\}$ have convex epigraphs. The authors provide different results depending for GF and GD for convex and $L$-smooth objectives:\n\n- **GD with step size $\\eta$**: When $\\eta \\in [0, 1.75/L]$, the iteration curve is convex.\n- **GD with step size $\\eta$**: Although GD is convergent for $\\eta < 2/L$, in the range $\\eta \\in [1.75/L, 2/L]$, the authors provide a counterexample showing that the iteration curve is neither convex nor concave.\n- **GF**: For convex and smooth functions, the curve is convex.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Mathematical\n\n- It would be helpful to provide a geometric definition of what is meant by convexity of the curve, possibly using epigraphs to formalize it.\n- **Proof of Theorem 6**: The derivative of $g$ should be $-|| \\nabla f ||^2$. This does not affect the result, but should be corrected for accuracy.\n- Theorem 6 and Theorem 3 show that the gradient norms of GF and GD are non-increasing. However, I assume that these results can be found in prior work, although some off-the-shelf references did not have it. \n\n### Non-Mathematical\n\n- **Page 3** – `lemma 1` → `Lemma 1`\n- **Page 4** – \"`Rearranging terms, left-hand side equals`\" → \"`Rearranging terms, right-hand side equals`\"\n- **Page 10** – Missing period in the last equation of Corollary 1.\n- **Page 11** – \"`and thus, a $C^1$ function...`\" → \"`and thus, $f$ is a $C^1$ function...`\"\n- **Page 11** – The definition of the function $g$ is slightly bulky. It would be clearer to use different sizes of parentheses to improve readability.", "broader_impact_concerns": "The paper is of theoretical nature. There are no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)