Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems
Authors: Stefano Sarao Mannelli
Pierfrancesco Urbani
Venue: NeurIPS 2021 Poster (2021)
Keywords: Momentum-based methods
statistical physics of learning
dynamical mean field theory
high-dimensional non-convex dynamics

Abstract: The optimization step in many machine learning problems rarely relies on vanilla gradient descent but it is common practice to use momentum-based accelerated methods. Despite these algorithms being widely applied to arbitrary loss functions, their behaviour in generically non-convex, high dimensional landscapes is poorly understood.
In this work, we use dynamical mean field theory techniques to describe analytically the average dynamics of these methods in a prototypical non-convex model: the (spiked) matrix-tensor model. We derive a closed set of equations that describe the behaviour of heavy-ball momentum and Nesterov acceleration in the infinite dimensional limit. By numerical integration of these equations, we observe that these methods speed up the dynamics but do not improve the algorithmic threshold with respect to gradient descent in the spiked model.

Analytical Study of Momentum-Based A Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems
Stefano Sarao Mannelli
Pierfrancesco Urbani Université Paris-Saclay, CNRS, CEA Institut de physique théorique Yvette, France pierfrancesco. ur urbani@ipht. fr
Department of Experimental Psychology University of Oxford
Oxford, United Kingdom
stefano. www.aommmeellleeeeeee..oo ox. ac.uk
Abstract
The optimization step in many machine learning problems rarely relies on vanilla gradient descent but it is common practice to momentum-bent based accelerated methods. Despite these algorithms being widely applied to arbitrary loss functions, their behaviour in generically non-convex, high dimensional landscapes is poorly understood. In this work, we use dynamical mean field theory techniques to describe analytically the average dynamics of these methods in prototypical non-convex model: the (spiked) matrix-tensor model. We derive a closed set of equations that describe the behaviour of heavy-ball momentum and Nesterov acceleration in the infinite dimensional limit. By numerical integration of these equations, we observe that these methods speed up the dynamics but do not improve the algorithmic threshold with respect to gradient descent in the spiked model.
Introduction
In many computer science applications one of the critical steps is the minimization of a cost function. Apart from very few exceptions, the simplest way to approach the problem is by running local algorithms that move down in the cost landscape and hopefully approach minimum at small cost. The simplest algorithm of this kind is gradient descent, that has been used since the XIX century to address optimization problems [1]. Later on, faster and more stable algorithms have been developed: second order methods [2, 3, 4, 5, 6, 7] where information from the Hessian used to adapt the descent to the local geometry of the cost landscape, and first order methods based on momentum [8, 9, 10, 11, 12] that introduce inertia in the algorithm and provably speed up convergence of convex problems. In the era of deep-learning and large datasets, the research has pushed towards memory efficient algorithms, in particular stochastic gradient descent that trades off computational and statistical efficiency [13, 14], and momentum-biin based methods are very used in practice [15]. Which algorithm the best in practice seems not to have a simple answer and there are instances where class of algorithms outperforms the other and vice-versa [16]. Most of the theoretical literature on momentum- based methods concerns convex problems [17, 18, 19, 20, 21] and, despite these methods have been successfully applied variety of problems, only recently high dimensional non-convex settings have been considered [22, 23, 24]. Furthermore, with few exceptions [25], the majority of these studies focus worst-case analysis while empirically could also be interested in the behaviour such algorithms on typical instances of the optimization problem, formulated in terms of generative model extracted from probability distribution.
variety
The main contribution of this paper is the analytical description of the average evolution momentum- based methods in two simple non-convex, digensmiessi,,,,, optimization problems. First consider the mixed p-spin model [26, 27], a paradigmatic random figh-dimensional optimization problem.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Furthermore we consider its spiked version, the spiked matrix-tenss [28, 29] which is prototype high-ding digh-dimensional non-convex inference problem in which one wants to recover a signal hidden in the landscape. The second main result of the paper is the characterization of the algorithmic threshold for sncelerated-methodd the inference setting and the finding that this seems to coincide with the threshold for gradient descent.
The definition of the model and the algorithms used are reported in section In section 3 and 4 we use dynamical mean field theory [30, 31, 32] to derive a set of equations that describes the average behaviour of these algorithms starting from random initialization in the high dimensional limit and in a fully non-convex setting.
We apply our equations to the spiked matrix-tensod model [29, 33, 34], which displays similar phenomenology as the one described in [24, 35] for the phase retrieval problem: all algorithms have two dynamical regimes. First, they navigate in the non-convex landscape and, second, if the signal to noise ratio is strong enough, the dynamics eventually enters in the basin of attraction of the signal and rapidly reaches the bottom of the cost function. We use the derived state evolution of the algorithms to determine their algorithmic threshold for signal recovery.
Finally, in Sec. 5 we show that in the analysed models, momentum-basse methods only have an advantage in terms of speed but they do not outperform vanilla gradient descent in terms of the algorithmic recovery threshold.
2
Model definition
We consider two paradigmatic non-convex models: the mixed p-spin model [32, 36], and the spiked matrix-tensor model [28, 29]. Given tensor T E (IRV)os and matrix Y E <R the goal is to find a common low-rank representation æ that minimizes the loss
N
N Σ 1,=1
1 A
p
1)! NP-1
Σ $1
Tiy
1
(1)
A
with in the N-dimensional sphere of radius vN. The two problems differ by the definition of the variables T and Y. Call (0) and ((2) order p tensor and matrix having i.i.d. Gaussian elements, with zero mean and variances Ap and A₂ respectively. In the mixed p-spin model, tensor and matrix are completely random T = {(p) and Y = While in the spiked matrix-tensor model there is low-rank representation given by x= E S (VNN embedded in the problem as follows:
1)!
T Ti
T, + + "
YU
(2)
These problems have been studied both in physics, and computer science. In the physics litera- ture, research has focused on the relationship of gradient descent and Langevin dynamics and the corresponding topology of the complex landscape [32, 37, 38, 36, 39, 27,40) 40]. The state evolution of the gradient descent dynamies for the mixed spiked matrix-tensor model has been studied only more recently [33, 34]. All these works considered simple gradient descent dynamics and its noisy (Langevin) dressing.
In this work we focus on accelerated methods and provide an analytical characterization of the average performance of these algorithms for the models introduced above. In order to simplify the analysis we relax the hard constraint on the norm of the vector æ and consider æ E R while adding
penalty term to C to enforce soft constraint IN (E, 2 2)² so that the total cost function is
H. = + t [Σ, - 2 Using the techniques described in detail in the next section we write the state evolution for the following algorithms:
[9] starting from y|0] = z00] E N- (VN)
Nesterov acceleration
z + 1| yit| a (H
(3)
y + 1] = z 1|+ ++3 (zst + 1] =z(1))
(4)
given the learning rate of the algorithm.

---

Polyak's or heavy ball momentum (HB) [8] starting from y/O]
0 and z/0]
SN-1 (VN)
given the parameters a, 3
y + 1| = Sy + (H(=(t))
(5)
x + x azy + 1];
gradient descent (GD) starting from =00 SNN VN
x 1] =||| a (z(l(())
This case has been considered in (27.33) with the constraint E; 2 = N. The generalization to the present case in which constraint is soft is straightforward small extension of these previous works.
We will not compare the performance of these accelerated gradient methods to algorithms of different nature (such as for example message passing ones) in the same settings. Our goal will be the derivation of set of dynamical equations describing the average evolution of such algorithms in the high dimensional limit N - 0o.
3 Dynamical mean field theory
HB $ 0.9
1.20
Nesterov
-04
1.15
-066
radlus
0.8
1.10
-1.0
-12
1.05
-14
-16
10a
10a
10
Iteration
iteration
Figure Simulation and DMFT comparison in mixed p-spin model. The simulations in the figures have parameters = 3, A = 2/p. y. A = 1, ridge parameter 10 and input dimension N 1024. In all simulations we the dilution technique [41, 42] to reduce the computational cost. We consider: Nesterov acceleration in pink; heavy ball momentum in blue with a 0.01 and 3 0.9; and gradient descent in grey. We run 100 simulations (in transparency) and draw the average. The parameters for heavy ball are the best parameters found in our simulations, see also Fig. 2 for a comparison. The results from the DMFT equations are drawn with dotted lines.
We use dynamical mean field theory (DMFT) techniques to derive set of equation describing the evolution of the algorithms in the high- nigh-dimensional limit. The method has its origin in statistical physics and can be applied to the study of Langevin dynamics of disordered systems [30, 31, 43). More recently it proved be rigorous in the case of the mixed p-spin model [44, 45J. The application to the inference version of the optimization problem is [29, 33]. The same techniques have also been applied study the stochastic gradient descent dynamics in single layer networks [46] and in the analysis of recurrent neural networks [47, 48, 49].
The derivation presented in the rest of the section is heuristic and, such, it is not fully rigorous. Making our results rigorous would be an extension the works [44, 45] where math-integral methods used to prove a large deviation principle for the results are checked against extensive numerical simulations.
limit. Our non-rigorous
The idea behind DMFT is that, if the input dimension N is sufficiently large, one can obtain description of the dynamics in terms of the typical evolution representative entry of the vector (and vector y when it applies). The representative element evolves according to non-Markovian

---

stochastic process whose memory term and noise source encode, in a self-consistent way, the interaction with all the other components of vector z (and y). The memory terms well as the statistical properties of the noise are described by dynamical order parameters which, in the present model, are given by the dynamical two-time correlation and response functions.
In this first step of the analysis we obtain an effective dynamics for representative entry x; (and y:). The next step consists in using such equations to compute self-consistently the properties of the corresponding stochastic processes, namely the memory kernel and the statistical correlation of the noise. In Fig. we anticipate the results by comparing numerical simulations with the integration of the DMFT equations for the different algorithms: on the left we observe the evolution of the loss, on the right we observe the evolution of the radius of the vector z, defined as the L2 norm of the vector |||||- We find good agreement between the DMFT state evolution and the numerical simulations.
We compare Nesterov acceleration with the heavy ball momentum in the mixed p-spin model Fig. 1, and in the spiked model Fig. 3. Nesterov acceleration allows for a fast convergence to the asymptotic energy without need of parameter tuning. In Fig. we compare the numerical simulations for the HB algorithm and the DMFT description of the corresponding massive momentum version for several control parameters.
DMFT equations
In the following we describe the resulting DMFT equations for the correlation and response functions. The details of their derivation for the case of the Nesterov acceleration are provided in the following section, while we leave the other cases the supplementary material (SM). The dynamical order parameters appearing in the DMFT equations are one-time or two-time correlations. e.g. Czylt,t'] E, x (t y. | and response to instantaneous perturbation of the dynamics, e.g. [t (E, 8x,, (E
by local field H [t') R where the symbol denotes the functional derivative. In this section we show only the equations for the mixed p-spin model and we discuss the difference and the derivation of the equations for the spiked tensor in the SM.
From the order parameters we can evaluate useful quantities that describe the evolution of the algorithms. In particular in Figs. 1,2,3 we show the loss, the radius, and the overlap with the solution in the spiked case (Fig. 3):
Average loss
R lt CC
Σ ("=0
R It, (C,,tt (8)
ttt
Radius
tz,
1 Σ, 2 [+]] an additional order parameter for the spiked matrix tensor model (more details are given in the SM), the overlap with ground truth is
Define m2
n'
x [t] x= x
my
Nesterov acceleration. It has been shown that this algorithm has a quadratic convergence rate to the minimum in convex optimization problems under Lipschitz loss functions [9, 50), thus it outperforms standard gradient descent whose convergence linear in the number of iterations. The analysis of the algorithm is described by the flow of the following dynamical correlation functions
Ca(t,11
Σ a [t]))
N
Cylt,&|
Σ uiltluitt) it',
(10)
N
(,y = N
1
Σ
(11)

---

1
dzú(t]
Re(1,11
(12)
N
8H.(17'
[y:
Rg!t, N
(13)
[
The dynamical equations are obtained following the procedure detailed in section 4. Call Q(z) x² (2A2) + x²/ (p4p).
=
Czlt + =, Coult, 1'] an -) a² Σ t (Cylt, ("D) +
(14)
+ ax Σ Ry (cul,
=-=0
i'
Czylt + 1,1],
ap (C - a² Σ ""
t"=0
(15)
+ 2
Rylt, Q"
2t + 3
Cnyle,t 1t 1]
Czlt [t + 1, 1+3 1+3 Czlt,
(16)
1+3
21 + 3
C,ft,,+11
Cayl [t 1, 1+3 Coy
(17)
1 1+3
R + 1,(]= = R, [t, t') + 8 - op (Cylt, - 1) Ry
t
(18)
+ a² Σ
Ryll, 1") R,""", .110" (C,ltt());
8"=!"
+ 3
t+3 R2 [1 |1,1 - 1+3 - [.)
(19)
The initial conditions are: 21+3 x4-3
= 1, Cay = 1, 1,,0+ = 1, =1, Ry
=
The equations show a discretized version of the typical structure of DMFT equations. We can observe: terms immediately ascribable to the dynamical equations (3,4) and summations whose interpretation is less trivial without looking into the derivation. They represent memory kernels that take into account linear response theory for small perturbations to the dynamics (c.g. the last term of Eq. (14)) and noise whose statistical properties encode the effect of all the degrees of freedom representative one (e.g. the second last term of Eq. (14)).
Heavy ball momentum.
The DMFT equations are obtained analogously to previous ones.
1, = + c2y,1+1++
Ry (C)(t,t")
(20)
Σ Ro(l, 1" (Calt, (n)) Crylt", 1');
+
=0=0
Czylt',t t + 1| = 1 Σ lt'a'' (Czlt,t"))
(21)
+ Σ Rolt,t" (C, C.V''
===0
+1 Caylt,t'] - - -c Co[t+1,tt] = - 1]:
(22)
(23)
5

---

Ry =
de + (C.lt. - 1) R.
(24)
Σ Rglt,t" t" R,,tt, (C)lt,t"]):
#0 R2 + R, aRy [t 1,
(25)
with initial conditions: =, C,
C,y[0,0] - 1. Fig. 2 shows the consistency of theory and simulations.
0, R,(++1,4 = 1/a, R. 11t+,1,0
Mappings between discrete update equation and continuous flow for both heavy ball momentum and Nesterov acceleration have been proposed in the literature. In the SM we considered the work [51] that maps HB to second order ODEs some regimes of and 3. This mapping establishes the equivalence of the algorithm to the physics problem of massive particle moving under the action of a potential. This problem has been studied in [52] but the result limited to the fully under-damped regime where there is no first order derivative term, corresponding therefore to dynamics that is fully inertial and which never stops due energy conservation. In the SM we obtain the dynamical equations for arbitrary damping regimes, and we recover the equivalence established [51] comparing the results from the two DMFTs formulations.
Gradient descent. A simple way to obtain the gradient descent DMFT is by taking the limit m + 0 the DMFT of the massive momentum description HB. We get
a Σ t tt,")
(26)
+ a
Σ
R R, t "C.tt""
#-=0
Ra[l+ + 1,(] R1 + on +
Σ =-=0
Ralt, Ro, ,10"" (Cal4e"))
(27)
- ac [] Rx (t,
with initial conditions: C₂ [0,0 and R 1 Apart from the y-dependent term, these equations are particular case of the ones that appear in [36, 37] and we point to these previous references for details.
0=0
-02
==077
-04
1.15
-0
radius
-08
-1.0
-12
1.05
-16
1.00
10a
101
107
10a
10a
10a
10'
10a
10a
101
Itcration
Iteration
Figure 2: DMFT for HB. Simulations of HB momentum in the mixed p-spin model with p 3, 1024. The parameters are 0.01 for all the simulations and 3 E {0.5, 0.7, 0.9). We use solid lines to represent the result from the simulation, the dotted lines for the DMFT of HB.
Aa = 2/p, A₂ = 1, ridge parameter μ = 10 and input dimension

---

1.0
G0
HB p-0.9
Nesterov
1.20
overtup With acluton
0.8
0.6
1055
1.20
1.05
-20
1.00
10a
10
10P
10a
102
10"
10a
Eoration
Reration
Figure 3: DMFT in the spiked matrix-fensor model. Performance of heavy ball and Nesterov in the spiked matrix-tensor model with p = 3. 1/42 = 2.7, A3 1.0, and μı 10. The parameters in the simulations are: = 0.01 and B = 0.9 for HB. The different solid lines correspond to simulations with input dimension N 8192, while the dotted lines are obtained from the DMFT that, by definition, is in the infinite dimension limit. In the spiked version of the model the finite size effects are stronger and larger simulation sizes are needed.
Derivation of DMFT for Nesterov acceleration
The approach for the DMFT proposed in this section based the dynamical cavity method [43]. Consider the problem having dimension + and denote the additional entry of the vectors x and y with the subscript 0, zo and you The idea behind cavity method is to evaluate how this additional dimension changes the dynamics of all degrees of freedom. If the dimension is sufficiently large the dynamics only slightly modified by the additional dimension, and the effect of the additional degree of freedom can be tracked in perturbation theory.
The framework described in this section might be extended
other momentum based algorithms (such as PID [11] and quasi-hyperbod momentum [12]) with some minor adaptations. The steps to follow [43] can be summarised in:
Writing the equation of motion isolating the contributions of an additional degree of freedom,
leading Eqs. (28-30;
Treating the effect of the terms containing the new degree of freedom in perturbation theory, Eqs. (32-34);
Identifying the order dynamical order parameters, namely dynamical correlation and re- sponse functions, Eqs. (37,38).
Consider the Nesterov update algorithm and isolate the effect of the additional degree of freedom
5ز 14
azlt = viftl +
Σ Jo +
Σ
Vi axp
1
V4
N
(6.12....17p)
1=0
(28)
+ a Σ
J Jr Mo V., [ooooll
N Hil.
(29)
(p.
t
vilk + 2:(1
t+3 (x. + +1)))
(30)
We identify the term line (29) as a perturbation, denoted by H.(t). We will assume that the perturbation is sufficiently small and the effective dynamics is well approximated first order expansion around the original updates, so-called linear response regime. Therefore, the perturbed entries can be written as
8x, HH [t"
dy HH, [ H.((").
x
RJ x
mill R v +
(31)

---

The dynamics of the Oth degree of freedom to the leading order in the perturbation is
رyg [4]
rolt + 11o=tolt] - aqp
Σ
+ - 1)oott yolt)
+ =[|
+ a² Σ Jos
Hy
Hy[t"]
(32)
N
8ili [t] 8 ig [t Hig Hig[""]us (""viall) [1 ... yi, [1] + perm.) 0
+ a² Σ
Jo
(33)
N
(0,8)
y: + 1| x; + 1 t+3
(x,(t + 1] - xi(t)),
(34)
with = = a Ej JosUi + a ((.62....)t)) jo Vig [t]... Mi, [t] a Gaussian noise with moments:
{|] 0,
Cult,t+ 1 11 Q (C =K|t, A,
-| = 2
The terms in Eqs. (32,33) can be simplified. Consider the last term in Eq. (32): after substituting the H, Joj and Joj (1o.....). can be approximated by their expected values with difference that is subleading in 1/N
8 t H
2 A
8y 1"
a
Joj P'=0
Vo
Volt
it
t t"lolt",, (35)
öH,
where the last equality follows from the definition of response function in y- The same approximation is applied to Eq. (33), taking carefully into account the permutations, obtaining
a² 2 A
Σ (C,lt, volt").
(36)
Finally, collecting all terms, the effective dynamics of the additional dimension is given by
xol1 + 1] yo + a= - am (C,ll, 4] 1) v014 + a² Σ Ry (Cyll, voll"]; (37)
Volt + 1| = zo it 1]
(2olt + zu.tt)
(38)
t ++3
In order to derive the updates of the order parameters, we need the expected values of (E(t) and (S(t] with respect to the stochastic process. These are obtained using Girsanov theorem
[t = a Σ Ro Ru it'tttt" 1 (C,lt,t"),
(Elt)oolt') = a Σ Ri,lt,tt" (Cylt,
The final step consists in substituting the Eqs. (37,38) into the equations of the order parameters Eqs. (14-19). Then we identify the order parameters in the equations and use the results of Girsanov theorem to obtain the dynamical equations reported in section 3.
5 Algorithmic threshold
Finally we investigate the performance of accelerated methods in recovering a signal in a complex non-convex landscape. The dynamics of the gradient descent has been studied in the spiked matrix- tensor model in [33]. Using DMFT it was possible to compute the phase diagram for signal recovery in terms of the noise levels A2 and Ap. This phase diagram later confirmed theoretically [34].
Given the DMFT equations derived in the previous sections we can apply the analysis used in [33] to accelerated gradient methods. Given order of the tensor and Ap. increasing 22 the problem becomes harder and moves from the easy phase where the signal can be partially recovered to an algorithmically impossible phase where the algorithm remains stuck at vanishingly small overlap

---

3.5
GD extrapolated th. HB extrapolated th.
3.0
Nesterov extrapolated th.
2.5
2.0
1.5
1.0
Phase diagram of the spiked matrix-tensor model. The horizontal and vertical axis represent the parameters of the model Ap and 1/A2. We identify two regions the diagram: where Nesterov, heavy ball and gradient descent algorithms lead to the hidden solution (upper region), and where they fail (lower region). The grey square connected by solid line represents the threshold of gradient descent estimated numerically as detailed in the text. We use points to indicate the threshold extrapolated from the DMFT: pink circles for Nesterov accelcration and blue diamonds for heavy ball momentum with 3 0.9 and 0.01.
Figure 4:
with the signal. The goal of the analysis is to characterize the algorithmic threshold that separates the two phases. Using the DMFT we estimate the relaxation time the time the accelerated methods need find the signal. Since this time diverges approaching the algorithmic threshold, the fit of the divergence point gives an estimation of the threshold.
More precisely, for each value of Ap the noise to signal ratio (A2) increases the simulation time The algorithmic threshold Ag (Ap) is obtained by fitting the parameters of the power law (a, 0, Ag In the SM we show an example of the extrapolation
required to arrive close to the signal' increases like power law | Ag)((A)) (Ap)1
single point where many initial conditions m²²0)) considered in order to correctly characterize the limits N + and (2) 0+. Finally
the fits obtained for the three algorithms and for several Ap are shown in the phase diagram of Fig. for p We observe that all the algorithms give very close thresholds. DMFT allows to obtain a good estimation of the threshold, free from finite size effects and stochastic fluctuations that are present in the direct estimation from the simulations.
Conclusions and broader impact
In this work we analysed momentum accelleraed methods in two paradigmatic high-dimensions non-convex problems: the mixed p-spin model and the spiked matrix-tensor model. Our analysis is based on dynamical mean field theory and provides a set of equations that characterize the average evolution of the dynamics. We have focused on Polyak's heavy ball and Nesterov acceleration, but the same techniques may be applied to more recent methods such as quasi-hyperbolic momentum [12] and proportional integral-derivatee control algorithm [11].
Nomentum-based methods are techniques commonly used in practice but poorly understood at the theoretical level. This work analysed the dynamics of monentum-based algorithms in very con- trolled setting of a high-dimensional non-convex inference problem which allowed us to establish that accelerated methods have recovery threshold which is within the limits of numerical integration the same of vanilla gradient descent.
Our analysis can be easily extended 1-layer neural networks combining our technical results with the techniques of [46] and to simple inference problem seen from the learning point of view, such as the phase retrieval problem [53]. The same questions can also be analysed in the context of recurrent networks [48, 49] where DMFT approaches have already been applied to gradient- based methods.
'Since the best possible overlap for maximum a posteriori estimator m MAP can be computed explicitly, "close" means the time that the algorithms takes arrive at 0.9m. MAP

---

Our study is theoretical in nature and we do not foresee any societal impact.
Acknowledgments
The authors thank Andrew Saxe for precious discussions, This work was supported by the Wellcome Trust and Royal Society (grant number 216386/7/19/2). and by "Investissements d'Avenir" LabEx- PALM (ANN-100LABX-0009-AAAA.
References
[1] Augustin Cauchy, Méthode générale pour la résolution des systemes d' d'équations simultanées. Comp. Rend. Sci. Paris, 25(1847):536-555 538, 1847.
[2] Kenneth Levenberg. A method for the solution of certain non-linear problems in least squares. Quarterly of applied mathematics, 2(2):164-16) 168, 1944.
[3] Donald W Marquardt. An algorithm for least-squares estimation of nonlinear parameters. Journal of the society for Industrial and Applied Mathematics, ((2):431-44) 1963.
[4] Charles G Broyden. The convergence of a class of double-rank minimization algorithms: 2. the new algorithm. IMA journal of applied mathematics, 6(3):222-231, 1970.
[5] Roger Fletcher. new approach to variable metric algorithms. The computer jourraal, 13(3):317- 322, 1970.
[6] Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathe- matics of computation, 24(109):23-26, 1970.
[7] David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathemat- ics of computation, 24(L11):647-656 1970.
[8] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
[9] Yurii E Nesterov. method for solving the convex programming problem with convergence rate (1/k* 2). In Dokl. akad. nauk Sssr, volume 269, pages 543-543 1983.
[10] Saman Cyrus, Bin Hu, Bryan Van Scoy, and Laurent Lessard. A robust accelerated optimization algorithm for strongly convex functions. In 2018 Annual American Control Conference (ACC), pages 1376-1381 IEEE, 2018
[11] Wangpeng An, Haoqian Wang, Qingyun Sun, Jun Xu, Qionghai Dai, and Lei Zhang. A pid controller approach for stochastic optimization of deep networks. In Proceedings of the IEEE Conference Computer Vision and Pattrnn Recognition, pages 8522-8531, 2018.
[12] Jerry Ma and Denis Yarats. Quasi-hyyerbolic momentum and adam for deep learning. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[13] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[14] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1139- 1147. PMLR, 2013.
(15) Laurent I Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
[16] Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. 2018 Information Theory and Applications Workshop (ITA), pages 1-9, IEEE, 2018.
10

---

[17] Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. 2015 European control conference (ECC), pages 310-315. IEFE, 2015.
[18] Nicolas Flammarion and Francis Bach. From averaging to acceleration, there is only a step-size. In Conference on Learning Theory, pages 695. PMLR, 2015.
[19] Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. In H. Wallach, H. Larochelle, A. Beygelzimer, Alché-Buc, E. Fox, and Garnett, editors, Advances Neural Information Processing Systems, volume 32, pages 9633-9643. Curran Associates, Inc., 2019.
[20] Tao Sun, Penghang Yin, Dongsheng Li, Chun Huang, Lei Guan, and Hao Jiang. Non-crgodic convergence analysis of heavy-ball algorithms. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 5033-5040, 2019.
[21] Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3):653-711 2020.
[22] Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint 1644v01604 2016.
[23] Sébastien Gadat, Fabien Panloup, Sofiane Saadane, et al. Stochastic heavy ball. Electronic Journal of Statistics, 12(1):461-529) 2018.
[24] Jun-Kun Wang and Jacob Aberntthy. Quickly finding a benign region via heavy ball momentum in non-convex optimization. arXiv preprint arXiv:2010.01449, 2020.
[25] Damien Scieur and Fabian Pedregosa. Universal average-case optimality of polyak momentum. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8565-8572. PMLR, 13-18 Jul 2020.
[26] Alain Barrat, Silvio Franz, and Giorgio Parisi. Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses. Journal of Physics A: Mathematical and General, 30(16):5593-5612, aug 1997.
[27] Giampaolo Folena, Silvio Franz, and Federico Ricci-Tersenghi. Rethinking mean-field glassy dynamics and its relation with the energy landscape: The surprising case of the spherical mixed p-spin model. Physical Review X, 10(3):031045, 2020.
[28] Emile Richard and Andrea Montanari. A statistical model for tensor pca. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, pages 2897-2905. Curran Associates, Inc., 2014.
[29] Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Marvels and pitfalls of the langevin algorithm in noisy high- dimensional inference. Physical Review X, 10(1):01 1057,, 2020.
[30] Paul Cecil Martin, ED Siggia, and HA Rose. Statistical dynamics of classical systems. Physical Review A, 8(1):423, 1973.
[31] C De Dominicis. Dynamics as a substitute for replicas in systems with quenched random impurities. Physical Review B, 18(9)4913,, 1978.
[32] Andrea Crisanti and H-J Sommers. The sphericalp-spin interaction spin glass model: the statics. Zeitschrifi für Physik Condensed Matter, 87(3):34-334, 1992.
[33] Stefano Sarao Mannelli, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Passed spurious: Descent algorithms and local minima in spiked matrix-tensor models. In Interna- tional Conference on Machine Learning, pages 4333-4342. 2019.

---

[34] Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, and Lenka Zde- borová. Who is afraid of big bad minima? analysis of gradient-flow in spiked matrix tensor models. In Advances in Neural Information Processing Systems, pages 8679-8689, 2019.
[35] Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdehorová. Complex dynamics in simple neural networks: Understanding gradient flow phase retrieval. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 3265-3274, Curran Associates, Inc., 2020.
[36] Leticia F Cugliandolo and Jorge Kurchan. Analytical solution of the off-cquilibrium dynamics of a long-range spin-glass model. Physical Review Letters, 71(1):173, 1993.
[37] Andrea Crisanti, Heinz Homer, and H-J Sommers. The sphericalp-spin interaction spin-glass model. Zeitschrift für Physik Condensed Matter, 92(2):257-271, 1993.
[38] Andrea Crisanti and Luca Leuzzi. Spherical 2+ p spin-glass model: An analytically solvable model with glass-to-glass transition. Physical Review B, 73(1):014412, 2006.
[39] Antonio Auffinger, Gérard Ben Arous, and Jifí Černý. Random matrices and complexity of spin glasses. Communications Pure and Applied Mathematics, 66(2): 2013.
[40] Giampaolo Folena, Silvio Franz, and Federico Ricci- Terce-Tersenghi. Gradient descent dynamics in the mixed p-spin spherical model: finite-size simulations and comparison with mean-field integration. Journal of Statistical Mechanics: Theory and Experiment, 2021(3),03302,, 2021.
[41] Guilhem Semerjian, Leticia F Cugliandolo, and Andrea Montanari. On the stochastic dynamics of disordered spin models. Journal of statistical physics, (5551)::93-3000 2004.
[42] Florent Krzakala and Lenka Zdeborová. Performance of simulated annealing in p-spin glasses. In Journal of Physics: Conference Series, volume 473, page 012022. IOP Publishing, 2013.
[43] Mare Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
[44] Gérard Ben Arous, Amir Dembo, and Alice Guionnet. Cugliandolo-Kurchan equations for dynamics of spin-glasses. Probability theory and related fields, 136(4):619-660, 2006.
[45] Amir Dembo and Eliran Subag. Dynamics for spherical spin glasses: disorder dependent initial conditions. Journal of Statistical Physics, pages 1-50, 2020.
[46] Francesca Mignacco, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Dynamical mean-field theory for stochastic gradient descent in gaussian mixture classification. In 2020 Conference on Neural Information Processing Systems-Neurle 2020, 2020.
[47] Haim Sompolinsky, Andrea Crisanti, and Hans-Jurgen Sommers. Chaos in random neural networks. Physical review letters, 61(3):259, 1988.
[48] Francesca Mastrogiuseppe and Srdjan Ostojic. caannnicallyggnnerate fluctuating activity in excitatory-inhiiitory networks. PLoS computational biology, 1005498, 2017.
[49] Tankut Can, Kamesh Krishnamurthy, and David J Schwab. Gating creates slow modes and controls phase-space complexity in grus and Istms. In Mathematical and Scientific Machine Learning, pages 476-511. PMLR, 2020.
[50] Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nes- terov's accelerated gradient method: Theory and insights. Advances in neural information processing systems, 27:2510-2511 2014.
[51] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12(5):155-551, 1999.
12

---

[52] Leticia F Cugliandolo, Gustavo S Lozano, and Emilio N Nessi. Non equilibrium dynamics of isolated disordered systems: the classical hamiltonian p-spin model. Journal of Statistical Mechanics: Theory and Experiment, 2017 2017(8)003331, 2017.
[53] Francesca Mignacco, Pierfrancesco Urbani, and Lenka Zdeborová. Stochasticity helps to navigate rough landscapes: comparing cradient-descent based algorithms in the phase retrieval problem. Machine Learning: Science and Technology, 2021.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]] Refer to the conclusion and broader impact section.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? sections "model definition".
[Yes] Refer to
(b) Did you include complete proofs of all theoretical results? [N/A] Our results are not rigorous but are consistently checked against numerical simulations. We comment on possible strategies to make them rigorous.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [No] We use standard algorithms and provide details on the parameters. They can be easily reproduce in any computer.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All the figures resulting from the experiments contain details to reproduce them.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [No] Tha data for each figure can be obtained in maximum one day of laptop simulation.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "IJeMZZYhlG", "reviewer": "Reviewer_AYp2", "summary": "The authors try to understand analytically momentum-based accelerated methods in non-convex setting. ", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "The  originality is very good for us to understand analytically momentum-based accelerated methods in non-convex setting and propose a new (spiked) matrix-tensor model. But the quality and clarity is not good, I have never seen how the new model is better than others and how the model is related to momentum-based accelerated methods  in non-convex setting.  Moreover, I have never seen any significance in this manuscript. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should propose some efficient proofs, not the descriptions. I hope the authors can provide more information to make sure their claim is more convincible. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "35"}, "extra_text": {}}, {"review_id": "AesNgJVyXvm", "reviewer": "Reviewer_JN9a", "summary": "This work studies two types of high-dimensional non-convex optimization problems: (1) the mixed p-spin model; (2) the spiked matrix tensor model. Authors studied a high-dimensional, mean-field type limit of momentum-accelerated optimization dynamics solving these two types of non-convex problems. Mean-field type dynamical equations for Polyak's heavy-ball and Nesterov's method are derived.", "questions": "", "limitations": "", "rating": 6, "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": "The idea of considering a high-dimensional limit of optimization dynamics using mean-field methodology is novel and interesting. It would be great if authors can derive more about the gap between the mean-field limit and the high (but finite) dimensional case. Also, it would be interesting to point out why mean-field equations are useful in understanding these optimization dynamics, such as  its connection with deep learning. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "5PdUT7nH6da", "reviewer": "Reviewer_9jn4", "summary": "The authors study the dynamics of accelerated gradient methods applied to two prototypical, non-convex problems: recovering the ground state of a mixed p-spin model, and recovering a planted signal from a spiked matrix-tensor model. The two models are defined according to the following loss function\n\n$$\n\\mathcal{L}(x) = - \\eta_p(\\Delta_p) \\cdot \\sum_{i_1, \\ldots, i_p}^N T_{i_1, \\ldots, i_p} \\cdot x_{i_1} \\ldots x_{i_p} - \\eta_2(\\Delta_2) \\cdot \\sum_{i,j}^N Y_{i,j} \\cdot x_{i} x_{j}\n$$\n\nwhere $T \\in (\\mathbb{R}^N)^{\\otimes p}$ is a tensor, $Y \\in \\mathbb{R}^{N \\times N}$ is a matrix and $\\eta_p(\\Delta_p)$ and $\\eta_2(\\Delta_2)$ are normalization constants dependent on $\\Delta_p$ and $\\Delta_2$ respectively. When $T$ and $Y$ possess entries that are i.i.d Gaussians with mean 0 and variance $\\Delta_p$ and $\\Delta_2$ respectively, we have the mixed $p$-spin model. When $T$ and $Y$ are given by a Gaussian perturbation of vector $x^*$ on the $\\sqrt{N}$ radius $N$-dimensional sphere, we have the spiked matrix-tensor model. Finding the ground state for mixed $p$-spin, and recovering the planted signal from the spiked tensor model then correspond to finding $x$ which minimizes loss $\\mathcal{L}$. Note in the latter case that $x$ which minimizes loss will also have a large overlap with $x^*$ hence why one considers this problem as recovering a planted signal.\n\nThis work uses the cavity method to derive mean dynamics for iterates produced by accelerated gradient methods. They construct a sequence of equations that track correlation between iterates maintained by Nesterov’s acceleration and Polyak’s Heavy Ball Momentum. These equations are parameterized by different time steps of the algorithm; for example, the equation for $C_x[t, t’]$ corresponds to the overlap of $x$ at time $t$ with that at time $t’$.\n\nThe dynamic mean field equations can be used to heuristically determine computational thresholds for statistical signal recovery in the following sense. For an instance of finding a planted signal from a spiked matrix-tensor model given by samples of $T$ and $Y$, consider the instance’s signal-to-noise ratio $\\frac{\\Delta_p}{\\Delta_2}$. For a fixed value of $\\Delta_p$ and as one increases $\\Delta_2$, it becomes increasingly difficult to recover the planted spike $x^*$. At a certain value of $\\Delta_2$, say $\\delta^*$, an iterative method solving the instance may exhibit a phase transition: for $\\Delta_2 < \\delta^*$ the method will find $x$ that has large overlap with $x^*$, while for $\\Delta_2 > \\delta^*$, the method only converges to $x$ that has vanishingly small (w.r.t. $N$) overlap with $x^*$. \n\nThe authors use the mean dynamic equations to compute statistical recovery thresholds for Nesterov acceleration and Heavy Ball momentum. The cavity method calculations are heuristic, and so the authors support their estimates with experiments that suggest the true threshold for these two methods are very close to their estimates. The results also suggest that the threshold for accelerated methods align closely with the threshold achieved by vanilla gradient descent. As a separate results, the authors demonstrate an equivalence between the dynamics of Polyak’s Heavy Ball Momentum and the dynamics of a massive particle under the effect of a certain potential field.", "questions": "", "limitations": "", "rating": 7, "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": "The primary contribution of this paper that I see is its estimation of a computational threshold when Nesterov's acceleration and Polyak's Heavy Ball momentum are used to recover a planted signal from a spiked matrix-tensor model. The methodology required to compute the dynamic equations and subsequently estimate the threshold are non-trivial and interesting. Even though this use of the Cavity method implies that the calculations are non-rigorous, experiments demonstrate that the estimates align closely with the true computational threshold. One might hope then to use the techniques of (Mannelli et. al., 2019) to rigorously establish this threshold, or alternative methods of establishing the rigor of the cavity method (Bapst et. al., 2016), (Coja-Oghlan & Panagiotou, 2016), (Ding et. al., 2015). \n\nThe observation that the computational threshold for accelerated methods align closely with the threshold achieved by “vanilla” gradient-flow algorithms is surprising. Accelerated methods can be viewed as a coupling between the “primal” method of gradient descent, and the “dual” method of mirror descent. Mirror descent has classically been employed in certain combinatorial optimization problems to efficiently construct “certificates” that establish that the target solution cannot exist in a region of the search space. A priori, one might imagine that accelerated methods then recover the planted signal for a broader range of parameters when compared to gradient descent because, simultaneous to searching for the planted signal, accelerated methods also implicitly maintain a certificate regarding where not to search. These experiments suggest that the aforementioned intuition is likely either misguided, or not enough to supersede the gradient descent computational threshold.\n\nA few broad comments. \n- Further discussion regarding rigorously establishing the calculations presented in this work is warranted. What prevents making this application of the Cavity method rigorous? Separately, is there a significant roadblock towards extending the results of Mannelli et. al. to encompass accelerated methods?\n- Certain approximations are made within the calculations without much warning (c.f. equations 31, 35). These are standard approximations employed in spin glass calculations; however they also increase the inaccessibility of such topics to those who may not have extensive background. When an approximation is made, can there be a brief exposition (perhaps even one sentence) explanation motivating its use?\n- The paper lists extending their techniques to other models such as “1-layer feedforward networks, and recurrent networks” as future work. However, broader discussion regarding why one might wish to study statistical recovery thresholds for different models and optimization methods is warranted. For example, does this give some algorithmic insight into designing methods that would recover planted signal for a larger range of parameters?\n\nOther minor comments\n- On line 118 $C_{xy}[t, t’]$ as written doesn’t depend on $t’$\n- On line 119, please provide a definition for the first time $\\delta$ is used.\n- On line 119, define what local field is (or specify the dimensions of this object).\n- On equation 11, the equation is missing a $t’$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have reasonably addressed these concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "2yzNbLOkbB", "reviewer": "Reviewer_KU8M", "summary": "The paper derives a dynamical model for a few numerical solvers for the spiked matrix-tensor model, and analyzes the performance of the accelerated methods using the model. The main contribution is the derivation of the analytic form of the model.", "questions": "", "limitations": "", "rating": 5, "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": "The main strength of this paper is the derivation of closed-form dynamical models for different solvers, as well as the performance analysis based on the model. The results appear to be new.\n\nThe are some issues with the presentation that will benefit from clarification:\n\n- Both the abstract and the end of the first section claim that the accelerated method improves the convergence speed. Is this conclusion derived from the proposed model? Or is this already known in previous work? Given that this is a non-convex problem and the gradient descent solver uses a fixed step size parameter, it is likely that the convergence/acceleration of these methods relies on specific parameter values. So under what settings are these models analyzed? Were you already assuming that all the considered methods converge/accelerate under the given parameters?\n\n- The models were proposed based on a relaxed formulation of the problem. i.e., the hard constraints have been replaced with a soft constraint term with a specific weight parameter mu. The choice of mu will affect the accuracy of the resulting solution (assuming the methods converge). Unless mu approaches infinity, the solution will deviate from the actual solution to the original problem. So how should we interpret the performance analysis? Shall we consider it as performance analysis for the approximate solver which may not indicate the actual performance if we want to look for an accurate solution? One of the conclusions is that the accelerated methods do not alter the algorithmic threshold. Is this reliant on the choice of mu? Can you prove that this behaviour persists no matter how you choose mu?\n\n- At the end of the paper, it is claimed that \"the same techniques apply to more recent methods such as quasi-hyperbolic momentum and proportional integral-derivative control algorithm\". Looking at this paper only, it is not very clear how the derivation of these analytical model can be carried out for arbitrary methods. (In fact the derivation process for the proposed models were not clear either.) It appears that each new model may need a specific set of mathematical derivations. Can you clarify if there is a common way to analytically analyze these models?\n\n- Line 128 claims that Nesterov acceleration has \"quadratic convergence rate\". Were you suggesting that Nestertov acceleration has the same convergence rate as Newton's method (which is well known to be quadratically convergent)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and AC agree that the idea of considering a high-dimensional limit of optimization dynamics using mean-field methodology to heuristically derive computational thresholds for important statistical recovery methods is interesting and may be conducive towards stronger theoretical results. The experiments demonstrating the accuracy of these predictions are very helpful in supporting the mathematical approach. A number of useful suggestions on presentation were made by the reviewers. The authors should make sure to incorporate these in their final version.


Decision: Accept (Poster)