An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
Cutting plane method: the setup
Our result Separation oracle
History of cutting plane method
Oversimplified Vaidya 89 algorithm
The runtime bottleneck
Maintenance problem
Leverage score maintenance: the challenge
A multi-layered data structure
Matrix Multiplication Zoo
More General Cutting Plane Method
Applications
Questions?
Taught by
Association for Computing Machinery (ACM)