Geodesic Convex Optimization and Its Applications to Theory
Event details
| Date | 19.07.2018 |
| Hour | 12:15 › 14:15 |
| Speaker | Ozan Yildiz |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Patrick Thiran
Thesis advisor: Prof. Nisheeth Vishnoi
Co-examiner: Dr. Nicolas Macris
Abstract
We consider the application of geodesically convex optimization techniques to the computation of the optimal constant in the Brascamp-Lieb inequality. The computation of the optimal constant in the Brascamp-Lieb inequality is an important theoretical problem that generalizes other theoretical problems such as computation of the maximum entropy distribution and computation of the capacity of an operator with applications in machine learning, information theory, and theoretical computer science. Lieb [Lie90] proved that the optimal constant in the Brascamp-Lieb inequality has a non-convex optimization characterization, and the best-known algorithm to compute the optimal constant using this characterization [GGdOW17] runs in polynomial time in the unary bit-complexity of the input. Although Lieb's characterization is non-convex, it is jointly geodesically convex on the direct sum of canonical Hessian manifold over positive definite cones. Furthermore, it can be formulated as a geodesically convex problem on the canonical Hessian manifold over a single positive definite cone. Recently a polynomial time algorithm for a related problem, operator scaling, that is also geodesically convex on the same manifold, using geodesically convex optimization techniques proposed by Allen-Zhu et al. [AZGL+18]. We discuss the applicability of this algorithm and other geodesically convex optimization techniques to the computation of the optimal constant in the Brascamp-Lieb inequality.
Background papers
Entropy, Optimization and CountingMohit Singh, Nisheeth K. Vishnoi
Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling, by Ankit Garg, et al.
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing, by Zeyuan Allen-Zhu
Exam president: Prof. Patrick Thiran
Thesis advisor: Prof. Nisheeth Vishnoi
Co-examiner: Dr. Nicolas Macris
Abstract
We consider the application of geodesically convex optimization techniques to the computation of the optimal constant in the Brascamp-Lieb inequality. The computation of the optimal constant in the Brascamp-Lieb inequality is an important theoretical problem that generalizes other theoretical problems such as computation of the maximum entropy distribution and computation of the capacity of an operator with applications in machine learning, information theory, and theoretical computer science. Lieb [Lie90] proved that the optimal constant in the Brascamp-Lieb inequality has a non-convex optimization characterization, and the best-known algorithm to compute the optimal constant using this characterization [GGdOW17] runs in polynomial time in the unary bit-complexity of the input. Although Lieb's characterization is non-convex, it is jointly geodesically convex on the direct sum of canonical Hessian manifold over positive definite cones. Furthermore, it can be formulated as a geodesically convex problem on the canonical Hessian manifold over a single positive definite cone. Recently a polynomial time algorithm for a related problem, operator scaling, that is also geodesically convex on the same manifold, using geodesically convex optimization techniques proposed by Allen-Zhu et al. [AZGL+18]. We discuss the applicability of this algorithm and other geodesically convex optimization techniques to the computation of the optimal constant in the Brascamp-Lieb inequality.
Background papers
Entropy, Optimization and CountingMohit Singh, Nisheeth K. Vishnoi
Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling, by Ankit Garg, et al.
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing, by Zeyuan Allen-Zhu
Practical information
- General public
- Free
Contact
- EDIC - [email protected]