2019

Efron-Stein PAC-Bayesian Inequalities

Kuzborskij, Ilja, Szepesvári, Csaba

Understand

We prove semi-empirical concentration inequalities for random variables which are given as possibly nonlinear functions of independent random variables.

These inequalities describe concentration of random variable in terms of the data/distribution-dependent Efron-Stein (ES) estimate of its variance and they do not require any additional assumptions on the moments.
In particular, this allows us to state semi-empirical Bernstein type inequalities for general functions of unbounded random variables, which gives user-friendly concentration bounds for cases where related methods (e.g.
bounded differences) might be more challenging to apply.

Built on

Weighted sums of certain dependent random variables
K. Azuma · 1967
Earlier work this paper cites.
Asymptotic evaluation of certain Markov process expectations for large time
M. D. Donsker and S. S. Varadhan · 1975
Earlier work this paper cites.
Weighted average importance sampling and defensive mixture distributions
T. Hesterberg · 1995
Earlier work this paper cites.
A Weak Convergence Approach to the Theory of Large Deviations
P. Dupuis and R. S. R. S. Ellis · 1997
Earlier work this paper cites.
Concentration
C. McDiarmid · 1998
Earlier work this paper cites.
Some PAC-Bayesian theorems
D. A. McAllester · 1998
Earlier work this paper cites.
Localized rademacher complexities
P. L. Bartlett, O. Bousquet, and S. Mendelson · 2002
Earlier work this paper cites.
PAC-Bayesian generalisation error bounds for Gaussian process classification
M. Seeger · 2002
Earlier work this paper cites.
Concentration inequalities using the entropy method
S. Boucheron, G. Lugosi, and P. Massart · 2003
Earlier work this paper cites.
Pac-bayes & margins
J. Langford and J. Shawe-Taylor · 2003
Earlier work this paper cites.
A bound on the deviation probability for sums of non-negative random variables
A. Maurer · 2003
Earlier work this paper cites.
A note on the pac bayesian theorem
A. Maurer · 2004
Earlier work this paper cites.
Pac-bayesian supervised classification: The thermodynamics of statistical learning
O. Catoni · 2007
Earlier work this paper cites.
Tuning bandit algorithms in stochastic environments
J.-Y. Audibert, R. Munos, and C. Szepesvári · 2007
Earlier work this paper cites.
Improved second-order bounds for prediction with expert advice
N. Cesa-Bianchi, Y. Mansour, and G. Stoltz · 2007
Earlier work this paper cites.

Similar

Self-normalized processes: Limit theory and Statistical Applications
V. H. de la Peña, T. L. Lai, and Q.-M. Shao · 2008
Cited alongside, same era.
Empirical bernstein bounds and sample variance penalization
Original
A. Maurer and M. Pontil · 2009
Cited alongside, same era.
Smoothness, low noise and fast rates
N. Srebro, K. Sridharan, and A. Tewari · 2010
Cited alongside, same era.
Learning bounds for importance weighting
C. Cortes, Y. Mansour, and M. Mohri · 2010
Cited alongside, same era.
Entropy and Information Theory
R. M. Gray · 2011
Cited alongside, same era.
Pac-bayesian inequalities for martingales
Y. Seldin, F. Laviolette, N. Cesa-Bianchi, J. Shawe-Taylor, and P. Auer · 2012
Cited alongside, same era.
Concentration inequalities: A nonasymptotic theory of independence
S. Boucheron, G. Lugosi, and P. Massart · 2013
Cited alongside, same era.
Pac-bayes-empirical-bernstein inequality
I. O. Tolstikhin and Y. Seldin · 2013
Cited alongside, same era.
Counterfactual reasoning and learning systems: the example of computational advertising
L. Bottou, J. Peters, J. Quiñonero Candela, D. X. Charles, M. Chickering, E. Portugaly, D. Ray, P. Y. Simard, and E. Snelson · 2013
Cited alongside, same era.
Monte Carlo theory, methods and examples
A. B. Owen · 2013
Cited alongside, same era.
The self-normalized estimator for counterfactual learning
A. Swaminathan and T. Joachims · 2015
Cited alongside, same era.
On the properties of variational approximations of Gibbs posteriors
P. Alquier, J. Ridgway, and N. Chopin · 2016
Cited alongside, same era.

Then

Optimal learning with bernstein online aggregation
O. Wintenberger · 2017
Later among the works it cites.
Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data
G. K. Dziugaite and D. M. Roy · 2017
Later among the works it cites.
Empirical bounds for functions with weak interactions
A. Maurer and M. Pontil · 2018
Later among the works it cites.
Simpler pac-bayesian bounds for hostile data
P. Alquier and B. Guedj · 2018
Later among the works it cites.
Bandit algorithms
T. Lattimore and C. Szepesvári · 2018
Later among the works it cites.
Rethinking the effective sample size
Original
V. Elvira, L. Martino, and C. P. Robert · 2018
Later among the works it cites.
Policy optimization via importance sampling
A. M. Metelli, M. Papini, F. Faccio, and M. Restelli · 2018
Later among the works it cites.
A pac-bayesian approach to spectrally-normalized margin bounds for neural networks
B. Neyshabur, S. Bhojanapalli, and N. Srebro · 2018
Later among the works it cites.
Pac-bayes bounds for stable algorithms with instance-dependent priors
O. Rivasplata, E. Parrado-Hernandez, J. S. Shawe-Taylor, S. Sun, and C. Szepesvári · 2018
Later among the works it cites.
A bernstein-type inequality for functions of bounded interaction
A. Maurer · 2019
Closest in time.
An exponential tail bound for lq stable learning rules
K. Abou-Moustafa and C. Szepesvári · 2019
Closest in time.
Pac-bayes under potentially heavy tails
M. Holland · 2019
Closest in time.
Distribution-dependent analysis of gibbs-erm principle
I. Kuzborskij, N. Cesa-Bianchi, and C. Szepesvári · 2019
Closest in time.
A tight excess risk bound via a unified pac-bayesian–rademacher–shtarkov–mdl complexity
P. D. Grünwald and N. A. Mehta · 2019
Closest in time.
Pac-bayes un-expected bernstein inequality
Z. Mhammedi, P. D. Grünwald, and B. Guedj · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…