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

Online gradient descent (OGD) is well known to be doubly optimal under strongconvexity or monotonicity assumptions: (1) in the single-agent setting, itachieves an optimal regret of $\Theta(\log T)$ for strongly convex costfunctions; and (2) in the multi-agent setting of strongly monotone games, witheach agent employing OGD, we obtain last-iterate convergence of the jointaction to a unique Nash equilibrium at an optimal rate of$\Theta(\frac{1}{T})$. While these finite-time guarantees highlight its merits,OGD has the drawback that it requires knowing the strong convexity/monotonicityparameters. In this paper, we design a fully adaptive OGD algorithm,\textsf{AdaOGD}, that does not require a priori knowledge of these parameters.In the single-agent setting, our algorithm achieves $O(\log^2(T))$ regret understrong convexity, which is optimal up to a log factor. Further, if each agentemploys \textsf{AdaOGD} in strongly monotone games, the joint action convergesin a last-iterate sense to a unique Nash equilibrium at a rate of$O(\frac{\log^3 T}{T})$, again optimal up to log factors. We illustrate ouralgorithms in a learning version of the classical newsvendor problem, where dueto lost sales, only (noisy) gradient feedback can be observed. Our resultsimmediately yield the first feasible and near-optimal algorithm for both thesingle-retailer and multi-retailer settings. We also extend our results to themore general setting of exp-concave cost functions and games, using the onlineNewton step (ONS) algorithm.

Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback