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

We present new efficient \textit{projection-free} algorithms for onlineconvex optimization (OCO), where by projection-free we refer to algorithms thatavoid computing orthogonal projections onto the feasible set, and instead relayon different and potentially much more efficient oracles. While moststate-of-the-art projection-free algorithms are based on the\textit{follow-the-leader} framework, our algorithms are fundamentallydifferent and are based on the \textit{online gradient descent} algorithm witha novel and efficient approach to computing so-called \textit{infeasibleprojections}. As a consequence, we obtain the first projection-free algorithmswhich naturally yield \textit{adaptive regret} guarantees, i.e., regret boundsthat hold w.r.t. any sub-interval of the sequence. Concretely, when assumingthe availability of a linear optimization oracle (LOO) for the feasible set, ona sequence of length $T$, our algorithms guarantee $O(T^{3/4})$ adaptive regretand $O(T^{3/4})$ adaptive expected regret, for the full-information and banditsettings, respectively, using only $O(T)$ calls to the LOO. These bounds matchthe current state-of-the-art regret bounds for LOO-based projection-free OCO,which are \textit{not adaptive}. We also consider a new natural setting inwhich the feasible set is accessible through a separation oracle. We presentalgorithms which, using overall $O(T)$ calls to the separation oracle,guarantee $O(\sqrt{T})$ adaptive regret and $O(T^{3/4})$ adaptive expectedregret for the full-information and bandit settings, respectively.

New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees