Empirical Bernstein Bounds and Sample-Variance Penalization

By Andreas Maurer, Massimiliano Pontil. 2009

619 citations recorded by the source corpus.

We give improved constants for data dependent and variance sensitive confidence bounds, called empirical Bernstein bounds, and extend these inequalities to hold uniformly over classes of functions whose growth function is polynomial in the sample size n. The bounds lead us to consider sample variance penalization, a novel learning method which takes into account the empirical variance of the loss function. We give conditions under which sample variance penalization is effective. In particular, we present a bound on the excess risk incurred by the method. Using this, we argue that there are situations in which the excess risk of our method is of order 1/n, while the excess risk of empirical risk minimization is of order 1/√n. We show some experimental results, which confirm the theory. Finally, we discuss the potential application of our results to sample compression schemes.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Counterfactual reasoning and learning systems: the example of computational advertising (2012, methodology): “For instance, appendix E leverages uniform empirical Bernstein bounds (Maurer and Pontil, 2009) and obtains the uniform confidence interval P { ∀θ ∈ F , Ŷ θ− R ≤ Y θ ≤ Ŷ θ+M(1−Ŵ θ+ξR)+ R } ≥ 1−M(n) δ , (24) where the growth functionM(n) measures the capacity of the family of functions { fθ : ω…”
Offline A/B Testing for Recommender Systems (2018, background): “we want to take a statistically significant decision, we need to build a confidence interval around Rˆ CIS(πt,c). We can bound R (πt,c)using any concentration bound (e.g. an empirical Bernstein bound [2, 17]). However the bias term can only be controlled in the worst case: 0 ≤BCIS(πt,c)≤rmax (1 −P(W”
High-Confidence Off-Policy Evaluation (2015, background): “11 of Maurer and Pontil (2009), with probability at least 1− δ, we have”
Variance-based Regularization with Convex Objectives (2016, background): “Maurer and Pontil [19] consider this idea, giving a number of guarantees on the convergence and good performance of such a procedure.”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, background): “By combining Hoeffding’s inequality, Bernstein’s inequality and the concentration result on empirical standard deviations by Maurer and Pontil [18] with the union bound, we get that p ( s (cid:48) | s, a ) ∈ P with probability at least 1 − δ 1 for a single phase k , ﬁxed s, a ∈ S × A and ﬁxed s (cid”
Efficient Policy Learning (2017, methodology): “Meanwhile, bounds that scale as √ E [Γ2] log(n)/n are developed by Cortes et al. (2010) and Maurer and Pontil (2009); however, the additional log(n) factor makes these bounds inappropriate for asymptotic analysis.”
Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization (2019, background): “…on DRO has focused on models that cannot approach zero training loss, such as generative models (Oren et al., 2019) or convex predictive models with limited capacity (Maurer & Pontil, 2009; Shaﬁeezadeh-Abadeh et al., 2015; Namkoong & Duchi, 2017; Duchi & Namkoong, 2018; Hashimoto et al., 2018).”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, methodology): “Convergence of the System Dynamics in the Dominant Term of the Exploration Bonus Theorem 10 of (Maurer & Pontil, 2009) gives the high probability state- ment: ∣∣∣∣∣ √ Var p̂k(·|s,a) V π ∗ t+1 − √ Var p(·|s,a) V π ∗ t+1 ∣∣∣∣∣ / H nk(s, a) (8) to quantify the rate of convergence of the empirical…”
Uniform, nonparametric, non-asymptotic confidence sequences (2018, background): “Audibert et al. (2009) prove an empirical variance bound uniform over a finite time horizon based on Freedman’s inequality, and Maurer and Pontil (2009) contains a fixed-sample empirical variance bound.”
Offline Multi-Action Policy Learning: Generalization and Optimization (2018, background): “Note that in the above definition, covering number is a classical notion (see Maurer and Pontil (2009) for a detailed treatment). Further, the entropy integral κ(Π) is a complexity measure of the policy class Π and is a variant of the classical entropy integral introduced(4) in Dudley (1967).”
Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence (2012, background): “All the algorithms have an exploration parameter a.”
Batch learning from logged bandit feedback through counterfactual risk minimization (2015, methodology): “Based on this bound, Maurer and Pontil (2009) deﬁne two Lipschitz continuous functions, Φ , Ψ : These functions are Lipschitz continuous, The inequalities follow directly from ˆ ar ( s For the symmetrization argument, consider two sets of n samples D and D (cid:48) drawn from h 0 according to the…”
A Non-parametric Learning Method for Confidently Estimating Patient's Clinical State and Dynamics (2016, methodology): “Additionally, the algorithm provides statistical guarantees on the dynamic model parameters using generalizations of the scalar Bernstein inequality [13] to vector-valued and matrix-valued random variables.”
Bandit Algorithms (2020, background): “Neu [2015a] proves high probability bounds for Exp4-IX.”
PAC-Bayesian Inequalities for Martingales (2011, result): “In this case, the inequality is comparable with empirical Bernstein’s bounds [22]–[24].”