Location: Gilman 132
When: March 9th at 1:30 p.m.
Title: Scalable, Projection-Free Optimization Methods
Abstract: We will introduce an approach to constrained optimization replacing orthogonal projections with much cheaper radial ones. This results in new first-order methods that are (i) scalable, sporting minimal per iteration costs, (ii) always yield fully feasible solutions, and (iii) applicable to a wide family of potentially nonconvex constraints. For example, when applied to linear programs, iteration costs amount to one matrix multiplication instead of more costly pivoting or matrix inverses. For semidefinite programming, iterations require computing one eigenvector, avoiding full decompositions. Beyond these classic settings, modern applications with nonconvex objectives and constraints will be discussed. The key mathematical insight underlying these methods is a new duality relating constrained optimization problems to unconstrained “radially dual” problems. From this, we will present accelerated projection-free first-order methods using smoothness, strong convexity, or other common structures in the primal objective or constraints.