Timezone: »

Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes
Jai Moondra · Hassan Mortagy · Swati Gupta

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing ``projections" in potentially each iteration (e.g., $O(T^{1/2})$ regret of online mirror descent). On the other hand, conditional gradient variants solve a linear optimization in each iteration, but result in suboptimal rates (e.g., $O(T^{3/4})$ regret of online Frank-Wolfe). Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points over widely-prevalent submodular base polytopes $B(f)$. We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives. We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination. For the special case of cardinality based submodular polytopes, we improve the runtime of computing certain Bregman projections by a factor of $\Omega(n/\log(n))$. Our theoretical results show orders of magnitude reduction in runtime in preliminary computational experiments.

Author Information

Jai Moondra (Georgia Institute of Technology)
Hassan Mortagy (Georgia Institute of Technology)
Swati Gupta (Georgia Institute of Technology)

More from the Same Authors