Acceleration in Hyperbolic and Spherical Spaces
Authors: David Martínez-Rubio
Venue:  (2021)
Keywords: Riemannian optimization
acceleration
first-order methods

Abstract:     We further research on the acceleration phenomenon on Riemannian manifolds by introducing the first global first-order method that achieves the same rates as accelerated gradient descent in the Euclidean space for the optimization of smooth and geodesically convex (g-convex) or strongly g-convex functions defined on the hyperbolic space or a subset of the sphere, up to constants and log factors. To the best of our knowledge, this is the first method that is proved to achieve these rates globally on functions defined on a Riemannian manifold $\mathcal{M}$ other than the Euclidean space.
    Additionally, for any Riemannian manifold of bounded sectional curvature, we provide reductions from optimization methods for smooth and g-convex functions to methods for smooth and strongly g-convex functions and vice versa.

Under review as a conference paper at ICLR 2021
ACCELERATION SPACES
IN HYPERBOLIC AND SPHERICAL
Anonymous authors Paper under Houble-blind review
ABSTRACT
We further research on the acceleration phenomenon on Riemannian manifolds by introducing the first global first-order method that achieves the same rates as accelerated gradient descent in the Euclidean space for the optimization of smooth and geodesically convex (g-convex) or strongly g-convex functions defined on the hyperbolic space subset of the sphere, up to constants and log factors. To the best of our knowledge, this is the first method that is proved to achieve these rates globally functions defined on a Riemannian manifold M other than the Euclidean space. Additionally, for any Riemannian manifold of bounded sectional curvature, we provide reductions from optimization methods for smooth and g- convex functions to methods for smooth and strongly g-convex functions and vice versa.
INTRODUCTION
Acceleration in convex optimization is phenomenon that has drawn lots of attention and has yielded many important results, since the renowned Accelerated Gradient Descent (AGD) method of Nesterov (1983). Having been proved successful for deep learning Sutskever al. (2013), among other fields,
there have been recent efforts to better understand this phenomenon Allen Zhu & Orecchia (2017); Diakonikolas & Orecchia (019); (Su et al.] (2016); Wibisono al. (2016). These have yielded numerous new results going beyond convexity or the standard oracle model, in a wide varicty of settings AZuen-Zhu (017 2018a by: Allen Zhu & Orecchia 2015 y Allen Zhu al. (2016) Ahlen-Zhu Carmonn et al. (2017): Cohen et al. (2018); Cutkosky & Sarlós (2019), Diakonikolas & Jordan (2019) Diakonikolas & Orecchia (2018); Gasnikov et al. (2019); Wang et al. (2016). This surge of research that applies tools of convex optimization to models going beyond convexity has been fruitful. One these models is the setting of geodesically convex Riemannian optimization. In this setting. the function to optimize is geodesically convex (g-convex), ie. convex restricted to any geodesic (cf. Definition I.I).
et al. (2017) Carmon
Riemannian optimization, g-convex and non-g-convex alike, is extensive area of research. In recent years there have been numerous efforts towards obtaining Riemannian optimization algorithms that share analogous properties to the more broadly studied Euclidean first-order methods: deterministic
de Carvalho Bento et al. (2017); WWi et al. (2016); Zhang & Sra (2016), stochastic Hosseini & (2018), pariance-reduced (Sato al. (2017)
Sraj (2017); Khuzani & Li (2017); Tripuraneni
2019); Zhang et al. (016)) adaptive Kasai et al. (2019). saddle-point-ssaapp
Criscitiello & Boumal (2019). Sun et al. (2019): Zhang et al. (2018): Zhou et al. (2019): Criscitiello Boumal (2020).
and projection-free methods Weber & Sra (2017 (2017)2019) among others. Unsurprisingly Riemannian
optimization has found many applications in machine learning, including low-rank matrix completion
Cambier & Absil (2016); Heidel & Schulz (2018); Mishra & Sepulchre (2014); Tan et al. (2014);
Vandereycken (2013), dictionary learning Cherian & Sra (2017); Sun et al. (2017), optimization under orthogonality constraints Edelman et al. (1998), with applications to Recurrent Neural Networks
Lezcano-Casee 2 Ezzaao-Casade & Martinez-Ruut (2019), robust covariance estimation
in Gaussian distributions Wiesel (2012), Gaussian mixture models Hosseini & Sra (2015), operator
scaling Allen-Zhu et al. (2018), and sparse principal component analysis Genicot et al. (2015): 5) Huang
& Wei 2019b): Jolliffe al. (2003).

---

Under review as a conference paper at ICLR 2021
However, the acceleration phenomenon, largely celebrated in the Euclidean space, is still not under- stood in Riemannian manifolds, although there has been some progress on this topic recently (cf. Related work). This poses the following question, which is the central subject of this paper:
Can Riemannian first-order method enjoy the same rates as AGD in the Euclidean space?
In this work, we provide an answer in the affirmative for functions defined on hyperbolic and spherical spaces, up to constants depending on the curvature and the initial distance to an optimum, and up to log factors. In particular, the main results of this work are the following.
Main Results:
* Full acceleration. We design algorithms that provably achieve the same rates of convergence as AGD in the Euclidean space, up to constants and log factors. More precisely, we obtain the rates (LL/ and O" (VLL/ log(u/e)) when optimizing T-smooth functions that are, respectively, g-convex and j--ttrngly g-convex, defined on the hyperbolic space or subset of the sphere. The notation Ō(-) and O' (.) omits log(L/e) and log [/)x) factors, respectively, and constants. Previous approaches only showed local results Zhang & Sra (2018) or obtained results with rates in between the ones obtainable by Riemannian Gradient Descent (RGD) and AGD Ahn & Sra (2020). Moreover, these previous works only apply to functions that are smooth and strongly conveex and not to smooth functions that are only g-convex. As proxy, we design an accelerated algorithm under a condition between of convexity and guasar-comexitt in the constrained setting, which is of independent interest.
Reductions. We present two reductions for any Riemannian manifold of bounded sectional curvature. Given optimization method for smooth and g-convex functions they provide method for optimizing smooth and strongly g-convex functions, and vice versa. This allows to focus on designing methods for one set of assumptions only.
is often the case that methods and key geometric inequalities that apply to manifolds with bounded sectional curvatures curvature Grove et al. (199)); Zhang & Sra (2016] 2018). Consequently, our contribution is relevant not only because we establish an algorithm achieving global accelcration on functions defined on a manifold other than the Euclidean space, but also because understanding the constant sectional curvature case is an important step towards understanding the more general case of obtaining algorithms that optimize g-convex functions, strongly or not, defined on manifolds of bounded sectional curvature.
obtained from the ones existing for the spaces of constant extremal sectional
Our main technique for designing the accelerated method consists of mapping the function domain to subset of the Fuclidean space via geodesic map: a transformation that maps geodesies to geodesics. Given the gradient of a point x E M,, which defines a lower bound on the function that is linear over the tangent space of æ, we find a lower bound of the function that is linear over B, despite the map being non-conformal, deforming distances, and breaking convexity. This allows to aggregate the lower bounds easily. We believe that effective lower bound aggregation is key to achieving Riemannian acceleration and optimality. Using this strategy, along the lines of the one in Diakonikolas & Orecchia (2018) to define a continuous method that we discretize using an approximate implementation of the implicit Euler method, obtaining a method achieving the same rates as the Euclidean AGD, up to constants and log factors. Our reductions take into account the deformations produced by the geometry to generalize existing Euclidean reductions Allen Zhu & Hazan (016)); Allen Zhu & Orecchia (2017).
are able provide an algorithm
Basic Geometric Definitions. We recall basic definitions of Riemannian geometry that we use in this work. For a thorough introduction we refer to Petersen et al. (2006). A Riemannian manifold (M.g) is a real smooth manifold M equipped with metric g. which a smoothly varying inner product. For x E M and any two vectors v, w E T.M in the tangent space of M, the inner product
w), is g(v, w). For u E T.M, the norm is defined as usual ||v||= duf Vir, u).- Typically, is known given a or w, so we will just write (u. w) or |||||| if I is clear from context. A geodesic is a curve : [0, 1] + M of unit speed that is locally distance minimizing. A uniquely geodesic space is a space such that for every two points there is one and only one geodesic that joins them. In such a case the exponential map Exp,, T,M + M and inverse exponential map Exp,-" :M- + T,M well defined for every pair of points, and are follows. Given &, y E M, E T.M, and
2

---

Under review as a conference paper at ICLR 2021
geodesic of length ||o||| such that 70) = z, 711 y. 70() = e/||eil, we have that Expa (v) y and Exp, (y) v. Note, however, that (-) might not be defined for each E T.M. We denote by d(x,2) the distance between and y. Its value is the same as || Exp_ (v)ll. Exp="(t)] Given
2-dimensional subspace V C T,M, the sectional curvature at a with respect to is defined as the Gauss curvature of the manifold (V) at r.
Notation. Let .M be a manifold and let B RR. We denote by M + B geodesic map Kreyszig (1991), which is a diffeomorphism such that the image and the inverse image of a geodesic is a geodesic. Usually, given an initial point 2y of our algorithm, we will have h(z))) = O. Given a point x E M we use the notation 3-- h(xx) and vice versa, any point in B will use a tilde. Given two points x. y E M and a vector U E T.MM in the tangent space of x, we use the formal notation yu.y-2) def (v. J v) def (v, Exp, Ex)))(v)) Given a vector u E T.MM we call û E Rd the vector of the same norm such that {a + Xē E R+ @ + λö E B) (h(Exp, (Au) I C R+}. for some interval I. Likewise, given x and a vector e E Rd, we define v E T.M. Let x" be any minimizer of F: M + R. We denote by R 2 x(x a bound on the distance between x² and the initial point vo- Note that this implies that x² E Exp2,, (B( It), for the closed ball B(0, Rt S M. Consequently, we will work with the manifold that is subset of a d-dimensional complete and simply connected manifold of constant sectional curvature K. namely a subset of the hyperbolic space or sphere Petersen al. (2006), defined as Exp.., (B, with the inherited metric. Denote by H this manifold in the former case and S in the latter, and note that we are not making explicit the dependence on d. R and K. We want to work with the standard choice of uniquely geodesic manifolds Ahn & Sra 2020); Liu et al. (2117): Zhang & Sra 2016 2018). Therefore, in the case that the manifold is S, we restrict ourselves to R < T 7/2vK, K, so S is contained in an open hemisphere.
The big O notations O()) and (-) omit log( and log(L/p) p/) factors, respectively, and constant factors depending on R and K.
We define now the main properties that will be assumed on the function F to be minimized.
Definition 1.1 (Geodesic Convexity and Smoothness). Let F: : -M- + R be a differentiable function defined on a Riemannian manifold (M, g). Given L 2 μ > O, we say that F' is L-smooth, and respectively p-strongly g-convex, if for any two points x, E M, F satisfies
Fly) S F(x)+ + (VF(a), + d(x, y)² resp. F(y) 2 F(x) (VF()). 2) = y)²
d(z
We say F' is g-convex if the second inequality above, i.c. ju-strong g-convexity, is satisfied with μ O. Note that we have used the formal notation above for the subtraction of points in the inner product.
Comparison with Related Work. There are a number of works that study the problem of first- order acceleration in Riemannian manifolds of bounded sectional curvature. The first study is Liu et al. (2017). In this work, the authors develop accelerated method with the same rates as AGD for both g-convex and strongly g-convex functions, provided that at each step a given nonlinear equation can be solved. No algorithm for solving this equation has been found and, in principle, it could be intractable or infeasible. In Alimisis et al. (2019) a continuous method analogous to the continuous approach accelerated methods is presented, but it is not known if there exists an accelerated discretization of it. In Alimisis et al.] (2020), an algorithm presented is claimed to enjoy an accelcrated rate of convergence, but fails to provide convergence when the function value gets below a potentially large constant that depends on the manifold and smoothness constant. In Huang Weil (2019a) an accelerated algorithm is presented but relying on strong geometric inequalities that are not proved to be satisfied. IZhang& & Sra (2018) obtain a local algorithm that optimizes L-smooth and y-strongly g-convex functions achieving the same rates as AGD in the Euclidean space, up to constants. That is. the initial point needs start close to the optimum, ((p/L) close, to be precise. Their approach consists of adapting Nesterov's 's estimate sequence technique by keeping a quadratic on M that induces on M regularized lower bound on F(x*) via Exp,,, (.). They aggregate the information yielded by the gradient to it, and use a geometric lemma to find a quadratic in T whose induced function lower bounds the other one. Ahnn & Sra (020)) generalize the previous algorithm and, by using similar ideas for the lower bound, they adapt it to work globally, obtaining strictly better rates than RGD, recovering the local acceleration of the previous paper, but not achieving global rates comparable to the ones of AGD. In fact, they prove that their algorithm eventually decreases the function value at a rate close to AGD but this can take as many iterations as the ones needed by RGD to minimize the function. In our work, we take a step back and focus
3

---

Under review as a conference paper at ICLR 2021
on the constant sectional curvature case to provide a global algorithm that achieves the same rates as AGD, up to constants and log factors. It is common to characterize the properties of spaces of bounded sectional curvature by using the ones of the spaces of constant extremal sectional curvature Grove et al. 1997); Zhang & Sra (2016) 2018), which makes the study of the constant sectional curvature case critical to the development of full accelerated algorithms in the general bounded sectional curvature case. Additionally, our work studies g-convexity besides strong g-convexity.
Another related work is the approximate duality gap technique Diakonikolas & Orecchia (2019). which presents a unified view of the analysis of first-order methods for the optimization of convex functions defined in the Euclidean space. It defines a continuous duality gap and by enforcing a natural invariant, it obtains accelerated continuous dynamics and their discretizations for most classical first-order methods. A derived work DDiakonikllss & Orecchia (2018) obtains acceleration in fundamentally different way from previous acceleration approaches, namely using an approximate implicit Euler method for the discretization of the acceleration dynamics. The convergence analysis of Theorem 2.4 is inspired by these two works. We will see in the sequel that, for our manifolds of interest, g-convexity is related to a model known in the literature as quasar-convexity or weak-quasi- convexity Guminov & Gasnikov (017)) Hinder et al. (2019): Nesterov et al. (2018).
2
ALGORITHM
We study the minimization problem min F(x) with a gradient oracle, for a smooth function F: .M- - R. that is g-convex strongly g-convex. In this section, M refers to manifold that can be H or S, i.e. the subset of the hyperbolic space or sphere Exp,,, (B(0, R)), for an initial point zg- For simplicity, we do not use subdifferentials we assume F M + R is differentiable function that defined over the manifold of constant sectional curvature M def Exp,, (B(0, R)), for an R' > R. and we avoid writing F : M'' + R. We defer the proofs of the lemmas and theorems in this and following sections to the supplementary material. We assume without loss of generality that the sectional curvature of M is K E {1,-1}, since for any other value of K and any function F : MM- + IR defined on such a manifold, we can reparametrize F by a rescaling, so it is defined a manifold of constant sectional curvature K {1, -1}. 'he parameters I,, f and R are rescaled accordingly as a function of K, cf. Remark C.1 We denote the special cosine by (.).) which is cos(.) if K = 1 and cosh(.) if K 1. We define X' h(M) B C R.d. We use classical geodesic maps for the manifolds that we consider: the Gnomonic projection for S and the Beltrami-KIi Klein projection for H. Greenberg (193)). They map an open hemisphere and the hyperbolic space of curvature K {1, 1 results from the following characterization Greenberg (1993). Let ă ÿ E B be two points. Recall that we denote x = (Z), y - (7) E .M. Then we have that d(x, v), the distance between and y with the metric of M, satisfies
} to B = R" and B = B 1) S IRd, respectively. We will derive our
1+ K 1)
CK (d(x,)))
(1)
K
Observe that the expression is symmetric with respect to rotations. In particular, the symmetry implies X is a closed ball of radius R, with (R = (1 + K R22) 1/2.
Consider point x E .M and the lower bound provided by the g-convexity assumption when computing (xx). Dropping the μ term in case of strong g- g-convexity, this bound is linear over T.M. We would like our algorithm to aggregate effectively the lower bounds it computes during the course of the optimization. The deformations of the geometry make it a difficult task, despite the fact that we have simple description of each individual lower bound. We deal with this problem in the following way: our approach is to obtain a lower bound that is looser by constant depending on R. and that is linear over B. In this way the aggregation becomes easier. Then, we are able to combine this lower bound with decreasing upper bounds in the fashion some other accelerated methods work in the Euclidean space Allen Zhu & Orecchia (2017) ): Diakonikolas & Orecchia (2018) 2019); Nesterov (1983). Alternatively, we can see the approach in this work as the constrained non-convex optimization problem of minimizing the function f X R, 7 F(h-1())
minimize f(Ø), for 7 E X.
In the rest of the section, will focus the g-convex case. For simplicity, instead of solving the strongly g- g-convex case directly in an analogous way by finding a lower bound that is quadratic over B. we rely on the reductions of Section 3 to obtain the accelerated algorithm in this case.
4

---

Under review as a conference paper at ICLR 2021
The following two lemmas show that finding the aforementioned linear lower bound is possible, and defined as a function of V (ā). We first gauge the deformations caused by the geodesic map h. Distances are deformed, the map h is not conformal and, in spite of it being a geodesic map, the image of the geodesic Exp,, (XV Fx)) is not mapped into the image of the geodesic ş + AV fØ²) ie. the direction of the gradient changes. We are able to find the linear lower bound after bounding these deformations.
Lemma 2.1. Let z, E M be two different points, and in part b) different from 2o. Let ā be the angle Lūgēy, formed by the vectors To and ÿ-ã. Let a be the corresponding angle between the vectors Exp= (Za) and Exp, (t). Assume without loss of generality that ă E span span(c1) and f(() E span(é1 62) for the canonical orthonormal basis {2)) Let e, T,M be the unit vector such that h maps the image of the geodesic Exp, to the image of the geodesic ã + Xe d, for = =,....,,, and X, x2 2 0. Then, the following holds.
Distance deformation:
d(x v)
KC
S K
S K.
1 Ø7
b) Angle deformation:
+ K K
sin(a) = sin(a)
cos(a) = cos(aa)
K sin
+ K|| sin"
c) Gradient deformation:
VF(x) = (1 (1+ + K
and e, Le for forit) jj.
And i &T,M is a vector normal to F(r),, then normal Vf(()).
The following uses the deformations described in the previous lemma to obtain the linear lower bound on the function, given a gradient at a point T. Note that Lemma 2. implies that we have In the proof we lower bound, generally,
(ā) T Σ) if and only if (VF(z). y z) linear functions defined on T&M by linear functions in the Euclidean space B. This generality allows to obtain result with constants that only depends on R.
Lemma 2.2. Let F -M- + R be a differentiable function and let f = F h- Then, there are constants J/u 7pp (0, 1] depending on such that for all x, M satisfying (V 1) # we have:
1 Jp (V((T.. σ) 7n
VF(x).V-2 x)
<
(2)
In particular, if F is g-convex we have:
f(ō) + 1 (VS(), In f(ø) + 7p (V (V) 2)
1()
VV(V -) <
(3)
if (V (2). 8) 2.
The two inequalities in (3) show the linear lower bound. Only the first one is needed to bound f(ă*) = f(=*). The first incquality applied to y = .² defines a model known in the literature as quasar-convextie
Guminov & Gasnikov (207): Hinder et (2019): Nesterov et al. (2018), for which accelerated algorithms exist in the unconstrained case, provided smoothness is also satisfied. However, to the best of our knowledge, there is no known algorithm for solving the constrained case in an accelerated way. The condition in (3) is, trivially, a relaxation of convexity that is stronger than quasar-convexity. We will make use of (3) in order to obtain accelcration in the constrained setting. This is of independent interest. Recall that need the constraint to guarantce bounded deformation due to the geometry. We also require smoothness of f. The following lemma shows that is smooth as F up to constant depending R.
or weak-quasi-convent
Lemma 2.3, Let F M + R be an L-smooth function and f = F h Assume there is a point x² E M such that V F(x") = 0. Then f is O (L.. s.m-moothh
5

---

Under review as a conference paper at ICLR 2021
Using the approximate duality gap technique Diakonikolas & Orecchia (2019) obtain accelerated continuous dynamics, for the optimization of the function f. Then we adapt AXGD to obtain an accelerated discretization. AXGD Diakonikolas & Orecchia (0188) is method that is based on implicit Fuler discretization of continuous accelerated dynamics and is fundamentally different from AGD and techniques Linear Coupling Alllnn Zhu & Orecchia (2017) or Nesterov's estimate sequence Nesterov (1983). The latter techniques use a balancing gradient step at each iteration and our use of looser lower bound complicates guaranteeing keeping the gradient step within the constraints. We state the accelerated theorem and provide a sketch of the proof in inSecciion 2.1]
Theorem 2.4. Let Q C Rd be a convex set of diameter 2R. Let f Q + IR be an L-smooth i-smmooth,unctiio function satisfying 3 with constants Yn. "ip (0, 1]. Assume there is point i" E Q such that f
Then, we can obtain an E-minimizer of using Ö( L/ queries to the gradient oracle of s.
Finally, we have Riemannian acceleration direct consequence of Theorem 2.4 Lemma 2.2 and
Lemma 2.3]
Theorem 2.5 (g-Convex Acceleration). Let F M + R be an L-smooth and g-convex function and assume there is a point x² E M satisfying F=(=*) = O. Algorithm computes a point 2t M
satisfying F(x+) - F(x*) < e using Lfs) queries to the gradient oracle.
We observe that if there is geodesic map mapping manifold into convex subset of the Euclidean space then the manifold must necessarily have constant sectional curvature, ef. Beltrami's Theorem Busemann & Phadke (9844) Kreyszig (999T) This precludes straightforward generalization from our method to the case of non- non-constant bounded sectional curvature.
Algorithm 1 Accelerated g-Convex Minimization
Input: Smooth and g-convex function .M + R. for M = or M
Initial point zg; Constants L, 7p. Ta. Geodesic map h satisfying ( and h(zo)) = 0.
Bound on the distance to minimum R > d(xo,x)). Accuracy and number of iterations t.
1: X der h(Exp=,, (B(0, R))) C B; f del Foh-1 and (()
der ||
2: ăo + Vu(īo); Ao +-
for i from 0 to do
4: 0;-1 + (i 1
5:
A+11 f A, + a:+1
6:
A + BinaryLinnSearch(fi (ī,, E,, J, X, 0:41, Ai, L, 7os 7p) (cf. Algorithm in Appendix A
7:
+ (1 - + AV (2:)
8:
4 + Σ - (a,+1/7m1) (f
9:
344 + (1-) + AV
V arg mex =11) II (x)
10: 2,11 4 (at+1/%u) V (((++)
11: end for
12: return Tt-
2.1 SKETCH OF THE PROOF OF THEOREM 2.4]
Inspired by the approximate duality gap technique Diakonikolas Orecchia (219)), let a be an increasing function of time f, and denote A, = Ste da, = Sr å,d We define continuous method that keeps solution é, along with differentiable upper bound U, on f(x) and lower bound Le on f(i"). In our case differentiable so we can just take Ug = f(z)). The lower bound comes from
f(ā)) Se. (ax
1t L
LV T+)daa,
(4)
A. after applying some desirable modifications, like regularization with 1-strongly convex function
A.
z and removing the unknown i" by taking minimum over X. Note (4) comes from averaging (3) for ÿ -.. Then, if we define the gap G2 = U, L, and design method that forces G to be non-increasing, we can deduce f(x,) - fx*) < G, < a, Gta/ /aa By forcing d (a,GG) = 0, we naturally obtain the following continuous dynamics, where
z mirror point and is the Fenchel

---

Under review as a conference paper at ICLR 2021
dual of 1, cf. Definition A.2
1 ((z))
V2h (2))
Ft. Ctt
Cx
21o = Ve(ttt)
(5)
7/
7n
We note that except for the constant Yn. these dynamics match the accelerated dynamics used in the optimization of convex functions Diakonikolas & Orecchia (2019) 2018); Krichene et al. (2015). The AXGD algorithm,Diatee Diiaknikolls Orecchia (2018), designed for the accelerated optimization of convex functions, discretizes the latter dynamics following approximate implementation of implicit Euler discretization. This has the advantage of not needing a gradient step per iteration to compensate for some positive discretization error. Note that in our we must use (3) instead of convexity for a discretization. We are able to obtain the following discretization coming from an approximate implicit Fuler discretization:
Xi A
3,4;
E. a4t1/To
V (Z)) -= 2; ai+1 f((())
A
7a
(6)
i++1= A.t B. +
V (5);
ait 241 E, 7a
(((++))
A.9. 4141/0
where 9t E hyp, 1/7m] is parameter, To X is an arbitrary point, 20 = (āo) and now a is discrete measure and d; is a weighted sum of Dirac delta functions d; = =i=
EE= a:d(t (to - Compare (6) with the discretization in AXGD Diakonikolas & Orecchia (2018) that equal to our discretization but with no in or k. Or equivalently with 2 1/7h and with "n for the mirror descent updates of S, and ž441. However, not having convexity, in order to have per-iteration discretization error less than E/Ar, we require 9 to be such that ã,41 satisfies
0,41 f(;++1) f(ă.) S % (), - _,) +E,
where é is chosen that the accumulated diseretization error is =/2, after having performed the steps necessary to obtain an 2/2 minimizer. We would like to use (3) to find such a % but we need to take into account that we only know _z+1 a posteriori. Indeed, using (3) we conclude that setting 7 to 1/% or Pp then we either satisfy (7) or there is point 2/ E (7p, 1/%)) for which (V 3441 z = O, which satisfies the equation for é Then, using smoothness of f. existence of x= (that satisfies V fx(=") = 0), and boundedness of X' we can guarantee that binary search finds point satisfying 7 in (log (Lin,,L))) iterations. Each iteration of the binary search requires to run (6). that is, one step of the discretization. Computing the final discretization error, we obtain acceleration after choosing appropriate learning rates a; Algorithm contaiins the pseudocode of this algorithm along with the reduction of the problem from minimizing F to minimizing f. We chose (T) 2 | as our strongly convex regularizer.
3 REDUCTIONS
The construction of reductions proves to be very useful in order to facilitate the design of algorithms in different settings. Moreover, reductions are helpful tool to infer new lower bounds without extra ad hoc analysis. We present two reductions. We will see in Corollary 3.2 and Example 3.4 that one can obtain full accelerated methods to minimize smooth and strongly g-convex functions from methods for smooth and g-convex functions and vice versa. These are generalizations of some reductions designed to work in the Euclidean space Allen Zhu & Hazan (2016); Allen Zhu & Orecchial (2017). The reduction to strongly g-convex functions takes into account the effect of the deformation of the space on the strong convexity of the function (x) = d(x,, //2 for xr y E M. The reduction to g g-convexity requires the rate of the algorithm that applies to g-convex functions to be proportional to the distance between the initial point and the optimum d(xro, x²). The proofs of the statements in this section can be found in the supplementary material. We will use Timens and Time(-) to denote the time algorithms Ans and A below require, respectively, to perform the tasks we define below.
Theorem 3.1. Let M be Riemannian manifold, let F . R be an L-smooth and u-strongly g-convex function, and let x" be its minimizer. Let Zu be a starting point such that d(x0, x*) < R. Suppose we have an algorithm Ans to minimize F. such that in time T = Timeue (L, μ. R) produces a point ir satisfying F(iT) F(x*) S f. d(xo, /2/2 Then we can compute an S-minimizer of F in time OTTimens (T., H, R) log( R p(p()))
Theorem 3.1 limplies that we forget about the strong g-convexity of a function and we treat as just g-convex can in stages algorithm designed for optimizing g-convex functions. The
7

---

Under review as a conference paper at ICLR 2021
fact that the function is strongly g-convex is only used between stages, as the following corollary shows by making use of of|Algorithm I]
Corollary 3.2. We can compute an e-minimizer of L-smooth and y-strongly 8-convex fumction queries to the gradient oracle, where M = S M H.
F.M- - R in
We note that in the strongly convex case, by decreasing the function value by a factor we can guarantee we decrease the distance to x² by another factor, can periodically recenter the geodesic map to reduce the constants produced by the deformations of the geometry, see the proof of Corollary 3.2 Finally, we show the reverse reduction.
Theorem 3.3. Let M be a Riemannian manifold of bounded sectional curvature, let F :M + RR be an L-smooth and g-convex function, and assume there is point x² M such that VF(x=) O. Let No be a starting point such that x") S R and let A satisfy F(Fo) - F(x*) ) S A. Assume we have an algorithm A that given an L-smooth and p-stroonly g-convex function F. - - IR, with minimizer in Expao (B(0, R)), and any initial point Eo E . produces a point & E Expao (B(0, R)) in time T = Time L., μ1, M, R) satisfying F()) minzeM F(x)= S (F(2o) mingeM Fxx))/4. Let T [loge / + 1. Then, we can compute an E-minimizer in time Et= Time(L- 2 'AK R/ R2; 2 A R2, M, R). where KRR and KR are constants that depend on R and the bounds on the sectional curvature of M.
Example 3.4. Applying reduction Theorem 3.3 the algorithm in Corollary 3.2
we can optimize L-smooth and g-convex functions defined on H or S with a gradient oracle complexity of Õ(L/ V+).
Note that this reduction cannot be applied to the locally accelerated algorithm in (Zhang & Sra 2018).
that we discussed in the related work section. The reduction runs in stages by adding decreasing fi-Strongly convex regularizers until we reach μı; = Oss). The local assumption required by the algorithm in (Zhang & Sra 2018) on the closeness to the minimum cannot be guaranteed. In (Ahn & Sral (020), the authors give an unconstrained global algorithm whose rates strictly better than RGD. The reduction could be applied to a constrained version of this algorithm to obtain a method for smooth and g-convex functions defined on manifolds of bounded sectional curvature and whose rates are strictly better than RGD.
4 CONCLUSION
In this work we proposed a first-order method with the same rates as AGD, for the optimization of smooth and g-convex or strongly g-convex functions defined on manifold other than the Euclidean space, up to constants and log factors. We focused on the hyperbolic and spherical spaces, that have constant sectional curvature. The study of geometric properties for the constant sectional curvature case can be usually employed to conclude that a space of bounded sectional curvature satisfies property that is in between the ones for the cases of constant extremal sectional curvature. Several previous algorithms have been developed for the optimization in Riemannian manifolds of bounded sectional curvature by utilizing this philosophy, for instance Ahn & Sra (2020); Ferreira et al. (2019); Wang al. (2015); Zhhng & Sra 60 2018). In future work, we will attempt to use the techniques and insights developed in this work to give an algorithm with the same rates as AGD for manifolds of bounded sectional curvature.
The key technique of our algorithm is the effective lower bound aggregation. Indeed, lower bound aggregation is the main hurdle obtain accelerated first-order methods defined on Riemannian manifolds. Whereas the process of obtaining effective decreasing upper bounds on the function works similarly as in the Euclidean space- the same approach of locally minimizing the upper bound given by the smoothness assumption is task. We usually want a simple lower bound such that it, or a regularized version of it, can be easily optimized globally. We also want that the lower bound combines the knowledge that the g-convexity or g-strong convexity provides for all the queried points, commonly an average. These Riemannian convexity assumptions provide simple lower bounds, namely linear or quadratic, but each with respect to each of the tangent spaces of the queried points only. The deformations of the space complicate the aggregation of the lower bounds. Our work deals with this problem by finding appropriate lower bounds via the use of geodesic map and takes into account the deformations incurred to derive fully accelerated algorithm. We also needed to deal with other technical problems. Firstly,
obtaining adequate lower bounds proves to be difficult
8

---

Under review as a conference paper at ICLR 2021
needed a lower bound the whole function and not only F(x*), for which we had construct two different linear lower bounds, obtaining a relaxation convexity. Secondly, we had to use an implicit discretization of an accelerated continuous dynamics, since at least the vanilla application of usual approaches like Linear Coupling Allen Zhu & Orecchial (2017) or Nesterov's 's estimate sequence Nesterov (1983). that can be seen forward Fuler discretization of the accelerated dynamics combined with a balancing gradient step Diakonikolas & Orecchia (2019), did not work in our constrained case. We interpret that the difficulty arises from trying keep the gradient step inside the constraints while being able to compensate for lower bound that is looser by a constant factor.

---

whw.lleeennllaaatttt Under review as a conference paper at ICLR 2021
REFERENCES
Kwangjun Ahn and Suvrit Sra. From Nesterov's estimate sequence to riemannian acceleration. arXiv preprint arXiv:2001.0es 08886, 2020. URL htKLLttts///ariioorr//abas wttp://wwrrrrab/////...o..
Foivos Alimisis, Antonio Orvicto, Gary Bécigneul, and Aurelien Lucchi. A continuous- cittuuuuus-tmmeeeeee perspec- tive for modeling acceleration riemannian optimization. arXiv preprint arXiv: 10782, 2019. URL https::/arsiv.org// abs/ 1910. 10782.
Foivos Alimisis, Antonio Orvicto, Gary Béeigneul, and Aurelien Lucchi. Practical accelerated optimization on riemannian manifolds. arXiv preprint WiXiv:2002.04/44 2020. URL htips:
//aaxii.orgg/bbs/200000444 2444.0444.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. J. Mach. Learn. Res., 18:221:1-221:511 2017. URL http://mllrrrr///aaaapp v 11-416...mm
Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than SGD. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 2680-2660 2691, 201 8a. URL than-sgd.
http://paprss.nips... cecpipps.pppppppe paper///33333 1at3--ntasha--a f-fater--oon www.see--oo-cooeee-oooee catn--cooexooppiizatiiie
Zeyuan Allen-Zhu Katyusha X: practical momentum method for stochastic sum nonconvex optimization. Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, pp. 179-185, 2018b. URL http://pnocedingg....rrrppp
Zeyuan Allen Zhu and Elad Hazan. Optimal black-box reductions between optimiza- tion objectives. In Advances in Neural Information Processing Systems 29: An- nual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spuin, pp. 1606-1614, 2016. URL http://ppprrsnissccc///ee 6364-optimal ciciiall-black-Be bolack-box-ii reduuctiss between-wwee...e......b..bbeeeee www.beenn-ooiiiiitiitneee hptpr--ooppiiiaatiooooeectteee
Zeyuan Allen Zhu and Lorenzo Orecchia. Nearly-linear time positive LP solver with faster con- vergence rate. In Proceedings of the Forty-Seventh Annual ACM Symposium Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pp. 229-236, 2015. doi: 10.1 10.1145/2746539.276666 27477777733 URL
Zeyuan Allen Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Jamuary 9-11, 2017, Berkeley, CA, USA, pp. 3:1-3:22, 2017. doi: I0.4230/LIPPcss.TCS.. 2017.3.
URL https://doi.org/
Zeyuan Allen Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In Proceedings of the 33nd International Conference Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pp. 1110-1119, 2016. URL http:://pmoceeddnggssl...ppppep v4s waw.lleennhuuoohhieee
Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In 58th IEEE Annual Symposium Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 890-901, 2017. doi: 10.1109/
FOCCS2001.88. URL https://doi.org 10. 200.F/0SS.20..8..7.
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 172-181, 2018.
Herbert Busemann and Bhalchandra Phadke. A general version of Beltrami's theorem in the large. Pacific Journal of Mathematics, 15(2)):99-3115 1984.
Léopold Cambier and Pierre-Antoine Absil. Robust low-rank matrix completion by riemannian optimization. SIAM J. Scientific Computing, 38(5), 2016. doi: 10.1137/15M1025153. URL
https://doi.or//10.. 155
10

---

Mochen18a.htm Under review as a conference paper at ICLR 2021
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. "Convex until proven guilty": Dimension-Fe free acceleration of gradient descent on non-convex functions. In Proceedings of the 34th International Conference Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 654-663, 2017. URL http:// www.ceediings.ml..reere.
carmon 7a.html.
Anoop Cherian and Suvrit Sra. Riemannian dictionary learning and sparse coding for positive definite matrices. IEEE Trans. Neural Networks Learn. Syst., 28( (2))2298 2871, 2017. doi: 10.100//NNLSS2016226013333 URL https://dooi.org//// 10. wtw.://///...11//TNNNN.....
Michael Cohen, Jelena Diakonikolas, and Lorenzo Orecchia. On acceleration with noise-corrupted gradients. In Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 1018-1027, 2018. URL http://proceedingsmmtprrrsss/
Chris Crisciticllo and Nicolas Boumal. Efficiently escaping saddle points manifolds. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 5985-5995, 2019, URL http:/ppppeeeiisssccpapppeeeeeee -eficiinnty--eeaapiiii saieing--ddle---ed coadle-points-one on-manifolss.
Chris Criscitiello and Nicolas Boumal. An accelerated first-order method for non-convex optimization manifolds. arXiv preprint arXiv:2008. 022552, 2020.
Ashok Cutkosky and Tamás Sarlós. Matrix-free preconditioning in online learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 1455-1464, 2019. URL http:// pin.reddingg..l.prrrss// v97/ cutkossy 99ml...
Glaydston de Carvalho Bento, Orizon P. Ferreira, and Jefferson G. Melo. Peration-complext of gradient, subgradient and proximal point methods on riemannian manifolds. J. Optim. Theory Appl., 173(2)544-566) 2017. doi: 10.1007//10057-01---0033 URL https:///oi.org/ 10. 1007/ s10957-0177-1093-4
Jelena Diakonikolas and Michael I. Jordan. Generalized momentum based methods: A hamiltonian perspective. CoRR, abs/1906.00445 2019. URL http://arxii.orr/ abs/ / 1906. 00436.
Jelena Diakonikolas and Lorenzo Orecchia. Accelerated extra-gradient descent: A novel accelerated first-order method. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pp. 23:1-23:19, 2018. doi: 10.4230/LIPIe.ITCSS
2018.23. URL https://doi.on org/
Jelena Diakonikolas and Lorenzo Orecchia. The approximate duality gap technique: A unified theory of first-order methods. SIAM Journal on Optimization, 29(1):660-689 2019. doi: 10.1137/ 18M1 URL https://doi.org// 10.p/10.110 1ttp:////0..13/81111311111
Alan Edelman, Tomás A. Arias, and Steven Thomas Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Analysis Applications, 20(2):303-333, 1998. doi: 10.1 10.1137775089547999999955 URL https://doi.org/ 1ttt://g//..1117//099579999//8/9 21113///00089557999999555
OP Ferreira, MS Louzeiro, and LF Prudente. Gradient method for optimization riemannian manifolds with lower bounded curvature. SIAM Journal on Optimization, 29(4):2517-2541 2019.
Alexander Gasnikov, Pavel E. Dvurechensky, Eduard A. Gorbunov, Evgeniya A. Vorontsova, Daniil Selikhanovych, César A. Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near optimal methods for minimizing convex functions with lipschitz Sp$-th th derivatives. In Conference Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pp. 1392-1393, 2019. URL http:// http:://poceediggg..lrppp v99/ gasnikov html.
Matthieu Genicot, Wen Huang, and Nickolay T. Trendafilov. Weakly correlated sparse components with nearly orthonormal loadings. In Geometric Science of Information Second International Conference, GSI 2015, Palaiseau, France, October 28-30, 2015, Proceedings, pp. 484-490, 2015. doi: 00077/978-3-319-25000
URL https://doi.org/ 10. 01177797783319-250000
Marvin J Greenberg. Euclidean and non -n-cudeid geometries: Development and history. Macmillan, 1993.
11

---

Under review as a conference paper at ICLR 2021
Karsten Grove, Peter Petersen, and Silvio Levy. Comparison geometry, volume 30. Cambridge University Press, 1997.
Sergey Guminov and Alexander Gasnikov. Accelerated methods for alpha-weatty-quaai-connes problems. arXiv preprint arXiv: 2017. URL http:://arriiorryddd//7/0001111
Gennadij Heidel and Volker Schulz. A riemannian trust-region method for low-rank tensor completion. Numerical Lin. Alg. with Applic., 25(6), 2018. doi: 10.1002/nla.215. URL https://doi.org// 10.
1002/nla.2175.
Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. CoRR, abs/1906. 1985, 2019. URL http://arsiiv.or//abbb 1906. 11985.
Reshad Hosseini and Suvrit Sra. Matrix manifold optimization for gaussian mixtures. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 910-918, 2015. URL http://appprnnssssccpppppppppppp 1-tisli--------------- siciiii-annifodd-oooo wotpoodddddiiiitiionoiooo p gaussian-mixte mixtures.
Reshad Hosseini and Suvrit Sra. An alternative to EM for gaussian mixture models: Batch and stochastic riemannian optimization. CoRR, abs/ 706.03367, 2017. URL http://arxiiv.or//abbs 1706. 03267.
Wen Huang and Ke Wei. Extending FISTA to riemannian optimization for sparse pea. arXiv preprint 1909.099990 2019a. URL http:://aazivv.or//aaaaao 1909.05485.
Wen Huang and Ke Wei. Riemannian proximal gradient methods. arXiv preprint arXiv:1909.06065 2019b. URL
0609006065
lan T Jolliffe, Nickolay Trendafilov, and Mudassir Uddin. A modified principal component technique based on the lasso. Journal of computational and Graphical Statistics, 12(3):531-547, 2003.
Jürgen Jost and Jeurgen Jost. Riemannian geometry and geometric analysis, volume 42005. Springer, edition, 2008
Hiroyuki Kasai, Pratik Jawanpuria, and Bamdev Mishra. Riemannian adaptive stochastic gradient algorithms matrix manifolds. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 3262-3271, 2019. URL http:// proc://pgseeed.s.mmrr... mwr.press/////peoommm wttpee/ss/////// 997/kasai (aasailla.hiin html.
Masoud Badiei Khuzani and Na Li. Stochastic primal-dual method on riemannian manifolds of bounded sectional curvature. In 16th IEEE International Conference on Machine Learning and Applications, ICMLA 2017, Cancun, Mexico, December 18-21, 2017, pp. 133-140, 2017. doi: 10.1 10.1109/CMMA.2211.0000 167. URL https:/dcii.ng//01100////A11..10
E. Kreyszig. Differential Geometry. Differential Geometry. Dover Publications, 1991. ISBN 9780486667218. URL http:://bbook.oooggl...ooo httpee////oooo//dt///////o
Walid Krichene, Alexandre M. Bayen, and Peter L. Bartlett. Accelerated mirror descent in continuous and discrete time. In Advances Neural Information Processing Systems 28: Annual Conference Neurul Information Processing Sysiems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2453, 2015. URL http://papers.iiss.cccppppp
5843-acceles mineeeeerrtedmmirrr---eeeeee wewe-dddee-eeneettnieeee in- can--continuuus--e and discrete- time.
Mario Lezcano-Casado. Trivializations for bradient-based optimization on manifolds. In Advances in Neural Information Processing Systems 32: Annual Conference on
Neural Information Processing Systems 2019. NeurIPS 2019, 8-14 December 2019. Vancouver, BC, Canada, pp. 9154-9164, 2019. URI. http://pupers.nipsscc/pppe
91 9 cooo-gradient-o gradient-basdd-ppieeee bussed-prtimizationn on- on-manifolds.
Mario Lezcano-Casse Casado. Curvature-dependee global convergence rates for optimization on manifolds of bounded geometry. arXiv preprint arXiv:2008.025/1 2020.
12

---

Under review as a conference paper at ICLR 2021
Mario Lezcano- Lezcano-Casado and David Martinez-Rubio Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In Proceedings of the 36th Interna- tional Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 3794-3803, 2019. URL proee////ceeeednggss.m. www.llrrees//////eeeee/e 97//eezcano-caaaal htm..
Yuanyuan Liu, Fanhua Shang, James Cheng. Hong Cheng, and Licheng Jiao. Accelerated first-order methods for geodesically convex optimization on riemannian manifolds. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 4868 4877, 2017.
Bamdev Mishra and Rodolphe Sepulchre. R3MC: A riemannian three- algorithm for low-rank matrix completion. In 53rd IEEE Conference on Decision and Control, CDC 2014, Los Angeles, CA, USA, December 15-17, 2014, pp. 1137-1142, 2014, doi: N0.1009/CDDC2221447333555 URL https://doi.or// 10. 109/
Yurii Nesterov. A method of solving a convex programming problem with convergence rate o(1/k2).
In Soviet Mathematies Doklady, volume 27, pp. 372-376, 1983.
Yurü Nesterov, Alexander Gasnikov, Sergey Guminov, and Pavel Dvurechensky. Primal-dual accelcrated gradient descent with line search for convex and nonconvex optimization problems. arXiv preprint arXiv: 0ee.i0009.0.990 2018. URL http:://arxiivorr//aa///////// 1809.05899
Peter Petersen, S Axler, and KA Ribet. Riemannian geomelry, volume 171. Springer, 2006.
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gradient. CoRR, abs/1702.05594, 2017. URL http://arziiv.or//abs/ 1702.05594
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gradient
algorithm with retraction and vector transport. SIAM Journal on Optimization, 1442):144-1147,, 2019. doi: 10.1 71777111111 16787. URL https://
10. 137/ 1777///111655
Weijie Su, Stephen P. Boyd, and Emmanuel J. Candès. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. J. Mach. Learn. Res., 11553:33 2016. URL wttp://rrr/pppre/////5----000 html.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere II: recovery by riemannian trust-region method. IEEE Trans. Inf. Theory, 63(2):885-914, 2017. doi: 10. 10.1109/T 2016.2632149, URL hhlps://doi.nr org/ 10.1 1099TTT.20166263222
Yue Sun, Nicolas Flammarion, and Maryam Fazel. Escaping from saddle points rieman- nian manifolds. In Advances in Neural Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 7274-7284, 2019. URL http://papers.mips.co paper! 8948- Sei8--scaping--ron saddle- sinill--ponnt--aaee on- caamaannian-mmanifon
Iya Sutskever, James Martens, George E. Dahl, and Geoffrey E. Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, pp. 1139-1147, 2013. URL
www.:reeddinnss..pprrsss.. / himl.
Mingkui Tan, Ivor W. Tsang, Li Wang, Bart Vandereycken, and Sinno Jialin Pan. Riemannian pursuit for big matrix recovery. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pp. 1539-1547, 2014. URL http: parroceedings.mlrpreeee pttp:pree///////a/// v32/tanl1e h4....
Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael I. Jordan. Averaging stochastic gradient descent on riemannian manifolds. CoRR, abs/1 882.09922 28, 2018. URL htt:://rxivv.r//
Bart Vandereycken. Low-rank matrix completion by riemannian optimization. SIAM Journal on Optimization, 23(2):1214-1236 2013. doi: 10.1137/1 10845768. URL https:://oi.orrg///////// 10..g//00113/111 110845768.
13

---

Under review as a conference paper at ICLR 2021
Di Wang. Satish Rao, and Michael W. Mahoney. Unified acceleration method for packing and covering problems via diameter reduction. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 50:1-50: 13, 2016. doi: 11..0WL.P.cs..CCAPP22200
URL https:://di.oorrr///////
X. M. Wang, C. Li, and J. C. Yao. Subgradient projection algorithms for convex feasibility on riemannian manifolds with lower bounded curvatures. Optim. Theory Appl. 202(222 2015. doi: 10.7007//0095--01440000
URL http://ooo0000000000000000000000
Melanie Weber and Suvrit Sra. Frank-wolfe methods for geodesically convex optimization with application to the matrix geometric mean. CoRR, abs/1710.107700, 2017. URL http://urxiv.or// abs/1710.10070.
Melanie Weber and Suvrit Sra. Nonconvex stochastic optimization on manifolds via riemannian frank-wolfe methods. CoRR, abs/1910.04194, 2019. URL http::/arxivvorg/ abbss///wwirr///////////bss/ 9494.4494.
Ke Wei, Jian-Feng Cai, Tony F Chan, and Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. arXiv preprint abs/ 260366603000
2016. URL, htpps://rrxai/
Andre Wibisono, Ashia C. Wilson, and Michael I. Jordan. A variational perspective accelerated methods in optimization. CoRR, abs/1603. 2016. URL http:///rxiv.on abs/ 1603.60330000
wttpo//////.////02222221 04245.
Ami Wiesel. Geodesic convexity and covariance estimation. IEEE Trans. Signal Process., 60(12): 6182-6189, 2012.
doi: 10.1 10.1109/TSP:20122211824 URL http:://doi.or// 10. 1091
2218241.
Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Proceedings of the 29th Conference on Learning Theory, COL.T 2016, New York, USA, June 23-26, 2016, pp. 1617-1638, 2016. URL.
zhang h6m.
Hongyi Zhang and Suvrit Sra. An estimate sequence for geodesically convex optimization. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings Machine Learning Research, pp. 1703-1723. PMLR, 2018. URL http:://rooeeddigggs.mtpp.p wttpss/////e/ee//////// zhangl I8. htmll.
Hongyi Zhang, Sashank J. Reddi, and Suvrit Sra. Riemannian SVRG: fast stochastic op- timization on riemannian manifolds.
Advances in Neural Information Processing Sys-
tems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 4592-4600, 2016. URI. pttp::/pppers.ipss.co 6515-riemannian- svrr--sst--------a- weachastii-optimizatii cot.rattoot-------mmmiiaaaaaa maniiolds.
Jingzhao Zhang, Hongyi Zhang, and Suvrit Sra. R-SPIDER: A fast riemannian stochastic optimization algorithm with curvature independent rate. CoRR, abs/181 881 .04194, 2018. URL http:/// abs/18 12///////444 1.04/94.
Pan Zhou, Xiao-Tona Tong Yuan, and Jiashi Feng. Faster first-order methods for stochastic non-convex optimization on riemannian manifolds. In The 22nd International Conference on Artificial Intelli- gence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pp. 138 188-147,2 2019. URL http://pmoeeedingssmtpresssss
zhou 19. himl.
14


Reviews:
[{"review_id": "u_hJgk14spc", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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: This paper provides a generalization of AGD to constant sectional curvature spaces (or subsets of them), and proves the same global rates of convergence that hold in the Euclidean space. Additionally, they provide reductions for the bounded sectional curvature case. Their basic strategy involves the use of geodesic maps to accumulate local linear lower bounds, in a way that accounts for the geometric distortion incurred by the map.\n\nStrengths: The paper is written well and organized in a reasonable fashion. They have a clear description of the general techniques applied in their work, and push overly technical arguments to the appendix. They provide global rates which also apply to g-convex functions (not just strongly convex). Where I have checked, their statements are mathematically sound.\n\nWeaknesses: The domain of applicability for their main rates are restricted to the constant curvature spaces, and it could be argued that it is relatively narrow in scope. I am not sure of the convention in this community, but perhaps it would helpful also to have some experimental results and code to assist in reproduction and discussion of practical import and comparison.\n\nRecommendation: I gave a score of 7, as it seems to provide technical progress over previous results and the authors are clear in describing their contributions. My score is relatively uncertain as I was not able to check many of the technical arguments and lemmas. UPDATE: I would reduce my score to a 6 based on the opinions of my fellow reviewers. It appears that the restricted scope and lack of experimental results is quite a problem within this community and venue.", "extra_scores": {}, "extra_text": {}}, {"review_id": "jsAkYhHDQgf", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considered the problem of minimizing (strongly and non-strongly) geodesically convex functions on hyperbolic and spherical manifolds, manifolds of constant curvature 1 and -1, respectively, and proposed accelerated algorithms for such problems. In particular, the author(s) showed the proposed algorithms enjoy global accelerated rates that match their Euclidean counterparts. A key to the main result is Lemma 2.2 which asserts a certain quasar convexity-type condition of the pull-back of the objective function to some Euclidean domain through a geodesic map. Based on this lemma, the main result follows from combining techniques for developing accelerated algorithms in Euclidean space, such as the approximate duality gap technique and a certain discretization scheme for continuous dynamics. Some reduction results, which obtain accelerated algorithms for the strongly convex case from the non-strongly convex case, and vice versa, are also presented.\n\nI believe that the technique is new, to the best of my knowledge. And I think that obtaining accelerated algorithms for manifold optimization problems is definitely an important topic. Therefore, the results should be interesting to a broad audience of the conference and deserve some merits. However, I have some doubts about the paper.\n\n1. The presentation of the proofs in the supplementary material is unsatisfactory. There are so many arguments like \"trivial/easy to see/prove\", \"follows straightforwardly/trivially\", etc. It makes the proofs very difficult to follow.\n\n2. In Lemma 2.2, it's a bit surprising to me that the constants gamma_p and gamma_n depends only on the radius R of the geodesic ball but not the function F (which implicitly contains K due to the rescaling) nor the point x. Perhaps some intuition of why this is the case and some interpretation of these two constants would be good. It is important as the gamma constants are involved in the complexity in Theorem 2.4 (and hence in Theorem 2.5). \n\n3. The setting of manifolds of constant curvature seems to be quite restrictive. And, as pointed out in the paper, it seems difficult that the technique could be extended to other manifolds.\n\n4. The practicality of the main algorithm (Algorithm 1) seems to be very limited. I understand that this paper focuses more on theoretical side. I am not hoping for practical use either. However, it would be good to demonstrate that performance/behaviour of the proposed algorithm does corroborate with the theories, at least in some toy examples such as optimization problems on the Poincare disk.\n\nOther comments:\n1. On page 3, the \\tilde{v} (vector of the same norm) is not well-defined. If \\tilde{v} satisfies the definition, then it can be checked that 2 \\tilde{v} also satisfies the definition.\n\n2. On page 3, it is mentioned that R\\ge d(x_0, x^*) implies x^* \\in \\Exp_{x_0} (\\bar{B}(0,R)). I believe such implication requires geodesic completeness of the manifold.\n\n3. On page 3, in the notation section, the constant K appeared without definition.\n\n4. The notions of curvature of manifolds and angles between points on manifolds are used without definition. It would be good to present the definition somewhere in the paper or the supplementary material.\n\n5. A recent paper \"An accelerated first-order method for non-convex optimization on manifolds\" by Criscitiello and Boumal, which studied accelerated algorithms for non-g-convex optimization on a more general class of manifolds, is missing from the comparison.\n\n6. Sometimes the tangent space T_x M is mistakenly written as T_x. For example, on page 4 and also in the supplementary material.\n\n7. In Lemma 2.3, it is a bit strange that the smoothness property of the pull-back function would require the assumption of the existence of a stationary point. Could you please provide some explanation?", "extra_scores": {}, "extra_text": {}}, {"review_id": "g64i4_ZEJUs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "This paper proposes a global accelerated method on Riemannian manifolds with the same rates as accelerated methods in the Euclidean space up to log factors. Reductions have also been studied on Riemannian manifolds.\n\nQuality: I think this paper has high quality in theory.\n\nClarity: I have no experience on Riemannian manifolds before. This paper reads difficult for me. I think this paper is too technical and some descriptions are not clear.\n\nOriginality: There are a number of works that study the problem of first-order acceleration on Riemannian manifolds. This paper studies the special case of constant sectional curvature, i.e., the hyperbolic and spherical spaces. I am not sure whether there are literatures studying the optimization algorithms (either accelerated or non-accelerated) on the constant sectional curvature before.\n\nSignificance: This paper gives the state-of-the-art rates in the special case of constant sectional curvature. I think it is significant.\n\nI have some comments. I have no experience on the optimizaton on Riemannian manifolds before. My comments may be too strict for the analysis on Riemannian manifolds.\n\n1. Previous literatures have studied the optimization on Riemannian manifolds of bounded sectional curvature, while this paper focuses on the special hyperbolic and spherical spaces, that have constant sectional curvature. Is there any literature focusing on the constant sectional curvature before? either accelerated or non-accelerated. What is the critical difference when transforming the analysis on the bounded sectional curvature to constant sectional curvature? Is it a straightforward extension, or very challenging?\n\n2. I am not sure whether each step of the proposed method needs more computations than the standard accelerated gradient method. For example, function f is a composition of F and h^{-1}, can \\nabla f(x) be efficiently computed? The BinaryLineSearch needs to compute \\Gamma_i^{-1} and x_{i+1}^{\\lambda}, do they need more computations? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "IBUhGkEhe8y", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The paper claims to provide a first order gradient algorithm that achieves (global) equivalent rates of convergence than in Euclidean space on two particular models of geometry (though important) the hypersphere and the hyperbolic space.\nThe strategy proposed here consists in using the geodesic maps in order to write the minimization problem on the Euclidean space with a controlled distortion, which makes possible the use of a relaxed version of convexity inequalities. In the new coordinate system, the minimised function is not convex but not far from it, in a way the authors are able to control quantitatively.\n\nMy opinion on the technical content of the paper is hindered by the difficulty of reading this paper. See the remarks for improving its readability below. The overall result seems a bit weak for all this work (40 pages long paper in total incl. supplementary material.) and the calculations do not seem particularly enlightening. \n\nI would suggest an important rewriting of the paper; Ideally, the main ideas of the paper should be illustrated in the fist technical part section in a simple and enlightening example. Also, putting forward a skeleton of proof of the main result of the paper with more details on the objects would be very helpful for the reader.\n\nOther comments on the readability:\n\nIn the contribution section, the third point on reductions is not clear at all. I suggest a rewriting of the sentence that makes it more understandable. \n\nThe method uses geodesic maps and in particular  …maps geodesics from the constant curvature space to geodesics in the  Euclidean space… This condition is very stringent. For instance, there is a theorem by Kobayashi which quantifies that affine maps (a condition which implies geodesic maps) are often isometries.\nI would suggest the authors spend more time on the definition of a geodesic map and provide a discussion. In particular, they could  write the explicit definition of such maps in the two cases of interest: the (hyper)sphere and the hyperbolic space instead of pointing to the so-called classical geodesic maps. \n\nThe beginning of section 2 is difficult to read. The strategy is explained in wordy manner: example:\n…. Our approach is to obtain a lower bound that is looser by a constant depending on R, and that is linear over B. In this way the aggregation becomes easier. … Helping the reader with equations or more precise definitions would be helpful.\n\nSection 2.1 is hard to follow, example:\n… after applying some desirable modifications, like regularization with a 1-strongly convex function \nψ and removing the unknown x ̃∗ by taking a minimum over X . Note (4) comes from averaging (3) ∗ \nfor y ̃ = x ̃ . …\n\nThe contributions to reductions techniques in Section 3 is only accessible to the expert reader and the main text is only statement of the results. The authors could make their point more explicit here.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5E68Ap3rZaa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "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": "Unfortunately, though I am familiar with the literature on accelerated gradient methods in Euclidean spaces, I am not familiar enough with Riemannian geometry to provide a confident review of this paper. That being said I can provide some feedback.\n\nOverall, this paper is very dense with mathematics that will not be not particularly familiar to most machine learning people. Moreover the suggested applications to ML (a single line in the paper) is not particularly convincing without more discussion and context (e.g., a fully worked example). This is compounded by the fact that no experiments were presented. This paper would be greatly improved by an experiment that showed the improvement of this algorithm over vanilla gradient approaches on a Riemannian manifold, even if the experiment was totally synthetic. Even better would be to present a real machine learning application. With that in mind, I have a concern that ICLR is not the right venue for this paper. After all, ICLR is focussed on Learning Representations and though I tend to have a relaxed approach to this I think this paper might not be of general enough interest to the ICLR community (even though it may well be an excellent paper).\n\nSome more minor comments:\n\nThis paper focuses on hyperbolic and spherical manifolds. How important are these spaces in practical problems? I wonder if the limited scope of the results covers the machine learning applications discussed in the introduction. This needs more discussion. If these spaces are presented primarily because the analysis is easier then this is another reason why ICLR might not be the right venue.\n\nI am surprised that any of the parameters of the manifold do not appear in the bound. Is there some intuition why the bound relies only on the constants of the function f (\\mu and L) and not on any property of M (eg, the main results section the results are in terms of L and mu and ignore only factors of log(L/mu))? It would be good to add a discussion of this, or be explicit with the dependency in the bounds if there is one.\n\nVery minor comment: the word 'unfeasible' is unusual (though apparently it is a real world), infeasible is more common.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers generally appreciate the theoretical contribution of the paper, namely Accelerated Gradient Descent on the sphere and hyperbolic space with the same convergence rate as the Euclidean counterpart. However, there are several major concerns with the current work. From a theoretical standpoint, the geodesic map, which plays a crucial role in the algorithm and theoretical analysis, exists if and only if the manifold has constant sectional curvature (sphere and hyperbolic space). It is not at all clear how the current approach can be extended beyond this setting. 
From an algorithmic viewpoint, the stated algorithm has not been experimentally validated. It is suggested that at least some synthetic experiments, e.g. on the sphere or Poincare disk, be carried out. Finally, the current presentation is quite dense and should be considerably improved.
Decision: Reject