Population-Based Optimization on Riemannian Manifolds (Studies in Computational Intelligence, 1046)

✍ Scribed by Robert Simon Fong, Peter Tino

• Publisher: Springer
• Year: 2022
• Tongue: English
• Leaves: 171
• Category: Library

✦ Synopsis

Manifold optimization is an emerging field of contemporary optimization that constructs efficient and robust algorithms by exploiting the specific geometrical structure of the search space. In our case the search space takes the form of a manifold.

Manifold optimization methods mainly focus on adapting existing optimization methods from the usual “easy-to-deal-with” Euclidean search spaces to manifolds whose local geometry can be defined e.g. by a Riemannian structure. In this way the form of the adapted algorithms can stay unchanged. However, to accommodate the adaptation process, assumptions on the search space manifold often have to be made. In addition, the computations and estimations are confined by the local geometry.

This book presents a framework for population-based optimization on Riemannian manifolds that overcomes both the constraints of locality and additional assumptions. Multi-modal, black-box manifold optimization problems on Riemannian manifolds can be tackled using zero-order stochastic optimization methods from a geometrical perspective, utilizing both the statistical geometry of the decision space and Riemannian geometry of the search space.

This monograph presents in a self-contained manner both theoretical and empirical aspects of stochastic population-based optimization on abstract Riemannian manifolds.

✦ Table of Contents

Contents
Acronyms
1 Introduction
1.1 Motivation
1.2 Overview
1.3 Detailed Book Synopsis
References
Part I Information Geometry of Probability Densities Over Riemannian Manifolds
2 Riemannian Geometry: A Brief Overview
2.1 Smooth Topological Manifolds
2.2 Tangent Spaces, Metric and Curvature
2.2.1 Tangent Bundle and Riemannian Metric
2.2.2 Affine Connection and Parallel Transport
2.2.3 Parallel Transport
2.3 Domain of Computation: Exponential Map and Normal Neighbourhood
2.3.1 Parallel Transport in Geodesic Balls/Normal Neighborhoods
2.4 Discussion and Outlook
References
3 Elements of Information Geometry
3.1 Statistical Manifolds
3.2 Levi-Civita Connection and Dual Connections
3.3 Curvature, Flatness and Dually Flat
3.4 Discussion
References
4 Probability Densities on Manifolds
4.1 Volume on Riemannian Manifold in the Literature
4.1.1 Co-Tangent Bundle
4.1.2 Volume and Density Function
4.2 Intrinsic Probability Densities on Manifolds
4.3 Discussion
References
5 Dualistic Geometry of Locally Inherited Parametrized Densities on Riemannian Manifolds
5.1 Naturality of Dualistic Structure
5.1.1 Computing Induced Dualistic Structure
5.2 Locally Inherited Probability Densities on Manifolds
5.2.1 Local Probability Densities on Manifolds via Bundle Morphism
5.2.2 Special Case—``Statistical'' Approach of Local Probability Densities on Manifolds via Riemannian Exponential Map
5.3 Discussion and Outlook
References
6 Mixture Densities on Totally Bounded Subsets of Riemannian Manifolds
6.1 Refinement of Orientation-Preserving Open Cover
6.2 Mixture Densities on Totally Bounded Subsets of Riemannian Manifolds
6.3 Geometrical Structure of Mixture densities
6.3.1 Mixture Densities as a Smooth Manifold
6.3.2 Torsion-Free Dualistic Structure on Mixture densities
6.4 Mixture densities as a Product Statistical Manifold
6.5 Towards a Population-Based Optimization Method on Riemannian Manifolds
References
Part II Model-Based Stochastic Derivative-Free Optimization on Riemannian Manifolds
7 Geometry in Optimization
7.1 Principle of Riemannian Adaptation
7.1.1 Riemannian Gradient and Hessian
7.2 Examples of Riemannian Adaptation of Optimization Algorithms in the Literature
7.2.1 Riemannian Gradient-Based Optimization
7.2.2 Riemannian Particle Swarm Optimization
7.2.3 Riemannian CMA-ES
7.3 Bridging Information Geometry, Stochastic Optimization and Riemannian Optimization
References
8 Stochastic Derivative-Free Optimization on Riemannian Manifolds
8.1 RSDFO: Riemannian Stochastic Derivative-Free Optimization Algorithms
8.1.1 Discussion, Shortcoming and Improvements
8.2 Extended RSDFO on Riemannian Manifolds
8.2.1 Parametrized Mixture Distribution on Totally Bounded Subsets of Riemannian Manifold
8.2.2 Extended RSDFO
8.2.3 Additional Parameters
8.2.4 Evolutionary Step
8.2.5 Monotone Improvement on Expected Fitness
8.2.6 Exploration Distribution of Extended RSDFO
8.2.7 Termination Criterion
8.3 Geometry of Evolutionary Step of Extended RSDFO
8.3.1 Geometry and Simplicial Illustration of Evolutionary Step
8.3.2 Detailed Description of Evolutionary Step
8.4 Convergence of Extended RSDFO on Compact Connected Riemannian Manifolds
8.4.1 Detailed Exposition of Convergence Behaviour of Extended RSDFO
8.5 Discussion
References
9 Illustrative Examples
9.1 On the Assumptions of Manifold Optimization Algorithms in the Literature
9.2 Hyperparameters of Algorithms and Experiment Set-Up
9.3 Sphere S2
9.4 Grassmannian Manifolds
9.5 Jacob's Ladder
9.6 Discussion
9.6.1 On Sphere and Grassmannian Manifold
9.6.2 On Jacob's Ladder
References
10 Conclusion and Future Research
10.1 Conclusion
10.2 Future Research
References
Appendix Index
Index