Empirical Bernstein Bounds and Sample Variance Penalization

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.

10 pages, 1 figure, Proc. Computational Learning Theory Conference (COLT 2009)

Cited by in corpus (105)

• Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization
• Counterfactual Risk Minimization: Learning from Logged Bandit Feedback
• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Predicting Grades
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Concentration inequalities for sampling without replacement
• MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
• Neuron Shapley: Discovering the Responsible Neurons
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Online Stochastic Optimization under Correlated Bandit Feedback
• Minimax Regret Bounds for Reinforcement Learning
• Selecting Computations: Theory and Applications
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Tracking the Best Expert in Non-stationary Stochastic Environments
• Exploration-Exploitation in Constrained MDPs
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm
• A Framework for Parallel and Distributed Training of Neural Networks
• Fairness risk measures
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• The Importance of Pessimism in Fixed-Dataset Policy Optimization
• CoinDICE: Off-Policy Confidence Interval Estimation
• $M{C}^2$: Rigorous and Efficient Directed Greybox Fuzzing
• ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
• Why distillation helps: a statistical perspective
• Distributionally Robust Optimization and Generalization in Kernel Methods
• Learning Bounds for Risk-sensitive Learning
• PAC-Bayesian aggregation and multi-armed bandits
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• PAC-Bayesian Bound for the Conditional Value at Risk
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
• Active Nearest-Neighbor Learning in Metric Spaces
• Discrepancy-Based Active Learning for Domain Adaptation
• On Data-Driven Prescriptive Analytics with Side Information: A Regularized Nadaraya-Watson Approach
• Optimistic Policy Optimization with Bandit Feedback
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting
• On Tilted Losses in Machine Learning: Theory and Applications
• Confidence sequences for sampling without replacement
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Ad-load Balancing via Off-policy Learning in a Content Marketplace
• Post-selection inference for e-value based confidence intervals
• Learning Prediction Intervals for Regression: Generalization and Calibration
• Tighter Confidence Intervals for Rating Systems
• Adaptive Stratified Sampling for Monte-Carlo integration of Differentiable functions
• Rationally Inattentive Inverse Reinforcement Learning Explains YouTube Commenting Behavior
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Optimal Confidence Regions for the Multinomial Parameter
• A Theory-Driven Self-Labeling Refinement Method for Contrastive Representation Learning
• Maximum Weighted Loss Discrepancy
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Multi-Objective SPIBB: Seldonian Offline Policy Improvement with Safety Constraints in Finite MDPs
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Online A-Optimal Design and Active Linear Regression
• Knowledge Distillation as Semiparametric Inference
• Efficient crowdsourcing of crowd-generated microtasks
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Tilted Empirical Risk Minimization
• A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
• Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization
• Universal Bayes consistency in metric spaces
• Learning with risks based on M-location
• Dynamic Pricing with Finitely Many Unknown Valuations
• Derivative-Free & Order-Robust Optimisation
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Active Model Estimation in Markov Decision Processes
• A Survey of Learning Criteria Going Beyond the Usual Risk
• On the Value of Bandit Feedback for Offline Recommender System Evaluation
• Dealing with Unknown Variances in Best-Arm Identification
• Semi-Parametric Efficient Policy Learning with Continuous Actions
• Stochastic Optimization for Non-convex Inf-Projection Problems
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Enhancing the Antidote: Improved Pointwise Certifications against Poisoning Attacks
• Robust learning under clean-label attack
• Sequential no-Substitution k-Median-Clustering
• Defining Admissible Rewards for High Confidence Policy Evaluation
• Adaptive estimation in the nonparametric random coefficients binary choice model by needlet thresholding
• Improved Exploration in Factored Average-Reward MDPs
• Measurable Monte Carlo Search Error Bounds
• Size of Interventional Markov Equivalence Classes in Random DAG Models
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• Improving Offline Contextual Bandits with Distributional Robustness
• Over-Conservativeness of Variance-Based Efficiency Criteria and Probabilistic Efficiency in Rare-Event Simulation
• PAC Mode Estimation using PPR Martingale Confidence Sequences
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
• Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables
• K-NN active learning under local smoothness assumption
• Confidence-Budget Matching for Sequential Budgeted Learning
• Learning the Linear Quadratic Regulator from Nonlinear Observations
• Risk-Monotonicity in Statistical Learning
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Online Selection of Diverse Committees
• Approximating a Target Distribution using Weight Queries
• Covariance Adaptive Best Arm Identification
• Empirical Hypothesis Space Reduction
• Differentially Private Link Prediction With Protected Connections
• Towards Practical Mean Bounds for Small Samples
• The Label Complexity of Active Learning from Observational Data
• Adaptive Sampling for Estimating Multiple Probability Distributions
• Tightly Robust Optimization via Empirical Domain Reduction