Accelerated Riemannian Optimization: Handling Constraints to Bound Geometric Penalties
Authors: David Martínez-Rubio
Sebastian Pokutta
Venue: Submitted to ICLR 2023 (2023)
Keywords: Riemannian optimization
geodesic convexity
first-order accelerated methods

Abstract:     We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in Hadamard manifolds. Our algorithm enjoys the same convergence rates as Nesterov's accelerated gradient descent, up to a multiplicative geometric penalty and log factors.  
    Crucially, we can enforce our method to stay within a compact set we define. Prior fully accelerated works resort to assuming that the iterates of their algorithms stay in some pre-specified compact set, except for two previous methods, whose applicability is limited to local optimization and to spaces of constant curvature, respectively. Achieving global and general Riemannian acceleration without iterates assumptively staying in the feasible set was asked as an open question in (Kim & Yang, 2022), which we solve for Hadamard manifolds.
    In our solution, we show that we can use a linearly convergent algorithm for constrained strongly g-convex smooth problems to implement a Riemannian inexact proximal point operator that we use as a subroutine, which is of independent interest.

Under review as a conference paper at ICLR 2023
ACCELERATED RIEMANNIAN OPTIMIZATION: HAN- DLING CONSTRAINTS TO BOUND GEOMETRIC PENAL- TIES
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly not) geodesically-conve functions in Hadamard mani- folds. Our algorithm enjoys the same convergence rates as Nesterov's 's accelerated gradient descent, up to multiplicative geometric penalty and log factors. Crucially, we can enforce our method to stay within a compact set we define. Prior fully ac- celerated works resort to assuming that the iterates of their algorithms stay in pre-specified compact set, except for two previous methods, whose applicability is limited local optimization and to spaces of constant curvature, respectively. Achieving global and general Riemannian acceleration without iterates assump- tively staying in the feasible set was asked as an open question in (Kim Yang, 2022), which we solve for Hadamard manifolds. In our solution, we show that we can use a linearly convergent algorithm for constrained strongly g-convex smooth problems to implement Riemannian inexact proximal point operator that we use as a subroutine, which is of independent interest.
INTRODUCTION
Riemannian optimization concerns the optimization of a function defined over Riemannian manifold. motivated by constrained problems that can be naturally expressed on Riemannian manifolds allowing to exploit the geometric structure of the problem and effectively transforming it into an unconstrained one. Moreover, there are problems that are not convex in the Euclidean setting, but that when posed as problems over manifold with the right metric, are convex when restricted to every geodesic, and this allows for fast optimization (Cruz Neto et al., 2006; Carvalho Bento & Melo, 2012; Bento al.. 2015; Allen-Zhu et al., 2018). That is, they geodesically convex (g-convex) problems, cf. Definition 1.1. Some applications of Riemannian optimization machine learning include dictionary learning (Cherian & Sra, 2017; Sun al., 2017), robust covariance estimation in Gaussian distributions (Wiesel, 2012), Gaussian mixture models (Hosseiní & Sra, 2015), operator scaling (Allen-Zhu al., 2018), computation of Brascamp-Lieb constants (Bennett et al., 2008), Karcher mean (Zhang et al., 2016). Wasserstein Barycenters (Weber & Sra, 2017), low-rank matrix completion (Cambier & Absil, 2016; Heidel Schulz, 2018: Mishra Sepulchre, 2014: Tan et al., 2014; Vandereycken, 2013). optimization under orthogonality constraints (Edelman et al., 1998; Lezcano-Casado & Martinez-Rubio, 2019), and sparse principal component analysis (Genicot et al., 2015; Huang& & Wei, 2019b; Jolliffe et al., 2003). The first seven problems are defined over Hadamard manifolds, which we consider this work. fact, the optimization in these cases is over symmetric spaces, which satisfy property that one instance of our algorithm requires, cf. Theorem 2.4.
Riemannian optimization, whether under g-convexity or not, is an extensive and active area of research, for which one aspires to develop Riemannian optimization algorithms that share analogous properties to the more broadly studied Euclidean methods, such as the following kinds of Riemannian first-order methods: deterministic (Bento al., 2017; Wei et al., 2016; Zhang & Sra, 2016), adaptive
Most of the notations in this work have a link to their definitions. For example, if you click or tap on any instance of L, you will jump to the place where it is defined as the smoothness constant of the function we consider in this work.

---

Under review as a conference paper at ICLR 2023
(Kasai et al., 2019), projection frrec (Weber & Sra, 2017; 2019), saddle-point-ssappine (Criscitiello & Boumal, 2019; Sun et al.. 2019; Zhou et al., 2019; Criscitiello & Boumal, 2020), stochastic (Hosseini & Sra, 2017; Khuzani & Li, 2017; Tripuraneni et al., 2018), variance-reduced (Sato et al., 2017; 2019; Zhang et al., 2016), and min-max methods (Zhang et al., 2022), among others.
Riemannian generalizations accelerated convex optimization are appealing due their better convergence rates with respect to unaccelerated methods, specially in ill-conditioned problems. Acceleration in Euclidean convex optimization is concept that has been broadly explored and has provided many different fast algorithms. A paradigmatic example is Nesterov's ' Accelerated Gradient Descent (AGD), cf. (Nesterov, 1983). which is considered the first general accelerated method, where the conjugate gradients method can be seen as an accelerated predecessor in a more limited scope Rurbi,, 2021). There have been recent efforts to better understand this phenomenon in the Euclidean case (Allen Zhu & Orecchia, 2017; Su et al., 2016; Drori & Teboulle, 2014; Wibisono et al., 2016; Diakonikolas & Orecchia, 2019; Joulani et al., 2020), which have yielded some fruitful techniques for the general development of methods and analyses. These techniques have allowed for a considerable number of new results going beyond the standard oracle model, convexity, or beyond first-order, in wide variety of settings (Tseng, 2008; Beck & Teboulle, 2009; Wang et al., 201 6a; Allen Zhu & Orecchia, 2015; Allen- -hu, 2017; 2018; Carmon et al., 2017; Diakonikolas & Orecchia, 2018; Hinder al., 2019; Gasnikov al., 2019; Ivanova al., 2021; Kamzolov & Gasnikov, 2020; Criado et al., 2021), among many others. There have been some efforts to achieve acceleration for Riemannian algorithms as generalizations of AGD, cf. Section 1.3. These works try to answer the following fundamental question:
Can Riemannian first-order method enjoy the same rates of convergence as Euclidean AGD?
The question is posed under (possibly strongly) geodesic convexity and smoothness of the function to be optimized. And due to the lower bound in (Criscitiello & Boumal, 2021), we know the optimization must be under bounded geodesic curvature of the Riemannian manifold, and we might have to optimize over bounded domain.
Main result In this work, we study the question above in the case of Hadamard manifolds M of bounded sectional curvature and provide an instance of our framework for a wide class of Hadamard manifolds. For a differentiable f : .M- - with a global minimizer at x", let zy E AM be an initial point and R be an upper bound on the distance d( x²) ). If is L-smooth and (possibly p-strongly) g g-convex in a closed ball of center x" and radius (R). our algorithms obtain the same rates of convergence as AGD, up to logarithmic factors and up to a geometric penalty factor, ef. Theorem 2.4. See Table for a succint comparison among accelerated algorithm and their rates. This algorithm is a consequence of the general framework we design:
General accelerated scheme Riemacon. Given a not necessarily accelerated, linearly-convereent subroutine for strongly g-convex smooth problems, constrained to geodesically convex set X, we design first-order algorithms that enjoy the same rates as AGD when approximating mingex f fx)) up to logarithmic factors and up a geometric penalty factor, where f : : M - R is a differentiable function that is smooth and g-convex (or strongly g-convex) in X' C N, cf. Theorem 2.2.
Importantly, our algorithms obtain acceleration without undesirable assumption that most previous works had to make: that the iterates of the algorithm stay inside of a pre-specified compact set without any mechanism for enforcing or guarateeing this condition. To the best of our knowledge only two previous methods are able to deal with some form of constraints, and they apply to the limited settings of local optimization (Criscitiello & Boumal, 2021) and constant sectional curvature manifolds (Martínez-Rubbee that the iterates of their algorithms are always feasible. Removing this condition in general, global, and fully accelerated methods was posed as an open question in (Kim & Yang, 2022), that we solve for the case of Hadamard manifolds. The difficulty of constraining problems in order to bound geometric penalties as well as the necessity of achieving this goal in order to provide full optimization guarantees with bounded geometric penalties is something that has also been noted in other kinds of Riemannian algorithms, cf. (Hosseini & Sra, 2020).
2021), respectively. Techniques in the rest of papers resort to assuming
We develop new techniques on inexact proximal methods in Riemannian manifolds and show that with access to (not necessarily accelerated) constrained linear subroutine for strongly g-convex and smooth problems, we can inexactly solve a proximal subproblem to enough accuracy so it can be used in our accelerated outer loop, in the spirit of other Fuclidean algorithms like Catalyst (Lin
2

---

Under review as a conference paper at ICLR 2023
et al., 2017). After building this machinery, we show that are able to implement an inexact ball optimization oracle, cf. (Carmon et al., 2020), as an instance of our solution. Crucially, the diameter D of this ball depends on R and the geometry only, so in particular it is independent the condition number of f. We can use the linearly convergent algorithm in (Criscitiello & Boumal, 2021) for the implementation of the prox subroutine and show that iterating the application of the ball optimization oracle leads to global accelerated convergence.
The question concerning whether there are Riemannian analogs Nesterov's algorithm that enjoy similar rates is a question that, to the best of our knowledge, was first formulated in (Zhang & Sra, 2016). In particular, since Nesterov's AGD uses a proximal operator of a function's 's linearization, they ask whether there is a Riemannian analog to this operation that could be used to obtain accelerated rates in the Riemannian case. We show that, instead, a proximal step with respect to the whole function can be approximated efficiently in Hadamard manifolds and it can be used along with an accelerated outer loop. To the best of our knowledge, previously known Riemannian proximal methods either obtain asymptotic analyses, assume exact proximal computation, or work with approximate proximal operators by using different inexactness conditions as ours, and none of them show how to implement the proximal operators or obtain accelerated proximal point methods, ef. Section 1.3.
1.1 PRELIMINARIES
We provide definitions of Riemannian geometry concepts that we use in this work. The interested reader can refer to (Petersen, 2006; Bacák, 2014) for an in-depth review of this topic, but for this work the following notions will be enough. A Riemannian manifold (M, g) is real O manifold M equipped with a metric g, which is a smoothly varying, i.e., C inner product. For x E M, denote by T.M the tangent space of M at x. For vectors V, w E T.M, we denote the inner product of the metric by (u, w),, and the norm it induces by ||e|| def V(v, uv), Most of the time, the point is known from context, in which case we write (u, w: or ||
A geodesic of length é is curve y: [0, + 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 case the exponential map Exp, Tu- - MM and the inverse exponential map Log, .M- + T..M are well defined for every pair of points, and are as follows. Given 2, y E M, v E T.M, and geodesic ? of length |||||| such that 70) x. v[] (0(0) = / ||el|, we have that (x) between r and y. and note that it takes the same value as Log, [v)ll The manifold M comes with a natural parallel transport between vectors in different tangent spaces, that formally is defined from a way of identifying nearby tangent spaces, known as the Levi-Civita connection V (Levi-Civita, 1977). We use this parallel transport throughout this work.
y. and Loga (v) = v. We denote by d(z y) the distance
Given 2-dimensional subspace V C T2MM of the tangent space of point xr, the sectional curvature at with respect to V is defined as the Gauss curvature, for the surface Exp,, (V) at x. The Gauss curvature at a point æ can be defined as the product of the maximum and minimum curvatures of the curves resulting from intersecting the surface with planes that are normal to the surface x. A Hadamard manifold is a complete simply connected Riemannian manifold whose sectional curvature non-positive, like the hyperbolic space or the space of X n symmetric positive definite matrices with the metric (X, A def TI(AA'XA-ly where X, Y are in the tangent space of A. Hadamard manifolds are uniquely geodesic. Note that in general manifold Expx(.) might not be defined for each a E T,M, but in a Hadamard manifold of dimension n. the exponential map at any point is a global diffeomorphism between T&M _ R and the manifold, and so the exponential map is defined everywhere. We now proceed to define the main properties that will be assumed on our model for the function to be minimized and on the feasible set X
Definition 1.1 (Geodesic Convexity and Smoothness). Let f :N C CM- + R be a differentiable function defined on an open set A contained in Riemannian manifold M. Given L Z p > we say that f is L-smooth in a set X C if for any two points x, y E X, satisfies
L
f(y) S f(x) + (z) (v).
dd<,,))
2
Analogously, we say that f is p-strongly g-conver in X, if for any two points x, y E X, we have
f(v) 2 f(x) + Log, + /
d)
3

---

Under review as a conference paper at ICLR 2023
If the previous inequality is satisfied with O, we say the function is g-convex in X.
We present the following fact about the squared-distance function, when one of the arguments is fixed. The constants (D. dD below appear everywhere in Riemannian optimization because, among other things, Fact 1.2 yields Riemannian inequalities that are analogous to the equality in the Euclidean cosine law of triangle, cf. Corollary C.3, and these incqualities have wide applicability in the analyses of Riemannian methods.
Fact 1.2 (Local information of the squared-distance Let M be a Riemannian manifold of sec- tional curvature bounded by [Kimt mmax that contains a uniquely g-convex sel X C M of diameter D < cc. Then, given I, y E X' we have the following for the function 22 -M- + R. y + 2d(x, y)²:
(Φ = Log, (x)
and
dDllul12 - Hess (v)l,, v) s CDllell?
where
SD def D 1m coth (mmmn)))
if Kinn 0 if Kmin >
and
if maax S O ffux > 0 In particular, 42 is on-strongly g-convex and (D-smooth in X. See (Lezcano-Casado, 2020) for proof.
6D
(D /imox cot ( Flmax)
1.2 NOTATION.
Let M be uniquely geodesic n-dimensional Riemannian manifold. Given points 2, v, E M. we abuse the notation and write y in non-ambiguous and well-defined contexts in which we should write Logz(y). For example, for
(U. x y) (v. Log, (y) Log, Log, (v)ll; and [ly - = Log, (v) = d(y, x). We denote by X' a compact, uniquely geodesic g-convex set of diameter D contained in an open set C M and we use Ix for the indicator function of X, which at points in X' and +oo otherwise. For a vector v E M, we use (v) E T.M to denote the parallel transport of v from M to T.M along the unique geodesic that connects y to z. We call f:N C M + R a differentiable L-smooth g-convex function we want to optimize. We use & to denote the approximation accuracy parameter, Tg X for the initial point of our algorithms, and R d(x x²) for the initial distance to an arbitrary constrained minimizer E arg min f(x). We use R for upper bound on the initial distance d(zo, x²) to unconstrained minimizer x², if exists. The big-O notation Ö(-) omits log factors. Note that in the setting of Hadamard manifolds, the bounds on the sectional curvature are Kmin I Fmmx < 0. Hence for notational convenience, we
T we have (v. y - 2) -
(z) = (u, (y);; ||u yll = || - Log, (v)ll: :ll 2 yllz
define < def <D DV m/mi cooh (D DDVIn, (KEmin)) > 8 def 1, and similarly < def <R and 0 def 8R 1. /
If v E T.M,, we use II (u) E M for the projection of v onto the closed ball with center at 0 and radius r.
1.3 OUR RESULTS AND COMPARISONS WITH RELATED WORK
In this work, optimize functions defined over Hadamard manifolds M of finite dimension and of sectional curvature bounded in [Kmin Kmax] As all previous related works discussed in the sequel, we assume that can compute the exponential and inverse exponential maps, and parallel transport of vectors for our manifold. The differentiable function f to be optimized is defined over open set A' C M that contains a compact g-convex set X' of finite diameter D. Our function ff is L-smooth and g-convex (or μ-strongly g-convex) in X and we have access to it via a gradient oracle that can be queried at points in X. For this setting, we show in Theorem 2.2 that with access to a (possibly unaccelerated) linearly convergent subroutine for g g-strongly smooth problems in X, the algorithms we propose find a point yr X' such that f(yr) mingex fxx S after calling the gradient oracle and the subroutine the following number of times: LTC//RR/// for the g-convex case and
for the p-strongly g-convex case, where R def d(z0. Ø*) and To E X' is an initial point. Then in Theorem 2.4, we instantiate our algorithm with the method in (Criscitiello & Boumal, 2021) subroutine and boost the convergence by
4

---

Under review as a conference paper at ICLR 2023
implementing and sequentially applying an inexact ball optimization oracle and we obtain the rates Ō({² V /e) and Ō VL./ log(uR* /e)) where R is bound on the initial distance d(æo, x²) to an unconstrained minimizer x². In sum, the algorithms enjoy the same rates as AGD in the Euclidean space up to factor of <² = R? coth" (R//mml))) - (1 + R (< D2 (our geometric penalty) and up universal constants and log factors. Note that as the minimum curvature min approaches 0 we have Ç + 1.
We emphasize that our Algorithm 1 only needs to query the gradient of f at points in X' and the L-smoothness and ju-strong g g-convexity of f only need to hold in X. This is relevant because in Riemannian manifolds the condition number L/ in a set can increase with the size of the set, cf. (Martínez-Rubioc 2020, Proposition 27). Intuitively, although there are twice differentiable functions defined over the Euclidean space whose Hessian is constant everywhere, in other Riemannian cases the metric may preclude having such global condition and the larger the set is the larger the minimum possible condition number becomes. Compare this, for instance, with the bounds on the Hessian's s eigenvalues of the squared-distance function in Fact 1.2, which are tight for spaces of constant curvature (Lezcano-Casado, 2020).
Now we proceed to compare our results with previous works. We have summarized most of the following discussion in Table 1. We include Nesterov's AGD in the table for comparison purposes'. There are some works on Riemannian acceleration that focus on empirical evaluation or that work under strong assumptions (Liu et al., 2017; Alimisis et al., 2019; Huang & Wei, 2019a; Alimisis et al., 2020; Lin et al., 2020), see (Martínez- works. We focus the discussion on the most related work with guarantees. (Zhang & Sra, 2018) obtain an algorithm that, up to constants, achieves the same rates as AGD in the Euclidean space, for L-smooth and j--strongyy g-convex functions but only locally, namely when the initial point starts in a small neighborhood N of the minimizer x=: ball of radius O((μ/ L)3/4) around it. (Ahn & Sra, 2020) generalize the previous algorithm and, by using similar ideas as (Zhang & Sra, 2018) for estimating lower bound on S. they adapt the algorithm to work globally. proving that it eventually decreases the objective as fast as AGD. However, as (Martínez- iterations as the ones needed by Riemannian gradient descent (RGD) to reach the neighborhood of the previous algorithm. The latter work also noted that in fact RGD and the algorithm in (Zhang & Sra, 2018) can be run in parallel and combined to obtain the same convergence rates as in (Ahn & Sra, 2020), which suggested that for this technique, full acceleration with the rates of AGD only happens over the small neighborhood N in (Zhang & Sra, 2018). Note however that (Ahn & Sra, 2020) show that their algorithm will decrease the function value faster than RGD, but this is not quantified. (Jin & Sra, 2021) developed different framework, arising from (Ahn & Sra, 2020) but with the same guarantees for accelerated first-order methods. We do not feature it in the table. (Criscitiello & Boumal, 2021) showed, under mild assumptions, that in ball of center x E M and radius (((p/T.)1//2) containing x², the pullback function f Exp,, T.M- - R is Euclidean, strongly convex, and smooth with condition number O(L/M), so AGD yields local acceleration as well. In short, acceleration is possible in a small neighborhood because there the manifold is almost Euclidean and the geometric deformations are small in comparison to the curvature of the objective. These techniques fail for the g-convex case since the neighborhood becomes a point (n/L = 0).
2020) for instance for a discussion on these
2020) noted, it takes as many
Finding fully accelerated algorithms that are global presents a harder challenge. By a fully accelcrated algorithm we mean one with rates with same dependence as AGD on I,, e, and it applies, on μ.. (Martínez-Rubio, 2020) provided such algorithms for g-convex functions, strongly or not, defined over manifolds of constant sectional curvature and constrained to a ball of radius R. The convergence rates initially had large constants with respect to R but were later improved, cf. Table 1. Kim & Yang (2022) designed global algorithms with the same rates as AGD up to universal constants and a factor of Č, their geometrie penalty. However, they need to assume that the iterates of their algorithm remain in their feasible set X' and they point out on the necessity of removing such an assumption, which they leave as an open question. Our work solves this question for the case of Hadamard manifolds. In their technique, they show that they can use the structure of the accelerated scheme to move lower bound estimations on f(=*) from one particular tangent space to another without incurring extra errors, when the right Lyapunov function is used. By moving lower bounds here we mean finding
NNot that the original method in (Nesterov, 1983) needed to query the gradient of the function outside of the feasible set, and this was later improved to only require queries at feasible points (Nesterov, 2005) as in our work, hence our choice of citation in the table.
5

---

Under review as a conference paper at ICLR 2023
Table 1: Convergence rates of related works with provable guarantees for smooth problems over uniquely geodesic manifolds. Column K? refers to the supported values of the sectional curvature, G to whether the algorithm is global (any initial distance L' mean they are local algorithms that require initial distance O((L/u)=3 -3/4) and O(LL/u) 1/12)) respectively. Column F? refers to whether there is full acceleration, meaning dependence on L, Je, and e like AGD up possibly log factors. Column C? refers to whether the method can enforce some constraints. All methods require their iterates to be in some specified compact set, but the works
minimizer is allowed). Here L and
with X just assume the iterates will remain within the constraints. We use W def VH log LR" AA mild condition on the covariant derivative of the metric tensor is required.
Method
g-convex
js-tt. g-CvX
K?
G?
F?
C?
(Nesterov, 2005, AGD)
Olv LR
O(W)
/
(Zhang & Sra, 2018)
O(W)
bounded
/
x
(Ahn & Sra, 2020)
bounded
V
X
x
MMartínez-Rubio 2020)
ols/ LIR
Ö(C-W)
ctant
J
/
(Criscitiello & Boumal, 2021)
O(W)
bounded
L
J
d
(Kim & Yang, 2022)
V LR²
Ols. W)
bounded
/
x
Theorem 2.4
ōl5² V LRe
Ö W)
Hadamard"
/
suitable lower bounds that are simple (a quadratic in their case), if pulled-back to one tangent space, we start with a similar bound that is simple when pulled-back to another tangent space.
Lower bounds. In this paragraph, we omit constants depending on the curvature bounds in the big-O notations for simplicity. (Hamilton & Moitra, 2021) proved an optimization lower bound showing that acceleration in Riemannian manifolds is harder than in the Euclidean space. (Criscitiello & Boumal, 2021) largely generalized their results. They essentially show that for large family of Hadamard manifolds, there is function that smooth and strongly g-convex
ball of radius that contains the minimizer x², and for which finding a point that is R/5 close to x requires ?2 R) calls to the gradient oracle. Note that these results do not preclude the existence of a fully accelerated algorithm with rates AAG rates, for instance, A similar hardness statement is provided for smooth and only g- g-convex functions. Also, reductions as in Martinez-Rubio 2020) evince this hardness also present in this case.
Handling constraints to bound geometric penalties. In our algorithm and in all other known fully accelerated algorithms, learning rates depend on the diameter of the feasible set. This is natural: estimation errors due to geometric deformations depend on the diameter via the constants Çn. 8n, the cosine-law incqualities Corollary C.3, or other analogous inequalities, and the algorithms take these errors into account. All other previous works not able to deal with any constraints and hence they simply assume that the iterates of their algorithms stay within one such specified set, except for (Martínez-Rublee 2020) and (Criscitiello & Boumal, 2021) that enforce ball constraint, explained above. However, these two works have their applicability limited to spaces of constant curvature and local optimization, respectively. Note that even if one could show that given choice of learning rate, convergence implies that the iterates will remain in some compact set, then because the learning rates depend on the diameter of the set, and the diameter of the set would depend on the learning rates, one cannot conclude from this argument that the assumption these works make is going to be satisfied. In contrast, in this work, we design a general accelerated framework and an instance of it that keep the iterates bounded, effectively bounding geometric penalties while we do not need resort to any other extra assumptions, solving the open question (Kim Yang, 2022).
Riemannian proximal methods There have been some works that study proximal methods in Riemannian manifolds, but most of them focus on asymptotic results or assume the proximal operator can be computed exactly (Wang al., 2015; Bento et al., 2017; 2016; Khammahawong et al., 2021; Chang et al., 2021). The rest of these works study proximal point methods under different inexact versions of the proximal operator as ours and they do not show how implement their inexact version

---

Under review as a conference paper at ICLR 2023
in applications, like in our case of smooth and g-convex optimization. In contrast, implement the inexact proximal operator with a first-order method (Ahmadi & Khatibzadeh, 2014) provide a convergence analysis of mexaac proximal point method but when applied to optimization they assume the computation of the proximal operator is exact. (Tang & Huang. 2014) uses a different inexact condition and proves linear convergence, under growth condition on (Wang et al., 201 obtains linear convergence of an inexact proximal point method under a different growth assumption on and under an absolute error condition on the proximal function.
ALGORITHMIC FRAMEWORK AND PSEUDOCODE
In this section, we present our Riemannian accelerated algorithm for constrained g-convex opti- mization, Riemacon'. This is a general framework that we later instantiate to provide a full algorithm. Recall our abuse of notation for points E . to mean Log, (p) in contexts in which one should place vector in T and note that in algorithm Tg and yk points in M whereas 2h E Ta, M, 2 2k
2k 2 E T M.
Algorithm 1 Riemacon: Riemannian Acceleration Constrained g- g-Convex Optimization
Input: Feasible set X. Initial point un E C N. Diff. function f : C M - for Hadamard
manifold M that is L-smooth and g-convex in X. Optionally: final iteration T or accuracy e. If e is provided, compute the corresponding T, cf. Theorem 2.2.
Parameters:
Geometric penalty 5 def 4G2D 3 S 8Ç 3 0())
Implicit Gradient Descent learning rate À def L2D/L. L.
Mirror Descent learning rates 7),
def /
Proportionality constant the proximal subproblem accuracies: 4 (k+1))
Definition:
(computation of this value not needed)
Prox. accuracies: Okk 78A
d. where vi def
arg min yEX (/(x) + 2x 1x
1: yo + To: Ao + 200AE
2: 20 0 T M;
20
2y t 0 E To
3: for k = 1 to
T do
4: Og +- 2A* ++322
5
A + dx/E A-- = u:/E+ + Ao ((++1+645) + +200E)
5:
56
6:
F + ExPye-1 ( (Ap on = A ta, yk-1) ExPy
A It t I't (z + Logz, (Ma-1) = Logg,
A-1
ta
2k-1)
Coupling
7:
(Expys yb
k-1
8:
yk On-minimizer of the proximal problem m (f()) U +- Logz, (2A)
dl( y)
2x
9:
o Approximate subgradient
10:
2
Zt + 2k UT
Mirror Descent step Moving the dual point to M M o Easy projection done so the dual point is not very far
11:
2 + T (2 Loggs (mx)
12:
E + II (z M
13:
end for
14:
return yr-
We start with an interpretation of our algorithm that helps understanding its high-level ideas. The fol- lowing intends to be a qualitative explanation, and we refer to the pseudocode and the supplementary material for the exact descriptions and analysis. Euclidean accelerated algorithms can be interpreted, cf. (Allen Zhu & Orecchia, 2017), as a combination of a gradient descent (GD) algorithm and an online learning algorithm with losses being the affine lower bounds f(x,) + (zz)),, 2x) obtain on f(-) by applying convexity at some points zg. That is, the latter builds a lower bound estimation on f. By selecting the next query the gradient oracle as cleverly picked convex combination of the predictions given by these two algorithms, one can show that the instantaneous
Riemacon rhymes with "rima con" in Spanish.
7

---

Under review as a conference paper at ICLR 2023
regret of the online learning algorithm can be compensated by the local progress GD makes, which leads to accelerated convergence. In Riemannian optimization, there are two main obstacles. Firstly, the first-order approximations of f at points 24. yield functions that are affine but only with respect to their respective Ta., M, and so combining these lower bounds that are only simple in their tangent spaces makes obtaining good global estimations not simple. Secondly, when one obtains such global estimations, then one naturally incurs an instantancous regret that is worse by a factor than is usual in Euclidean acceleration. This factor a geometric constant depending on the diameter D of set X' where the iterates and a (possibly constrained) minimizer lie. As a consequence, the learning rate of GD would need to be multiplicatively increased by such a constant with respect to the one of the online learning algorithm in order for the regret to still be compensated with the local progress of GD (and the rates worsen by this constant). But if we fix some X' of finite diameter, because GD's s learning rate is now larger, it is not clear how to keep the iterates in X. And if we do not have the iterates in one such set X, then our geometric penalties could grow arbitrarily.
We find the answer in implicit methods. An implicit Euclidean gradggradient descent step is one that computes, from a point Ty. E X, another point y = Iy - Aug- E X. where Vk E O + 1x) ( is subgradient of f + Ix at vg. Intuitivelyy if we could implement Riemannian version of an implicit GD step then it should be possible to still compensate the regret of the other algorithm and keep all the iterates in the set X. Computing such an implicit step is computationally hard in general, def
but we show that approximating the proximal objective (y) = f(y + के dx y)² with enough accuracy yields an approximate subgradient that can be used to obtain an accelerated algorithm as well. In particular, we provide an accelerated scheme for which we show that the error incurred by the approximation of the subgradient can be bounded by some terms we can control, ef. Lemma A.2, namely a small term that appears in our Lyapunov function and also a term proportional to the squared norm of the approximated subgradient, which only increases the final convergence rates by constant. This proximal approach works by exploiting the fact that the Riemannian Moreau envelop is convex in Hadamard manifolds (Azagra & Ferrera, 2005) and that the subproblem hu, defined with our A = /2D/ L. is strongly g-convex and smooth with a condition number that only depends on the geometry. For this reason, a local algorithm like the one in (Criscitiello & Boumal, 2021) can be implemented in balls whose radius is independent on the condition number of f. Besides these steps, we use a coupling of the approximate implicit RGD and of a mirror descent (MD) algorithm, along with a technique in (Kim & Yang, 2022) to move dual points to the right tangent spaces without incurring extra geometric penalties, that we adapt to work with dual projections, cf. Lemma A.3. Importantly, the MD algorithm keeps the dual point close to the set X' by using the projection in Line 12, which implics that the point Hg is close to X' as well, and this is crucial to keep low geometric penalties. This MD approach is mix between project the dual variable, and pure mirror descent algorithms that always project the dual variable. In the analysis, we note that partial projection also works, meaning that defining a new dual point that is closer to all of the points in the feasible set but without being a full projection leads to the same guarantees. Because we use the mirror descent lemma over Mr what we described translates to: we can project the dual 2 .t onto a ball defined on M that contains the pulled-back set Logy,, (X') and by means of that trick we can keep the iterates z3 close to X. And at the same time, the point for which we prove guarantees, namely yk. is always in X.
wollowtthe-reullle regularized-leade algorithms, that do not
Finally, we instantiate our subroutine with the algorithm in (Criscitiello & Boumal, 2021), in balls of radius independent on the condition number of f and show in Theorem 2.4 that if we iterate this approximate implementation a ball optimization oracle, we obtain convergence at a globally accelerated rate. We note (Zhang& & Sra, 2016) also provided a claimed linearly convergent algorithm for constrained strongly g-convex smooth problems, and thus in principle it could be used for our subroutine. Unfortunately, we noticed that the proof is flawed when the optimization is constrained.
We leave the proofs of most of our results to the supplementary material and state our main theorems below. Using the insights explained above, we show the following inequality on t'a defined below, that will be used as a Lyapunov function to prove the convergence rates of Algorithm 1.
Proposition 2.1. [4] By using the notation of Algorithm 1, let
- 1
vk def (,((())) f(ā*))
Logy, (I') +
-1 112
2
Then, for all k 2 L, we have (1 - Rbv < Φ
Finally, we can state our theorem for the optimization of L-smooth and g-convex functions.
8

---

Under review as a conference paper at ICLR 2023
Theorem 2.2. [1] Let M be a finite- dineet-dimensoonall Hadamard manifold of bounded sectional curvature, in a compact
and consider f : N C CM R be an L-smooth and g-convex differentiable
g-convex set X C N of diameter D, x' E arg min (z), and R di d(zo, ""), For any e > 0, Algorithm yields an e-minimizer yr X after T OOEV LER iterations. the function is ju-strongly convex then, via a sequence of restarts, converge in OCC L log(
uR²) iterations.
We note that a straightforward corollary from our results is that if we can compute the exact Rie- mannian proximal point operator and we use it as the implicit gradient descent step in Line 8 of Algorithm I, then the method is an accelerated proximal point method. One such Riemannian algorithm was previously unknown in the literature well. Finally, we instantiate Algorithm to implement approximate ball optimization oracles in an accelerated way. We show that applying these oracles sequentially leads to global accelerated convergence. Moreover, we show that the iterates do not get farther than 2R from x², which ultimately leads to the geometric penalty being a function of ( and not on the condition number of f. For the subroutine Line 8 of Algorithm I, we use the algorithm in (Criscitiello & Boumal, 2021, Section 6), and for that we require the following.
Assumption 2.3. Let R be the curvature tensor of a Riemannian manifold M. Its covariant derivative is 79 = 0.
We note that locally symmetric manifolds, like (0)... the SPD matrix manifold, the Grasmannian manifold, manifolds of constant sectional curvature are all manifolds such that V O. We argue that this assumption mild, since in particular these manifolds cover all of the applications in Section 1.
Theorem 2.4. [4] Let M be a finite-dimensionall Hadamard manifold of bounded sectional curvature satisfying Assumption 2.3. Consider f :N C .M - R. be L-smooth and p-strongly g-convex differentiable function in "(xx,3f8 where x² is its global minimizer and where R 2 d( x²) for an initial point Tq- For any >> 0, Algorithm 2 yields an E-minimizer after /T.// log( T.R2 /e)) calls to the gradient oracle of f. By using regularization, this algorithm E-minimizes the go g-convex case (μ = 0) after Ö(s2 LR2/s) gradient oracle calls.
Algorithm 2 Ball Optimization Boosting of Riemacon instance (Algorithm 1)
Input: Differentiable function f : N C M - R that is L-smooth and fu-strongly g-convex in B(x ,3R) C N; initial point To N; bound R 2 d(ro, x*); constant F from Assumplion 2.3; accuracy
1: 2R < (46R) (22R] then return RiemaconSC( f(E)
2: Compute D such that D = (46
K min (D) Alternatively, make D < (700H)mminl aR SR: 2T
3: T T [ [ In( LR² )1: e' 5- min
4: for k 1 to T do
5: X'ss < ((xx-1,
6: 2g +- RiemaconSC( Ik-i,
(Crisciticllo & Boumal, 2021) as subroutine 7: o RRiemaconSC is the strongly convex version of Algorithm I in Theorem 2.2 (cf. its proof).
8: end for
9: return 2T.
CONCLUSION AND FUTURE DIRECTIONS
In this work, we pursued an approach that, by designing and making use of inexact Riemannian proximal methods, yielded accelerated optimization algorithms. Consequently we were able to work without an undesirable assumption that most previous methods required, whose potential satisfiability is not clear: that the iterates stay in certain specified geodesically-converr set without enforcing them to be in the set. A future direction of research is the study of whether there are algorithms like ours that incur lower geometric penalties or that do not incur log(1 /e) factors. Another interesting direction consists of studying generalizations of our approach to more general manifolds, namely the full Hadamard case, and manifolds of non-negative even of bounded sectional cuvature.

---

Under review as a conference paper at ICLR 2023
REFERENCES
P Ahmadi and H Khatibzadeh. On the convergence of inexact proximal point algorithm on hadamard manifolds. Taiwanese Journal of Mathematics, 18(2):419-433, 2014. URL https://doi.rr// 10. 11650/ 18.1....6..
Kwangjun Ahn and Suvrit Sra. From Nesterov's estimate sequence to Riemannian acceleration. arXiv preprint arXiv:2001.0887 088766 2020. URL http://////rrriiarrr///////// http:///////200087/7777
Foivos Alimisis, Antonio Orvieto, Gary Bécigneul, and Aurelien Lucchi. A continuous-time per- spective for modeling acceleration Riemannian optimization. arXiv preprint 1rXiv:1910.1078., 2019. URL https://aaxii.orr///////// abs//////////////////////// 1910.10782.
Foivos Alimisis, Antonio Orvieto, Gary Bécigneul, and Aurelien Lucchi. Practical accelerated
optimization on Riemannian manifolds. arXiv preprint 0041:20002.0444,, 2020. URL https:
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. J. Mach. Learn. Res., 18:221:1-2211 2017. URL http:://mmm..rrg/aaprsr//s /tteerss////////// 16-410.html
Zeyuan Alu.n-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, NewrIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 2680-2691, 2018. URL pupp:ppppernips..cppppep/r////e 753--trr/73---ntthhaaa---- sasisshhaa--ftte---nee censter-onnccmmexxpppinttatuttt than-sgg..
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 on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pp. 229-236, 2015. doi: 10.1 10.11452744333..2446773 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, January 9-11, I, 7017, Berkeley, CA, USA, pp. 3:1-3:22, 2017. doi: 10.42300LIPhcs.TTCSS2200 URL https://doi.or/// 10.
2011...
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 172-181, 2018. URL http:://rxiv..rr/ abs/ 1800,00077
Daniel Azagra and Juan Ferrera. Inf-convolution and regularization of convex functions Riemannian manifolds of nonpositive curvature. arXiv preprint math/0505496, 2005. URL
https://arxiv.org/ abs/matt/0505599
Miroslav Bacák. Convex analysis and optimization in hadamard spaces. In Convex Analysis and Optimization in Hadamard Spaces. de Gruyter, 2014. doi: http:://oo..rg110.15551/1777 10361629.
Amir Beck and Mare Teboulle. A fast iterative thrnshage algorithm for linear inverse problems. SIAM J. Imaging Sci., 2(1):183-202, 2009, doi: 10. 10.1137/088711542. URL htips: //doi.org/ 10/ 00011170080016542.
Jonathan Bennett, Anthony Carbery, Michael Christ, and Terence Tao. The brascamp-lieb inequalities: finiteness, structure and extremals. Geometric and Functional Analysis, 17(5):1333 1415, 2008.
GC Bento, OP Ferreira, and PR Oliveira. Proximal point method for a special class of nonconvex functions on hadamard manifolds. Optimization, 64(2):289-31 319, 2015.
Glaydston de Carvalho Bento, João Xavier da Cruz-Neto, and Paulo Roberto Oliveira. A new approach to the proximal point method: Convergence general Riemannian manifolds. J. Optim. Theory Appl., 168(3):743-755, 2016. doi: 10. 10.10077..00...015008811... URL https:
doiioorg/ 10. 10.100077
10

---

Under review as a conference paper at ICLR 2023
Glaydston de Carvalho Bento, Orizon P. Ferreira, and Jefferson G. Melo. (leration-complexiie of gradient, subgradient and proximal point methods on Riemannian manifolds. J. Optim. Theory Appl.. 173(2)554- 562, 2017. doi: 10.1007//119957-01--0099. URL https::/doo.org/1...o s10957-017-1092. 1093-4.
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
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. "Convex until proven guilty": Dimension-free acceleration of gradient descent on non-convex functions. In Proceedings of the 34th International Conference on Machine Learning, ICMI. 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 654 354-663, 2017. URL http::/proceedingg..mrr.r catpeesss///////ooo//oo/oom/mon/ carmonl 17a. h7..tml.
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with ball optimization oracle. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL propee//rooeeeinng neurips..errucoc paper! 2020/hash/ dba4clal (bbu4ccul177723/ocu05552 12 1285d0587eee --
Glaydston de Carvalho Bento and Jefferson G. Melo. Subgradient method for convex fea- sibility on Riemannian manifolds. J. Optim. Theory Appl., 152(3):773-785, 2012. doi:
10.10077/10057-011199921- URL https://doi.rr// http:////....00000000000000---00
Shih-Sen Chang, Jen-Chih Yao, M Liu, and LC inclusion in hadamard manifolds. Applicable Analysis, pp. 1-12, 2021. doi: https://doi.or//I/
LC Zhao. Inertial proximal point algorithm for variational
1080/0003681 212.22222211....
Anoop Cherian and Suvrit Sra. Riemannian dictionary learning and sparse coding for positive definite matrices, IEEE Trans. Neural Networks Learn. Syst., 28(12):859-2877, 2017. doi: N0.11100/TNNISS.221....00 2.001107.. URL http:://oi..or/// 10.1 200011100//NNNSSS1166600000
Francisco Criado, David Martinez-Rubio, and Sebastian Pokutta. Fast algorithms for packing proportional fairness and its dual. arXiv preprint arXiv:2109.03678, 2021. URL https://arxiv.orr/
19900368.
Chris Criscitiello and Nicolas Boumal. Efficiently escaping saddle points manifolds. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver. BC, Canada, pp- 5985-5995, 2019. URL http://paperrr.isssccpppppppepee cttcc// wefficientl-esccoeeee sascaping-aaddle saddle- uuddle-points-oee points-onn manifolds.
Chris Criscitiello and Nicolas Boumal. An accelerated first-order method for non-convex optimization on manifolds. arXiv preprint arXiv:2008. 02252, 2020. URL http:://azziv.rr//bbb///// 02252.
Christopher Criscitiello and Nicolas Boumal. Negative curvature obstructs acceleration for geodesi- cally convex optimization, even with exact first-order oracles. CoRR, abs/2111.13266, 2021. URL http:://artiorr//s///111..33 http://g/////////1122.1
João Xavier da Cruz Neto, Orizon Pereira Ferreira, L. R. Lucambio Pérez, and Sándor Zoltán Németh. mathematical programming problems and a proximal-like
Convex- and monotone-transfoomall point method. J. Glob. Optim., 35(1):53-69, 2006. doi: 10.1007/s 1000077/10898--00--774111--- URL
http:://doi.orr//0/ 000.:100000000000000550 005-6741-9.
Jelena Diakonikolas and Lorenzo Orecchia. Accelerated extra- attra-gradient descent: A novel accelerated first-order method. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 1 11-14, 2018, Cambridge, MA, USA, pp. 23:1-23:19, 2018. doi: 10.4230/LIPIcs.ITC
2018.23. URL https:// org/ 4230//LIPIcs.ITS..2200
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 172314. URL htpp:///oi.org// 10. 1

---

Under review as a conference paper at ICLR 2023
Yoel Drori and Mare Teboulle. Performance of first-order methods for smooth convex minimization:
a novel approach. Math. Program. 145(1-2):451-45) 2014. doi: 10.0007/110107-003--6663.0
URL https://doi.org I0. 10011007/111177001-0665553
Alan Edelman, Tomás A. Arias, and Steven Thomas Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Analysis Applications, 20(2):33--553 1998. doi: 10.1137//0899449895990999 URL https://doi.rr// ott.//o.o.rr/.111111/////5533330 1111117770885477899999999
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 SpS-th th derivatives. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pp. 1392-1393, 2019. URL v99/ gasnikov I 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. URL https://doi..rrg 10.1007/978-3-33 01119//88--1119-200--------
doi:
Linus Hamilton and Ankur Moitra. A no-go theorem for acceleration in the hyperbolic plane. arXiv preprint arXiv:2101.05633 2021. URL https://arxiv.org/ abs/2101.006677.
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/ma.22155 URL dttps:://oi.org/ 10. ww..10022nnllll.
Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. CoRR, abs/1906. 1985, 2019. URL htt:://arsiv.org//bb// 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 wwwatrii-mmmiilld--ppimaaaaoiooo hats:ff--guusiiammmmeeeee mixtures.
http://papprs.mips..co pappes/////
Reshad Hosseini and Suvrit Sra. An alternative to EM for gaussian mixture models: Batch and stochastic Riemannian optimization. CoRR, abs/ 0abs//706.032060 03267,, 2017. URL http://arxiv.org/ abs/ 1706.03267.
Reshad Hosseini and Suvrit Sra. Recent advances in stochastic Riemannian optimization. Handbook of Variational Methods for Nonlinear Geometric Data, pp. 527-554, 2020.
Wen Huang and Ke Wei. Extending FISTA to Riemannian optimization for sparse PCA. arXiv preprint arXiv:1909.05455 2019a. URL http:://aaxiiioo////b/////////// heabb///999905440
Wen Huang and Ke Wei. Riemannian proximal gradient methods. arXiv preprint arXiv:1909.0606. 2019b. URL. https://arrsiiv.rr/uubss 1909.06063.
Anastasiya Ivanova, Dmitry Pasechnyuk, Dmitry Grishchenko, Egor Shulgin, Alexander V. Gasnikov, and Vladislav Matyukhin. Adaptive catalyst for smooth convex optimization. In Nicholas N. Olenev, Yuri G. Evtushenko, Milojica Jacimovic, Michael Yu. Khachay, and Vlasta Malkova (eds.), Optimization and Applications 12th International Conference, OPTIMA 2021, Petrovac, Montenegro, September 27 October I, 2021, Proceedings, volume 13078 of Lecture Notes URL
in Computer Science, pp. 20-37. Springer, 2021. doi: https://doiorr// 10. wtt..//////.1100/998988.8809 11100000-0-0000-110000 3-000-0000-99---222
Jikai Jin and Suvrit Sra. A Riemannian accelerated proximal extragradient framework and its implications. CoRR, abs/2111 abs/2111.00763,, 2021. URL http::///rrivv.o//aaa///
Ian T Jolliffe, Nickolay T Trendafilov, and Mudassir Uddin. A modified principal component technique based on the lasso. Journal of computational and Graphical Statistics, 12(3):531-547 2003. URL http::///oi.or///...... 10.1 198/ 10618600321488
12

---

Under review as a conference paper at ICLR 2023
Pooria Joulani, Anant Raj, András György, and Csaba Szepesvári. A simpler approach to accelerated optimization: iterative averaging meets optimism. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020. 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 4984-4993. PMLR, 2020. htt.htp: http:he///mmceeeeiggge mix.press/vl vl 190ooanni2aa..m
Dmitry Kamzolov and Alexander Gasnikov. Near-optimal hyperfast second-order method for convex optimization and its sliding. arXiv preprint arXiv:2002.09050 2020. URL hutps://arxiv.org/ abs/ 2002.09050.
Hiroyuki Kasai, Pratik Jawanpuria, and Bamdev Mishra. Riemannian adaptive stochastic gradient algorithms on 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://pooeedddngs...preeees http////////////// html.
Konrawut Khammahawong, Poom Kumam, Parin Chaipunya, and Juan Martinez-Moremt Tseng's methods for inclusion problems hadamard manifolds. Optimization, pp. 1-35, 2021. URL
htlps://doi.or// 10. 108000233 /55/0/00333944222...1. 1940179.
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.100//MM..2211..0 201....0.......01111.. 167. URL http::////oooooo./00... http:///..oog//..1/////////..000
Junghin Kim and Insoon Yang. Accelerated gradient methods for geodesically convex optimization: Tractable algorithms and convergence analysis. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 11255-11282. PMLR, 2022. URL https::/poceeddings.sli..m v162/kim22k.hrr
Tullio Levi-Civita. The absolute differential calculus (calculus of tensors). Courier Corporation, 1977. ISBN 978-0-486-31625-3.
Mario Lezcano-Casado, Curvature-dependaat global convergence rates for optimization on manifolds of bounded geometry. arXiv preprint arX1v:2008.025177, 2020. URL https:/arssiv.or// abs/ 2008.
02517.
Mario Lezcano- Casado and David Martínez-Rubie Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In Proceedings of the 36th Interna- tional Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 3799-3803. 2019. URL http:///pncceedngg..mnprre http:iinw..mmmrrree///////eeeeme wttps/////////e/oc/////aa/a casadol9a.
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. J. Mach. Learn. Res., 18:212:1-212:54, 2017. URL
http://jmllorg/paaprrs V&/ 11/18/77747777 17774..
Lizhen Lin, Bayan Saparbayeva, Michael Minyi Zhang, and David B. Dunson. Accelerated algorithms for convex and non-convex optimization on manifolds. CoRR, abs/2010.08908, 2020. URL
https://arxiv.orr//aua wttpp/////../0000000
Yuanyuan Liu, Fanhua Shang, James Cheng, Hong Cheng, and Licheng Jiao. Accelcrated first- order methods for geodesically convex optimization on Riemannian manifolds. Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vish- wanathan, and Roman Garnett (eds.), Advances in Neural Information Prucessing Systems 30: Annual Conference Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA. USA, pp. 1868-4877 2017. URL 6cf80bb..7adff6677770000220000 hat.:0000000020000000barrrrratl
David Martinez- Global Riemannian acceleration in hyperbolic and spherical spaces. arXiv preprint arXi::20/2.036/8. 2020. URL.
13

---

Under review as a conference paper at ICLR 2023
David Martinez-Rubic Acceleration in first-order optimization methods: promenading beyond convexity or smoothness, and applications. PhD thesis, University of Oxford, 2021.
Bamdev Mishra and Rodoiphe Sepulchre. R3MC: A Riemannian three-factor 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: 10. 10.1109/CDC22914470355553 URL htps:///doi.or//10 10. (009//DCC2001..000000
Yurii Nesterov. A method of solving a convex programming problem with convergence rate of (1//2). In Soviet Mathematics Doklady, volume 27, pp. 372-376, 1983. URL http://www.mahhnee..vw
Yurii Nesterov. Smooth minimization of non- non-smooth functions. Math. Program. 103(1):127-152, 2005. doi: 10.1007//11110--044-55533 URL http:://oi..or/// /tt.1/000/111000000555555555
Peter Petersen. Riemannian geometry, volume 171. Springer, 2006. ISBN 978-0-387-29403--2
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gradient. CoRR, abs/1702.05594, 2017. URL http://arrii:oor//abb// /ttp://ara...or//////00000000050 1702.05594.
Hiroyuki Sato, Hiroyuki Kasai, Bamdev Mishra. Riemannian stochastic variance reduced gradient
algorithm with retraction and vector transport. SIAM Journal Optimization, 29(2)1444-14772 2019. doi: 10.1 00.1137/17M111661
URL https:://oi.orrg org/ 10. 17711177771111778
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., URL http:://mmrr.rggppppeeeee
2016.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery the sphere II: recovery by Riemannian trust-region method. IEEÉ Trans. Inf. Theory, 63(2):885 914, 2017. doi: 10.1109/ TIT.2016.2632144 149. URL http:://doi.or// 1ete//1..11100 (T0.1199/II.22162662222..
Yue Sun, Nicolas Flammarion, and Maryam Fazel. Escaping from saddle points on Rieman- nian manifolds. In Advances in Neural Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 7274-7284, 2019. URI. http://papers.mips.cd paper/ 8948- 8948- 1148-escaping-fione saddle-points-eee on- riemannian-maniee
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, 1539-1547, 2014. URL http: ponoocedings.mmrppesss. watps///////aaannnmm
Guo-ji Tang and Nan-Jing Huang. Rate of convergence proximal point algorithms on hadamard manifolds. Oper. Res. Lett., 42(6-7):383 388777, 2014. doi: 00..0166..01.22144.60009999 URL 10..11166......2114.66....
http:://do.org/100011////
Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael Jordan. Averaging stochastic gradient descent on Riemannian manifolds. CoRR, abs/1802.00128, 2018. URL http://rrvrr// 0bss/1802.09
Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM Journal on Optimization, 2(3), 2008. URL httpp::/www..ii....dddddtttbbbb. paperss adgm.pdf..
Bart Vandereycken. Low-rank matrix completion by Riemannian optimization. SIAM Journal on Optimization, 23(2):1214-1236, 2013. doi: 10. 10.1137/1 10845768. URL https:://oi.org/11... 10.1137/ 110845768.
Di Wang, Satish Rao, and Michael W. Mahoney. Unified acceleration method for packing and covering problems via diameter reduction. In 43rd International Colloquium Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016. Rome, Italy, pp. 50:1-50:13, 2016a. doi:
URL http:///oo.rrr...2200.0.........
14

---

Under review as a conference paper at ICLR 2023
Jinhua Wang, Chong Li, Genaro López-Acedo, and Jen-Chih Yao. Convergence analysis of inexact proximal point algorithms on hadamard manifolds. J. Glob. Optim.. 61(3):553-5733 2015. doi:
10.1007/ 1017///14--8-0--1102220 014-0182-2. URL https:// 1000000000000000088 -01-9888-1--112-22
Jinhua Wang, Chong Li, Genaro López-Acedo, and Jen-Chih Yao. Proximal point algorithms on hadamard manifolds: Linear convergence and finite termination. SIAM J. Optim., 26(4)2669-2229, 2016b. doi: 10.1 1371155555055 URL http://0...or1111111111111111111
Melanie Weber and Suvrit Sra. Frank- wolfe methods for geodesically convex optimization with application to the matrix geometric mean. CoRR, abs/1710.10770, 2017. URL http://arxxvvorr/ abs/1710.1077..
Melanie Weber and Suvrit Sra. Nonconvex stochastic optimization on manifolds via Riemannian Frank-Woll Wolfe methods. CoRR, abs/1910.04194, 2019. URL http://aarziiuu.r//aaa//// abs// 1910.04194,
Ke Wei, Jian-Feng Cai, Tony Chan, and Shingyu Leung. Guarantees of Riemannian optimization for low rank matrix completion. arXiv preprint arXiv:1603.06111 2016. URL https///axxivorr/ abs/1602. 06610.
Andre Wibisono, Ashia C. Wilson, and Michael I. Jordan, variational perspective on accelerated methods in optimization. CoRR, abs/1603 00245, 2016. URL http://aaxxiv.rr/// htt.:h/or///bb//0...4444/ 162.00445..
Ami Wiesel. Geodesic convexity and covariance estimation. IEEE Trans. Signal Process., 60(12): 6182-6189, 2012.
doi: 10. 10.11099TS220122211244 URL. https://doi.org/ 10. 109/TSP:2012.
2218241.
Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA. June 23-26. 2016, pp. 1617-1638, 2016. URL. http::/proceedingss.lrprpre
v49/ zhang hmml.
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 of Machine Learning Research, pp. 1703-1723. PMLR, 2018. URL http::/
wttpp/eees///////////// zhang himl.
Hongyi Zhang, Sashank J. Reddi, and Suvrit Sra. Riemannian SVRG: fast stochastic opti- mization on Riemannian manifolds. In 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. http://pupers. paper/ rall--iemannnn--ssrg--e fatts----tt--------tttts-------- wwwpehasstcc-opmmizattiooooooooe htwpriatttitt----iimmmmannntnnna riemammiat-manijoll..
Peiyuan Zhang, Jingzhao Zhang, and Suvrit Sra. Minimax in geodesic metric spaces: Sion's theorem and algorithms. CoRR, abs/2202.069500, 2022. URL httpss//arxivv.oor ab//2202.06950
Pan Zhou, Xiao-Tong Yuan, and Jiashi Feng. Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pp. 138 138-147, 2019. URL http:///poeeedinngs..irprsssssss zhoul 19a himl.
15


Reviews:
[{"review_id": "ji8LRji5v_", "reviewer": "Reviewer_E5FH", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper presents a theoretical result on accelerated methods for Riemannian optimization. In particular, it proposes  general Riemannian acceleration without iterates assumptively staying in the feasible set (which is an interesting open question posed earlier). \n", "summary_of_the_review": "I find the work interesting but very far from complete for the audience of this conference.", "strength_and_weaknesses": "Strengths:\nIt is an interesting piece of research which aims to solve an important theoretical problem in Riemannian optimization. The developments seem to be on solid foundation.\n\nWeakness:\nI find the paper far from complete. I would have liked to see some numerical experiments to see how useful Algorithm 1 is in practice to other methods. Without this, the paper looks very incomplete for the audience of this conference. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "e-jhiZtjPkQ", "reviewer": "Reviewer_S9aC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors propose an accelerated first-order method for the optimization of the Hadamard manifold. They theoretically show that the proposed algorithm enjoys the same convergence rate as Nesterov's accelerated gradient descent method in Euclidian space, under the assumption that the objective function is geodesically-convex. Besides, they can apply the linearly convergent algorithm to solve the subproblem in each iteration, which is a constrained strongly geodesical-convex smooth problem.", "summary_of_the_review": "This paper should be a very good theoretical paper, even though I can not understand all the details. However, owing to the lack of concrete applications and numerical experiments, I think it may not be suitable for this conference, so I recommend not accepting this paper. I further recommend the authors submit it to a journal directly, given its amazing theoretical contributions.", "strength_and_weaknesses": "Strength:\n1. The designed algorithm looks very interesting because it seems to be a combination of the extension of Nesterov's acceleration gradient method on the Riemannian manifold and the mirror descent algorithm. \n2. The theoretical results are very strong since the most accelerated algorithms can only be proved to enjoy the same convergence rate as standard GD, even though they perform much better than GD in practice.\n\nWeaknesses:\n1. This paper is very hard to understand. The authors should give more background on the problem and show some examples. At least there is no formally mathematical description of the problem. Besides, For each step in the algorithm, the authors should give more intuition to help us to understand it. \n2. No concrete example or application is mentioned in this paper. Even though it is a theoretical paper, the author should mention at least one concrete example that satisfies all the assumptions and can be solved well using the proposed algorithm.\n3. No simulation results. The author should compare their method with, for example, a non-accelerated first-order method to show the strength of acceleration.  It will be great if a better convergence rate is observed. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GtrYu3EDNw5", "reviewer": "Reviewer_qdaa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in Hadamard manifolds.It enjoys the same convergence rates as Nesterov’s accelerated gradient descent.The most improvement is that this method without the assumption that the iterates of their algorithms stay in some pre-specifified compact set.The theoretical work is comprehensive.", "summary_of_the_review": "Although the paper is theoretically sound, there are still some questions need to be discussed in this paper:\n1.\tIn written. Although we know what problem we study, It would be better to add  mathematical description .\n2.\tA mistake.In notation,  ||v-y||=||v-\\log_x(y)|| may be ||v-y||=||\\log_x(y)-y|| .\n3.\tAbout workload. The authors use a linearly convergent algorithm for constrained strongly g-convex smooth problems to implement the Line 8 of Algorithm 1.But from my point of view, the Riemacon instance for g-convex function is also important.Perhaps the authors want to add this in future work.\n", "strength_and_weaknesses": "Strength: This paper proposed a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in Hadamard manifolds. Technically strong, highly general results, advanced techniques", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject