Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Can Euclidean Symmetry be Leveraged in Reinforcement Learning and Planning?
In robotic tasks, changes in reference frames typically do not influence the underlying physical properties of the system, which has been known as invariance of physical laws.These changes, which preserve distance, encom…
reinforcement-learningReinforcement LearningEquivariant Action Sampling for Reinforcement Learning and Planning
Reinforcement learning (RL) algorithms for continuous control tasks require accurate sampling-based action selection. Many tasks, such as robotic manipulation, contain inherent problem symmetries. However, correctly inco…
continuous-controlContinuous ControlDecision Makingreinforcement-learning+2Improving Optimization for Models With Continuous Symmetry Breaking
Many loss functions in representation learning are invariant under a continuous symmetry transformation. For example, the loss function of word embeddings (Mikolov et al., 2013) remains unchanged if we simultaneously rot…
Representation LearningTime SeriesTime Series AnalysisWord EmbeddingsImproving Optimization in Models With Continuous Symmetry Breaking
Many loss functions in representation learning are invariant under a continuous symmetry transformation. For example, the loss function of word embeddings (Mikolov et al., 2013) remains unchanged if we simultaneousl…
Representation LearningTime SeriesTime Series AnalysisWord EmbeddingsMachine learning a manifold
We propose a simple method to identify a continuous Lie algebra symmetry in a dataset through regression by an artificial neural network. Our proposal takes advantage of the $ \mathcal{O}(\epsilon^2)$ scaling of the outp…
BIG-bench Machine Learningregression