Dynamical Models and tracking regret in online convex programming

By Eric C. Hall, Rebecca M. Willett. 2013

134 citations recorded by the source corpus.

This paper describes a new online convex optimization method which incorporates a family of candidate dynamical models and establishes novel tracking regret bounds that scale with the comparator's deviation from the best dynamical model in this family. Previous online optimization methods are designed to have a total accumulated loss comparable to that of the best comparator sequence, and existing tracking or shifting regret bounds scale with the overall variation of the comparator sequence. In many practical scenarios, however, the environment is nonstationary and comparator sequences with small variation are quite weak, resulting in large losses. The proposed Dynamic Mirror Descent method, in contrast, can yield low regret relative to highly variable comparator sequences by both tracking the best dynamical model and forming predictions based on that model. This concept is demonstrated empirically in the context of sequential compressive observations of a dynamic scene and tracking a dynamic social network.

Subfields: 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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, neutral): “For example, References [10, 11] choose the reference points {x∗ t }t=1 satisfying ∑T−1 t=1 ‖x∗ t+1 − Φ(x∗ t )‖ ≤ M , where Φ(x∗ t ) is the predictive optimal model.”
An Online Learning Approach to Model Predictive Control (2019, methodology): “We will show that a range of existing MPC algorithms are in essence applications of a classical online learning algorithm called dynamic mirror descent (DMD) [14].”
Adaptive Online Learning in Dynamic Environments (2018, methodology): “Theorem 5 indicates our method achieves an O( √ T (1 + P ′ T )) dynamic regret, improving the O( √ T (1 + P ′ T )) dynamic regret of Hall and Willett [2013] significantly.”
Online Optimization in Dynamic Environments (2013, methodology): “th the Department of Electrical and Computer Engineering, University of Wisconsin-Madison, Madison, WI 53706, USA. e-mail: willett@discovery.wisc.edu. Portions of this paper appeared in an ICML paper [1], which proposed the DMD method and the xed-share approach to choosing among dynamical models. Th”
Markov Decision Processes with Time-varying Transition Probabilities and Rewards (2019, unknown): “…(Hazan, 2016; Shalev-Shwartz, 2012; Zinkevich, 2003; Mokhtari et al., 2016; Jadbabaie et al., 2015; Li et al., 2018; Besbes et al., 2015; Hall & Willett, 2015; 2013; Zhang et al., 2017), in prediction with expert advice (Cesa-Bianchi & Lugosi, 2006; Herbster & Warmuth, 1998; Adamskiy et…”
Understand Dynamic Regret with Switching Cost for Online Decision Making (2019, methodology): “(2) Our new formulation of the dynamic regret RA D makes a balance between the operating cost and the switching cost, which is dierent from the previous denition of the dynamic regret in [20, 21, 51].”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “When Φ(yt) predict the dynamic environment accurately, [22], [23] obtain a better regret than [1], but it is still bounded by O (√ TD0 + √ T ) .”
Shifting Regret, Mirror Descent, and Matrices (2016, methodology): “…overly general (it allows maps that do not functionally depend on vt), several algorithms from the literature can be written in this form using some special function φt with some structure (Herbster & Warmuth, 2001; Bousquet & Warmuth, 2002; Cesa-Bianchi et al., 2012; Hall & Willett, 2013).”
Improved Dynamic Regret for Non-degenerate Functions (2016, background): “A novel algorithm named dynamic mirror descent is proposed to take Φ t ( u t − 1 ) into account, and the dynamic regret R ( u 1 , . . . , u T ) is on the order of √ T P ′ ( u 1 , . . . , u T ) (Hall and Willett, 2013).”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “To address this limitation, new forms of performance measure, including adaptive regret (Hazan & Seshadhri, 2007; 2009) and dynamic regret (Zinkevich, 2003; Hall & Willett, 2013), were proposed and received significant interest recently.”
Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “…1 , y 2 , · · · , y T } , and the dynamics upper bound L TD 0 is deﬁned by It was shown that the dynamic regret of Online Gradient (OG) is bounded [Hall and Willett, 2013, 2015, Zinkevich, 2003] by This reminds people to ask a few fundamental questions: • As we know the dependence on T is tight,…”