author:
- 'Fredrik Hellström, , Giuseppe Durisi,  [^1] [^2] [^3]'
bibliography:
- 'reference.bib'
title: Generalization Bounds via Information Density and Conditional Information Density
---

Introduction {#sec:introduction}
============

A randomized learning algorithm $P_{W\vert {\boldsymbol{Z}}}$ consists of a probabilistic mapping from a set of training data ${\boldsymbol{Z}}=(Z_1,\dots,Z_n)\in \mathcal{Z}^n$, which we assume to have been generated independently from an unknown distribution $P_Z$ on the instance space $\mathcal{Z}$, to an output hypothesis $W\in\mathcal{W}$, where $\mathcal{W}$ is the hypothesis space. The goal is to find a hypothesis $W$ that results in a small expected loss $L_{P_Z}(W)= \Exop_{P_Z}[\ell(W,Z)]$, where $\ell(\cdot,\cdot)$ is some suitably chosen loss function. A typical strategy to achieve this goal is *empirical risk minimization*, according to which $W$ is selected so as to minimize the empirical loss $L_{{\boldsymbol{Z}}}(W)=\tfrac{1}{n}\sum_{i=1}^n\ell(W,Z_i)$. A central objective in statistical learning theory is to determine when this choice results in a small population loss $L_{P_Z}(W)$. To this end, one seeks to bound the *generalization error*, defined as $\textnormal{gen}(W,{\boldsymbol{Z}}) = L_{P_Z}(W)-L_{{\boldsymbol{Z}}}(W)$. Since the learning algorithm is randomized, bounds on ${{\textnormal{gen}}(W,{\boldsymbol{Z}})}$ can come in several flavors. One possibility is to bound the average generalization error $\abs{\Exop_{P_{W\!{\boldsymbol{Z}}}}[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}]}$. In practice, one might be more interested in an upper bound on $\abs{\Exop_{P_{W\vert {\boldsymbol{Z}}}}[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}]}$ that holds 