Convergence Analysis of Fractional Gradient Descent
Authors: Ashwani Aggarwal
Venue: Accepted by TMLR ()

Abstract: Fractional derivatives are a well-studied generalization of integer order derivatives.  Naturally, for optimization, it is of interest to understand the convergence properties of gradient descent using fractional derivatives.  Convergence analysis of fractional gradient descent is currently limited both in the methods analyzed and the settings analyzed.  This paper aims to fill in these gaps by analyzing variations of fractional gradient descent in smooth and convex, smooth and strongly convex, and smooth and non-convex settings.  First, novel bounds will be established bridging fractional and integer derivatives.  Then, these bounds will be applied to the aforementioned settings to prove linear convergence for smooth and strongly convex functions and $O(1/T)$ convergence for smooth and convex functions.  Additionally, we prove $O(1/T)$ convergence for smooth and non-convex functions using an extended notion of smoothness - H\"older smoothness - that is more natural for fractional derivatives.  Finally, empirical results will be presented on the potential speed up of fractional gradient descent over standard gradient descent as well as some preliminary theoretical results explaining this speed up.

Published in Transactions on Machine Learning Research (03/2024)
Convergence Analysis of Fractional Gradient Descent
Ashwani Aggarwal Department of Computer Science University of California, Los Angeles
astraggarval@ucla.co edu
Reviewed on OpenRevicw: httpps//pparrrriis..e/////ottot/
Abstract
Fractional derivatives are a well-studiod generalization integer order derivatives. Naturally, for optimization, it of interest to understand the convergence properties of gradient descent using fractional derivatives. Convergence analysis of fractional gradient descent, is currently limited both in the methods analyzed and the settings analyzed. This paper aims to fill in these gaps by analyzing variations of fractional gradient descent in smooth and convex, smooth and strongly convex, and smooth and non-convex settings. First, novel bounds will be established bridging fractional and integer derivatives. Then, these bounds will be applied to the aforementioned settings to prove linear convergence for smooth and strongly convex functions and OL1/T) convergence for smooth and convex functions. Additionally, we prove (11/T) convergence for smooth and non-convex functions using an extended notion of smoothness Hölder smoothness that is more natural for fractional derivatives. Finally, empirical results will be presented on the potential speed up of fractional gradient descent over standard gradient descent as well as some preliminary theoretical results explaining this speed up.
1 Introduction
Fractional derivatives DDvid et al. 2011), Oldham & Spanier (1974), [uchhoo 2023) as a genoralization of integer order derivatives are a much studied classical field with many different variations. One natural question ask if they can be utilized in optimization similar to gradient. descent which utilizes integer order derivatives.
To motivate the usefulness of fractional gradient descent, can observe from experiments in Shin al. (202T) that their Adaptive Terminal Caputo Fractional Gradient Descent (AT-CFGD) method is capable of empirically outperforming standard gradient descent in convergence rate. In addition, they showed that training neural networks based on their AT-CFGD method can give faster convergence of training loss and lower testing error. Figure D depicts convergence on a quadratic function for standard gradient descent as well as AT-CFGD and the mothod Corollary 15 labeled Fractional Descent guided by Gradient. For specifically picked typerparametees, both of these fractional methods can significantly outperform standard gradient descent. This suggests that study on the application of fractional derivatives to optimization has lot of potential.
The basic concept of a fractional derivative is a combination of integer-order derivalives and fractional integrals (since there is an easy generalization for integrals through Cauchy repeated integral formula). The fractional derivative that will be studied here is the Caputo Derivative since has nice analytic properties. The definition from Shin al. (2021) as follows where is the gamma function generalizing the factorial (many texts give the definition only for c, but this will be extended later on).

---

Published in Transactions on Machine Learning Research (03/2024)
10-11
41
10-71
fix.y) y1)
10 10-101
10-131
10
19
AT-CFGD
Fractional Descent guided by Gradient
10
Standard Gradient Descent
20
40
60
80
100
Number iterations (t)
Figure 1: Convergence of descent methods function f(x,y) = 10x² + y² beginning at 1, 110 In all cases, the optimal (not theorctical) step size is used. AT-CFGD is as described in Shhin et al. (2021) with x(-1) = 1.5, (11) -10.5, a = 1/2, B = -4/10. Fractional Descent guided by Gradient is the method 0.0675 in It - -\x
discussed in Corollary 15 with a = 1/2, B = - 4/10, X = (r+1)o.2
Definition 1 (Left Caputo Derivative). For x > e, the (left) Caputo Derivative of f IR of order a is (n [a]):
C Da f(x) = [(n - a) I/ (*
(x t)a-n+1 dt.
The main contributions of this paper are highlighted as follows:
First, we establish novel inequalities that connect fractional derivatives to integer derivatives. This is important since properties like smoothness, convexity, and strong convexity are expressed in terms of gradients (first derivatives). Without these inequalities, assuming these properties would be meaningless from the perspective of fractional derivative.
2. Next, we apply these inequalities to derive convergence results for smooth and strongly convex functions. In particular, the fractional gradient descent method examine is variation of the AT-CFGD method of Shin el al. 2021). Theorem 14 gives linear convergence rale for this method on different hyperparameter domains for single dimensional functions. Corollary 15 extends these results to higher dimensional functions that are surms of single dimensional functions. Lastly, Theorem 16 gives lincar convergence results for general higher dimensional functions.
3. Continuing onwards, we examine smooth and convex functions. In particular, if hyperparameters satisfy certain assumptions, Theorem 17 and Theorem 18 give a O(1/T) convergence rate for the fractional gradient method similar to standard gradient descent.
4. The last setting we examine is smooth, but non-convex functions. For this setting, we use an exlension of standard smoothness Hölder smoothness in which standard gradient descent needs varying learning rate converge. We establish general O(1/T) convergence result to a stationary point Theorem 20 and show that fractional gradient descent with well chosen hyperparameters is more natural for optimizing Hölder smooth functions.
Finally, we present results which show potential for fractional gradient descent speeding up convergence compared to standard gradient descent. One main point of inquiry how fractional gradient descent,
2

---

Published in Transactions on Machine Learning Research (03/2024)
in some cases, is able to significantly beat the theoretical worse case rates derived (which are at best as good as gradient descent). Empiriaalyy, it seems that this can be explained by the optimal learning rate far exceeding the theoretical learning rate. Another interesting example that is explored is how functions with the same amount of smoothness and strong convexity might have different preferences between fractional and slandard gradient descent. Lastly, some basic theoretical results on this speed up are given for quadratic functions.
2
Related Work
Fractional gradient descent is an extension of gradient descent so its natural context is in the literature surrounding gradient descent. Gradient descent as an idea is classical, however, there are a number of variations some of which are very recent (Ruder) 2016). One variation is acceleration algorithms including momentum which incorporates past history into the update rule and Nesterov's accelerated gradient which improves on this by computing the gradient with look-ahead based on history. Another line of variation building this is adaptive learning rates with algorithms including Adagrad, Adadelta, and the widely popular Adam (Kingma& & Ba 2017). There is also descent method combining the ideas of Nesterov's accelcrated gradient and Adam called Nadam.
Moving to fractional gradient descent, it is not possible to simply replace the derivative in gradient descent, with a fractional derivative and expect convergence to the optimum. This is because, as discussed in Wei et al. (2020) and Wei et al.] (2017), the point at which fractional gradient descent converges highly dependent on the choice of terminal, C, and may not have zero gradient. if is fixed. This leads to variely of methods discussed in Wei et al. (2020) and [Shin et al. 2022 to vary the terminal or order of the derivative to achieve convergence to the optimum point. Later on, the former will be done in order to guarantee convergence. Other papers take a completely different approach like Hai & Rosenfeld (2021) which opts to generalize gradient flow by changing the time derivative to a fractional derivative thus bypassing these problems.
One reason why there are so many different approaches across the literature is that fractional derivatives can be defined in many different ways (David et al.] 2011) (the most commonly talked about include the Caputo derivative used in this paper as well as the Riemvnn--iouville derivative). Some papers like [Sheng ct al. (2020) also choose simply to take a 1st degree approximation of the fractional derivative which be expressed directly in terms of the 1st derivative. There are also further variations such as laking convex combinations of fractional and integer derivatives for the descent method like in Khan et al. (2018). Finally, there are extensions combining fractional gradient descent with one of the aforementioned variations on gradient descent. One example of this is in Shin el al. 20233 which extends the results Shin el al. 2021 to propose fractional Adam optimizer.
To provide further motivation for the usefulness of this field, there many papers studying the application of fractional gradient descent methods on neural networks and other machine learning problems. For example,
Han & Dong (2023) and Wang et al. (2017) have shown improved performance when training back propagation neural networks with fractional gradient descent. In addition, other papers like Wang et al. (2022) and Sheng
et al. 2020) have trained convolutional neural networks and shown promising performance on the MINST dataset. Applications to further models have also been studied in works like Khan al. (2018) which studied RBF ncural networks and Tang (2023) which looked at optimizing FIR models with missing data.
In general, when reading through the literature, many fractional derivative methods have only been studied theoretically for a specific class of functions like quadratic functions in Shiin et al. (2021) lack strong convergence guarantees like in Wei et al. (2020). Detailed thcoretical results like those of Hai & Rosenfeld (2021) and Wang et al. (2017) are fairly rare or limited. Thus, one main goal of this paper is to develop methodology for proving theoretical convergence results in more general smooth, convex, or strongly convex settings. As an interesting aside, fractional derivatives are generally defined by integration which means they fall under the field of optimization called nonlocal calculus which has been studied in general by Nagaraj (2021).
3

---

Published in Transactions on Machine Learning Research (03/2024)
3 Relating Fractional Derivative and Integer Derivative
Before beginning the thcoretical discussion, it is important to note that for the most part, all of the setup will be done in terms of single-variable functions. Although this might appear odd, due to how the fractional gradient higher dimensions defined, when generalizing to higher dimensional functions much of the math ends up being coordinate- In fact, all of the later results will generalize to higher dimensions following very similar logic as the single dimension case.
Before presenting bounds relating fractional and integer derivatives, need to extend the definition of the fractional derivative to x < For the extension, the definition of the right Caputo Derivative from Shin et al. (2021) is used:
Definition 2 (Right Caputo Derivative). For x < the right Caputo Derivative of f: RR - R of order a is (n = [a]):
(-1)a Sr (e- I'm 0) (1- (1= dt.
f"(()
From this, we can unify both the left and right Caputo Dorivatives into one definition.
Definition 3 (Caputo Derivativo). The Caputo Derivative of f R R of order a is (n = [a]]:
(()(())= = (sgn(x - c))a-1
(t)
7(n - a) 0 aa-n+1
where sgn is the sigu function.
In order to motivate calling this fractional derivative, we can compute limits as the order of the derivative
tends to an integer following the logic of 5.3.1 in Atangana (2018).
Theorem 4. Choose some a E R and let n = [a]. Suppose f:R. + R is times differentiable and (*) is absolutely continuous throughout the interval mmnn(, c), max(æ, c)). Then,
lima-t (D)f(x) sgn(x (xx),
lima-n-1 C sgn(# -
(c).
Proof. Proof via integration by parts, see Appendix for details.
One interesting point of this theorem is that for odd n, a extra sgn(r - c) term appears in the upper limit in addition to the ordinary nth derivative. This will end up motivating coefficients that are proportional to sgn(x c) to cancel this term out.
Next, we present key theorem relating the first derivative with the fractional derivative. To do so, we modify Proposition 3.1 of Hai & Rosenfeld (2021) with the extended domain of x < c.
Theorem 5 (Relation between First Derivative and Fractional Derivative). Suppose f IR + R is continuously differentiable. Let a E (0, 1). Define (t) as:
(t) = f(t) f(x) f(( x).
Then, we have:
(z) c)
(c)
a sgnn( (x - c) I'1 - a) 10 fa+t dt.
f" (t(t)
DD)((x) 1(2 a) - cla
r(1 - a) x cla
Proof. Proof is via integration by parts following the logic of Proposition 3.1 of Hai & Rosenfeld 2021 see Appendix A.2 for details.
4

---

Published in Transactions on Machine Learning Research (03/2024)
Corollary 6. Suppose IR + R is continuously differentiable. Let E (0, If f is convex,
[x -
f()))) r(2 - a) cl
Proof. Start with Thcorem Bis conclusion. Convexity implics (z 2 0. Thus, the first term on the RHS is immeediately S O. the second term on the RHS, sgu(xr - c) fixes the integral to be in the positive direction. Therefore, the second term is also I since the interior of the integral positive.
In the interest of getting the most general results possible, we need to extend the notion of I-smooth and p-strongly convex as will be defined here following Nesterov (2015). As will be shown in later results, this extended nolion could be more natural for fractional gradient descent.
Definition 7. ʃ R + R is (L,p))Hölder smooth for p > if:
If(y) -
- -(x)
2)1 S
1 ++1 11 x 1+p
If p-pp1 1, f L-smooth.
Note that when convexity is assumed, the absolute value signs on the LHS do not malter since convexity means the LHS is non-negative.
Definition 8. f R* + R is (H, Juunffoolyyyyy convex for p> 0 if:
f(v) f(z) - (VI(z), - x) 2
1 1 bly x =xlitp
If p=pp1a 1, is j-strongly convex.
Note that here the norm changes with as well. Although this may be somewhat non-standard, the lincarity over dimension is useful in proving later results.
In later sections, both p = 1 and p * cases will studied so for this section we derive bounds the most general p case. For p 1, Zhou (2018) provides many useful properties that will be leveraged in proving convergence rates later on. These smoothness and convexity definitions are now combined with Theorem get two more useful incqualities.
Corollary Suppose f IR R continuously differentiable. Let (0,1). If is (L,p)-Hölder smooth,
(x) c) I'(2 - a) - claa
DD S r(1 - +1=-a)
L r c 1t
Proof. Proof is a straightforward application of Thcorem and the definition of (L. HH-ldrr smooth, see Appendix A.3 for details.
Corollary 10. Suppose f IR- R is continuously differentiable. Let E (0, If is (un)))unifornly convex,
(x) - c)
C f()()) 2 r(1 a) a)
4 x c 1tp-a
r(2 a)la x ccla
Proof. The proof is identical to that of Corollary g simply replacing L with μ and using 2 instead S.
We now will make of these bounds to derive convergence rates for several different settings.

---

Published in Transactions on Machine Learning Research (03/2024)
4 Smooth and Strongly Convex Optimization
4.1 Fractional Gradient Descent Method
This section will focus modification of the AT-CFGD method from Shin et al. (0221) from the perspective of smooth and strongly convex twice differentiable functions. This study is a natural extension of prior work since they focused primarily on quadratic functions. For this section, we also assume that p = since * introduces many complications stemming from the non-cxistence of inner products corresponding to L L' norms p # The fractional gradient descent method is defined for f R with a E (0, 1), B E I as:
= TT C 80.. f(t))
where
8g f(x)
1 + f(x)) DD C DD a) x cl + B|x D1ta
[xx)[ a) d
x
I
2021p. It states that given a Taylor The intuition for this method is given by Theorem 2.3 in Shin et al
expansion of f around c, Co f(x) is the derivative of a smoothed function where the kth term for k 2 2 is scaled by Ck.a, = [(2-a))(()] T(k+T-o) + T(k-a) The sign of / therefore determines the asymptotic behavior of these coefficients with respect to since the first. term goes to as k and the second has asymptotic (Qi & Luo 2013
rate 3(k a) due to Wendel's double inequality
For this method to be complete, we need to define how to choose Ct. We will see that convenient choice is 34 4 = V for well chosen A In later experiments, this method will thus be labelled as Fractional Descent guided by Gradient. This choice of с differs from Shin et al. (2021) whose AT-CFGD method used G = ft-m for some positive integer m. In practice this fractional gradient descent method can be computed with Gauss-Jacobi quadrature as described in detail in Shin al. (2021).
In order better understand this fractional gradient descent method, we take the limit - 1. Calculating, arrive at &ga.3 (xx)) = f'(xx) A,3J (xx) =
(x.)((( Inluitively, if X,8 is chosen properly, this approximates (m(xx) ff f((x)) up to proportionality which corresponds to a 2nd order gradient method update. We will see in Section 7 that we can actually accomplish similar behavior on quadratic functions even with 3 = 0 as long as a E 1).
4.2 Single Dimensional Results
Before prove convergence results, we need one more inequality for bounding the 1 derivative. Lemma 11. Suppose f R twice differentiable. If is L-smooth and a E (1, Then,
L 12-c2-00 2-0
D2 < T(3 a)
Tf f is j-strongly convex and a E (1, Then,
C D)f(()) 2 1(3 a)
P x c 2-0
Proof. This is a dircct result of the fact that L-smooth implics that f"(x) S and p-strongly convex implics that (*(x) 2 μ. See Appendix B.1 for details.
The next theorems the primary tool that will be used for convergence results of this method.

---

Published in Transactions on Machine Learning Research (03/2024)
Theorem 12. Suppose f :.R. R is twice differentiable. If is L-smooth and p-strongly convex, E (0, B 2 0. Then,
f(x) - Kí(æ c)l S K2/2 cl. where Ki = (- (3 7) and K2 = (B + with 7 L-smooth and convex if f is to
1-o 2-a
Note that the above also holds if f is
Proof. Holds by applying Corollary Corollary 10 and Lemma 11 See Appendix B.2 for details.
Theorem 13. Suppose f : : R twice differentiable. f L-smooth and p-strongly convex, a E (0, 1],
8 < 0. Then,
88. f((x) Ki( -o) K2|2 cl.
where Ki - ( L-smooth and convex if is set to O.
(7),8) and K2 = (7ar) with 7a,8 = 3
1-a
Note that the above also holds if f
2-a
Proof. Holds by applying Corollary
Corollary 10 and Lemma 11 See Appendix B.3 for details.
Everything is now ready for beginning discussion of convergence results. We have two cases: 3 2 0 and / < 0. We can treal these cases simultaneously by deffinng K1. K2 as in Theorem 12 for the former and Theorem l3 for the latter. Tn both these cases, K2 2 O, however, K1 can be positive or negative. For single dimensional f, we get the following convergence analysis theorem.
Theorem 14. Suppose f R + IR is twice differentiable, I-smooth, and y-strongly convex. Set 0 < a and 3 IR. B 2 0, define K1, K₂ as in Theorem 12 if 3 S 0, define Ki, K₂ as Theorem Let the fractional gradient descent method be defined as follows.
Et+1 = It - Th 800.0 f(x))
(I-KGA, Do for 0 < << <
KilK
z4 = - (f with 1 K2A: - K2/Ad > <>0
Then, this method achieves the following linear convergence rate:
| - x2 1- - 1 =) (1 (1- K, - K2/del) 27
K2de + Ka/Nel) 100. x²12.
In particular, however, this rate is at best the same as gradient descent.
Proof. Follows by applying Theorem 12 and Theorem 13 to bound the fractional gradient descent operator with an approximation in terms of the first derivative. Then, the proof of standard gradient descent rate for smooth and strongly convex functions can be followed with additional error terms from the approximation depending Iz Q-- This rate at best same gradient descent. where would expect to coefficient. of since K2/Adl 0. See Appendix B.4 for details.
As remark the condition Ki\ Ae/Ad O, consider the special case x 2 0, K1 2 0 then this condition reduces to A K,+K, Similarly, for X, < 0, K1 0, this condition reduces to A K.-Ki
Ultimately, this proof does not give a better rate than gradient descent. In some sense, this is a limitation of the assumptions that everything is expressed in terms of integer derivatives making it necessary to connect them with fractional derivatives. This in turn makes the bound weaker due additional error terms scaling on Ir - G. However, this result is still useful for providing linear convergence results on wider class of functions since Shin et al. (2021) only studied this method applied to quadratic functions.
7

---

Published in Transactions on Machine Learning Research (03/2024)
4.3 Higher Dimensional Results
We can also consider J: I R by doing all operations coordinale-wise. Following Shin et al. 2021 the natural extension for the fractional gradient descent operator for f is:
C C f(z)
s (it (x) C & fx.:2((
Here f(=(1)= f(x + (y - 200) with eli) the unit vector in the jth coordinate.
Generalizations Theorem 14 can now be proven. We first assume that f has a special form, namely that it is of single dimensional functions.
Corollary 15. Suppose f: _ R is twice differentiable, L-smooth, and p-strongly convex. Assume f is of form f(x) Σ fi(x!0) where Ji IR - R. Set 0 < a and 3 E R. II B 2 0, define K1, K2 as in
Theorem 12 if 3 < 0, define K1, K2 as in Theorem 13 Let the fractional gradient descent method be defined
as follows.
F++1 = Zt Ts 80.. f(at)
(1- K, K Ae for 0 < <<<<> <2
Ttt (T- (1-Kk
Zt c = - V with 1 - Kiλ K2/Ad > E>
Then, this method achieves the following linear convergence rale:
| - x²113 - 1 - 1) (1 K1 - KelAel 27
(
- Ki + Ka/Del | - x=113
In particular, however, this rate is at best the same as gradient descent.
Proof. If f is I-smooth, each (y) is L-smooth according to the single dimensional definition and all relevant results hold for it. The same goes for p-strong couvexily. Note that taking the derivalive of each fy.r(y) is the same as taking the jth partial derivative of at a with the jth coordinate replaced by y. Thus, C5a.9 f(x [C g (z(2)), Cgo. fa (x))))). Additionally, Vf(x) = (=(()))),,......... ((( (=(()))). As such, the optimal point of f in the ith coordinate is the optimal point of ft. Therefore, Theorem holds coordinate wise. This immediately gives the result.
In the more general case, there is a single term that does not immediately generalize to higher dimensions proportional (Iv)( |2, x²1)> the absolute value is taken element wise. For the single dimension case, convexity allowed us to bypass this issue, but for higher dimensions, we have to use Kauchy-Schwarry
Theorem 16. Suppose f: R R is twice differentiable, L-smooth, and p-strongly convex. Set 0 <
and 3 E R. If B 2 0, define K1, K₂ as in Theorem 12 if B < O, define K1, K2 as in Theorem 13 Let the fractional gradient descent method be defined as follows.
Ze+1 = 2t 17t 88 (2x)
(1-Ki 2k
N = (1-Ki K for < <
z - Vf with (1-Ki))) 2K2|del 0.
Then, this method achieves the following linear convergence rate:
(2 - 2)n(1 - Kide) E Kide)
2K2 1
| 111 < 1
I 20
(1 K, K2/D,)2²
In particular, however, this rate is at best the same gradient descent.
8

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. Follows by very similar logic to Theorem except generalized to higher dimensions by taking operations woordinate-wise. The key difference as mentioned above is a single term whose bound requires more care. Similarly, the rate is at best the same as gradient descent where we expect - coefficient since [1 2 0 See Appendix B.5 for details.
As a remark on the condition on X, in the special case of X 2 0, K1 2 0, we have:
ΦK1
2kKg
Ø <
L
L
A
K1
2kK₃L
For implementing the learning rate for the method in this section, we note that as L + 00, Th - 0. Since L can always be increased while still satisfying smoothness, in principle the learning rate just needs to be chosen small enough same as in standard gradient descent. Similarly, for sufficiently small A the condition will always be satisfied. Of course, finding optimal hyper-paramettrs is important and techniques like line search can be employed improve convergence rate.
5 Smooth and Convex Optimization
This scction considers optimizing L-smooth and convex function, f: - R. For similar reasons as the previous section, the case + 1 is deferred for future work. The fractional gradient descent method for this section will be identical to the previous section. Similarly to the prior section, split into two cases: 1) that f is a sum of single dimensional functions and 2) that f is a general higher dimensional function. For the first case, we have the following.
Theorem 17. Suppose f I + RR is twice differentiable, L-smooth, and convex. Assume f is of form ((x) Σ fi(x!(0) where ʃi RR R. Set a and R. Tr 3 2 O, define K1, K₂ as Theorem 12 if 3 < 0, define K1, K2 as in Theorem 13 Let the fractional gradient descent method be defined follows.
Te+1 St - 1f C0.00
7=
1 I-AK; I-XKI-IA7K3
2 = - -VV with 1 - -A1
V2+1
12
V2-1
Then, this method achicves the following O(1/T) convergence rate with By as the average of all n, for 1
ao x=112
f(Ør) - f(x))
-K- -I-AK-121j66 1-XX[+
4
-
In particular, however, this rate is at best the same gradient descent.
reduce to the single dimensional case. This case follows by applying Theorem 12 and Theorem 13 to bound the fractional gradient descent operator with approximation in terms of the first derivative. Then, the proof of standard gradient descent rate for smooth and convex functions can be followed with additional error terms from the approximation ion depending on 3 - -.. This L rate is at best the same as gradient descent (which has coefficient. 27 since [][K2 2 0. See Appendix C.1 for details.
Proof. By similar reasoning as Corollary 15
For the general case, just as in the previous section, there single term proportional to </V (ax)), ja, x*D if the absolute value is taken element wise that must be dealt with more carefully. This term ends up making the method somewhat more complicated.

---

Published in Transactions on Machine Learning Research (03/2024)
Theorem 18. Suppose f FR + R is twice differentiable, L-smooth, and convex. Set 0 a < and / E R. If B 2 O, define K1, K2 in Theorem 12 if B < O, define K1, K2 as in Theorem 13 Let the fractional gradient descent method be defined as follows.
Jt+1 = Ht - Tht C 8a. f(x))
[ L + 1-t,K, 1(1-),Ki)
(ect1)2
It - - V (xx)) with 1 - Ar = =st\ee//2
(+--+11²
2 (1+ - with v5 +
Bc+1
Then, this method achieves the following O(1/T) convergence rate with To as the average of all 22 for 1s
(5p + 1)
10000 - x
((T)) - S
2 8
480
In particular, however, this rate is at best the same as gradient descent.
Proof. Follows by very similar logic to Theorem The key difference mentioned above is single term whose bound requires more care. This term ends up causing difficulties when passing to telescope sum. This motivates step-dependent and A which are determined by an underlying increasing sequence 8;. This rate
is best the same as standard gradient descent since coefficient 27
4 48g +
(1)+1)²
2 1
and gradient descent's rate has
L See Appendix C.2 for details.
For implementation, this theorem requires first choosing the s sequence satisfying the algebraic condition. Then, with an approximation of (which gradient descent also requires), x and т can be computed following the formulas. In general, the condition on de has two solutions: one positive and one negative.
6
Smooth and Non-Conver Optimization
6.1 Fractional Gradient Descent Method
This section will focus on fractional gradient descent in smooth and non-convex setting. This setting turns out to be the most straightforward to generalize to p * and demonstrates potential for fractional gradient descent to be more natural. [Berger et al. (2020) approaches this setling by varying the learning rate in gradient descent. For this section, we will adapt their proof in 3.1 to fractional gradient descent. We use similar fractional gradient descent method as the previous sections defined as:
Fe+1 Et Thpp 80 [(x)
C
where (for f: IR ++R) R):
6 (5)(())= ( a)) a-p--1
The difference from previous sections is that the second term is dropped since Lemma I1 no longer holds and the exponent of Ix - cl now depends on p. For higher dimensional f, we use the same extension as in the previous sections where each component follows this definition. Namely, for f: IR R, the definition is
C Cg8a 8 f(x) = [C (ix Cga So Se (z(
10

---

Published in Transactions on Machine Learning Research (03/2024)
6.2 Convergence Results
For easing convergence analysis compulation, we leverage the following Lemma.
Lemma 19. Suppose : R is continuously differentiable. If f is (L.p)-Hölde) smooth, E (0, 11, then
[1(x)) -tt--- - 55 & K| cl
L(l-a) where K = (1+p-a)*
Proof. Using Corollary 9 rearranging terms gives this bound directly.
Now, present O(1/T) convergence result to stationary point as follows.
Theorem 20. Suppose I R is continuously differentiable, (Hölderö smooth, and Vx, f(x) 2 f" Set 0 < 1. Define K as in Lemma 19 Let the fractional gradient descent method be defined as follows.
I++1 = 2t Up
f
(i)
(i) X /
0s Dulo
(or) with 0 < A < /
0 P<イ<
(A KA) +KA)+
Then, this method achieves the following convergence rate:
Vf(+))] f(x0) l
(T + 1)1b
where
v = 17 (
(
L + 1+p I+p
Kλ
Proof. Follows by applying Corollary g to bound the fractional derivative with an approximation in terms of the first derivative. Then, the proof as aforementioned from 3.1 of Berger et al. (2020) can be followed with additional error terms from the approximation. Careful choice of c is required in order for the degrees of various terms to allow simplification. See Appendix D.1 for details.
The key difference in the fractional gradient descent operator from previous sections is the exponent now a - a-p+1 instead a. If we choose a = (assuming < p < 1), the total order of |æ - cl terms becomes with a remaining sgn(æ c). In this case, the fractional gradient descent operator is (up and sign correction) just fractional derivative. Theorem 20 tells us that convergence can be achieved in this case with constant learning rate with proper choice of C which means that our fractional gradient descent. step at any t is directly proportional to the fractional derivative's value. In a sense, this means that the fractional derivative is natural for optimizing I when setting a
proportionality
7
Finding the Advantage of Fractional Gradient Descent
7.1 Experiments
We can see that there is an obvious gap between the motivation of doing better than standard gradient descent and the thcoretical results. While the theoretical results are crucial guarantecs on worst case rates, they currently cannot explain how fractional gradient descent can do better. Thus, this section dedicated to experiments trying to explain this gap.
11

---

Published in Transactions on Machine Learning Research (03/2024)
0.4
Learning Rate
AT-CFGD Optimal
0.3
Fractional Descent guided by Gradient Optimal
Standard Gradient Descent Optimal
Fractional Descent guided by Gradient Theoretical
0.1
0.0
20
40
60
80
100
Number of iterations
Figure 2: Learning rates used by different methods in Figure ! with the theoretical learning rate given by Corollary 15 added.
The first thing to note that in the experiments recorded in Figure 1 the learning rate used is not that of
Corollary 15 rather the optimal learning rate for quadratic functions from 3.3 (hhin el al. (2021 given by:
(Axt + b, de) ni (de, Ado)
for the function Jaa Ar + +bxx + e with descent rule Tz41 = 3t. nede.
We plot in Figure exactly what the optimal learning rates used in Figure ! are and how they can compare to the theoretical learning rate given by Corollary 15 The optimal learning rate for gradient descent and the theoretical learning rate from Corollary 15 tend to be significantly smaller than the optimal learning rate for fractional methods. It should be noted that the actual gradient norms may differ so the fairest comparison is between the optimal and theoretical learning rate of our method (Fractional Descent guided by Gradient).
From the equation in the discussion deriving Theorem 14 (Ie+1 x²²² S [1 - (2 - )) - Ki (x) - x²)², we see that larger learning rate directly improves the rate of convergence (assuming the larger learning rate is still valid with respect prior assumptions). Thus, it becomes apparent that in some cases, the theoretical learning rate being much lower than necessary explains why the theoretical convergence rate is no better than that of gradient descent.
One question that could then be raised is if the current data of the assumptions is enough to be able to prove a better bound that perhaps involves a speed-up over standard gradient descent. The data with respect to a smooth and strongly convex function is two numbers T., μ.. Other than this, the function is a black box and we would expect any bound basod on these assumptions to be equivalent for any functions with the same I,, I assuming same hyper-parameter choices.
Looking at Figure 3 and Figure f observe that despite the L, μ data being identical, the fractional gradient descent convergence rates are vastly different and in particular, there is no agreement over beating standard gradient descent. This suggests that to prove whether this fractional gradient descent method is better/worse than gradient descent requires more data than just p-strong convexity and L-smoothness about the function. Note that in order construct this example, X₂ had to be chosen very close to the constraint which meant that the theoretical learning rate and convergence rate are both extremely slow. This means that it may be possible to prove advantage of fractional gradient descent with tighter constraints X,-
12

---

Published in Transactions on Machine Learning Research (03/2024)
5
10
10
4
Learning Rate
10-41
3
Fractional Descent guided by Gradient Optimal
Standard Gradient Descent Optimal
10
2
Practional Descent guided by Gradient Thecretical
10
10 11
10-13
Fractional Descent guided by Gradient
Standard Gradient Descent
0
20
60
100
20
40
6b
80
100
Number of iterations
Number of iterations
Figure 3: Comparison of fractional and standard gradient descent methods for f(z) x²
with (1, 10, 5, 8, -6). Hyper-parameters in Corollary 15
are 1/2, B -4/10, d 000665
Fractional Descent guided by Gradient
0.4
10a
Standard Gradient Descent
10-2
Learning Rate
0.3
10-5
Fractional Descent guidedd by Gradient Optimal
f(x+)
Standard Gradient Descent Optimal
10-8
Fractional Descent guided by Gradient Theoretical
10:
0.1
10 14
0.0
20
40
80
100
60
80
100
Number of iterations (t)
Number of iterations
Figure 4: Comparison of fractional and standard gradient descent methods for f() xx 1,,g((10,1,,,9)) 9, 9]), with vo (1, 10,,-0,,555 10,5,8, -6). Hyper-parameters in Corollary 15 are 1/2, B -4/10, A -0.0675
7.2 Quadratic Function Analysis
Motivated by these empirical findings, we present one final result applying the fractional gradient doscent method from Section 4.1 to quadratic functions. This result is important in that it shows that with more information than just L, μe, we are able to understand when the fractional gradient descent method will outperform gradient descent (at least in this limited case).
Thcorem 21. Suppose fxx = 1.=" Ar + 8T x + Yo for some positive definite μ be its smallest eigenvalue and L be its largest. eigenvalue. Choose 3 S O, a E (0, 1), and A E R. Choose from that
lt with elements ai. Lot
A fx) with (8-y) where 7 == 1-a Then, we have the following:
Let = I dia A' = and v' Db. Then, C8a = A'x In particular, if A' is non-symmetric, this fractional gradient operator not given by the gradient of any function.
2. Suppose that Vy E RR we have that /' v'llv/l2 < of A'y < L'llvll2 and suppose that A is chosen so that all elements of D are positive. Then, we have the following linear convergence rate for fractional gradient descont:
| -
1
|20 x 1=.
L'
13

---

Published in Transactions on Machine Learning Research (03/2024)
In particular, if the condition number of A', x(A)) = k, is smaller than x(A) j then fractional gradient descent achieves faster convergence rate (in number of iterations).
Proof. The first point follows from straightforward calculation of the fractional gradient descent operator on quadratic functions. The second point follows from a proof almost identical to that of gradient descent on quadratic functions. The linear rate of convergence for gradient descent is 1 - 4 so if m(A') < x(A), the convergence will be faster. See Appendix E.1 for more details.
For one simple application of this theorem, consider the case where A is diagonal. Then A' is also diagonal with elements of the form di a1 az ) on the diagonal. This case corresponds to all of the above experiments. We note that μ² and L' in this case simply the smallest and largest eigenvalues of A' since A' is positive definite. Some μ = oz will be the smallest eigenvalue of A and some L = Ojj will be the largest eigenvalue. In A', these elements become 101 - - L(1 - A) with 0 < A < 1. We then have the following:
L(1-A)
L 11-A
L 1 μL- 1
LL-
x(A).
A(1 + / -1-
This appears to contradict Figure since this seems to imply that fractional gradient descent should always outperform gradient descent on these simple quadratic functions. However, the key is that the LHS is not necessarily equal to k(A'). In particular, d; can also amplify μ < ag < such that these components become the maximum eigenvalues of A' and can shrink components to become minimum eigenvalues. To avoid this, observe that if A S 1. the maximum of the d; will always be where a₂ L and the minimum will always be where au - ps. Thus, if A < 2, for these simple functions, fractional gradient descent always does at least good as gradient descent. Figure corresponds to the case of A 0.99 which does not satisfy this condition.
One more point to note is that in the limit as a + 1, the theorem still holds as long as 3 o 0. In particular, as long as 3 7 * 0 the theorem's convergence rate has no dependence on B and a since À inversely scaling on 3 y is effectively cancelling it out. This means that in some sense if we set / = O, we are getting the benefits of a second order method where a 1, B * 0 (sce Scction 4.1 for details on this limit) without. actually using more than the first derivative.
For more complicated A, applying this theorem requires comparing the condition number of A' against that of A with no easy relationship like in the previous simple case. While this theorem is limited to quadratic functions, it is promising in providing a theoretical explanation of how fractional gradient descent can outperform gradient descent - question that prior work left open.
8 Future Directions
Going off of the preceding discussion, one important future direction is to scarch for additional assumptions to classify when this fractional gradient descent method will outperform gradient descent on general classes of functions. It is also important to develop lower bounds to prove when general fractional gradient descent. methods are capable of achieving superior performance to gradient descent and to verify whether the convergence rates developed in the paper are tight.
With respect to the tightness of the bounds, one potential area for further improvement is to better handle the second term of C8a.8 f(z) involving fractional derivative of order between I and with coefficient scaling with B. Currently Lemma [I handles bounding this term, however, it is rather weak in that it loses any information that would make this term useful for convergence. This is reflected in how sending / + 0 tends to improve the theorctical rate. Even in Theorem 21 3 could be set to 0 without any loss in the results. If we consider Theorem 4 we have for < a < 2 that lim.-.1 CD fx)) sgn(x ()) (())). If e is chosen properly, this could potentially work similarly to acceleration algorithms in gradient descent. More work nceded to understand this term outside the limit case since attempting to use integration by parts express it in terms of the gradient fails. It is important in future work to understand if this term can be useful for proving better rates.
14

---

Published in Transactions on Machine Learning Research (03/2024)
Another interesting direction would be to investigate the effects of changing ct- Both Shin et al. (2021) and this paper use different methods of choosing 6 and it is not clear which is better since it is difficult to directly compare without more theoretical results. In addition, future work could look at applying similar strategics of relating fractional and integer derivatives to different underlying fractional derivatives such as the Reimann-Liouville derivalive.
One important future direction is show convergence results for p + for more settings. In this paper, we only discuss p # 1 for smooth and non-convex functions while leaving the other two settings for future work. As aforementioned the difficulties of this setting stem from the norm not being induced by an inner product on I spaces making it difficult to expand terms of the form | yll +p or even just |z yl' for some arbitrary I,
i+p
Another line of thought is to bypass the need for inequalities relating fractional and integer derivatives by using convexity and smoothness definitions that only involve fractional derivatives. This would be idcal since the current proof methodology loses lot of information about the fractional derivative in connecting it to the gradient causing the convergence rates to be bounded by those of gradient descent. One direction that may be promising is using fractional Taylor series like in Usero (000)) to construct these definitions. However, these series for Caputo Derivatives are somewhat limited in how they need to be centered at the terminal point of the derivative. If we ignore the terminal point and try to use simple assumptions like Lipschitz contimuity of the fractional derivative, bad behavior around the terminal point (where the fractional derivative rapidly tends to 0) prevents it from being applicable even to simple test functions like |x|' One potential solution would be to the terminal point depending on x only and not the iteration number and consider Lipschitz continuity properties after integrating this dependency. Following this line of thought, take the conditions from point 2 of Theorem 21 and replace A' with the total derivative of the fractional gradient descent operator. This could serve as a natural generalization of smoothness and strong convexity.
could
In conclusion, this paper proves convergence results for fractional gradient descent in smooth and strongly convex, smooth and convex, smooth and non-convex, and quadratic settings. Future work is needed in extending these results to other classes of functions and other methods to show a general guaranteed benefit. over gradient descent.
Acknowledgments
T thank Prof. Quanquan Gu for his constructive comments on this manuscript.
References
Abdon Atangana. Chapter 5 fractional operators and their applications. In Abdon Atangana (ed.), Fractional Operators with Constant and Variable Order with Application to Geo-HHydrolog, pp. 79 112. Academic doi:
Press, 2018. ISBN 978-0-12-809670-33
3.00005.. URL httpss//www.ccceeeeeireecc.. cwtestttccccccccoee/eeeeeeeeee orc.epac..................aaaaae
Guillaume O. Berger, P.-A. Absil, Raphaël M. Jungers, and Yurii Nesterov. On the quality of first- order approximation of functions with hölder continuous gradient. Journal of Optimization Theory and Applications, 185(1):17-33, Apr 2020. ISSN 1573-2878, doi: 10.1007/s119955-0000-11133 http:://eaa.orr//000000///00000. 107.0000000/10000000000 https://doi.oor 10.
URL
S. David, Juan López Linares, and Eliria Pallone. Fractional order calculus: Historical apologia, basic concepts and some applications. Revista Brasileira de Ensino de Física, 33:4302-4302. 12 2011. doi:
10.1590/S1 00000//1180-11122900 00111122211000000000000 1000400002.
Pham Viet Hai and Joel A. Rosenfeld. The gradient descent method from the perspective of fractional calculus. Mathematical Methods in the Applied Sciences, 44(7):5520 5547, 2021. doi: https:/ /doi..rg//10 1002/mma.71i URL
http://abbb/.1..0/mmmmamm. 100.00000.mmmmmmmm 7127
Xiaohui Han and Jianping Dong. Applications of fractional gradient descent method with adaptive momentum in bp neural networks. Applied Mathematics and Compulation, 448:127944, 2023. ISSN 0096-3003. doi:
15

---

Published in Transactions on Machine Learning Research (03/2024)
http://6d...r//10000000///aa0m00 p:1/8009630032300113.
URL httpp////www...aaaooooooooo.oooa
Shujaat Khan, Imran Naseem, Muhammad Ammar Malik, Roberto Togneri, and Mohammed Bennamoun. A fractional gradicnt descent-based rbf neural network. Circuits, Systems, and Signal Processing, 37(12): 5311 5332, Dec 2018. ISSN 1531-5878. doi: 10. 10.1007//500334-010-00333 URL httpp:://doi.orr/////..
600034-018-0835-3
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Yuri Luchko. General fractional integrals and derivatives and their applications. Physica D: Nonlinear
Phenomena, 455:133906, 2023. ISSN 0167-2789. doi: http:://oo.oor////0000///pppsss
2003.3...22.333306 URL
https: www. www.sscieneeiiectt. htt.a//cc.....c..........././aaa
Sriram Nagaraj. Optimization and learning with nonlocal calculus, 2021.
Yu Nesterov. Universal gradient methods for convex optimization problems. Mathematicnl Programming, 152(1):381 404, Aug 2015. ISSN 1436-4646. doi: 10.007//40107--1400999. URL https://doi.org: 1007/810117-014-0799-00
Keith Oldham and Jerome Spanier. The fractional calculus theory and opplications of differentiation ond inlegration to arbilrary order. Flsevier, 1974.
Feng Qi and Qiu-Ming Luo. Bounds for the ratio of two gammn functions: from wendel's asymptotic relation to dozzovi-giordano-peearrt theorem. Journal of Inequalities and Applications, 2013(1), November 2013. ISSN 1029-242X. doi: 10.1186/IM 01/86/119--2 112111222222001111112222 242x-2013-54.. URL http://áx.doo doi org//o.////...o..oooooooo 10e/1118611200 11111002222222
Sebastian Ruder. An overview of gradient descent optimization algorithms. CoRR, abs abs/1609.04747, 2016.
URL httt:httt///xii wtrgg/abs1669. 04747
Dian Sheng, Yiheng Wei, Yuquan Chen, and Yong Wang. Convolutional neural networks with fractional order gradient method. Neurocomputingg, 408:42-50, 2020. ISSN 0925-2312. doi: httpss://doi.org/10.1000 neucom. 2019.10.017. URL
Yeonjong Shin, Jérôme Darbon, and George Em Karniadakis, caputo fractional derivative based algorithm for optimization, 2021.
Yeonjong Shin, Jerome Darbon, and George Karniadakis. Accelerating gradient descent and adam via fractional gradients. Newral Nelworks, 161, 04 2023. doi: 22.1066/..euuee222223...00000
Jia Tang. Fractional gradient descent-based auxiliary model algorithm for fir models with missing data. Complexity, 2023:7527478, Feb 2023. ISSN 1076-2787. doi: (0.1155/2023/557777 URL https://doi org 10. 1151101.15///22//55//11
D. Domínguez Uscro. Fractional taylor scrics for caputo fractional derivatives. construction of numerical schemes. 2008. URL https://api. ttttps://ap..semantiic.m www.nti oetpaaattccccolo....ooo/ooppopps 54594739
Jian Wang, Yanqing Wen, Yida Gou, Zhenyun Ye, and Hua Chen. Fractional-order gradient descent learning of bp neural networks with caputo derivative. Neural Netu., 89(C):19 30, may 2017. ISSN 0893-6080. doi:
URL https://doii orgo -eweee nwwnet........mm...m 2017.02.0000
Yong Wang, Yuli He, and Zhiguang Zhu. Study on fast speed fractional order gradient descent method and its application in neural networks. Neurocompuling 489:366 376, 2022. ISSN 0925-2312. doi: https://
doi.org/ 1tt///011110/////1111//1 nwwp:////..ncommmmmmmmm neucom. weucom.2022.02.. www..222......... URL $0925231222001994
Yiheng Wei, Yuquan Chen, Songsong Cheng, and Yong Wang. A note on short memory principle of fractional caleulus. Fractional Calculus and Applied Analysis, 20, 12 2017. doi:
16

---

Published in Transactions on Machine Learning Research (03/2024)
Yiheng Wei, Yu Kang, Weidi Yin, and Yong Wang. Generalization of the gradient method with fractional order gradient direction. Journal of the Franklin Instibule, (57(4):2514-28) 2532, 2020. TSSN 0016-0032. doi: http://.o..opp//000.....rraaaaaa atticle//s//90010052220333
2020.01.008. URL httpppps/wwa..scceaaaaaaaooo/oop
Xingyu Zhou. On the fenchel duality between strong convexity and lipschitz continuous gradient, 2018.
A Missing Proofs in Section 3 Relating Fractional Derivative and Integer Derivative
A.1 Proof of Theorem 4
Proof.
D2)(() sg - c)
(t)
dt
[(n ())
C Ma-ntI
sgn(x - c)m
(t) 2 t sgn( - c) + - fn+tl (t)lz fn+1(t))z - -
sgn xr c)dt
I'nn a)
sgn r c²
(M(c)x cp + { pm+
(t)|z 11m
[(n 1)
As - n, this simplifies
= (2)0--/----0-------00- --
As - n 1, directly from the definition,
fDz sgn(æ - c)- [ ("(()dt sgn(x-c)" -p- fm-1(())
A.2 Proof of Theorem 5
Proof. First, note that for (0, DD fractional derivative can be both positive and negative unlike the first derivative of a line. Also note that (t) (f) (z)) Therefore, we begin with the following expression:
x-c r(2-a)la-da- One interesting thing here that this
(x)(x)) (1(x)) 1'xx-
1
f' | - -()))
T(1 a))
|" 1 dt)
r(1 - a)
|0 1| (t)
a
1 12-11 - sgn (t)dt
r(1 a)
r(1 a)
(1)
angn J c)
fr
(1)
t dt.
r(1 a) t/m t=c
T(1
It remains to show that the first term vanishes as t + x which is done using L d'Hopital's Rule:
(t())
f(() - (x)))
lim [(1 a)} 1/a
lim to of a)}x - a sgu(x 1) 0.
The last equality is since E (0. 1] so 1150 0.
17

---

Published in Transactions on Machine Learning Research (03/2024)
A.3 Proof of Corollary 9
Proof. Note that (loperrölder smooth implies that (t()) <
1-pl |r l|ttp.
Also
p a > since
p p> 0 (0, 1]. Thus,
fx) c) (z)((x)= [(2 a) x cla
(x(c)
a as 22 c)
(t
dt
r(1 a) r d0
T(1 a)
T 1 1a+1""
L/x c 1+p-o
a.. c)
t|p dt
(1 + pl a)
(1+ a)
L/r c -
aLs c)
x c =
sgn(# c)
(1 + p a)
(1 p[ (1-a)
1 1+ +pp-
L
x c ---lttp-a(1 +
(1 + p)[(1 a)
1 +
I
|r clltaa
M(1 - a)(1 +
The other direction of the inequality follows by the same logic using instead (o(t) 2 -4
I+p x - -11tt and using
2 instead of S.
B Missing Proofs in Section 4 Smooth and Strongly Convex Optimization
B.1 Proof of Lemma
Proof. L-smooth implies that f"(x)= S L. Since a E (1, 2].
sgn(z v c)
c
(t)
Dc
dt
T(2 a)
a
sgn x - c)
L
a-1 dl
T(2 a)
eg c)
[r 2-2
sgn(a (I L)
T(2 o))
2
L
1 c2aa
r(3 a)
The bound holds since the integral is in the positive direction due to sgn(æ- c).. The proof for p-strongly convex is identical except using f (x) 2 n.
B.2 Proof of Theorem 12
Proof. We begin by upper bounding fx)) Note that since both terms in it have (x-c) c) in the denominator, sgn(x- c) determines which inequality must be used. Let R denote ReLU, Then,
go (()))(() 1'(xx) 1 "2 R(x + 11 - a R(e x) LBR(s -) -pBB(c x)
a
= =f'(x) p - c) + LRR(c x) - L3R(2x -)) - 113B11B -x)
= ['() + (L33 - R(= - c) + (Ly - 1BBRR(c- c x).
The first terms on the RHS come from bounding the first term of C &ga. f(x) and the latter two terms come from bounding the secon term of C 88.3 fx)) Similarly, we find that
Cg 2 f((x) + (u3 L)) c) + (4Y L3) x).
18

---

Published in Transactions on Machine Learning Research (03/2024)
Observe that
(LB - un) - (up - Ln)
(L- (L-1)3+ + (L +(
-Ph
(L p2)
(3 + +n):
2
2
2
(Iy - 149) - (Jry - T,3)
(T. - 11) (B +7))
2
2
(LB - u7) + (u3 - In)
(L + 8 - (L puy (1+
(B 7):
2
2
(Ly p3) + (Jy LB)
(L + p1)
(3 7)
2
2
Using these equations gives
(L (L- H)
(B ))((2 - c) + (++
C (f
(3 - R() c)
2
2
(L 11
(3 + ( (0lc-cc000 -x) xx- (L + 1)
(3 -7)R(c x)
2
2
= f((++ + (I+ 1))
(I. - 11)
2 (B - (z c) +
(B + 7)(x -c cl
2
f((x) Ki(E - c) + K2/0 - d.
Similarly, the lower bound is
о 80. f(x) 2 f'(x + K1(x c) - K21æ cl.
Putting both of these bounds together gives the desired result:
-K2l - cl s fxx) - fx(x) - K1 - c) S K21Ø - cl.
B.3 Proof of Theorem 13
Proof. The proof begins similarly as in Theorem 12
except 3 determines the sign as well.
1 - a
1 -
(aa S ('(x) 1 22-0
R(x c) L
R(e- - x)) + LR(3(x - c)) - pR[((c- - zr))
2-
1 - a
a
f(()) - -22-2 R(x - c) + L
2 R(c - x)) - L33R(c x) + 43RRIx - c)
f(()) + 2) c) (Ia, R(c - x))
f'(x) + Kí - c) Kg/2 cl.
Similarly, we find that
C Cg f(x))(()) 2 f'(x) + (L%..)) c) (NTa, x)
fx(x) + Kn(z c) K2 x cl.
B.4 Proof of Theorem 14
Proof. We start with 3 point identity. Note this is where the case p + 1 breaks down since the L'-p norm is not induced by an inner product if # 1.
(xe+1 - x²)² = (xt+1 - 22)2 + 2 - xx)( - x²) ) + (xz - x²)²
( g0. f(x))) 2m, C goall f(xz) x²) + (Ør x²)².
19

---

Published in Transactions on Machine Learning Research (03/2024)
We begin by bounding the first term:
(c8a.) f(x,))
- a)) + (f(xx) + - c)))2 S (2 -))² + 2 (xl) + K1 - -a)]
+ (z)(z)) + (i (
One observation here is that we would like everything to be in terms of f((x)2 to make canceling more convenient later. For this purpose, choose I2- - G ( Thus, we get
K ()))) (1-KIA))(((xx))) (80 (xx))) < ((( + 2x2/A.111 (K2|Arl + X. ((
Now, choose some Φ E (0, 2). We now bound the second term as follows (note we assume here 2 0 since unlike the past section this makes sense):
-2m C 80. (1=))(12 x²) s 2r, K2 cellar x11 -
2 ci( x²)
2n (z)lf x²1 -2 (Ix -x²) x²)
2el - xx)) - [ X,Ki) - x²)
--2mf (Ix) x² x²)(1 -ide - K2(Ael)
S @T)1 (1 K1dx (f
-2 - )) - K1Λ - (
We drop the absolute value signs due to the convexity assumption (note this works specifically for single dimension f). We need both terms of the RHS to be negative for proving convergence which puts condition on Ay
KG4, K2 Ap > 0.
This condition gives that 1 - KiAe > 0. Putting everything logether gives:
TTT (1 KIde - f (x,)²
(01+1 xx1 ( + -1-A
L
(2 12-o)mp(111 Kide (2) x²)² +(xx =2)
Now, we can figure out the learning rate since we want the first term on the RHS to be dominated by the second term.
ONT (1 KGA1 K2ldd))
ni (K2 +1 - xx1))²
L
1/1 (1- - K2l
Kíd, + K2
Finally, this leads to convergence rate as follows:
(w11- < [1 (2 @) Kide - K2/Ac11] (20 -x")²
(1 KiAt - K2/Adl 27
(2 Φ)Φ² L KIde +
(2) (01- x²)2
This is a linear rate of convergence since guarantees that this equation is a contraction as t - 30. The rate is at best good gradient descent. since K2/Ae| 0.
20

---

Published in Transactions on Machine Learning Research (03/2024)
B.5 Proof of Theorem 16
Proof. We follow the discussion deriving Theorem
14 We start with 3 point identity:
| - x= 112 = | - 22l22 + 2( - It - x²) + || x=112
m/ s0. f(x,))13 2 8 f(zx), x²) + 1 x2
For bounding the first term, this can be done coordinate wise.
180nf f(x011
C 8 20 20 fa (zt 1)
S
(2x))
For bounding the second term (note 1.1 is taken element-wise, nhe
is assumed):
-2m ( (0 80.9 (xx), (ot - x²)) - 2np K2 (x
- -2n (1
x²)
$ 2n, K2 A [[
2m (,kKi) (V x²)
2m. K2 [ 27 V())) --=x)
1
We see that 1- A > 0 is necessary for proving convergence since we need the latter term be negative to prove convergence. We bound the second term like in the single dimensional case as:
oMt (1 A,1i) \,
2m (())) x²)
- - - (1 1..
Gathering all terms yields:
| 2111 S m +1 - Kg
| [
ou (1 X, ff (2- (0))mp( AK11) 2²12
L
| - 11
For the 3rd term on the RHS to dominate the first two terms, the learning rate is:
(K2lae + 1- 2x + 2n,K2 Deel - TM (1 A,K1)
1
L
- mK( +1 1,,,,, S ①
(1 X,Ki) 2K2/Arl
L
6 K2\x) 2KdlAdl
M (1 Ki-K, 12
This in turn gives condition on d since the numerator needs to be strictly greater than 0 for this to make sense:
6( - K,
2K > O.
= We that this new condition is consistent with the past condition that (1 X,Ki) > 0. Finally, we write down the rate of linear convergence:
L
| x² 1|2 < (1 - (2 - @) - K1Aemm) - =0'1/
(2 - () - K1Ad) (1-1 K(de)
2KalAel M
I 1=
(1 Kide K22
21

---

Published in Transactions on Machine Learning Research (03/2024)
Similar to the proof of Theorem 14 in Appendix B.4 this is linear rate of convergence due and this rate is at best as good as gradient descent since K₂ Ax 2 0.
C Missing Proofs in Section 5 Smooth and Convex Optimization
C.1 Proof of Theorem 17
Proof. By similar reasoning as Corollary 15 we can reduce to the single dimensional case. We start by applying L-smoothness.
L
f(1-1)) f(x)) S (z) -1011---)))) xz) (+++1 - (11)
2
Lil²
(x)) 50.00 ((x) +
( ga.3 (xx)))
2
We bound the first term as:
(xx) s(tt) S (x,) + ( /
(
= =n1(1 AKi (x.))
We bound the second term
S (11 - AK1 + ((KK)
Putting everything together yields:
f(xx1)) S (-n(11 AKΙ (A/K2) + Ln ([1 AK1l + 1 (xr)
For this to converge, we need the RHS to be negative which means that AK1 1>|K2 > 0. Therefore, 1 AK1 |a|K2 > Now, we use point identity proceed. Note this is where the case p # 1 breaks down since the L norm is not induced by an inner product if p
(Ie+1 2²)² (54+1 x1)² + 2(x141 xe)( x²) + (zt - x=)²
= 80.3 )()))) 2n 2ni ga.0 fxt)) - x²) + (sx - x² x²
We now bound the middle term on the RHS. Note that the following only works due to f being convex and single dimensional.
-2 ((xe)((eer" <
-
(xF(((r - -x") AK (x) x²)
=-2n(1 -K1 (x)))) x²)
s 5-2n(1 - A (f(2)(f(xt) f(x'))
Putting everything together gives a bound on f(x)) ff(=').
f(x)) - f(x) S 27(1 XK, - -AI(K)) ((x, - x²)² - (5141 x²)))+++ 711 AK; + 2X
2(1 - XK, - -A((K2) (f:)):))
Combining this with the bound on f(x++1) - f(xx) yields:
1
((x+1)) - f(x))( 5
21/(1 AK₁ 12] (xx, xx0= -x141 - =)))
x²)²
(1 XKi + 12)
(1- AK₁ - 12(K2) + Lyj (1 --- +N[Kk))] (f.()))
+ 1
2(11 2(1-XK1 (((22)
22

---

Published in Transactions on Machine Learning Research (03/2024)
Now, we derive the learning rate 17 as follows that the f((x2) terms vanish.
Ln 2 (1 AK1 + 1NIK2)² - AK1 - (1(
(1 XK1 + 12(K2)²
2(1 AK1 (2/K2)
1 2(1 X 12)K2)
1
7 T. (1 A + 2)
- XK -
We require this learning rate to be positive (since this was assumed throughout the proof) so we get a condition X.
2 XK1 - (1112)
1
>0
- 1 + 22
AKI - - 1
1 XK1 1
2
1
1 1K1 + 17/K2
2
(1 (1-AK))( V2 - (1|
+
> 0
V2
v2 +
1 - XKG 2
V2 12-1
We can now write the earlier bound as:
L
[1++1)- - s(x')
((xx - x="/²- - (11+1 -1x+11111 -
)²)
L- 1-AK--IN l2ke [
-2
Applying telescope sum and bounding the LHS using convexity gives the desired result:
L(xo x²)²
(( {(x))
-A T- --IIK+AARE
-2) T
This rate is at best the same as standard gradient descent since |사|K₂ 2 O.
C.2 Proof of Theorem 18
Proof. We begin with L-smoothness.
L
f(a=11 f(x)) S (Vf(z,) - xx)) + = -1 =ell2
Line
= <V(()( 0 f(xi)) + 2
|| g0. f(z1)113
We bound the first term as:
(Vf(z), Cg f(xf)(()))) < -m XK1 (A
We bound the second term as:
& f(x,))13 < X.Ki -M/
Putting everything together yields:
Lud (|1
f(ar+1 f(x,) S (- X,K, (2
(f
For this to converge, we need the RHS to be negative which means that A.Ki > A K₂ > O. Now, we use point identity to proceed.
||0+11 - x²1 = || - 2r.13 2( - 21, - x²) + ||00 x:" 112
1 1 8 f(xx))113 2n gga.3 f(zt), It x²) + | x 113
23

---

Published in Transactions on Machine Learning Research (03/2024)
For bounding the second term (note | is taken element-wise, ni 0 is assumed):
-21 (o. ( (1t - x²))
2r, K2 />///////////(>(>)) |2r =²1) 21 (1- -.. (2)e, =x))
2m 22 A [ - -21(11 - (x11) (1)), x=)
K2 A T1
=1112 (1 (1- - -
Putting everything together gives bound on f(x+)) f(x)).
1
12
((x)) s 2m A,K1) (1/ore xx 11 -1|-21111 - + 1 X,
| - x x21
+ 1e(1 - AK + (2)
ff(x)))
2(1 - 2(1-1)
Combining this with the bound on f(0(+1) f(x)e) yields:
1
12 A₁
f(141)--fa $ 2m {x11)
(112g x= 112 11 1
|| x= 21
(1 - Ae + 17o
11
(1 -1-Acki (2)(K2)
2(1 AeKi)
Lij: (1 A.1 22
Solving for 7/+ such that the [[V terms vanish yields:
2( A, K2)
1/ [1 - Ae + AA K2)
Kn
The proof thus far assumes that 17: > 0 which creates constraint on '
2(1 AK11 (20
1
>0
(1 - A,Ki + 22 T- A.Ki
Ax1 (1 - AeK1) 1
(1 A, + K2)
2
(1 \x1))² 4/A, K2(1 ArK1) 1 00
(1 Ar1 21Ar/K2)2 > 5/2
- AK1 > (V5+ (15+2)11 \e|Ke
Now, suppose 1 - A,K = K2 (&+ > v5 + 2). Then the following useful equation holds:
2(31
1)
1
11 = I (s, +
s, S Kg
1
87 48, 1
Th Ls, \ee| Kg
(st + 1)2
1
5
4s
1
- settlAr
L
(8x 1)3
Returning to the bound on f(z(41) - fx*), with the chosen ne, we have:
1A K2L
1
f(1+11) - f(x)) 2m XxK1)
|1:2 -x'1
| x²1
1 X,K₁
2mp AeKi)
24

---

Published in Transactions on Machine Learning Research (03/2024)
For this sum to telescope, we need the following condition to hold:
1
|
S
21++1 \
X K
2n/e (1 - Xe Ki)
| K2L
+
2/++1 114 Met1
8t- Ac41 1k2
2n (7((se/))
(sc+1 + 1)²
(1 + 1)²
+
s/41 - 18441 1
S141
8
4s;- -
For St > v5+2, + 2, both the LHS and RHS are decreasing functions that going from oo + 1 as 5t + 00. Thus if St+1 is chosen large enough, it will satisfy the telescoping condition. To solve for an exact cutoff would require solving cubic equation so for practical use it is better to use mumerical solver. Now, assuming this condition holds, applying telescope sum to the f(1+11) - f(x") inequality yields the desired result:
1o K2L
|100 - x= 11
+
217011 )1)
1
Ag
T
L
(50
+ 1)2
2
200
x
112
2
2
480
80
T
D Missing Proofs in Section
6 Smooth and Non-Convex Optimization
D.1 Proof of Theorem 20
Proof. Throughout the proof we will use the notation [a]] to denote a vector of l elements with ith element 0g- We note that all the results for single variable f hold since I satislies the single variable (T,le)Hölder smooth definition in each component. We start with the HLölerHölder smooth property:
L
f(1+11) - f(x)) s (Vf(z), 2411 xz) +
| Zz lptt1
1 ++p
=-<V C 80 (xx)) + Lnp+1
1tp 11 ( fx)) ( ||
<-n ([
05
(I
Ox(() (xr) - 10P
05
(
+1 ([ 1 (x1)
0
K |K( - d01)
Lip
+ 1 1+ p
I1 80 f (xzz 1|
of
1+1/P
Lnp
= =-n(>'> - KA) Σ
Ox(0) (x.)
c ( ||+
1 p
Lippt1
-- - /A)IV/(<>>)))
15000 80 fxxx |+
1 + p
S - KX) KX)
L
0f
(x:)) (8) 10 1- + K|a (0) (00)
p+1
+ 1 1+p
0r(()
p+1
< <n KX>I fZ 1+1/2
p1
as
1/7
p+l
+ 1+p
(AI + KA)P+1
(Iz)
Ozl()
1+1
Lip+11 (X2-P + KX)++I10
=-m(A - V
[V)))) 1+1//
1+p p
25

---

Published in Transactions on Machine Learning Research (03/2024)
Lyp+11
= -
+
1 (A KA)=+
141//
1+1//
-
For this converge, we need & which gives a condition on 1) as follows:
\ K\
I+ 1/ KA) >
(1+ p) (A
1
T(AI-P + +X)]+
(1 + ( L(X-+++
This in turn gives a condition on À order to make the interior of the root positive:
(A--P- KA)
XP
K
K
We derive the convergence bound as follows:
1 T
min OStST
/f(
<
[f(2))]
T+1 1=0
T f(x) f((+11
(T (T'1))
1=0
(Fo) - f((T+1)
(T+ + 1)bb
f(00) -f"
(T 1)4)
E Missing Proofs in Section 7 Finding the Advantage of Fractional Gradient Descent
E.1 Proof of Theorem 21
Proof. We first note some useful equations:
Vf(x) Ar + b
2. 0g 1 (for 1 dimensional x)
Cga. b
4. Cga.3 qx² = a(B - (x - c) + aax (for 1 dimensional x)
Cg 1
Equation simple differentiation. Equation follows since the 2nd derivative of x is Equation 3 follows by lincarity of the fractional gradient descent operator and equation 2. Equation follows directly from Lemma A.1 of Shin al. (021). Equation follows since derivatives of constant. function are 0.
26

---

Published in Transactions on Machine Learning Research (03/2024)
We now leverage these equations to apply the fractional gradient descent operator to f. These equations tell us that the only terms where the fractional gradient descent operator does not act like normal gradient are the squares corresponding to diagonal elements of A, azi- These elements look precisely like equation 4 and can be handled as follows:
C 80. Osi e(i) 2
(2())= = aa.(B - 7)((00)))))))))))))))) - -c()) + an:
a -7) ( (B- (V((z))(()) + a
-0ū (A)
Oii
x (10 2
(x)
2
Putting everything together with linearity we calculate the full fractional gradient descent operator as follows:
A
A
C0 f(x)
diag( 411
(00g((1011-0
OAk
L
1(A b)+ Vf(x))
A
A
diag(( ([ag((101111
-111
OAk
L
[(x + + ()) (Ar++))
(DA)) Db
A'r b
Thus we have the desired result for point 1 of the theorem. For point 2, we start by noting that C8 f(x*) when DAx* Db. Since A and D are both invertible, we see that x" --1.. At this point, we also have Vf(=*)= = This tells us that if fractional gradient descent converges, converges to the right point.
The update rule for fractional gradient descent be written as r++1 2t m((AA' x B). For proving convergence, we begin with the 3 point equality:
|+++1 - x= 11 || 21112 + 2 24, D2 x²) + ||, x x2
1/21AA' xr + 611 (n) b1, xe - x²) | - x²
1/21AA xr + b1 (A x, 1/ A'x" b/, 3y - x²) + ||| - x=1
-7711A xx + 1 2n(xx == A (ax x²) + ||ا; - -x²13
11 1x + 1' m/ |0+,
x 112 170, x²) /T (A 'x; + 81 A' - b') | x xx112
1721|A' 12 + 11 nH [z, =²1 11 (Az; + - Ar - -B) A 1-1 (A'zz + b') + || =0 11
1,211 || 12 + 61 np
|0, x" 11 (Az, + b') A 1-1 (A' ~ + b') + 1 x²11
117 'x + -'11 nhl |z, x 11 L' |A + b' + || x
-nn² D) |A'r + 6'112 + (1 npp ) |2 x= 211
Setting = z similarly to in standard gradient descent, we arrive at the desired convergence rate:
11 || x x1
| x0112 <
L'
27


Reviews:
[{"review_id": "uEbvfbTOtu", "reviewer": "Reviewer_6T9r", "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": "**Strength**\n\nFractional gradient descent is not well studied in the literature. The paper gives several convergence rates of fractional gradient descent. For smooth and convex problems, the paper derives convergence rates of order $O(1/T)$ after $T$ iterations. For smooth and strongly convex problems, the paper derives linear convergence. \n\nThe paper considers general strong convexity and general smoothness with $p\\geq1$.\n\n\n**Weakness**\n\n- While the paper derives several convergence rates, these theoretical results of fractional gradient descent do not show the advantage of fractional gradient descent over gradient descent. Indeed, these convergence rates match those of the gradient descent.\n\n- In Section 4 and Section 5, the paper considers the one-dimensional case. While Section 5.1 considers the high-dimensional case, it assumes the function to take a specific separable structure, i.e., f(x)=\\sum_if_i(x^{(i)}), where $f_i$ is a one-dimensional function. This limits the application of theoretical analysis.\n\n- The theoretical analysis focuses on $\\alpha\\in(0,1)$, which corresponds to a low-order derivative. This seems to be a bit restrictive. It would be interesting to extend the analysis to a larger $\\alpha>1$, and show the advantage of the algorithm over gradient descent.\n\n- The step size selection seems to be very complicated. For example, Theorem 14 requires very complicated assumptions on c_t and \\eta_t. These assumptions make the implementation of the algorithm difficult. \n\n- The theoretical analysis is not presented in a clear way. For example, in the proof of Theorem 10, I cannot follow clearly the way to bound $-\\eta_tf'(x_t)^CD^\\alpha_{c_t}f(x_t)$. It would be helpful if the authors can explain it more clearly.\n\n- The experimental results seem to be not convincing. For example, I cannot see clearly the advantage of fractional gradient descent over gradient descent in Figure 4. The objective functions considered in the paper seem to be a bit simple.", "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 paper considers optimization by fractional gradient descent, where the Caputo derivative is used to construct the search direction. The paper first shows the quantitative connection between the first derivative and fractional derivative, and uses it to derive convergence rates of the fractional gradient descent for several problems, including smooth & convex problems, smooth & strongly convex problems and smooth and nonconvex problems. The paper also gives some experimental results to illustrate the behavior of fractional gradient descent versus gradient descent.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see the discussions on the extensions to a larger $\\alpha>1$, and show the advantage of the algorithm over gradient descent.\n\nHow to compute the step size efficiently in practical implementations?\n\nThe theoretical deductions should be explained more clearly.", "broader_impact_concerns": "I have no concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZjEeDUmISo", "reviewer": "Reviewer_x1vw", "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 main strength of this paper is the novelty of the fractional gradient scheme.\nAlthough the convergence theorems presented have substantial drawbacks, this\nmay be mitigated by the fact that they are early contributions to a newly\ndeveloping sub-area in iterative optimization.\nTo summarize, the strengths and weaknesses are the following:\n\n**Strengths**:\n\n- The authors provide a novel convergence analysis analysis for fractional\n    gradient descent on general convex and non-convex functions, going beyond\n    previous work which focused on quadratic optimization.\n\n- The analysis for fractional gradient descent in the non-convex setting\n    makes novel use Hölder continuity and uses a simplified update.\n\n- Experiments show fractional gradient descent can be significantly faster\n    than gradient descent on toy problems.\n\n**Weaknesses**:\n\n- The convergence rates follow by bounding the difference between the fractional\n    and first-order derivatives. This means that (a) the analysis doesn't \n    give any intuition into fractional gradient descent and (b) the rates\n    proved this way cannot improve upon the guarantees for gradient descent.\n\n- The theoretical guarantees for scalar minimization (and separable minimization\n    to a lesser degree) are not particularly interesting, given that bisection\n    obtains a linear rate in this setting.\n\n- Some algorithmic parameters, such as $\\beta$, are not explained despite\n    playing an integral role in the algorithm and analysis.\n\n- The experiments are presented only for synthetic data and it is not clear why\n    fractional gradient outperforms gradient descent when it does. \n\n\n### Additional Details\n\nThe area of fractional gradient methods is new from an optimization\nperspective, but the motivation for studying and using these methods \n(beyond novelty) is not well developed. \nThe authors suggest fractional gradient descent should be investigated by\npresenting an experiment (Figure 1) that demonstrates it can sometimes converge\nfaster than gradient descent.\nHowever, they also later show that fractional gradient can vastly \nunder-perform gradient descent despite using a larger step-size (Figure 4).\nThus, the \"better methods\" argument is not quite sufficient for motivating \nfractional gradient descent and I am left unsure of the motivation for \nthe paper.\n\nA similar issue applies to the convergence results presented here.\nThe convergence rates for fractional gradient descent are uniformly worse\nthan those for gradient descent; while I applaud the authors for being \nstraightforward about this weakness, I am left with two worries:\n(i) fractional gradient descent is a slow optimization method\nor (ii) the wrong assumptions have been used in the theoretical analysis. \nThis second issue is particularly noticeable, as much of the analysis feels,\nto use an analogy, \"like a square peg being inserted into a round hole\".\nI think the authors also feel this tension, as they comment that one way to\nimprove their results is to \"[use] convexity and smoothness definitions that\nonly involve fractional derivatives\".\nI think addressing one or both of these issues would greatly improve the paper.\n\nFinally, I think the paper suffers from a lack of explanation and clarity.\nFor example, no intuition is given for the main fractional gradient update\non page 5. In particular, the parameter $\\beta$ is not explained nor is the\nnecessity for a higher-order fractional derivative motivated.\nSimilarly, none of the convergence rates are interpreted or compared against\nrates for standard methods like gradient descent.\nProviding context of this kind is important for readability of the paper.\n\n### Minor Issues:\n\nFigure 1:\n- I suggest using LaTeX for the label of the y-axis. This is supported natively\n    by matplotlib.\n- The font-size of the figure labels, ticks, etc. should be increased. In general,\n    font-sizes for figures should be as at least as large as the font-size used\n    in the main text.\n- Rather than plot the logarithm of the objective along the y-axis, I suggest\n    plotting the objective in log-scale. This will be more readable.\n\nPage 2:\n- Since the list of contribution is ordered, you might want to use \"enumerate\"\n    rather than \"itemize\". \n\nDefinitions 1-3: It's a somewhat confusing to use the same notation for \n    the left derivative, the right derivative, the unified Caputo derivative. \n\nAppendix A.2: This is properly spelt L'Hopital's rule.\n\nDefinitions 7, 8: Nesterov a uses slightly different notion of Hölder continuity\n    and uniform convexity that where the power of the norm is raised to $p$,\n    but the norm itself is fixed. This allows Hölder continuity to interpolate\n    between Lipschitz continuity of $f$ and of $\\nabla f$ _in the same norm_.\n    What is the importance of changing the norm in your definition?\n\nSection 4.1:\n\n- What is the purpose of developing Hölder continuity in full generality\n    if only $p = 1$ is used? Then smoothness and strong convexity would be \n    sufficient, right?\n\n- Can you provide more insight into the definition of the fractional gradient\n    method? What is $\\beta$ and why do we include the $\\alpha+1$ order\n    fractional derivative in the descent step? \n\n- Does the inclusion of the $\\alpha + 1$ fractional derivative imply that \n    the fractional gradient method is somewhere between a first and second \n    order method?\n\n- It appears from Theorems 12 and 13 that $\\beta$ can be negative or positive\n    or even zero. Since $\\beta$ controls the role of the higher-order fractional\n    gradient in the update, I would have thought $\\beta > 0$ was strictly\n    necessary.\n    If this isn't true, how should $\\beta$ be chosen?\n    Looking at Theorem 16, is there a clear value of $\\beta$ minimizes the\n    oracle complexity?\n\nTheorem 20:\n- This result does not show convergence to a local optimum; it only shows \n    convergence to a critical point where the gradient is $0$. This could\n    be a saddle-point or even a local maximum.\n\n\nFigure 3: \n- I don't know what \"Guided by Gradient\" means.\n\n- You should also plot the performance of the theoretical step-size for \n    fractional gradient descent in the left-hand-side plot.\n\n\nSection 8:\n- It's not clear if the \"existing data\" from the assumptions is insufficient\n    or if the theorems are simply weak. You need lower bounds to determine this\n    fact.\n\n- Defining smoothness and convexity in terms of fractional derivatives\n    seems like the mos promising direction. This is the natural way to derive\n    convergence rates in this setting.", "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 studies the convergence of fractional gradient descent,\na modification of gradient descent that uses fractional derivatives\ninstead of the first-order \"integer\" gradient.\nThe analysis focuses on bounding the difference between fractional derivatives\nand the first-order derivative for functions which are Hölder smooth and\nuniformly convex (generalizations of Lipschitz-smooth and strongly convex).\nConvergence of gradient descent is then used to deduce convergence of\nthe fractional gradient method, although at a slower rate due to these errors.\nThis approach allows the authors to prove convergence for uniformly convex,\nconvex, and non-convex functions.\nToy experiments on low-dimensional quadratics are presented to showcase \nwhen fractional gradient descent outperforms gradient descent and vice-versa.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "At a minimum, missing explanations/intuitions, such as for  $\\beta$, should be\nadded to the text. \nI don't want to push for additional theorems, such as lower bounds or\nalternative analyses based on smoothness/convexity in terms of fractional\ngradients, since these are out of scope for a short submission. \nHowever, I do think some discussion of these issues could be raised in the\npaper, particularly regarding the necessity of lower bounds for determining if\nthe theorems presented are tight.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "T3Rnq4b8Pv", "reviewer": "Reviewer_4UxH", "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\nThe paper studies mathematically interesting question of understanding convergence of fractional gradient methods, and extends the convergence guarantees to standard optimization settings, e.g., convex, non-convex. \n\n**Weaknesses (major)**:\n1. The proposed algorithm, e.g., in Theorem 10 is only conceptual. It is unclear how to select the sequence c_t. Moreover, I find it weird that the proposed step-size sequence can become negative or infinity (when $c_t = x_t$). \n\n**Weaknesses (minor)**:\n1. On page 3, the objects like $g$ and $\\psi$ suddenly appear and are not properly defined. Moreover, it would make more sense to defer this inequality to the proof of Corollary 5. \n2. It should be properly discussed how Caputo derivative can be computed in practice (e.g., using Gauss-Jacobi quadrature) and if it coincides  with the integer order derivatives, e.g., for $\\alpha = 0, 1, 2$. This is not obvious from Definition 3. \n3. Definition 6 and 7 have been studied before in the context of usual gradient descent and have well-established names in the literature. Def. 6 is called Hölder smoothness, see e.g., Nesterov (2015). \n4. In Section 3, the approximation result (of Caputo derivative with the usual first order derivative) is presented for Hölder smooth and uniformly convex functions, but starting from the next section this generality is dropped and standard smoothness and strong convexity is considered. Could the authors comment what are the challenges for handling a more general setting? \n5. The paper would benefit from a separate “methods” section devoted to describing the proposed algorithms with specific choice of the sequences c_t and the stepsizes. \n6. It is unclear why the proposed algorithms for convex, strongly convex and non-convex settings differ so much. \n7. What is the difference between AT-CFGD in Shin et al (2021)? What is the intuition for why Fractional Descent is faster on a quadratic. Can it be simply attributed to the fact that this algorithm has more parameters to tune? Intuitively when decreasing $\\alpha$, the rate should become worse. \n\n\nNesterov, Y. Universal gradient methods for convex optimization problems. Math. Program. 152, 381–404 (2015).\n\n\n**Questions**:\n\n1. In Figure 1, the optimal step-size refers to the optimal according to theory or the one found by fine-tuning?\n\n2. In Section 5.1, some results are generalized from 1 dimensional to “high dimensional” case, i.e., k > 1. However, this is done in very limiting separable case. Could the authors elaborate more on the challenges for a more general setting? \n\nTypo: Page 1 “integral order derivatives” -> “integer order derivatives”", "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 extends the study of fractional derivatives for optimization. Some approximaition results are derived connecting first order derivatives with the fractional Caputo derivatives. The results are then applied to derive some guarantees for convex, strongly convex and non-convex settings. Preliminary empirical results are presented comparing convergence and proposed learning rates to those of standard GD.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section above.", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As a minor weakness, reviewers also pointed out that sometimes the paper is a bit hard to follow and that the experiments were performed on toy problems. Therefore, I suggest accepting this work with a revision and I hope the author goes through the paper another time to try to improve readability and fix any writing issues.
Decision: Accept (poster)