Quantitative Convergences of Lie Group Momentum Optimizers

• URL: http://arxiv.org/abs/2405.20390v1
• Date: Thu, 30 May 2024 18:01:14 GMT
• Title: Quantitative Convergences of Lie Group Momentum Optimizers
• Authors: Lingkai Kong, Molei Tao,
• Abstract summary: This article investigates two types of discretization, Lie Heavy-Ball and Lie NAG-SC, which is newly proposed. Lie Heavy-Ball and Lie NAG-SC are computationally cheaper and easier to implement, thanks to their utilization of group structure.
• Score: 21.76159063788814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Explicit, momentum-based dynamics that optimize functions defined on Lie groups can be constructed via variational optimization and momentum trivialization. Structure preserving time discretizations can then turn this dynamics into optimization algorithms. This article investigates two types of discretization, Lie Heavy-Ball, which is a known splitting scheme, and Lie NAG-SC, which is newly proposed. Their convergence rates are explicitly quantified under $L$-smoothness and local strong convexity assumptions. Lie NAG-SC provides acceleration over the momentumless case, i.e. Riemannian gradient descent, but Lie Heavy-Ball does not. When compared to existing accelerated optimizers for general manifolds, both Lie Heavy-Ball and Lie NAG-SC are computationally cheaper and easier to implement, thanks to their utilization of group structure. Only gradient oracle and exponential map are required, but not logarithm map or parallel transport which are computational costly.

Related papers

• Convergence of Kinetic Langevin Monte Carlo on Lie groups [21.76159063788814]
  We propose a Lie-group MCMC sampler, by delicately discretizing the resulting kinetic-Langevin-type sampling dynamics. This is the first convergence result for kinetic Langevin on curved spaces, and also the first quantitative result that requires no convexity or, at least not explicitly, any common relaxation such as isoperimetry.
  arXiv  Detail & Related papers  (2024-03-18T17:50:20Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  We show that by efficiently parallelizing existing causal discovery methods, we can scale them to thousands of dimensions. Specifically, we focus on the causal ordering subprocedure in DirectLiNGAM and implement GPU kernels to accelerate it. This allows us to apply DirectLiNGAM to causal inference on large-scale gene expression data with genetic interventions yielding competitive results.
  arXiv  Detail & Related papers  (2024-03-06T15:06:11Z)
• Optimal Potential Shaping on SE(3) via Neural ODEs on Lie Groups [4.595636071139437]
  We rephrase dynamic systems as neural ordinary differential equations (neural ODEs) A gradient descent optimization algorithm is presented to tackle the optimization numerically. In an extensive example, optimal potential energy shaping for control of a rigid body is treated.
  arXiv  Detail & Related papers  (2024-01-25T16:26:44Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• Accelerated Distributed Aggregative Optimization [5.5491171448159715]
  We propose two novel algorithms named DAGT-HB and DAGT-NES for solving the distributed aggregative optimization problem. We analyse that the DAGT-HB and DAGT-NES algorithms can converge to an optimal solution at a global $mathbfR-$linear convergence rate.
  arXiv  Detail & Related papers  (2023-04-17T08:11:01Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  We optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance.
  arXiv  Detail & Related papers  (2021-10-26T15:02:27Z)
• Momentum Doesn't Change the Implicit Bias [36.301490759243876]
  We analyze the implicit bias of momentum-based optimization. We construct new Lyapunov functions as a tool to analyze the gap between the model parameter and the max-margin solution.
  arXiv  Detail & Related papers  (2021-10-08T04:37:18Z)
• 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)
• Parameter-free Locally Accelerated Conditional Gradients [91.19349793915615]
  We introduce a novel,. Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms.
  arXiv  Detail & Related papers  (2021-02-12T22:50:01Z)
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems [10.203602318836444]
  The article considers smooth optimization of functions on Lie groups. By generalizing NAG variational principle in vector space to Lie groups, continuous Lie-NAG dynamics which are guaranteed to converge to local optimum are obtained.
  arXiv  Detail & Related papers  (2020-01-27T19:00:03Z)

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.