First-Order Methods and Hyperbolic Programming
summary
Shows how a hyperbolic program becomes an affine lambda_min maximization problem once a strictly feasible e is known, and how the boundary solution is recovered by the radial projection from e (a 1‑D root search). Replacing orthogonal projection with this radial map lets a subgradient method run using only a minimum eigenvector (not a full eigendecomposition). Complexity bounds: vanilla subgradient gives 1/epsilon^2, smoothing plus accelerated methods give ~1/epsilon (with log factors), and a parallel multi‑steps scheme achieves ~1/epsilon · log(1/epsilon) under quadratic growth.
AI-written summary · about
chapters (12)
- 0:00Start
- 0:23Basics for First-Order Methods
- 0:44First-Order Methods
- 3:26Basic Results for First Order Methods
- 4:39The Dependence on Epsilon
- 5:39Sub Gradient Methods
- 16:57Hypervelocity Cones Hyperbolic Programming
- 21:34Feasible Region
- 24:58Formula for the Radio Projection
- 33:58Smoothing
- 36:20Universal Method
- 45:26Quadratic Growth
related talks
46mSmooth Nonconvex Min-Max Optimization
51mAre Single-Loop Algorithms Sufficient for Unbalanced Minimax Optimization?
57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max Optimization
51mMin-max Optimization: From Complexity to Algorithms
27mTalk by Ali Kavis (UT Austin)
01h 11m(Hidden) Symmetries of Computational Problems (continued)
01h 04mSubmodularity: Theory and Applications I
12mEquilibrium Computation and the Foundations of Multi-Agent Machine Learning