Real-Time Decision Making Seminar

Learning with Combinatorial Structure

At the heart of most algorithms today, there is an optimization engine trying to provide the best decision with partial information observed thus far in time, the so-called problem of online learning. Often it becomes difficult to find near-optimal solutions to these problems due to their inherent combinatorial structure that leads to certain computational bottlenecks, for instance, computing Bregman projections for online mirror descent and its variants. Motivated by these bottleneck, we consider two fundamental convex and combinatorial optimization problems. First, we provide a conceptually simple algorithm to minimize separable convex functions over submodular base polytopes. This algorithm generalizes many known special cases, and enjoys a direct proof from first-order optimality conditions. Next, we consider the problem of movement along a line while staying feasible in submodular polytopes. The use of the discrete Newton’s method for this line search problem is natural, but no strongly polynomial bound on its number of iterations was known. We solve this open problem by providing a quadratic bound of O(n^2), resulting in a running time improvement by at least n^6 over the state of the art. This is joint work with MIchel Goemans and Patrick Jaillet.

Swati Gupta is currently a Research Fellow in the Real-Time Decision Making program at the Simons Institute for the Theory of Computing, UC Berkeley. She obtained her doctoral degree from the Operations Research Center at MIT in 2017 and was jointly advised by Michel Goemans and Patrick Jaillet. She graduated from Indian Institute of Technology (IIT), Delhi, in 2011 with dual Bachelors and Masters degree in Computer Science and Engineering. She won the Google Women in Engineering Award in 2011, special recognition from INFORMS Computing Society in 2016 and was a finalist in the INFORMS Service Science student paper award in 2016. Starting July 2018, Swati Gupta will be an assistant professor in the Industrial and Systems Engineering department at Georgia Institute of Technology.

Anyone who would like to give one of the weekly seminars on the RTDM program can fill in the survey at https://goo.gl/forms/Li5jQ0jm01DeYZVC3.