Optimal Dynamic Regret in Proper Online Learning with Strongly Convex
Losses and Beyond
- URL: http://arxiv.org/abs/2201.08905v1
- Date: Fri, 21 Jan 2022 22:08:07 GMT
- Title: Optimal Dynamic Regret in Proper Online Learning with Strongly Convex
Losses and Beyond
- Authors: Dheeraj Baby and Yu-Xiang Wang
- Abstract summary: We show that in a proper learning setup, Strongly Adaptive algorithms can achieve the near optimal dynamic regret.
We also derive near optimal dynamic regret rates for the special case of proper online learning with exp-concave losses.
- Score: 23.91519151164528
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the framework of universal dynamic regret minimization with strongly
convex losses. We answer an open problem in Baby and Wang 2021 by showing that
in a proper learning setup, Strongly Adaptive algorithms can achieve the near
optimal dynamic regret of $\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3}
\vee d)$ against any comparator sequence $u_1,\ldots,u_n$ simultaneously, where
$n$ is the time horizon and $\text{TV}[u_{1:n}]$ is the Total Variation of
comparator. These results are facilitated by exploiting a number of new
structures imposed by the KKT conditions that were not considered in Baby and
Wang 2021 which also lead to other improvements over their results such as: (a)
handling non-smooth losses and (b) improving the dimension dependence on
regret. Further, we also derive near optimal dynamic regret rates for the
special case of proper online learning with exp-concave losses and an
$L_\infty$ constrained decision set.
Related papers
- Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
We propose an online convex optimization approach with two different levels of adaptivity.
We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
arXiv Detail & Related papers (2023-07-17T09:55:35Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
We investigate the dynamic regret of online Frank-Wolfe (OFW), which is an efficient projection-free algorithm for online convex optimization.
In this paper, we derive improved dynamic regret bounds for OFW by extending the fast convergence rates of FW from offline optimization to online optimization.
arXiv Detail & Related papers (2023-02-11T07:19:51Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
We show that regret can be obtained for general convex and compact strategy sets.
Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space.
Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
arXiv Detail & Related papers (2022-06-17T12:58:58Z) - Second Order Path Variationals in Non-Stationary Online Learning [23.91519151164528]
We show that appropriately designed Strongly Adaptive algorithms achieve a dynamic regret of $tilde O(d2 n1/5 C_n2/5 vee d2)$.
The aforementioned dynamic regret rate is shown to be optimal modulo dimension dependencies and poly-logarithmic factors of $n$.
arXiv Detail & Related papers (2022-05-04T07:14:39Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game.
We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
arXiv Detail & Related papers (2021-11-11T01:19:53Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
We study the problem of emphdynamic regret minimization in $K$-armed Dueling Bandits under non-stationary or time varying preferences.
This is an online learning setup where the agent chooses a pair of items at each round and observes only a relative binary win-loss' feedback for this pair.
arXiv Detail & Related papers (2021-11-06T16:46:55Z) - Optimal Dynamic Regret in Exp-Concave Online Learning [28.62891856368132]
We consider the problem of the Zinkevich (2003)-style dynamic regret minimization in online learning with exp-contrivial losses.
We show that whenever improper learning is allowed, a Strongly Adaptive online learner achieves the dynamic regret of $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ where $C_n$ is the total variation (a.k.a. path length) of the an arbitrary sequence of comparators that may not be known to the learner ahead of time.
arXiv Detail & Related papers (2021-04-23T21:36:51Z) - Revisiting Smoothed Online Learning [70.09792747315323]
We investigate the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost.
To bound the competitive ratio, we assume the hitting cost is known to the learner in each round, and investigate the greedy algorithm which simply minimizes the weighted sum of the hitting cost and the switching cost.
arXiv Detail & Related papers (2021-02-13T14:15:55Z) - Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
We study the special case of online learning over strongly convex sets, for which we first prove that OFW can enjoy a better regret bound of $O(T2/3)$ for general convex losses.
We show that it achieves a regret bound of $O(sqrtT)$ over general convex sets and a better regret bound of $O(sqrtT)$ over strongly convex sets.
arXiv Detail & Related papers (2020-10-16T05:42:50Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
We investigate online convex optimization in non-stationary environments.
We choose the dynamic regret as the performance measure.
We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
arXiv Detail & Related papers (2020-07-07T14:10:57Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.