English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Optimization algorithms such as projected Newton's method, FISTA, mirrordescent, and its variants enjoy near-optimal regret bounds and convergencerates, but suffer from a computational bottleneck of computing ``projections''in potentially each iteration (e.g., $O(T^{1/2})$ regret of online mirrordescent). On the other hand, conditional gradient variants solve a linearoptimization in each iteration, but result in suboptimal rates (e.g.,$O(T^{3/4})$ regret of online Frank-Wolfe). Motivated by this trade-off inruntime v/s convergence rates, we consider iterative projections of close-bypoints over widely-prevalent submodular base polytopes $B(f)$. We first givenecessary and sufficient conditions for when two close points project to thesame face of a polytope, and then show that points far away from the polytopeproject onto its vertices with high probability. We next use this theory anddevelop a toolkit to speed up the computation of iterative projections oversubmodular polytopes using both discrete and continuous perspectives. Wesubsequently adapt the away-step Frank-Wolfe algorithm to use this informationand enable early termination. For the special case of cardinality-basedsubmodular polytopes, we improve the runtime of computing certain Bregmanprojections by a factor of $\Omega(n/\log(n))$. Our theoretical results showorders of magnitude reduction in runtime in preliminary computationalexperiments.

Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes