Empirical Bernstein Bounds and Sample Variance Penalization

2009/07/21 by Andreas Maurer, Maurer, Andreas, Massimiliano Pontil +1 · 35 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.0907.3740

openalex publication_date 2009/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 functionswhose 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/sqrt/n. We show some experimental results, which confirm the theory. Finally, we discuss the potential application of our results to sample compression schemes.

Cited by

• Closed-form empirical Bernstein confidence sequences for scalars and matrices
• Distribution-Free Selection of Low-Risk Oncology Patients for Survival Beyond a Time Horizon
• Contextual Dynamic Pricing with Heterogeneous Buyers
• Self-Normalized Concentration Inequalities of Marginal Mean with Sample Variance Only
• SnapAudit: Active Auditing of Differentially Private In-Context Learning via Snapshot-Based Simulation
• Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity
• Continuum: Efficient and Robust Multi-Turn LLM Agent Scheduling with KV Cache Time-to-Live
• From Unsupervised Subgroups to Hypothetical State-Intervention Policies: An Evaluation of Selected Subgrouping Methods in Observational Health Data
• Tightly Robust Optimization via Empirical Domain Reduction
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy\n Policies
• Scalable Oversight via Partitioned Human Supervision
• Fair Representation Learning with Controllable High Confidence Guarantees via Adversarial Inference
• Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach
• Online Policy Learning via a Self-Normalized Maximal Inequality
• Risk-Aware Reinforcement Learning with Bandit-Based Adaptation for Quadrupedal Locomotion
• Selecting Computations: Theory and Applications
• SGM: A Statistical Godel Machine for Risk-Controlled Recursive Self-Modification
• Defining Admissible Rewards for High Confidence Policy Evaluation
• Improved Exploration in Factored Average-Reward MDPs
• Size of Interventional Markov Equivalence Classes in Random DAG Models
• Confidence sequences for sampling without replacement
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal\n Algorithm Escaping the Curse of Horizon
• Hybrid Safety Verification of Multi-Agent Systems using ψ-Weighted CBFs and PAC Guarantees
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• On Tilted Losses in Machine Learning: Theory and Applications
• Semi-Parametric Efficient Policy Learning with Continuous Actions
• Fast Percolation Centrality Approximation with Importance Sampling
• Exploration-Exploitation in Constrained MDPs
• Sample Efficient Certification of Discrete-Time Control Barrier Functions
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Why distillation helps: a statistical perspective
• A variational approach to dimension-free self-normalized concentration
• ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning

Related

• Sharp empirical Bernstein bounds for the variance of bounded random variables
• Empirical Bernstein in smooth Banach spaces
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Online Policy Learning via a Self-Normalized Maximal Inequality
• Closed-form empirical Bernstein confidence sequences for scalars and matrices