2021
Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes
NeurIPS 2021poster
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…