Online Optimization : Competing with Dynamic Comparators

By Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, Karthik Sridharan. 2015

288 citations recorded by the source corpus.

Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we address these two directions together. We present a fully adaptive method that competes with dynamic benchmarks in which regret guarantee scales with regularity of the sequence of cost functions and comparators. Notably, the regret bound adapts to the smaller complexity measure in the problem environment. Finally, we apply our results to drifting zero-sum, two-player games where both players achieve no regret guarantees against best sequences of actions in hindsight.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Adaptive Gradient-Based Meta-Learning Methods (2019, neutral): “This has been widely analyzed by the online learning community [15, 30], often by showing a dynamic regret bound consisting of a sublinear term plus a bound on the variation in the action or function space.”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, neutral): “The dynamic regret of online learning algorithms has been widely studied for decades [Zinkevich, 2003, Hall and Willett, 2015, 2013, Jadbabaie et al., 2015, Yang et al., 2016, Bedi et al., 2018, Zhang et al., 2017a, Mokhtari et al., 2016, Zhang et al., 2018b, Gy¨orgy and Szepesv´ari, 2016, Wei et…”
Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, methodology): “[8] Convex No Deterministic O(√K (1 + WK )) [9] Convex No Deterministic O(√K (1 + WK )) [17] Convex No Stochastic O(K 2/3 (1 + VK )1/3 ) [17] Strongly convex No Stochastic O( √ K (1 + VK )) [38] Convex No Deterministic O(DK + 1 + min{ √ (DK + 1)WK , [(DK + 1)VK K ]1/3}) [11] Strongly convex No Deter”
Predictor-Corrector Policy Optimization (2018, background): “it is no-regret for any interval) or has sublinear dynamic regret (Jadbabaie et al., 2015), then its generated policy sequence will strictly, non-asymptotically improve.”
Distributed Online Optimization in Dynamic Environments Using Mirror Descent (2016, background): “In parallel to studies of centralized online optimization [14], [15], [26], the hardness of the problem should be characterized via a complexity measure that captures the variation in the minimizer sequence {x t }t=1 .”
Adaptive Online Learning in Dynamic Environments (2018, unknown): “As shown by Jadbabaie et al. [2015], these regularities reﬂect distinct aspects of the online problem, and are not comparable in general.”
Improved Dynamic Regret for Non-degenerate Functions (2016, background): “…there has been a recent surge of interest in analyzing a more stringent metric— dynamic regret (Besbes et al., 2015; Hall and Willett, 2013; Jadbabaie et al., 2015; Mokhtari et al., 2016; Yang et al., 2016), in which the cumulative loss of the learner is compared against a sequence of…”
Understand Dynamic Regret with Switching Cost for Online Decision Making (2019, background): “Many other previous researches investigate the regret under dierent denitions of dynamics such as parameter variation [19, 34, 44, 47], functional variation [7, 25, 46], gradient variation [17], and the mixed regularity [16, 24].”
Competing with Automata-based Expert Sequences (2018, background): “One perspective has been the design of algorithms that maintain a guarantee against sequences that do not vary too much [Mokhtari et al., 2016, Shahrampour and Jadbabaie, 2016, Jadbabaie et al., 2015, Besbes et al., 2015].”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “(2) It is well-known that in the worst case, a sublinear dynamic regret is impossible unless we impose some regularities on the comparator sequence or the function sequence (Jadbabaie et al., 2015).”
Provable Guarantees for Gradient-Based Meta-Learning (2019, unknown): “Furthermore, if Θ ∗ = Θ , i.e. if the tasks are not similar, then the algorithm will only do a constant factor worse than FTRL or OMD; this is similar to other “optimistic” methods that work well under regularity (Rakhlin & Sridharan, 2013; Jadbabaie et al., 2015).”
Optimization in Dynamic Environments : Improved Regret Rates for Strongly Convex Problems (2016, unknown): “[11] ∑T t=1 ft(xt)− ft(xt ) Convex O (√ DT + 1 +min {√ (DT + 1)CT , [(DT + 1)VTT ] 1/3 }) This work ∑T t=1 ft(xt)− ft(xt ) Strongly convex O ( 1 + CT )”
Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis (2019, unknown): “, static regrets[27, 28], dynamic regrets[29], etc.”
Markov Decision Processes with Time-varying Transition Probabilities and Rewards (2019, background): “Hence, some other nonestatic regrets have been proposed, dynamic regret (Zinkevich, 2003; Mokhtari et al., 2016; Jadbabaie et al., 2015; Li et al., 2018; Besbes et al., 2014; 2015), tracking regret (Herbster & Warmuth, 1998;”