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

Conditional gradient methods (CGM) are widely used in modern machinelearning. CGM's overall running time usually consists of two parts: the numberof iterations and the cost of each iteration. Most efforts focus on reducingthe number of iterations as a means to reduce the overall running time. In thiswork, we focus on improving the per iteration cost of CGM. The bottleneck stepin most CGM is maximum inner product search (MaxIP), which requires a linearscan over the parameters. In practice, approximate MaxIP data-structures arefound to be helpful heuristics. However, theoretically, nothing is known aboutthe combination of approximate MaxIP data-structures and CGM. In this work, weanswer this question positively by providing a formal framework to combine thelocality sensitive hashing type approximate MaxIP data-structures with CGMalgorithms. As a result, we show the first algorithm, where the cost periteration is sublinear in the number of parameters, for many fundamentaloptimization algorithms, e.g., Frank-Wolfe, Herding algorithm, and policygradient.

Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures