A large-deviation inequality for vector-valued martingales

By T. Hayes. 2003

73 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.

Sample Complexity of Multi-task Reinforcement Learning (2013, unknown): “Lemma 5 (Hayes [2005]) For vector-valued martingale, Pr ( (cid:107) X n (cid:107) ≥ a ) ≤ 2 exp 2 − a 2 2 n ; or equivalently, Pr X n n ≥ (cid:15) ≤ 2 exp 2 − n(cid:15) 2 2 .”
Computational and Statistical Tradeoffs in Learning to Rank (2016, methodology): “Also, from the independence of samples, it follows that E[Z j+1;1jZ j;‘ j ] = Z j;‘ j . Applying a generalized version of the vector Azuma-Hoeding inequality which readily follows from [Theorem 1.8, Hayes (2005)], we have P 2 krL RB()k 2e3 exp P n j=1 P ‘ j a=1 m j;a2 1 2 e2b ! ; (26) where we use”
Convergence of Value Aggregation for Imitation Learning (2018, methodology): “onstant6 of the complexity of Π. Proof. The proof is similar to the proof of Theorem 2. To handle the stochasticity, we use a generalization of Azuma-Hoeﬀding inequality to vector-valued martingales (Hayes, 2005) to derive a high-probability bound on k∇gn(xn) − ∇fn(xn)k∗ and a uniform bound on supx∈”