Generalization Error Bounds via $m$th Central Moments of the Information
Density
F. Hellström, and G. Durisi. (2020)cite arxiv:2004.09148Comment: to be presented at ISIT 2020.
Abstract
We present a general approach to deriving bounds on the generalization error
of randomized learning algorithms. Our approach can be used to obtain bounds on
the average generalization error as well as bounds on its tail probabilities,
both for the case in which a new hypothesis is randomly generated every time
the algorithm is used - as often assumed in the probably approximately correct
(PAC)-Bayesian literature - and in the single-draw case, where the hypothesis
is extracted only once. For this last scenario, we present a novel bound that
is explicit in the central moments of the information density. The bound
reveals that the higher the order of the information density moment that can be
controlled, the milder the dependence of the generalization bound on the
desired confidence level. Furthermore, we use tools from binary hypothesis
testing to derive a second bound, which is explicit in the tail of the
information density. This bound confirms that a fast decay of the tail of the
information density yields a more favorable dependence of the generalization
bound on the confidence level.
Description
[2004.09148] Generalization Error Bounds via $m$th Central Moments of the Information Density
%0 Journal Article
%1 hellstrom2020generalization
%A Hellström, Fredrik
%A Durisi, Giuseppe
%D 2020
%K bounds density generalization information readings
%T Generalization Error Bounds via $m$th Central Moments of the Information
Density
%U http://arxiv.org/abs/2004.09148
%X We present a general approach to deriving bounds on the generalization error
of randomized learning algorithms. Our approach can be used to obtain bounds on
the average generalization error as well as bounds on its tail probabilities,
both for the case in which a new hypothesis is randomly generated every time
the algorithm is used - as often assumed in the probably approximately correct
(PAC)-Bayesian literature - and in the single-draw case, where the hypothesis
is extracted only once. For this last scenario, we present a novel bound that
is explicit in the central moments of the information density. The bound
reveals that the higher the order of the information density moment that can be
controlled, the milder the dependence of the generalization bound on the
desired confidence level. Furthermore, we use tools from binary hypothesis
testing to derive a second bound, which is explicit in the tail of the
information density. This bound confirms that a fast decay of the tail of the
information density yields a more favorable dependence of the generalization
bound on the confidence level.
@article{hellstrom2020generalization,
abstract = {We present a general approach to deriving bounds on the generalization error
of randomized learning algorithms. Our approach can be used to obtain bounds on
the average generalization error as well as bounds on its tail probabilities,
both for the case in which a new hypothesis is randomly generated every time
the algorithm is used - as often assumed in the probably approximately correct
(PAC)-Bayesian literature - and in the single-draw case, where the hypothesis
is extracted only once. For this last scenario, we present a novel bound that
is explicit in the central moments of the information density. The bound
reveals that the higher the order of the information density moment that can be
controlled, the milder the dependence of the generalization bound on the
desired confidence level. Furthermore, we use tools from binary hypothesis
testing to derive a second bound, which is explicit in the tail of the
information density. This bound confirms that a fast decay of the tail of the
information density yields a more favorable dependence of the generalization
bound on the confidence level.},
added-at = {2020-05-23T19:36:33.000+0200},
author = {Hellström, Fredrik and Durisi, Giuseppe},
biburl = {https://www.bibsonomy.org/bibtex/266f9aa4a1b0eb648b667cdb604f768a0/kirk86},
description = {[2004.09148] Generalization Error Bounds via $m$th Central Moments of the Information Density},
interhash = {006489b3f7b29c24d3d590dcc5e2eaab},
intrahash = {66f9aa4a1b0eb648b667cdb604f768a0},
keywords = {bounds density generalization information readings},
note = {cite arxiv:2004.09148Comment: to be presented at ISIT 2020},
timestamp = {2020-05-23T19:36:33.000+0200},
title = {Generalization Error Bounds via $m$th Central Moments of the Information
Density},
url = {http://arxiv.org/abs/2004.09148},
year = 2020
}