Mind the Duality Gap: Logarithmic regret algorithms for online optimization

By Shai Shalev-Shwartz, Sham M. Kakade. 2008

109 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Adaptive Gradient-Based Meta-Learning Methods (2019, neutral): “[32] Sham Kakade and Shai Shalev-Shwartz.”
Online Meta-Learning (2019, neutral): “See Hazan (2016); Shalev-Shwartz (2012); Shalev-Shwartz & Kakade (2008) for algorithmic templates to derive sub-linear regret based algorithms.”
A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (2010, background): “Our approach is closely related to no regret online learning algorithms (Cesa-Bianchi et al., 2004; Hazan et al., 2006; Kakade and Shalev-Shwartz, 2008) (in particular Follow-The-Leader) but better leverages the expert in our setting.”
Learning to Filter with Predictive State Inference Machines (2015, background): “The prediction error for AR with k = 5, 10, 20 is too big to fit into the plot.”
Implicit Online Learning (2010, methodology): “Strongly convex losses are useful and widely studied because they have been shown to yield online learning algorithms with logarithmic regret bounds (e.g. Hazan et al. (2007); Kakade & Shalev-Shwartz (2008)).”
Proximal regularization for online and batch learning (2009, methodology): “Our analysis is closely related to the online learning framework of (Shalev-Shwartz & Kakade, 2009).”
The Interplay Between Stability and Regret in Online Learning (2012, methodology): “The FTL method was analyzed in [7] and [21] for the case when each loss function ` is at least αstrongly convex.”
Learning-to-Learn Stochastic Gradient Descent with Biased Regularization (2019, methodology): “Specifically, proceeding as in [28], the primal-dual setting we need to consider is the following.”
Accelerated Gradient Methods for Stochastic Optimization and Online Learning (2009, background): “However, as pointed out in [15], a very useful property that c an improve the convergence rates in machine learning optimization problems is strong convexity.”
Strong supervision from weak annotation: Interactive training of deformable part models (2011, background): “Learning with strongly convex loss functions (this includes arbitrary convex loss function with L2 regularization added such as Eq 16) has recently been extensively studied in online learning literature [12, 11, 18, 16].”
On the Generalization Ability of Online Strongly Convex Programming Algorithms (2008, background): “≤ RegT T + 4 √ L2 ln(1/δ) ν √ RegT T + max { 16L2 ν , 6B } ln(1/δ) T Further, using Jensen’s inequality,1T ∑ t F (wt) can be replaced byF (w̄) wherew̄ := 1 T ∑ t wt.”
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, methodology): “This Θ(1/ √ t) discount factor is also common for other previous work that use soft-thresholding, including Shalev-Shwartz and Tewari (2009). It is clear that the RDA method uses a much more aggressive truncation threshold, thus is able to generate significantly more sparse solutions.”
A survey of Algorithms and Analysis for Adaptive Online Learning (2014, methodology): “rem 1 or 2, we have Regret(x∗) ≤ 1 2 XT t=1 kgtk2 (t),⋆ = 1 2 XT t=1 1 t kgtk2 ≤ G2 2 (1+logT), where we have used the standard inequality PT t=11/t≤1 + logT and assumed kgtk≤ G. This recovers, e.g., Kakade and Shalev-Shwartz (2008, Cor. 1) for the the exact FTL algorithm. On the other hand, for a 1”