活动

Title:  Alternating Linear Minimization: Revisiting von Neumann’s alternating projections

Abstract: 

In 1933 von Neumann proved a beautiful result that one can compute a point in the intersection of two convex sets (under suitable assumptions) by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. Here we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets. Moreover, we provide a modification of the algorithm to minimize a linear function over the intersection and discuss further extensions.

Biography:  Sebastian Pokutta

Sebastian Pokutta serves as the Vice President of the Zuse Institute Berlin and is a Professor at TU Berlin, focusing on Artificial Intelligence and Optimization. He completed his education at the University of Duisburg-Essen in Germany, followed by postdoctoral work at MIT, roles at IBM ILOG, and various consulting companies. Before his current positions, he was the David M. McKenney Family Associate Professor in the School of Industrial and Systems Engineering and an Associate Director of the Machine Learning @ GT Center at the Georgia Institute of Technology as well as a Professor at the University of Erlangen-Nürnberg. His accolades include the prestigious Gödel Prize in 2023, the STOC Test of Time award in 2022, and several early career and best paper awards. 

Speaker:  Sebastian Pokutta

Time:  March 7^th, 10:00 – 10:45

Room:  Boardroom, DY103, Daoyuan Building