Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory

• URL: http://arxiv.org/abs/2109.01080v1
• Date: Thu, 2 Sep 2021 16:44:44 GMT
• Title: Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory
• Authors: Jonathan Leake and Nisheeth K. Vishnoi
• Abstract summary: We show examples of Lieant's theorem, Lie groups, Lie algebras, and the Harish-Chandra--Itzyintegrals formulas. We then present an introduction to optimization theory -- an indispensable mathematical toolkit for capturing continuous symmetries.
• Score: 26.555110725656963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the last few years, the notion of symmetry has provided a powerful and essential lens to view several optimization or sampling problems that arise in areas such as theoretical computer science, statistics, machine learning, quantum inference, and privacy. Here, we present two examples of nonconvex problems in optimization and sampling where continuous symmetries play -- implicitly or explicitly -- a key role in the development of efficient algorithms. These examples rely on deep and hidden connections between nonconvex symmetric manifolds and convex polytopes, and are heavily generalizable. To formulate and understand these generalizations, we then present an introduction to Lie theory -- an indispensable mathematical toolkit for capturing and working with continuous symmetries. We first present the basics of Lie groups, Lie algebras, and the adjoint actions associated with them, and we also mention the classification theorem for Lie algebras. Subsequently, we present Kostant's convexity theorem and show how it allows us to reduce linear optimization problems over orbits of Lie groups to linear optimization problems over polytopes. Finally, we present the Harish-Chandra and the Harish-Chandra--Itzykson--Zuber (HCIZ) formulas, which convert partition functions (integrals) over Lie groups into sums over the corresponding (discrete) Weyl groups, enabling efficient sampling algorithms.

Related papers

• Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry [63.694184882697435]
  Global Covariance Pooling (GCP) has been demonstrated to improve the performance of Deep Neural Networks (DNNs) by exploiting second-order statistics of high-level representations.
  arXiv  Detail & Related papers  (2024-07-15T07:11:44Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Sum-of-Squares Relaxations for Information Theory and Variational Inference [0.0]
  We consider extensions of the Shannon relative entropy, referred to as $f$-divergences. We derive a sequence of convex relaxations for computing these divergences. We provide more efficient relaxations based on spectral information divergences from quantum information theory.
  arXiv  Detail & Related papers  (2022-06-27T13:22:40Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning. Ultimately, we helps the broader broader the broader the broader the broader the work.
  arXiv  Detail & Related papers  (2022-06-22T23:57:40Z)
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents [102.42623636238399]
  We identify fundamental geometric structures that underlie the problems of sampling, optimisation, inference and adaptive decision-making. We derive algorithms that exploit these geometric structures to solve these problems efficiently.
  arXiv  Detail & Related papers  (2022-03-20T16:23:17Z)
• Noncommutative polynomial optimization under symmetry [0.0]
  We present a general framework to exploit the symmetries present in the Navascu'es-Pironio-Ac'in semidefinite relaxations. We put equal emphasis on the moment and sum-of-squares dual approaches.
  arXiv  Detail & Related papers  (2021-12-20T19:02:16Z)
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization [8.59387261480044]
  We consider the geometric landscape connection of the widely studied manifold and factorization formulations in low-rank positive semidefinite (PSD) and general matrix optimization. We show the sandwich relation can be used to transfer more quantitative geometric properties from one formulation to another.
  arXiv  Detail & Related papers  (2021-08-03T22:14:01Z)
• Curvature-Dependant Global Convergence Rates for Optimization on Manifolds of Bounded Geometry [6.85316573653194]
  We give curvature-dependant convergence rates for weakly convex functions defined on a manifold of 1-bounded geometry. We compute these bounds explicitly for some manifold commonly used in the optimization literature. We present self-contained proofs of fully general bounds on the norm of the differential of the exponential map.
  arXiv  Detail & Related papers  (2020-08-06T08:30:35Z)
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula) [23.15629681360836]
  We prove an analytical formula for the reconstruction performance of convex generalized linear models. We show that an analytical continuation may be carried out to extend the result to convex (non-strongly) problems. We illustrate our claim with numerical examples on mainstream learning methods.
  arXiv  Detail & Related papers  (2020-06-11T16:26:35Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

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.