Minimizing Dynamic Regret and Adaptive Regret Simultaneously
- URL: http://arxiv.org/abs/2002.02085v1
- Date: Thu, 6 Feb 2020 03:32:37 GMT
- Title: Minimizing Dynamic Regret and Adaptive Regret Simultaneously
- Authors: Lijun Zhang, Shiyin Lu, Tianbao Yang
- Abstract summary: We propose novel online algorithms that are able to minimize the dynamic regret and adaptive regret simultaneously.
Our theoretical guarantee is even stronger in the sense that one algorithm is able to minimize the dynamic regret over any interval.
- Score: 60.17824125301273
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Regret minimization is treated as the golden rule in the traditional study of
online learning. However, regret minimization algorithms tend to converge to
the static optimum, thus being suboptimal for changing environments. To address
this limitation, new performance measures, including dynamic regret and
adaptive regret have been proposed to guide the design of online algorithms.
The former one aims to minimize the global regret with respect to a sequence of
changing comparators, and the latter one attempts to minimize every local
regret with respect to a fixed comparator. Existing algorithms for dynamic
regret and adaptive regret are developed independently, and only target one
performance measure. In this paper, we bridge this gap by proposing novel
online algorithms that are able to minimize the dynamic regret and adaptive
regret simultaneously. In fact, our theoretical guarantee is even stronger in
the sense that one algorithm is able to minimize the dynamic regret over any
interval.
Related papers
- Universal Online Optimization in Dynamic Environments via Uniclass
Prediction [0.0]
We propose a novel and intuitive framework for universal online optimization in dynamic environments.
Our strategy does not rely on the construction of a set of experts and an accompanying meta-algorithm.
This is the first paper proposing a universal approach with state-of-the-art dynamic regret guarantees even for general convex cost functions.
arXiv Detail & Related papers (2023-02-13T03:00:45Z) - Distributed Online Non-convex Optimization with Composite Regret [31.53784277195043]
We propose a novel composite regret with a new network regret for distributed online general bounds losses.
To our knowledge, is the first regret bound for distributed online nonlinear learning.
arXiv Detail & Related papers (2022-09-21T04:16:33Z) - Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems [0.0]
We go through a variant of ADAGRAD (referred to as M-ADAGRAD) in a strong convex setting via the notion of dynamic regret.
We demonstrate a regret bound in terms of the path-length of the minimizer sequence that essentially reflects the non-stationarity of environments.
arXiv Detail & Related papers (2022-09-04T12:40:57Z) - Efficient Adaptive Regret Minimization [35.121567896321885]
In online convex optimization the player aims to minimize her regret against a fixed comparator over the entire repeated game.
Existing adaptive regret algorithms suffer from a computational penalty - typically on the order of a multiplicative factor that grows logarithmically in the number of game iterations.
In this paper we show how to reduce this computational penalty to be doubly logarithmic in the number of game iterations, and with minimal degradation to the optimal attainable adaptive regret bounds.
arXiv Detail & Related papers (2022-07-01T19:43:11Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
We investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO)
We show that the proposed algorithm can minimize the adaptive regret with switching cost in every interval.
arXiv Detail & Related papers (2022-05-02T08:48:22Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities.
Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
arXiv Detail & Related papers (2021-12-29T02:42:59Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
A natural goal when designing online learning algorithms is to bound the regret of the algorithm in terms of the temporal variation of the input sequence.
Data-dependent "pathlength" regret bounds have recently been obtained for a wide variety of online learning problems, including OCO and bandits.
arXiv Detail & Related papers (2021-10-24T22:43:15Z) - Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
In online learning an algorithm plays against an environment with losses possibly picked by an adversary at each round.
We introduce optimism and adaptive stepsizes to Lagrangian hedging, a class of online algorithms that includes regret-matching, and hedge.
arXiv Detail & Related papers (2021-01-23T23:32:40Z) - 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) - Dynamic Regret of Policy Optimization in Non-stationary Environments [120.01408308460095]
We propose two model-free policy optimization algorithms, POWER and POWER++, and establish guarantees for their dynamic regret.
We show that POWER++ improves over POWER on the second component of the dynamic regret by actively adapting to non-stationarity through prediction.
To the best of our knowledge, our work is the first dynamic regret analysis of model-free RL algorithms in non-stationary environments.
arXiv Detail & Related papers (2020-06-30T23:34:37Z)
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.