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

In this paper we propose a framework for solving constrained online convexoptimization problem. Our motivation stems from the observation that mostalgorithms proposed for online convex optimization require a projection ontothe convex set $\mathcal{K}$ from which the decisions are made. While forsimple shapes (e.g. Euclidean ball) the projection is straightforward, forarbitrary complex sets this is the main computational challenge and may beinefficient in practice. In this paper, we consider an alternative onlineconvex optimization problem. Instead of requiring decisions belong to$\mathcal{K}$ for all rounds, we only require that the constraints which definethe set $\mathcal{K}$ be satisfied in the long run. We show that our frameworkcan be utilized to solve a relaxed version of online learning with sideconstraints addressed in \cite{DBLP:conf/colt/MannorT06} and\cite{DBLP:conf/aaai/KvetonYTM08}. By turning the problem into an onlineconvex-concave optimization problem, we propose an efficient algorithm whichachieves $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound and$\tilde{\mathcal{O}}(T^{3/4})$ bound for the violation of constraints. Then wemodify the algorithm in order to guarantee that the constraints are satisfiedin the long run. This gain is achieved at the price of getting$\tilde{\mathcal{O}}(T^{3/4})$ regret bound. Our second algorithm is based onthe Mirror Prox method \citep{nemirovski-2005-prox} to solve variationalinequalities which achieves $\tilde{\mathcal{\mathcal{O}}}(T^{2/3})$ bound forboth regret and the violation of constraints when the domain $\K$ can bedescribed by a finite number of linear constraints. Finally, we extend theresult to the setting where we only have partial access to the convex set$\mathcal{K}$ and propose a multipoint bandit feedback algorithm with the samebounds in expectation as our first algorithm.

Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints