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

We study the online saddle point problem, an online learning problem where ateach iteration a pair of actions need to be chosen without knowledge of thecurrent and future (convex-concave) payoff functions. The objective is tominimize the gap between the cumulative payoffs and the saddle point value ofthe aggregate payoff function, which we measure using a metric called"SP-Regret". The problem generalizes the online convex optimization frameworkbut here we must ensure both players incur cumulative payoffs close to that ofthe Nash equilibrium of the sum of the games. We propose an algorithm thatachieves SP-Regret proportional to $\sqrt{\ln(T)T}$ in the general case, and$\log(T)$ SP-Regret for the strongly convex-concave case. We also consider thespecial case where the payoff functions are bilinear and the decision sets arethe probability simplex. In this setting we are able to design algorithms thatreduce the bounds on SP-Regret from a linear dependence in the dimension of theproblem to a \textit{logarithmic} one. We also study the problem under banditfeedback and provide an algorithm that achieves sublinear SP-Regret. We thenconsider an online convex optimization with knapsacks problem motivated by awide variety of applications such as: dynamic pricing, auctions, andcrowdsourcing. We relate this problem to the online saddle point problem andestablish $O(\sqrt{T})$ regret using a primal-dual algorithm.

The Online Saddle Point Problem and Online Convex Optimization with Knapsacks