Inequalities for the L1 Deviation of the Empirical Distribution

By Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú, Marcelo J. Weinberger. 2003

342 citations recorded by the source corpus.

Subfields: Statistics and Probability, Statistical Learning Theory

How researchers see this paper

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

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Theoretical Guarantees for Model Auditing with Finite Adversaries (2019, background): “Hence, The large deviation bound in Theorem 2.1 in [35] shows that, with probability at least 1 − δ , where ˆ P S,T is the empirical distribution of S and T .”
Safe Policy Improvement with Soft Baseline Bootstrapping (2019, methodology): “The proof relies on Theorem 2.1 in Weissman et al. (2003) and is identical to that of Equation 23 borrowed from Petrik et al. (2016), except that dπbM and d πb M̂ are state distributions and not probability distributions and that their sums are therefore bounded by 11−γ .”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, methodology): “…( s, a, t ) It states that the L1-distance of the empirical transition probabilities to the true probabilities for any ( s, a, t ) in any episode k is too large and we show that P ( F L 1 ) ≤ 1 − δ/ 9 using a uniform version of the popular bound by Weissman et al. [25] which we prove in Appendix F.”
Minimax Regret Bounds for Reinforcement Learning (2017, neutral): “The result of (Weissman et al., 2003) combined with a union bound on Nk(x, a) ∈ [T ] implies w.p. 1− δ ∥∥∥P̂k(·|x, a) − P (·|x, a) ∥∥∥ 1 ≤ √ 2S ln ( 2T δ ) Nk(x, a) .”
Near-optimal Reinforcement Learning in Factored MDPs (2014, positive): “This is a relaxation of the result proved by Weissman [28].”
Robust Policy Optimization with Baseline Guarantees (2015, methodology): “More information on building the simulator and computing the L 1 − deviation bound (using an empirical distribution for simulator (cid:98) P and the Weissman distribution bound [21]) is available in Appendix A.1.”
A theoretical analysis of Model-Based Interval Estimation (2005, neutral): “This result (Weissman et al., 2003) yields a confidence interval of CI = {T̃ (s, a, ·) | ||T̃ (s, a, ·) − T̂ (s, a, ·)||1 ≤ T n(s,a)}.”
Reinforcement Learning in Finite MDPs: PAC Analysis (2009, methodology): “The result of Weissman et al. (2003) is established using an informati n-theoretic argument.”
On the Robustness of Information-Theoretic Privacy Measures and Mechanisms (2018, background): “The proofs of these bounds rely on known large deviations results [27] and Lipschitz continuity properties of information leakage measures established in this paper.”
Bandit Algorithms (2020, result): “The result is due to Weissman et al. [2003]. It is worth comparing this to what can be obtained from Hoeffding’s inequality, which implies for any i ∈ [m] and δ ∈ (0, 1) that with probability 1− δ,”