Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties

• URL: http://arxiv.org/abs/2211.14645v1
• Date: Sat, 26 Nov 2022 19:28:48 GMT
• Title: Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties
• Authors: David Mart\'inez-Rubio and Sebastian Pokutta
• Abstract summary: We propose a globally-accelerated, first-order method for the optimization of smooth and geodesicallyrated functions. We achieve the same convergence rates as Nesterov's accelerated descent, up to a multipative compact set.
• Score: 20.711789781518753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in a wide class of Hadamard manifolds. We achieve 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 \textit{resort to assuming} that the iterates of their algorithms stay in some pre-specified compact set, except for two previous methods of limited applicability. For our manifolds, this solves the open question in [KY22] about obtaining global general acceleration without iterates assumptively staying in the feasible set.

Related papers

• Faster Acceleration for Steepest Descent [6.972653925522813]
  We propose a new accelerated first-order method for convex optimization under non-Euclidean smoothness assumptions. For $ell_p$ norm problems in $d$ dimensions, our method provides an complexity improvement of up to $O(d1-frac2p)$ in terms of calls to a first-order oracle.
  arXiv  Detail & Related papers  (2024-09-28T01:21:03Z)
• Riemannian Bilevel Optimization [35.42472057648458]
  We focus in particular on batch and gradient-based methods, with the explicit goal of avoiding second-order information. We propose and analyze $mathrmRF2SA$, a method that leverages first-order gradient information. We provide explicit convergence rates for reaching $epsilon$-stationary points under various setups.
  arXiv  Detail & Related papers  (2024-05-22T20:49:01Z)
• Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifold [59.73080197971106]
  This paper presents a first-order conjugate optimization method that converges faster than the steepest descent method. It aims to achieve global convergence over the Stiefel manifold.
  arXiv  Detail & Related papers  (2023-08-21T08:02:16Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration [33.247600151322466]
  We develop a deeper understanding of AdaGrad and its variants in the standard setting of smooth convex functions. First, we demonstrate new techniques to explicitly bound the convergence rate of the vanilla AdaGrad for unconstrained problems. Second, we propose a variant of AdaGrad for which we can show the convergence of the last iterate, instead of the average iterate.
  arXiv  Detail & Related papers  (2022-09-29T14:44:40Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• 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)
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
  In this work, we adapt the integral quadratic constraints theory to first-order methods for smooth and strongly-varying games and iteration. We provide emphfor the first time a global convergence rate for the negative momentum method(NM) with an complexity $mathcalO(kappa1.5)$, which matches its known lower bound. We show that it is impossible for an algorithm with one step of memory to achieve acceleration if it only queries the gradient once per batch.
  arXiv  Detail & Related papers  (2020-09-23T20:02:00Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  We generalize the approach Gasnikov et. al., 2017, which allows to solve (stochastic) convex optimization problems with an inexact gradient-free oracle. Our approach reduces $fracnlog n$ times the required number of oracle calls. In the second part of the paper, we analyze the case when such an assumption cannot be made, we propose a general approach on how to modernize the method to solve this problem.
  arXiv  Detail & Related papers  (2020-05-12T16:44:27Z)

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.