TITLE: Learning Combinatorial Structures

ABSTRACT:

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 bottlenecks, we consider three fundamental convex and combinatorial optimization problems. First, we provide a conceptually simple algorithm to minimize separable convex functions over submodular base polytopes. For cardinality-based submodular functions, we show the current fastest-known running time of O(n(log n+d)), where n is the size of the ground set and d is the number of distinct values of the submodular function (d<=n). 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(n2), resulting in a running time improvement by at least n6 over the state of the art. Finally, we show how efficient counting methods can be used for convex minimization. This is joint work with Michel Goemans and Patrick Jaillet. 

Bio: Swati Gupta is a PhD candidate in the Operations Research Center (ORC) and Laboratory for Information and Decision Systems (LIDS) at MIT, 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, received a special recognition from the INFORMS Computing Society in 2016 and was a finalist in the INFORMS Service Science student paper award in 2016.