A Riemannian Accelerated Proximal Extragradient Framework and its Implications

• URL: http://arxiv.org/abs/2111.02763v1
• Date: Thu, 4 Nov 2021 11:32:20 GMT
• Title: A Riemannian Accelerated Proximal Extragradient Framework and its Implications
• Authors: Jikai Jin and Suvrit Sra
• Abstract summary: We revisit the emphAccelerated Hybrid Proximal Extragradient (A-HPE) method of citetmonteiro2013accelerated, a powerful framework for obtaining accelerated Euclidean methods.
• Score: 52.31775617527208
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The study of accelerated gradient methods in Riemannian optimization has recently witnessed notable progress. However, in contrast with the Euclidean setting, a systematic understanding of acceleration is still lacking in the Riemannian setting. We revisit the \emph{Accelerated Hybrid Proximal Extragradient} (A-HPE) method of \citet{monteiro2013accelerated}, a powerful framework for obtaining accelerated Euclidean methods. Subsequently, we propose a Riemannian version of A-HPE. The basis of our analysis of Riemannian A-HPE is a set of insights into Euclidean A-HPE, which we combine with a careful control of distortion caused by Riemannian geometry. We describe a number of Riemannian accelerated gradient methods as concrete instances of our framework.

Related papers

• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Riemannian accelerated gradient methods via extrapolation [40.23168342389821]
  We show when the iterates are generated from the gradient descent method, the accelerated scheme achieves the optimal convergence rateally. Our experiments verify the practical benefit of the novel acceleration strategy.
  arXiv  Detail & Related papers  (2022-08-13T10:31:09Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds [9.173528450234906]
  Greene and Wu introduced a convolution, known as Greene-Wu (GW) convolution. In this paper, we introduce a reformulation of the GW convolution. Also enabled by our new reformulation, an improved method for gradient estimation is introduced.
  arXiv  Detail & Related papers  (2021-08-17T02:16:15Z)
• Acceleration Methods [57.202881673406324]
  We first use quadratic optimization problems to introduce two key families of acceleration methods. We discuss momentum methods in detail, starting with the seminal work of Nesterov. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates.
  arXiv  Detail & Related papers  (2021-01-23T17:58:25Z)
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces [0.0]
  Research on the acceleration phenomenon on Euclidian curvature by the first global firstorder method. First order method achieves the same rates as in Euclidean gradient as accelerated gradient descent.
  arXiv  Detail & Related papers  (2020-12-07T12:09:30Z)
• From Nesterov's Estimate Sequence to Riemannian Acceleration [52.99237600875452]
  We develop an alternative analysis for Nesterov's estimate sequence technique that may also be of independent interest. Then, we extend this analysis to the Riemannian setting, localizing the key difficulty due to non-Euclidean structure into a certain metric distortion''
  arXiv  Detail & Related papers  (2020-01-24T04:17:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.