Learning Combinatorial Structures

ACO Student Seminar
Friday, October 12, 2018 - 1:05pm
1 hour (actually 50 minutes)
Skiles 005
ISyE, Georgia Tech

At the heart of most algorithms today there is an optimization engine trying to learn online
and provide the best decision, for e.g.
rankings of objects, at any time with the partial information observed
thus far in time. Often it becomes difficult to find near optimal
solutions to many problems due to their inherent combinatorial structure that
leads to certain computational bottlenecks. Submodularity is a discrete
analogue of convexity and is a key property often exploited in tackling combinatorial optimization
In the first part of the talk, we will focus on computational
bottlenecks that involve submodular functions: (a) convex function
minimization over submodular base polytopes (for e.g. permutahedron) and
(b) movement along a line inside submodular base polytopes.
We give a conceptually simple and strongly polynomial algorithm Inc-Fix
for the former, which is useful in computing Bregman projections in
first-order projection-based methods like online mirror descent. For the
latter, we will bound the iterations of the
discrete Newton method which gives a running time improvement of at
least n^6 over the state of the art. This is joint work with Michel
Goemans and Patrick Jaillet. In the second part of the talk, we will
consider the dual problem of (a), i.e. minimization
of composite convex and submodular objectives. We will resolve Bach's
conjecture from 2015 about the running time of a popular Kelley's
cutting plane variant to minimize these composite objectives. This is
joint work with Madeleine Udell and Song Zhou.