Computation, complexity and curvature in information geometry
- Atsumi Ohara (Osaka University, Japan)
Abstract
Euler-Schouten embedding curvature (the second fundamental form) plays an important role in not only geometry itself but also computational mathematics or scientific computing.
A well-known example would be a relation with performance of estimators in statistical inference, which was elucidated by the Amari's seminal work.
In this talk, we show that iteration-complexity of an interior-point algorithm for conic linear programming problems (e.g., linear or semidefinite programming and so on) is characterized by dual embedding curvature of a feasible region, or specifically, what is called a central trajectory.
In an extreme case where the curvature vanishes, we can construct a formula for an optimal solution, and hence, need no iterations to solve it. The related topics will also be presented.
The talk is partly based on a joint work with Takashi Tsuchiya at ISM Japan.
