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\le 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.