On the Generalization Ability of Online Strongly Convex Programming Algorithms

By Sham M. Kakade, Ambuj Tewari. 2008

183 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

Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, methodology): “The SGD method belongs to the general scheme of stochastic approximation, which can be traced back to Robbins and Monro (1951) and Kiefer and Wolfowitz (1952). In general we are also allowed to use all previous information to compute wt+1, and even second-order derivatives if the loss functions are ”
Practical Evaluation and Optimization of Contextual Bandit Algorithms (2018, methodology): “e T; (12) where e T = log(2j j= T)=T and T = =(T2 + T). We denote this event by Ein what follows. 30 A Contextual Bandit Bake-off Proof We prove the result using Freedman’s inequality (see, e.g., Kakade and Tewari, 2009, Lemma 3), which controls deviations of a sum using the conditional variance of”
Convergence of Value Aggregation for Imitation Learning (2018, background): “In addition, by Theorem 2, the theoretical results of xN here can directly translate to that of the mean policy x̄N , which matches the bound for the average decision x̄N given by Kakade and Tewari (2009).”
Understanding How Feature Structure Transfers in Transfer Learning (2017, background): “Strongly convex programming algorithms have many benign properties, both in the speed of optimization and the quality of generalization [Kakade and Tewari, 2009].”
Online Learning: A Comprehensive Survey (2018, methodology): “ xed unknown distribution. Therefore, we would like to study the generalization performance of online algorithms through the Online to Batch Conversion (Cesa-Bianchi et al., 2004; Wang et al., 2012c; Kakade and Tewari, 2009; Levy, 2017), where the conversion relates the regret of the online algorith”
Differentially Private Distributed Online Learning (2015, methodology): “Kakade and Tewari [10] and Jain et al. [7] have both proposed that online learning algorithms with good regret bounds can be used to achieve fast convergence rates for ofﬂine learning algorithms.”
Composite objective mirror descent (2010, background): “(14) Note that when ψ(·) = ‖·‖2p we recover Shalev-Shwartz and Tewari’s SMIDAS, while with p = 2 we get Langford et al.’s 2009 truncated gradient method. See Shalev-Shwartz and Tewari (2009) or Gentile and Littlestone (1999) for the simple formulae to compute (∇ψ)−1 ≡ ∇ψ∗.”
A Contextual Bandit Bake-off (2018, unknown): “Proof We prove the result using Freedman’s inequality (see, e.g. , Kakade and Tewari, 2009, Lemma 3), which controls deviations of a sum using the conditional variance of each term in the sum and an almost sure bound on their magnitude, along with a union bound.”
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback. (2010, methodology): “We would like to mention that the techniques of Kakade and Tewari (2009), which provide such a result in the online to batch conversion setting, are not applicable to our case.”
Exponential convergence of testing error for stochastic gradient methods (2017, unknown): “Similar results for non-averaged SGD could be derived beyond least-squares (e.g., hinge or logistic loss) using results from Kakade and Tewari (2009).”
A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (2010, methodology): “…sampled trajectories, then using Azuma-Hoeffding’s inequality leads to the following guarantee: A more reﬁned analysis taking advantage of the strong convexity of the loss function (Kakade and Tewari, 2009) may lead to tighter generalization bounds that require N only of order ˜ O ( T log(1 /δ )) .”