A new accelerated gradient method inspired by continuous-time perspective
Authors: Yasong Feng
Weiguo Gao
Venue:  (2021)
Keywords: accelerated gradient method
matrix completion
first-order methods
differential equation

Abstract: Nesterov's accelerated method are widely used in problems with machine learning background including deep learning. To give more insight about the acceleration phenomenon, an ordinary differential equation was obtained from Nesterov's accelerated method by taking step sizes approaching zero, and the relationship between Nesterov's method and the differential equation is still of research interest. In this work, we give the precise order of the iterations of Nesterov's accelerated method converging to the solution of derived differential equation as step sizes go to zero. We then present a new accelerated method with higher order. The new method is more stable than ordinary method for large step size and converges faster. We further apply the new method to matrix completion problem and show its better performance through numerical experiments.

Under review conference paper at ICLR 2021
A New Accelerated Gradient Method Inspired by Continuous- Time Perspective
Anonymous authors Paper under double-blind review
Abstract
Nesterov's accelerated method are widely used in problems with machine learning background including deep learning. To give more insight about the acceleration phenomenon, an ordinary differential equation was obtained from Nesterov's 's accel- erated method by taking step sizes approaching zero, and the relationship between Nesterov's 's method and the differential equation is still of research interest. In this work, we give the precise order of the iterations of Nesterov's accelerated method converging to the solution of derived differential equation We then present a new accelerated method with higher order. The new method is more stable than ordinary method for large step size and converges faster. We further apply the new method to matrix completion problem and show its better performance through numerical experiments.
step sizes go to zero,
1 Introduction
Optimization is a core component of statistic and machine learning problems. Recently, gradient- basod algorithms are widely used in such optimization problems duc to simplicity and efficiency for large-scale situations. For solving convex optimization problem
min F(z). #CRd
where F(x) is convex and sufficiently smooth, a classical first-order method is gradient descent. We assume that ((x) = F*)) satisfies I--Lipsciiz condition, that is, there exists constant such that.
-())) S T.|x - vll, Va, y.
Under these conditions, gradient descent achieves a convergence rate of O(n i..., [[x(),, F(x*)]l decreases to zero at a rate of O(n where In denotes the nth iteration and x denotes the minimum point of F(x) in Rd.
Nesterov's accelerated method (Nesterov, 1983) is a more efficient first-order algorithm than gra- dient descent, of which we will use the following form: starting with Tg F1,
yn = In + n 3 (In - In-1),
n
(1.1)
En+1 = yn - sf(n) for 2 1. It is shown that under abovementioned conditions, Nesterov's accelerated method converges at rate of O).-2).
Accelerated gethod mothod has been successful in training deep and recurrent neural networks (Sutskever et al. 2013) and is widcly used in problems with machine learning background to avoid

---

Under review conference paper at ICLR 2021
sophisticated second-order methods (Cotter al, 2011: Hu et al., 2009: Ji & Ye, 2009). To provide more thcorical understanding, an important research topic of Nesterov's ss accelcrated method is to find an explanation of the anceleeeerr,oon On this topic, Nesterov's 's method was studied via a continuous-time perspective (Su et al 2014). They considered a curve x((), introduced the ansatz In & s(nv²) and substituted it to (1.1) Letting 8 + O, they obtained the following differential
equation.
3
3 - # + [(x) O. t
(1.2)
The differential equation was used as tool for analyzing and generalizing Nesterov's schome. Furthermore, this idea has been studied from different directions. A class of accelerated methods have been generated in continuous-time (Wibisono et al., 2016) ODE (1,2 1 can also be discretized
directly using Runge-Kutta method to achieve acceleration (Zhang et al., 2018).
Although many results have been achieved, the process of obtaining the differential equation (1.2) has not been rigorous, and the method is still time-consuming for large-scale problems. In this work, give the procise order of the iterations of Nesterov's accelerated method converging to solution of the differential equation (1.2) with initial conditions
xx0)= ro, x00) 0
(1.3)
step size goes to zero. Inspired from this perspect we present new accelerated method to make this convergence faster. As we expected, iterations of the new method are closer to the
solution zxt) of differential equation [1.2) than original Nesterov's method. Moreover, we find the
new method is more stable than original Nesterov's method when step size is large.
Based on abovementioned observations, we try take advantage of the new method in more practical problems. We apply the new method to matrix completion problem. We combine the new method with proximal operator (Parikh & Boydl, 2014) into a new algorithm. which we call modified FISTA. We find that the new method perlorms beiler than, FISTA (Beck & Teboulle, 2009) and acclerated proximal gradient method (Parikh & Boydl 2014) because it can work with larger step sizes.
This paper is organized as follows. In section 2, we prove that, iterations of Nesterov's accelerated method converge to solution of the differential equation (L.2). In section 3, we present new method to make the convergence faster and show its better stablity through two simple examples. In section 4, apply the new method to matrix completion problem.
2
A strict analysis of the relation between Nesterov's method and its continuous-time limit
We refer to x=f) the solution of differential equation with initial conditions 1.3) Existance and uniqueness of such solutions have been proved (Su et al,, 2014). In this section, We give the order of the iterations of Nesterov's accelerated method converging to xr() as step sizes go zero.
For convenience, we substitute the first equation in Nesterov's 's method (1.1) to the second one to get
n - 3 (In In-1) - s. (rnn n n (In xn-1)
In+1 = Fn
We write s = 1 and rewrite the above recurrence relation as
To+1 = In + n2 3 (In Iz-1) 112
In + n n (xn - 2m-1))
(2.1)
2

---

Under review conference paper at ICLR 2021
Inspired by the ansatz on ss x5n/5) (Su et al, 2014), we consider the convergence between 2n and r(nh). More preciscly, we show that for fixed time t, In converges to xxt) as h goes to zero, where n h'
2.1 Truncation error
Firstly, consider the following 'truncation error':
2f 3h
t =(1) + --3h 3h x(11 hi)+
Mx(()); -x]] + h)
(2.2)
f2 x(()) + t 1- (x(t) x(t ((hhhh))
(2.2) obtained from (2.1) by replacing In+1, In, In with (tt++-),, a(t), x(t-h) and substituting the relation n== f.- Our first result is the order of truncation error ht]:
Theorem Assume f satisfies I-Lipschitz condition, and solution s=t) of the derived differential
equation 1.2 has a continuous third derivative. For fixed time i, the truncation error (2.2) satisfies
=
Theorem shows the size of error caused by single iteration when the starting point is just <((). Then we have to add up these errors to prove the convergence proporly we need.
2.2 Convergence theorem
We now come to the convergence theorem. In this theorem, we give the precise order of the iterations of Nesterov's method converging to solution of the derived differential equation.
Theorem 2. Under conditions in Theorem i for fixed time Fefh converges to sxt) h goes to
zero rate of O(hln 1t) if rо z00) and 21 xh)..
Theorem coincides with derivation of ODE 1.2
(Su al. 2014).
3
New accelerated method
3.1 Derivation of the new method and analysis truncation error
Inspired from the continuous-time perspective and our proof of the convergence from iterations of Nesterov's method to its coniiuous-ting limit, we present new method to make this convergence faster. Precisely, the new method has a higher truncation order.
We need more step in our scheme than in Nesterov's ' method to achieve higher truncation order the following analysis, so we consider a recurrence relation with form
as
Yi n²
Int2-1 -sf In
11 3
(In xn- Bn-1)).
(3.1)
n
n
where fai), {B,} and (%) to be determined.
3

---

Under review conference paper at ICLR 2021
Now we expand xxt h) to first order. Calculation shows that
I x(1) + t 3h
1 (x(1) - x111 11))
- (1)(001))) - ( +1 x (1)
3h
3h
3
+
x x0 (1) + 0(12).
12
t
Substitute this expansion truncation error
ai + Bch + 7hh
[x((t;:]]
x(t + (2 (2-1)h)
f (t)) + t 3h (x(t) - z(t hi)
and choose parameters appropriately to eliminate low-order lerms, we get the following recurrence
relation
10n² + 9n +
6
4n²
+3
2n -
Tn+1
2n
In-1 +
4n + In-2
4n² + 8n
2n²
4n
(3.2)
12
3
n
2n + 8f
T
n
n
Here we rewrite this scheme as Algorithm
Algorithm The new method (32) step size
Input:
Initial value: X₂ =x= Xu.
(k - 1)th iteration (k: 2 2). Compute
Y 10h2 + 9k +
6
4k + 3
2k -1 1
X; 2k + 4k
X k-1
X
4k2 + 8k
4k 8
2k 3
k - 3
Z
Xx=
k-
ks
X = X
Yk
2k + 4 (Zx)
For truncation order of this new method, we have the following theorem. The abovementioned procedure presented in Appendix A.4 detailedly, as proof of Theorem
Theorem 3. If f has contimuus second order derivative, the first and second derivative are bounded, and xtt has continuous fourth derivative, then for fixed f, truncation error (3.2) satisfies
L[x(t.)::h] h| O(K*).
The convergence of the new method and x(1) can be proved similar to Theorem
3.2 Advantage of the new method
Since the new method has a truncation error of higher order than original Neaterov's method, the iterations of the new method converge to the diffcrential equation (1.2 when those of original
4

---

Under review conference paper at ICLR 2021
Nesterov's method diverge. In another word, the new method more stable for large step size. We present two numerical results in Figure | to confirm it.
Quadratic. F(x)= =x _TAAx Ax strongly convex function, in which x E I and A is x matrix.
Linear regression. F(x) = E (vi wu/x)² where n is the number of samples and (w0,, ys) is the
ith sample.
10
135
12
1000 2000
300
180
500
1030 700 1300 180
1806
30'
100
159
200
156
300
300
30
(a) min F(a) x Ax TAx
(b) min F(x)
Σ
w x²
Figure 1: Iterations of original Nesterov's method (Nesterov) and the new method (New method) for quodratic and linear regression objective function. Y-axis represents the gap (F(,,) F(x)))
In Figure (a) step size 0.03705; in Figure 1(b). step size 0.00565.
In these examples, iterations of the new method converge to the minimum point, while those of original Nesterov's method diverge, which confirms that the new method is more stable for large step size.
3.3 Absolute stability of Nesterov's method and the new method
In this subsection, we explain the better stability of the new method with absolute stability theory. Firstly, recall the scheme of our new method
10n² + 9n +
4n² +3
2n 1
In+1
4n + 8n
En
2n1 + 4n
Tn-
+
4n + 8 Tn-2
n
2n 3 3
n1 3
sf
Fn
In
2n + 4
We use linear approximation f Zn n - (zn zn-1)
VF
In +
11
3 (In
In
~ F2F.
In +
n n-3
(En xn-12)
and the characteristic equation of this finite scheme is approximately
10n² + 9n 6
22F 2n 3n
4n +
11a 3n
2n
3
4n² + 8n S.
X²+
8 22
= 0.
2n 4n
2n + 4n
2n + 4n
4n +
For large n, we can ignore the high order terms and the characteristic equation becomes
3
V2F.
xa +
_ ..--ve (.2r) A 0.
2
5

---

Under review conference paper at ICLR 2021
According the absolute stability theory, the numerical stability of Nesterov's scheme with respect to accumulated roundoff error is equivalent to this: all the roots of the characteristic equation lic the unit circle (Leader, 2004). Noticing that the left hand of the equation can be factorized
(A- (A² s2 (2-s.V2P)++1)
the largest modulu of the roots is when 0 V < 4, and the absolutely stable region of the new method s V E 4].
When F lies in the absoletely stable region, the related theory guarantees that the error caused by every itcration will not be magnified as the iteration number increases. To make the analysis more precise, should consider the difference of the scheme between iterations caused by different. n. We define the transfer matrix
10n +9m+6
V
2n 2-n-3n
dn 43
V
n² 3n 2n2+44
2n
4n2
2-2
2n
4
Pa =
1
0
and On PaPn-1..... Error analysis shows that if the largest modulu of eigenvalues of Qn goes to Lo,ero, then error caused by iterations will be eliminated as the iteration number increases. Figure 2 presents the largest module of eigenvalues of Qn for different values of F2F. From the experiment we can see that the above condition is satisfied.
10.
Figure 2: The largest modulu of eigenvalues of Qn. where s 2 is chosen to be 1, 2 and 3.
We then apply the same method to Nesterov's method discussed in (Su et al. 2014) and conclude that. the absolutely stable region of Nesterov's 's method is [o. $)-
According to the above analysis, the absolutely stable region of the new method is four times as large as Nesterov's method, so the new method is more stable, and we can choose larger step sizes to achieve faster convergence.
4 Application to matrix completion problem: modified FISTA
Our theory and numerical results show that the new method is more stable than original Nestrov's method. So choose larger step size for new method and convergence to the optimal solution
6

---

Under review conference paper at ICLR 2021
can be faster, compared with original Nesterov's method. In this section we apply the new method to matrix completion problem. We present a new algorithm which can be viewed as a modification of the well-konwn fast itcrative
algorithm (FISTA) (Beck & Toboulle, 2009).
The performance of modified FISTA can also confirm the advantage of the new method.
For mairix completion problem there exists a 'true' low rank matrix M. We are given some entries of M and asked to fill missing entries There have been various algorithms to solve such problem (Candès & Recht, 2009; Keshavan et al, 2010). Besides, it proposed that matrix completion can be transformed to the following unconstrained optimization problem (Mazunder et al. 2010)
min F(X) Xoha - Mabs 11 + X|
(4.1)
Notice that F(X) is composed of smooth term and a non-smooth term, so gradient -based algo- rithms cannot. be used directly. Proximal gradient algorithms (Parikh & Boydl 2014) are widely used in such composite optimization problems, and fast iterative shrinkage-trreshollding algorithm (FISTA) is successful algorithm. Moreover, FISTA has been extended to matrix completion case (Ji Ye, 2009). For convenience, we set G(X) = X - Moball? (X) = A||X and (( VG(X).
The idea of FISTA huilds on Nesterov's method, We also apply acclerated proximal gradient method (Parikh & Boyd, 2014) for our numerical experiment, which is composed of Nesterov's method and proximal gradient descent. These two algorithms are presented in Appendix A.5. We find the performances of them are similar in our experiments.
Our contribution is the third method (Algorithm 2) the new method 3.2 combined with proximal operator, which we call modified FISTA.
Algorithm 2 Modified FISTA
Input: step size
Initial value: X₂ = X1 = Xu E M100
(k 1)th iteration (k: 26>31 2). Compute
10k + 9K 6
4k2 3
2k- Xk-2-
Y=
X
X
X
+
412 + 8k
21 + 4k
4k +
2k
3
X
Xi-11
k
k
Xx+1 arg min
2k +
X
Y/2
2k + 4 g
ks
Zz.)
+
x
2
ks
Notice that the minimizing problems in of three algorithms can be solved directly by singular value decomposition (Cai & Candès, 2010). We take experiments on a simulated data set. We use fixed step sizes in the above three algorithms, and the performances are presented in Figure & We find empirically that for all methods, convergence is faster when step size is larger, so we choose the largest step sizes for all methods to compare their fastest convergence speed. Through experiments, we find the largest step size that makes modified FISTA convergent is 4.1 (accurate to one decimal place), while those for the first two algorithms are both 1.3. We also compare performances of the three methods with step sizes reduced from the largest in equal proportion. We find that when step sizes are chosen to be the largest or reduced from the largest in equal proportion (80,, 50%, 10%), convergence of modified FISTA is faster than the other two methods.
7

---

Under review conference paper at ICLR 2021
IDTA
(a) origilal
(b) reduced to 80%
167
367
100
150
100
50
100
150
130
(c) reduced to 50%
(d) reduced to 10%
Figure 3: Iterations of FISTA, accelerated proximal gradient descent (Nesterov) and modified FISTA (Modified FISTA) for matrix completion objective function. Y-axis represents the gap [T F(x*)J. In Figure 3(a) step size is 1.3 for FISTA and accelerated proximal gradient descent, and 4.1 for modified FISTA. In the other three figures, step sizes are reduced from 1.3 and 4.1 in the proportion marked below the figures.
We also combine the three methods with backtracking (Beck & Teboulle 2009) to choose step sizes automatically. We present modified FISTA with backtracking as Algorithm and the other two algorithms are similar.
Performances of the three algorithms with backtracking abovementioned data set are presented Figure 4 Convergence of modified FISTA is faster than the other two methods. Morcover, we find that the final step size of modified FISTA is larger.
5 Discussion
In this paper we prove that itcrations of Nestcrov's accelerated method converge to solution of the derived differential equation as stop sizes go zero. We present a new accelcrated method to make this convergence faster. We use numerical results to show that the method is more stable, especially for large step sizes, and explan it using the order truncation error. We then apply the new method to matrix completion problem and present modified FISTA. Numerical experiments show that modified FISTA performs better than existing algorithms based Nesterov's acceleration because it work with larger step sizes. We will also combine our new method with stochastic gradient-based algorithms and apply the new method to deep networks in the future.
algorithm which call
8

---

Under review conference paper at ICLR 2021
Algorithm Modified FISTA with backtracking
Input:
some B <
Initial value. X2 X1 Xo E Mi0; step size 82-
(k - 1)th iteration
(A: 2 2).
104 + 9k 6
4k2 +
2k 1
Y
X
-k-1 +
Xx-2:
4h2
+ 8k
2k + 4k
4k + 8
2k 3
k - X
Z
X
k
Find the smallest positive integer i+11 such that with 8 = B8i41 8k
1 2k +
F(X) < F(Yx)) + X Yk. 92.9(Zz)))
| 1x
kss
where
1
2k + 4
ki
g( (zx) )(² +
X arg min x
X
Yv
2
ks
2k
Set sk+1 gi++1 sk and compute
X = X.
Modifed FISTA
200
200
400
502
550
500
Figure 4: Itcrations of FISTA, accelerated proximal gradient descent (Nesterov) and modified FISTA (Modified FISTA) for matrix completion objective function. Y-axis represents the gap [x())) - F. Step sizes are chosen by backtracking.
Our work shows that for an accelerated gradient method, the rate at which it converges to the derived differential equation possibly related its property as an optimization algorithm. We think this work suggests that more consideration should be given to the corresponding differential equations when studying optimization algorithms.
9

---

Under review conference paper at ICLR 2021
References
Amir Beck and Marc Teboulle. A fast iterative shrinkage-thrrsholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183 202, 2009.
Jianfeng Cai and Emmanuel J. Candès. A singular value thresholding algorithm for matrix com- pletion. SIAM Journal on Optimization, 20(4):1956 1982, 2010.
Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 96):7117777, 2009.
Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Belter mini-batch algorithms via accelerated gradient methods. Advances in Neural Information Processing Systems 24, pp- 1647-1655, 2011.
John M. Holte. Discrete gronwall lemma and applications. MAA-NCS meeting at the University of North Dakota, 2009.
Chonghai Hu, Weike Pan, and James Kwok. Accelcrated gradicnt methods for stochastic op- timization and online learning, Advances in Neural Information Processing Systems 22, pp. 781 789, 2009.
Shuiwang Ji and Jiepeng Ye, Exact matrix completion via convex optimization. Proceedings of the 26th International Conference Machine Learning, pp. 457-464, 2009.
Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from few entries. IEEE Transactions on Information Theory, 56(6):2980 299929988899,,,,,, 2010
Jeffery J. Leader. Numerical analysis and scientific computation. 2004.
Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. The Journal of Machine Learning Rescarch, 11:2287-2322, 2010.
Yurii E. Nesterov. A method for solving the convex programming problem with convergence rate O(k-2) Soviet Mathematics Doklady, 27(2):372 376, 1983.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127-239 2014.
Weijie Su, Stephen Boyd, and Emmanuel J. Candès. A differential equation for modeling nesterov's accelerated gradient method: theory and insights. Advances in Neural Information Processing Systems 27, pp. 2510-2518, 2518, 2014.
llya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. Proceedings of the 30th International Conference on Machine Learning, pp. 1139-1147, 2013.
Andre Wibisono, Ashia C. Wilson, and Michael Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113(47):E7351 E7358, 2016.
Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaie. Direct runge-kutta discretization achieves accoleration. Advances in Neural Information Processing Systems 31, pp. 3900-3909, 2018.
10

---

Under review conference paper at ICLR 2021
A Appendix
A.1 Proof of Theorem
Theorem Assume f satisfies L-Lipschitz condition, and solution a<() of the derived differential equation [.2)
has a continuous third derivative. For fixed time i, the truncation error (2.2) satisfies
(A.1)
Proof. Notice that
x(t h) x(t) - (hh).
Substitute this equation to the last term of L[r(t); h| to get
(a(t)+
t 3h (x(t) z(t - h))) = f (((t)) + t-3h 3h
.0t))
t
t
Since satisfies L-Lipschitz condition, we know
t 3h (z(t)= - x(t- -n)) z((--))) = =f(((t)) + Ohh)
(t()) f +
x(1 =b))) + O(h).
To get the second oquality, we substitute the differential equation and third terms of L[r(t); h] to third order to get
1.2
Then we expend the first
h22
x(t h) = x(t) + hr (1)
(t) +
r
2
(t)
O
2
2
x(t h) .r(t) ho (1) (t) +
x
()) + 0(h))
2
Substitute these three equations to [.. we have
T.(((();)) h) = 01,3)
Remark
A.1 can also be written as
[[]x(t;;h]| S M₁h3,
where M1 depends on supast (s)) and supese (z( (s)l-
Remark 2. Theorem I deals with the problem for fixed time t. To finish the proof of the convergence, we have to consider the situation that f, nh, where n 2 1 is fixed.
We set fixed time tu and assume that tn = nh < to- Since srtt) has a continuous third derivative, all) and its first to third derivative are bounded in [0] We replace time I in the above proof by in and expend the terms of (..2) Now the term
3h
2t x (2) (1,)
obtained from the expansion of s0(n-1) cannot be viewed O(h)), but there exists M₂ such that
3h3
S .M h²2
x (2) (tn)
(t,))
2t.,
As consequence, have
[L(a(t.):: S Mnh² + M2 2
(A.2)
where Mj and M2 rely on to-
11

---

Under review conference paper at ICLR 2021
A.2 Two lemmas for Theorem 2
For the proof of Theorem we need the following two lemmas.
Lemma 1. (Holte. 2009) For constant a, B > and positive sequence { h220 satisfying
R-1 Th 5 0
Vn 0,
the following inequality holds
S (B + an)))
The above lemma a classic result and refered to as discrete Gronwall inequality. Lemma 2. We define matrices C, and Dn,
2n-1
C
a+1
a+1
Cn ... 1..-- Cn-1+1,
where and <<< <<lsn 11 In addition, we set Dn,0 = I2- Then there exist positive constants M, M3 such that for all n, the following two incqualities hold, where the matrix norm is 2-norm.
sup osign+1
Dn,ell s Mn,
Dant1 I M3-
(A.3)
Proof. Since
C2 (1 1
0
we notice that when > 2,
D Dan-1 = (1
9). D
(
1).
D Dan+I
having nothing to do with the value of n. So is obvious that there exists M3 to make A.3 holds and M4 > 0 such that for all < or 2, l >> 2 or / = O,
D $ M4n.
(A.4)
Then consider the condition when 2, 0 < S - 2. Notice that
1
!)
1
!)
C₂ =
n-2
1
For convenience, we write
1
0)
=
1
Assume we have alreagy gol
Dn.!' = P
1
an,i p-1
0
bn.1
satisfying
and S1
bnl 1,
12

---

Under review conference paper at ICLR 2021
then since
D = Dn,,Cn--b,
and 0 S n-1-7 < 1, Dra41 has the same form
Dn,11= 1
andl+ p-1, 0n.141
satisfying
0 < an11+1 E 11+1. 1,
0 < bad S 1.
Then for fixed n, induce from = 1, we gel
D = PD n.i P- A
and! p-1 bnd
satisfying
0 < an Sisn,
0 < bu,t 11,
(A.5)
for all n 2 0<1s 2. Then we can estimate
|nnill Notice that
1 + on
anaba.) an
DT nd =
1n,1
The cigenvalues of this matrix are
1 a b2 +
v1+ + 62 0221)2 4b4
112
2
Combining this representation with
A.5 we get the estimation
/max Pa13 S 1 a,, + 122 S n n
So there exists M3 O, such that for all 2 2, 0 < 1 S 2, inequality
Dr. < Mşn
(A.6)
holds. Combining A.4 with A.6
finish the proof.
D
A.3 Proof of Theorem
Theorem 2 Under conditions in Theorem for fixed time 1, Fe/h converges to a(1) as goes to zero at rate of O(h In 1)) if =0) and 21 x<)).
Proof. In this proof, we first calculate the error caused by a single iteration, which can be divided into accumulation term and a truncation term. Then we the estimation given by Theorem I and apply discrete Gronwall incquality to prove the convergence.
Recall the recurrence relation
n 3 (on In-1) - h2. In
n - 3 (xn xn-1))
En+1 Fn
and the definition of truncation error
x((n+1) = I((n) + n - (x((n) - x((n-1)) - 118 (((t)) + n2 3
(z((n)) - 2((12-)) + L[x(tn);
13

---

Under review conference paper at ICLR 2021
where in nh.
Subtract the above two equations, and introduce overall error
On
x(tx)
En
we have
2n 3
h²b + h[z(tt):h))
Cx+1
Cn
Cn-
n
n
which can also be written as
2n
7 2
en+2
en+1 +
On = -h?b, + ([<((tn1)ii
(A.7)
n1
+
+ 1
where
2m
n1 - 2
( 2n
n - 2
bn =f
In+l
+ En
-f
++ xxtx+1)
+ 20(tz))
(A.8)
+1
We will also use the notation
2n-1 n+1 n+1
Cut1 + n-2
Cx+2
Cn
h22
Then rewrite A.7 into form that is convenient for recurrence. We set
E,
Cn+1
)
Cn
2n
n+1
n
Bn =
(- -h2b;
En
0
Then A.7
can be written as
En+1
C. En + Ba.
By recursive method, we have
Ch- + Co. C.......tBBBB...... Ba-t-
1=1
With the notations introduced in Lemma
this equation can be written
E, Dn-1, Eo
D
(A.9)
I=1
Now need to estimate
|B Since ʃ satisfies L- L-Lipschitz condition, from A.8 we have
2n + 1
|e41l + n --2 n enl
|bal < L
$ (2/en+il + lewl) S 3L E,
and
BB < 3h Ex + L [[((tn+));h Take norm on both sides of (.9) and substitute following estimation
(A.10)
(A.10) and conclusion of Lemma
we have the
E ll S | + M(n 1)
(3h² L E1l + [(x(111);;1)
1=0
(A.11)
< Eoll + 3M.R2
E + Mn
[a((k+1):M1)
1=0
14

---

Under review conference paper at ICLR 2021
Now we deal with truncation errors. Recall A.2)) in remark of Theorem
h
[[][(t);h]] S M M2
1
Take sum to obtain
L [ 1): & nM, + Mah² 1=0
(A.12)
1+1
1=0
Notice the classic inequality
In + Me.
where Me refers to positive constant. Substitute it to (A112), we have
[[(((441) Ml] S nM, + M21 (In + Mc).
Substitute this inequality
A.11
get control of E,
Eill + MMmnh + MMM + MMnhh Inn E < Ma Boll + 3M Σ
Using discrete Gronwall inequalily, we have
E, < 3M (Mal Eo + MM MM2M,nh² + MManl Inn + 3Mmh 1 E.I
Then for fixed t, we choose n & to get
EEj/al S 2M02 ( + 3MthL) + (MM, + MM2M,tth MM2thh 4
Notice that
lim h00 h = 0,
if Eg O, then the vector form of overall error Eijh satisfics
lim E = 0.
A.4 Proof of Theorem
Theorem 3 f has contimuous second order derivative, the first and second derivative are bounded, and xtt) has continuous fourth derivative, then for fixed t, truncation error of (3.2) satisfies
Proof. Rocall the proof of Throrem
1 Now we expand z(t h) to first order
z(t - h) x(t) + (z) O(h)).
15

---

Under review conference paper at ICLR 2021
Then we have
$ (x(0)) + t- (x(t) xxtt - -h)) =f x(t) + (1-7) 3h (1) 0(12))
=f (a(1) + (t) + 0(1))
=f (a(1) + (1) 0(h7)
We now expand f:
/ a(()) + 1- 3h (z(t) (
(x(t))x(( x(t x((()) 1)))
= -(x((t) + ha (()))))
To do this, we need/ f has continuous second derivative and the second derivative is bounded. Take derivetive on both sides of differential equation
3
ä+ - + t
+ f(x) = 0,
we have
3 (t) + 82 t
(f(x(t))) = (z)
(t).
So
I a(()) (0(() + 1 -- 3h (x((t) - xelt hn)) ht)
13h +1 (1)
(A.13)
(3h
3h
3
(1) (t) + 0(h2).
82
Expand axt + 1), x0l - h), xrtt 22h) to the third order, we have
31h
n1h²)
x(1 + h) aai+ + 31h
nnh² 12
a1 +
1 12
s(11) + har + 122 x
(2)
(t) + h
6 (1)))( (1)+)) +
2
3zh
73h2
03 + Jgh
2ah?
03 + 1.
x(1 - h)
I + 12
12
x(1) - (1)) + h22
(1) (1(()
h
(3) (1) (1)) (1)+0(011
x
2
6
Bah
Tah2"
0e4 + Bah
rah
a4+ +
+
xx1 2hh
I + 12
1
12
4h3
x(() 2h (1) (1) + (2)
x + 0(1+)
3
Substitute these three equations and (A133) to truncation error of recurrence relation 3.1
Byh
[[r(t);h]=
a +
z(t + (2 -)))
t²
t - 3h
f
xx() +
(x(t) x(t h1))
16

---

Under review conference paper at ICLR 2021
then simple calculation shows that terms with order less than four will be eliminated if choose coefficients according to the following equations
9
k
71 m1
a1 = 2
2
3m1 + m2 +
02 5
B2 6 3k
72
2
4 , a1
B3 2
3
3k
73 m2
m2 + 7/1
my
B4 = k
2
where k. mi, M2 can be chosen randomly. Notice that coofficients of recurrence relation satisfy above equations.
3.2
A.5 Algorithms
Algorithm 4 FISTA
Input:
step size
Initial value: Y1 = Xo E M100, h = 1.
kth iteration (A: 1). Compute
(Yr sg((t)))1 X| 14 }
X arg min x
X
2s
+ 1 +
4t
fk+1
2
Yk+1 = Xx +
(Xx- - Xx-1).
t++1
Algorithm Accolerated proximal gradient method
Input:
step size 8
Initial value: X1 X M100-
kth iteration (A: 2 1). Compute
Y, = Xk-1 +
(X--1-X--2),
k
1 X
X arg min x
-Y: - -Y
28
A.6 Details about Numerical Experiments in Section
Here we produce some details for our numerical experiments in Scction 4.
simulated data set. Firstly, generated the 'true' low rank matrix M. To do this, we generate a random matrix Mo. Entries of Mo are independent and uniformly distributed
Our experiments are taken
(0, 20). Then compute the singular value decomposition of Mo, that is, Mo = UEVT. After that, we set M UV,VT where Σo is diagonal matrix with only three nonzero diagonal clements. It is not difficult to prove that M has rank 3.
17

---

Under review conference paper at ICLR 2021
Secondly, we generate the observation set. For every row of M, we choose randomly ten entrys to be observed. As consequence, 10% entries are observed in total.
After data gencration step, we apply the abovementioned algorithms (acceleratod proximal gradient method, FISTA and our modified FISTA) with fixed step sizes and backtracking to this data set. The parameter of the loss function (1.1) is 0.005. For initial point, we simply choose the zero matrix (every entry equals to zero). For backtracking, we set the initial step size as 10 and the decay factor 0.1.
18


Reviews:
[{"review_id": "vo_NltmAVzz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "summary:\nThis paper proposes an accelerated method that has a high-order truncation error $O(h^4)$ to the ordinary differential equation $\\ddot{x} + \\frac{3}{t}\\dot{x} + f(x) = 0$ obtained from Nesterov's accelerated method by (Su et al., 2014), while Nesterov's method has $O(h^3)$ error. This implies that the iterates of the proposed method converge to the trajectory of the differential equation faster than those of Nesterov's method. The two toy numerical experiments illustrate such phenomenon for certain large step size. A matrix completion problem experiment is further included.\n\nstrong point:\n- Finding a method that has a high-order truncation error seems new and interesting, and numerical experiment suggests that such method performs better.\n\nweak points:\n- There is no theoretical guarantee on the convergence (rate) to a solution of an optimization problem.\n- The reason why we care \"large\" step sizes seem insufficient, while Nesterov's method is stable for normal step sizes (e.g., $1/L$).\n- It is not clear when the step size is considered large, other than using an exhaustive search. Unlike Nesterov's method, the interval of step sizes that guarantee convergence to a solution is not known for the proposed method.\n- Numerical experiments are limited. \n\nminor comments:\n- page 1: $||F(x_n) - F(x^*)|| \\to F(x_n) - F(x^*)$\n- page 6: what is the Lipschitz constant for this experiment?\n- a figure of two-dimensional toy example could help better illustrate the effect of the truncation error.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZgmraklFuO", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors study a version of accelerated gradient method. Inspired by the ODE analysis of Nesterov accelerated gradient method by Su et.al., the authors propose a different discretization of the ODE by Su et al. The truncation order of this scheme is of a higher order, thus the authors claim that the proposed algorithm is more stable and, therefore,  will converge with larger steps. Unfortunately, I found these statements to be vague. \n\nApart from the above-mentioned truncation error, the only evidence we have is some simple $2$-dimensional experiment. I believe it is not sufficient. Second, for a new scheme convergence of iterates $(x_n)$ to a solution and the convergence rate $F(x_n) - F(x_*)$ should be proven explicitly, they do not follow automatically. Ideally, we need both sound theory and good experiments to claim that one method is better than another. I am afraid both are missing in this work. The same was done for the modified version of FISTA, where the authors add regularizer without any discussion about convergence of the scheme.\n\nBased on this, I cannot recommend this paper.\n\n\nI suggest the authors to address the above-mentioned concerns in their revision. I think it would be great if one can show directly the connection between the discretization truncation error and better algorithm performance. Note that, however, already Nesterov's methods have optimal performance. Probably, a significant experimental evidence will help here. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "YYfAT8rM6p", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "UPDATE: After reading through all other reviews and responses by the authors, I share the concern that the theoretical justification of the paper is lacking as the connection between the truncation error and the improved algorithm performance is not rigorously proven. Therefore, I have reduced my score.\n\n\nSummary:\n\n\nThe paper studies the well-known Nesterov's accelerated gradient method and shows the rate of convergence to the solution of an ordinary differential equation recently proposed by [Su et al, 2014]. Motivated by the proof, the authors then derive a new accelerated method with a faster rate of convergence than the original Nesterov's method, which is shown to be more stable than the original Nesterov's method when the step size is large. The method is combined with the proximal operator into a new algorithm referred to as modified FISTA, which is then applied to the matrix completion problem. \n\n\nStrengths:\n\n- The paper proves the convergence rate of Nesterov's method to the ODE proposed by [Su et al, 2014]. This proof then motivates them to derive a new faster accelerated method where the truncation error has a higher order of $O(h^4)$ compared to $O(h^3)$ in case of Nesterov's method.\n- It is shown in two simple examples that the new method is more stable as it can work with larger step sizes. \n- The method is applied to a matrix completion problem, where it is shown to have faster convergence than standard FISTA and Nesterov's gradient method.\n\n\nConcerns:\n\n- In Section 2.2., the purpose of Lemma 1 and Lemma 2 is not clear without looking into the proof of Theorem 2 in the supplementary material. The flow of the paper could be improved if an intuition was given of which role they play in the proof of Theorem 2.\n- Similarly, to understand the motivation for the derivation of the new accelerated method in Section 3, one is required to look at the proof of the convergence in the supplement. Also here it would help to provide a detailed motivation for the derivations already in Section 3.\n- In the numerical results in Figure 1, the gap $|F(x_n) − F(x^*)|$ (y-axis) does not seem to monotonically decrease but jump up and down erratically. Also there are periodic wave-like patterns visible in the plot. Why do we see those patterns?\n- The resulting accelerated numerical method is never explicitly written down, only the specific version derived for the matrix completion problems. The paper would be better understandable if the general numerical scheme (accelerated method) was written down in form of an algorithm after Section 3.\n- In the end of Section 4, a reference to Algorithm 2 is missing. Moreover, Figure 2 and Figure 3 are never referenced in the text.\n- Page 2, after (1.2) -> \"achive\" -> \"achieve\"\n\n\nConclusion:\n\nThe proposed method provides a theoretical contribution to the understanding of Nesterov's accelerated gradient method. Moreover, a novel algorithm is proposed which is shown to have a faster convergence to the underlying ODE. In the paper this is shown only for a matrix completion problem but I feel that this new algorithm could be adopted by the community if further experiments prove its worth. On the other hand, the flow and presentation of the paper could be improved. Overall this is a borderline paper but its merits may outweigh its flaws.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LpNT5j08DKm", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review:  This paper refines the the truncation error analysis for discretizing the ODE to obtain accelerated optimization method.  The truncation results include higher order term. Built upon the analysis, the authors propose a new method which is claimed to be more stable for large step size and converges faster. Numerical evidence on matrix completion problem is provided.\n\n \nPros:\n\n+ The truncation error analysis is new.\n\n+ Overall, the paper is clearly written.\n\n\n \nCons:\n\n- The biggest concern that I have with the paper is that it is unclear to me whether the convergence rate is really improved or not. From my understanding, truncation error is different from the convergence rate. What does Theorem 3 really imply here? It seems to me that Theorem 3 does not guarantee that there is an improvement in the convergence rate. A rigorous quantification of the convergence rate needs to be provided to justify the claim \"the proposed method converges faster.\"\n\n \n- Even the claim on \"stability\" is not well justified. Two simple examples do not provide that much evidence here. \n\n- This paper does not provide enough details such that the numerical results can be easily reproduced.\n\n \n\n \nSuggestions for improvements:\n It will significantly strengthen the paper if the authors can provide more theoretical justifications for the claim that their proposed method is faster and more stable. It is also important to clarify the true implications of the truncation error analysis on the algorithm performance. \n\n\n ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies a high-order discretization of the ODE corresponding to Nesterov's accelerated method, as introduced by Su-Boyd-Candes. The main claim of the paper is that the more complex discretization scheme leads to a method that is more stable and faster. However, the theoretical claims do not seem sufficiently supported, and the experimental results are insufficient to judge the usefulness of the proposed approach. Thus, the reviews could not recommend acceptance, and I concur. The authors are advised to revise the paper to provide more theoretical and experimental evidence for usefulness/competitiveness of the proposed approach, and resubmit to a different venue. 
Decision: Reject