Empirical Bernstein Bounds and Sample Variance Penalization
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 10 Pith papers
-
Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds
Joint KL yields horizon-free approximation but an information-theoretic lower bound of order Omega(H) for estimation error in autoregressive learning, with matching computationally efficient upper bounds.
-
Vitriflow: calibrated amorphous structure ensembles from melt-quench simulation
Vitriflow is a new explicit calibration framework for melt-quench MD that produces statistically converged, screened amorphous ensembles demonstrated on a-SiO2, a-Si3N4 and a-Sm2O3.
-
A data-dependent DKW inequality for regenerative Markov chains
Establishes an empirical concentration inequality for the empirical CDF of a functional on regenerative Markov chains, with data-dependent leading term and lower-order convergence bound.
-
Online Set Learning from Precision and Recall Feedback
A hypothesis class is learnable in this online precision-recall feedback model if and only if it has finite VC dimension, with algorithms achieving regret bounds in realizable and agnostic settings despite ERM failing.
-
Importance Sampling for Statistical Certification of Viable Initial Sets
An importance sampling framework with a derived empirical Bernstein inequality for weighted variables provides finite-sample guarantees for statistically certifying viable initial sets in control systems.
-
Understanding Uncertainty Sampling via Equivalent Loss
Uncertainty sampling optimizes an equivalent loss, enabling sample complexity analysis and asymptotic superiority guarantees over passive learning in binary classification.
-
Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
Extends MVP to contextual action-set RL and derives minimax regret bound O~(sqrt(S A H^3 K log L)) for adversarial contexts plus a gap-dependent bound.
-
On Local Population-Risk Certificates
Constructs expected-valid upper endpoints for local risk increments Pδ_v via cross-fitted ridge calibration for linear classes and componentwise application to nonsmooth loss decompositions.
-
Privacy Preserving Reinforcement Learning with One-Sided Feedback
POOL is a new RL algorithm that adds privacy protection in continuous spaces with one-sided feedback and achieves sample complexity matching known non-private lower bounds.
-
On Local Population-Risk Certificates
Introduces local population-risk certificates as two-sided confidence bands for loss increments to enable a risk-controlled update rule that accepts changes only when the upper band endpoint is nonpositive.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.