At the heart of most applications 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. We first consider a near-optimal learning algorithm, online mirror descent, which requires the computation of a certain Bregman projection over the combinatorial decision set. Submodularity is a key property often exploited in tackling combinatorial optimization problems. We provide a conceptually simple algorithm to compute these projections over submodular base polytopes. For cardinality-based submodular functions, we show the 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 a related question 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 very 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. Finally, we discuss our recent result that shows efficient counting methods can be used for convex minimization.

This is joint work with Michel Goemans and Patrick Jaillet.

Bio: 
Swati Gupta is a Ph.D. candidate in the Operations Research Center (ORC) (also affiliated with the 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 Master’s degrees 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.