Optimizing Optimization Methods with Computer Assistance, Ben Grimmer

Title: Optimizing Optimization Methods with Computer Assistance

Abstract: This talk will present highly optimized (sometimes minimax optimal) convergence theory for Gradient Descent, Frank-Wolfe, Alternating Projections, and other methods and key intuitions about optimal methods discovered along the way. Our optimized convergence theory is made possible by the use of a novel computer-assisted technology developed over the last decade called "Performance Estimation Problems" (PEPs). At their core, PEPs are infinite-dimensional problems, computing a worst-case problem instance from a given class for a given algorithm. The key ingredient to making PEPs useful for algorithm design is reducing them to an equivalent, tractable, finite-dimensional mathematical program. To facilitate our optimized convergence theory, we will develop new PEP reductions capable of computing worst-case constraint sets satisfying a range of possible structural conditions (smooth / strongly convex / bounded diameter / contains a Slater point).