2021/06/22 by Jai Moondra, Moondra, Jai, Hassan Mortagy +4 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2106.11943
openalex publication_date 2021/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Optimization algorithms such as projected Newton's method, FISTA, mirror\ndescent, and its variants enjoy near-optimal regret bounds and convergence\nrates, but suffer from a computational bottleneck of computing ``projections''\nin potentially each iteration (e.g., O(T1/2) regret of online mirror\ndescent). On the other hand, conditional gradient variants solve a linear\noptimization in each iteration, but result in suboptimal rates (e.g.,\nO(T3/4) regret of online Frank-Wolfe). Motivated by this trade-off in\nruntime v/s convergence rates, we consider iterative projections of close-by\npoints over widely-prevalent submodular base polytopes B(f). We first give\nnecessary and sufficient conditions for when two close points project to the\nsame face of a polytope, and then show that points far away from the polytope\nproject onto its vertices with high probability. We next use this theory and\ndevelop a toolkit to speed up the computation of iterative projections over\nsubmodular polytopes using both discrete and continuous perspectives. We\nsubsequently adapt the away-step Frank-Wolfe algorithm to use this information\nand enable early termination. For the special case of cardinality-based\nsubmodular polytopes, we improve the runtime of computing certain Bregman\nprojections by a factor of \Ω(n/\log(n)). Our theoretical results show\norders of magnitude reduction in runtime in preliminary computational\nexperiments.\n