(Hidden) Symmetries of Computational Problems (continued)
summary
Claims that geodesic convexity explains why greedy scaling (e.g., Sinkhorn) works, and that three problems — nullcone membership, norm minimization (capacity) and setting the moment map to zero — are equivalent and analyzable via that geometry. Constructions show gradients recover row/column sums and operator marginals; algorithms (gradient descent, trust-region Newton) converge with rates depending on explicit group-derived constants L and γ, where γ can be exponentially small so worst-case time blows up. The reachable marginals form a moment polytope (Newton polytope in commutative cases), often exponentially large but sometimes efficiently testable.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 5:08Overview
- 6:18NALCON
- 10:43Recap
- 22:41Noncommutative Setting
- 28:19Operator Scaling
- 36:48Smoothness
- 43:28Summary
- 47:08Algorithm
- 53:43Gain
related talks
46mSmooth Nonconvex Min-Max Optimization
57mHigh Dimensional Geometry and Concentration I
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
01h 01mRobustness, Stochastics, Uncertainty 2
58mContinuous Methods 2
11mGeometric Methods for Machine Learning and Optimization
01h 18mOptimization I
01h 03mMathematical connections of some local-to-global expressivity results over geometric graphs and...