Several first order stochastic optimization methods commonly used in the Euclidean domain such as stochastic gradient descent (SGD), accelerated gradient descent or variance reduced methods have already been adapted to certain Riemannian settings. However, some of the most popular of these optimization tools - namely Adam, Adagrad and the more recent Amsgrad - remain to be generalized to Riemannian manifolds. We discuss the difficulty of generalizing such adaptive schemes to the most agnostic Riemannian setting, and then provide algorithms and convergence proofs for geodesically convex objectives in the particular case of a product of Riemannian manifolds, in which adaptivity is implemented across manifolds in the cartesian product. Our generalization is tight in the sense that choosing the Euclidean space as Riemannian manifold yields the same algorithms and regret bounds as those that were already known for the standard algorithms. Experimentally, we show faster convergence and to a lower train loss value for Riemannian adaptive methods over their corresponding baselines on the realistic task of embedding the WordNet taxonomy in the Poincare ball. Developing powerful stochastic gradient-based optimization algorithms is of major importance for a variety of application domains. In particular, for computational efficiency, it is common to opt for a first order method, when the number of parameters to be optimized is great enough. Such cases have recently become ubiquitous in engineering and computational sciences, from the optimization of deep neural networks to learning embeddings over large vocabularies.This new need resulted in the development of empirically very successful first order methods such as ADAGRAD BID5 , ADADELTA BID29 , ADAM BID9 or its recent update AMSGRAD BID18 .Note that these algorithms are designed to optimize parameters living in a Euclidean space R n , which has often been considered as the default geometry to be used for continuous variables. However , a recent line of work has been concerned with the optimization of parameters lying on a Riemannian manifold, a more general setting allowing non-Euclidean geometries. This family of algorithms has already found numerous applications, including for instance solving Lyapunov equations BID27 , matrix factorization BID23 , geometric programming BID22 , dictionary learning BID2 or hyperbolic taxonomy embedding BID15 BID6 BID4 BID14 .A few first order stochastic methods have already been generalized to this setting (see section 6), the seminal one being Riemannian stochastic gradient descent (RSGD) BID1 , along with new methods for their convergence analysis in the geodesically convex case . However, the above mentioned empirically successful adaptive methods, together with their convergence analysis, remain to find their respective Riemannian counterparts.Indeed, the adaptivity of these algorithms can be thought of as assigning one learning rate per coordinate of the parameter vector. However, on a Riemannian manifold, one is generally not given an intrinsic coordinate system, rendering meaningless the notions sparsity or coordinate-wise update.Our contributions. In this work we (i) explain why generalizing these adaptive schemes to the most agnostic Riemannian setting in an intrinsic manner is compromised, and (ii) propose generalizations of the algorithms together with their convergence analysis in the particular case of a product of manifolds where each manifold represents one "coordinate" of the adaptive scheme. Finally, we (iii) empirically support our claims on the realistic task of hyperbolic taxonomy embedding.Our initial motivation. The particular application that motivated us in developing Riemannian versions of ADAGRAD and ADAM was the learning of symbolic embeddings in non-Euclidean spaces. As an example, the GloVe algorithm BID17 ) − an unsupervised method for learning Euclidean word embeddings capturing semantic/syntactic relationships − benefits significantly from optimizing with ADAGRAD compared to using SGD, presumably because different words are sampled at different frequencies. Hence the absence of Riemannian adaptive algorithms could constitute a significant obstacle to the development of competitive optimization-based Riemannian embedding methods. In particular, we believe that the recent rise of embedding methods in hyperbolic spaces could benefit from such developments BID15 BID6 b; BID4 BID28 . Driven by recent work in learning non-Euclidean embeddings for symbolic data, we propose to generalize popular adaptive optimization tools (e.g. ADAM, AMSGRAD, ADAGRAD) to Cartesian products of Riemannian manifolds in a principled and intrinsic manner. We derive convergence rates that are similar to the Euclidean corresponding models. Experimentally we show that our methods outperform popular non-adaptive methods such as RSGD on the realistic task of hyperbolic word taxonomy embedding. DISPLAYFORM0 i * . Combining the following formula 8 : DISPLAYFORM1 with the following inequality (given by lemma 6): DISPLAYFORM2 yields DISPLAYFORM3 where the use the notation ·, · x i for ρ DISPLAYFORM4 Now applying Cauchy-Schwarz' and Young's inequalities to the last term yields DISPLAYFORM5 From the geodesic convexity of f t for 1 ≤ t ≤ T , we have DISPLAYFORM6 Let's look at the first term. Using β 1t ≤ β 1 and with a change of indices, we have DISPLAYFORM7 where the last equality comes from a standard telescopic summation. We now need the following lemma.Lemma 3. DISPLAYFORM8 Proof. Let's start by separating the last term, and removing the hat on v. Using that β 1k ≤ β 1 for all k ∈ [T ], (1 − β 1j )β DISPLAYFORM9 Finally, (1 − β 1j ) ≤ 1 and
Adapting Adam, Amsgrad, Adagrad to Riemannian manifolds. 
{"src": "scitldr-AIC_train", "paper_id": "r1eiqi09K7"}