Primal-Dual Algorithms for Hyperbolic Programming Problems

on YouTube ↗54m

" summary

Presents a primal‑dual method that uses the barrier f(x) = -log P(x) for hyperbolic cones, exploits negative curvature (Hessian maps cone into its dual), and follows the central path where the duality gap equals theta·mu. Algorithm minimizes a convex W‑metric (with a rank‑two update when needed), requires evaluating P and its gradient from a straight‑line program, and proves an iteration bound of sqrt(theta) log(1/epsilon); theory guarantees the bound and polynomial‑time behavior given the input format.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 2:20Polynomials and cones
3. 6:35Optimization problem setup
4. 9:05Feasibility and duals
5. 11:45Barrier function properties
6. 17:11Geometric insights
7. 25:26Local metrics and geometry
8. 32:49Central path and updates
9. 37:38Algorithmic results
10. 43:05Special cone classes
11. 44:31Q&A session

" related talks

• 51mAre Single-Loop Algorithms Sufficient for Unbalanced Minimax Optimization?Niao He · Adversarial Approaches in Machine Learning 2022
• 01h 01mDuality 1Michel Goemans · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 51mMin-max Optimization: From Complexity to AlgorithmsEmmanouil Zampetakis · Adversarial Approaches in Machine Learning 2022
• 11mGeometric Methods for Machine Learning and OptimizationMelanie Weber · Meet the Fellows Welcome Event
• 01h 02mDuality 2Michel Goemans · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 12mGeodesic Convexity and OptimizationSuvrit Sra · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 11m(Hidden) Symmetries of Computational Problems (continued)Michael Walter, Avi Wigderson · Geometric Methods in Optimization and Sampling Boot Camp
• 18mReLU Hull ApproximationZhongkui Ma, Guangdong Bai, Jiaying Li · POPL 2024