Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes

arXiv2106.11943MaRDI QIDQ6370987

Author name not available (Why is that?)

Publication date: 22 June 2021

Abstract: 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 first give necessary and sufficient conditions for when two close points project to the same face of a polytope, and then show that points far away from the polytope project onto its vertices with high probability. We next use this theory and develop a toolkit to speed up the computation of iterative projections over submodular polytopes 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.

Has companion code repository: https://github.com/jaimoondra/submodular-polytope-projections

This page was built for publication: Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370987)