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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently, several works have shown that natural modifications of theclassical conditional gradient method (aka Frank-Wolfe algorithm) forconstrained convex optimization, provably converge with a linear rate when: i)the feasible set is a polytope, and ii) the objective is smooth andstrongly-convex. However, all of these results suffer from two significantshortcomings: large memory requirement due to the need to store an explicitconvex decomposition of the current iterate, and as a consequence, largerunning-time overhead per iteration, and worst case convergence rate thatdepends unfavorably on the dimension.  In this work we present a new conditional gradient variant and acorresponding analysis that improves on both of the above shortcomings. Inparticular: both memory and computation overheads are only linear in thedimension. Moreover, in case the optimal solution is sparse, the newconvergence rate replaces a factor which is at least linear in the dimension inprevious works, with a linear dependence on the number of non-zeros in theoptimal solution.  At the heart of our method, and corresponding analysis, is a novel way tocompute decomposition-invariant away-steps. While our theoretical guarantees donot apply to any polytope, they apply to several important structured polytopesthat capture central concepts such as paths in graphs, perfect matchings inbipartite graphs, marginal distributions that arise in structured predictiontasks, and more. Our theoretical findings are complemented by empiricalevidence which shows that our method delivers state-of-the-art performance.

Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes