  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.
