Mirror Descent Meets Fixed Share (and feels no regret)

By Nicolò Cesa-Bianchi, Pierre Gaillard, Gábor Lugosi, Gilles Stoltz. 2012

106 citations recorded by the source corpus.

Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets. Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters.

Subfields: Artificial Intelligence, 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 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, background): “…is usually termed as shifting regret or tracking regret [Herbster and Warmuth, 1998, Gy¨orgy et al., 2005, Gyorgy et al., 2012, Gy¨orgy and Szepesv´ari, 2016, Mourtada and Maillard, 2017, Adamskiy et al., 2016, Wei et al., 2016, Cesa-Bianchi et al., 2012, Mohri and Yang, 2018, Jun et al., 2017].”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “Mirror descent, ﬁrst introduced by Nemirovski & Yudin (1983), is one of the most widely used families of algorithms for optimization (Beck & Teboulle, 2003; Cesa-Bianchi et al., 2012; Zhou et al., 2017), which includes the popular gradient descent as a special case.”
Competing with Automata-based Expert Sequences (2018, background): “Other works that have recovered FIXED-SHARE (e.g. [Vovk, 1999, Cesa-Bianchi and Lugosi, 2006, Cesa-Bianchi et al., 2012, Koolen and de Rooij, 2013, György and Szepesvári, 2016]) have generally viewed the algorithm itself as the main focus and have not systematically derived it from first…”
Stochastic Mirror Descent in Variationally Coherent Optimization Problems (2017, methodology): “The stochastic mirror descent (SMD) method and its variants[1, 7, 8] is arguably one of the most widely used family of algorithms in stochastic optimization – convex and non-convex alike.”
Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “3 Shifting regret (or tracking regret) The M−shifting regret of an algorithm A ∈ A is defined by [6, 38, 40–47] R̃T := T ∑”
Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization (2018, background): “Stochastic Mirror Descent (SMD) (Nemirovskii et al., 1983; Beck & Teboulle, 2003; Cesa-Bianchi et al., 2012; Zhou et al., 2017) is one of the most widely used family of algorithms for stochastic optimization, which includes SGD as a special case.”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “In the setting of “online linear optimization in the simplex”, Cesa-bianchi et al. (2012) introduced a generalized notion of shifting regret which unifies adaptive regret and shifting regret.”
Improved Strongly Adaptive Online Learning using Coin Betting (2016, methodology): “Algorithm m-shift regret Time Agnostic to m Fixed Share [10, 3] √ mT (logN + log T ) NT 7 √ m2T (logN + log T ) NT 3 GeneralTracking〈EXP〉 [8] √ mT (logN +m log2 T ) NT log T 3 √ mT (logN + log2 T ) NT log T 7”
Dynamical Models and tracking regret in online convex programming (2013, background): “The relationship between the two has been formally shown (Cesa-Bianchi et al., 2012).”
Shifting Regret, Mirror Descent, and Matrices (2016, methodology): “In this section we generalize the results of Cesa-Bianchi et al. (2012) who only considered prediction on the simplex, that is, when K = A = Pd is the d-dimensional probability simplex, R(v) = ∑d i=1 vi log vi − vi for any vector v = (v1, . . . , vd) ∈ A, and the resulting Bregman divergence is…”
Efficient tracking of a growing number of experts (2017, methodology): “The seminal paper (Bousquet and Warmuth, 2002) proposed an ad-hoc strategy with essentially optimal regret bounds, the Mixing Past Posteri-ors (MPP) algorithm (see also Cesa-Bianchi et al. (2012)).”