# Information-Theoretic Foundations for Machine Learning

Hong Jun Jeon  Benjamin Van Roy  Department of Electrical Engineering,
Stanford University  Department of Management Science and Engineering,
Stanford University

###### Abstract

The staggering progress of machine learning over the past decade has been a
sight to behold. In retrospect, it is both remarkable and unsettling that
these milestones were achievable with little to no rigorous theory to guide
experimentation. Despite this fact, practitioners have been able to guide
their future experimentation via observations from previous large-scale
empirical investigations. However, alluding to Plato’s Allegory of the cave,
it is likely that the observations which form the field’s notion of reality
are but shadows representing fragments of that reality. In this work, we
propose a theoretical framework which attempts to answer what exists outside
of the cave. To the theorist, we provide a framework which is mathematically
rigorous and leaves open many interesting ideas for future exploration. To the
practitioner, we provide a framework whose results are very intuitive,
general, and which will help form principles to guide future investigations.
Concretely, we provide a theoretical framework rooted in Bayesian statistics
and Shannon’s information theory which is general enough to unify the analysis
of many phenomena in machine learning. Our framework characterizes the
performance of an optimal Bayesian learner, which considers the fundamental
limits of information. Unlike existing analyses that weaken with increasing
data complexity, our theoretical tools provide accurate insights across
diverse machine learning settings. Throughout this work, we derive very
general theoretical results and apply them to derive insights specific to
settings ranging from data which is independently and identically distributed
under an unknown distribution, to data which is sequential, to data which
exhibits hierarchical structure amenable to meta-learning. We conclude with a
section dedicated to characterizing the performance of misspecified
algorithms. These results are exciting and particularly relevant as we strive
to overcome increasingly difficult machine learning challenges in this
endlessly complex world.

###### Contents

  1. 1 Introduction
  2. 2 Related Works
    1. 2.1 Frequentist and Bayesian Statistics
    2. 2.2 PAC Learning
    3. 2.3 Information Theory
  3. 3 A Framework for Learning
    1. 3.1 Probabilistic Framework and Notation
    2. 3.2 Data Generating Process
    3. 3.3 Error
    4. 3.4 Achievable Error
  4. 4 Requisite Information Theory
    1. 4.1 Entropy
    2. 4.2 Conditional Entropy
    3. 4.3 Mutual Information
    4. 4.4 Differential Entropy
    5. 4.5 Requisite Results from Information Theory
  5. 5 Connecting Learning and Information Theory
    1. 5.1 Error is Information
    2. 5.2 Characterizing Error via Rate-Distortion Theory
  6. 6 Learning from iid Data
    1. 6.1 Theoretical Results Tailored for iid Data
    2. 6.2 Linear Regression
      1. 6.2.1 Data Generating Process
      2. 6.2.2 Theoretical Building Blocks
      3. 6.2.3 Main Result
    3. 6.3 Logistic Regression
      1. 6.3.1 Data Generating Process
      2. 6.3.2 Theoretical Building Blocks
      3. 6.3.3 Main Result
    4. 6.4 Deep Neural Networks
      1. 6.4.1 Data Generating Process
      2. 6.4.2 Theoretical Building Blocks
      3. 6.4.3 Main Result
    5. 6.5 Nonparametric Learning
      1. 6.5.1 Data Generating Process
      2. 6.5.2 Theoretical Building Blocks
      3. 6.5.3 Main Result
  7. 7 Learning from Sequences
    1. 7.1 Data Generating Process
    2. 7.2 Binary AR(K) Process
      1. 7.2.1 Data Generating Process
      2. 7.2.2 Preliminary Theoretical Results
      3. 7.2.3 Main Result
    3. 7.3 Transformer Process
      1. 7.3.1 Data Generating Process
      2. 7.3.2 Theoretical Building Blocks
      3. 7.3.3 Main Result
  8. 8 Meta-Learning
    1. 8.1 Data Generating Process
    2. 8.2 Meta-Learning Error
    3. 8.3 Achievable Error
    4. 8.4 General Theoretical Results
    5. 8.5 Linear Representation Learning
      1. 8.5.1 Data Generating Process
      2. 8.5.2 Theoretical Building Blocks
      3. 8.5.3 Main Result
    6. 8.6 In-Context Learning
      1. 8.6.1 Data Generating Process
      2. 8.6.2 Theoretical Building Blocks
      3. 8.6.3 Main Result
  9. 9 Misspecification
    1. 9.1 General Theoretical Results
    2. 9.2 Linear Regression with Misspecification
      1. 9.2.1 Data Generating Process
      2. 9.2.2 Misspecified Algorithms
    3. 9.3 Neural Scaling Laws
  10. 10 Conclusion
  11. Appendix
  12. A Lower Bounds for Linear Regression
  13. B Theoretical Results for Dirichlet-Multinomial
    1. B.1 General Combinatorics Results
    2. B.2 Lemmas pertaining to Dirichlet Multinomial

##  1 Introduction

In the past decade, the staggering progress of machine learning has been a
sight to behold. The research community has conquered games such as go, which
were thought to require human-level learning and abstraction capabilities
[Silver et al., 2016]. We have produced systems which are capable of
displaying common-sense and holding coherent dialogues with humans around the
globe [Achiam et al., 2023]. It is undeniable that these artifacts will be
remembered throughout the future of humanity’s pursuit of discovering and
understanding intelligence.

In retrospect, it is both remarkable and unsettling that these milestones were
achievable with little to no rigorous theory to guide experimentation. While
theorists have attempted to repurpose existing statistical tools to analyze
modern machine learning, the conclusions have largely contradicted the
observations of practitioners. Zhang et al. [2021] aptly demonstrated this
point via a series of simple experiments which elucidated the fundamental
incompatibility of empirically observed phenomena with existing notions of
generalization. Despite this incoherence, practitioners have been able to
guide their future experimentation based on prior large-scale empirical
investigations. However, without a clear idea of how these phenomena slot into
a larger picture, many research efforts will continue to be led astray.
Alluding to Plato’s Allegory of the cave, it is likely that the _observations_
which form the field’s notion of reality are but shadows representing
_fragments_ of that reality.

In this work, we propose a theoretical framework which attempts to answer what
exists outside of the cave. To the theorist, we provide a framework which is
mathematically rigorous and leaves open many interesting ideas for future
exploration. To the practitioner, we provide a framework whose results are
very intuitive, general, and which will help form principles to guide future
investigations. Concretely, we provide a theoretical framework rooted in
Bayesian statistics which is general enough to unify the analysis of many
phenomena in machine learning.

Our theoretical framework draws inspiration from both Shannon’s theory of
information _and_ his maxim of “information first, then computation”. The turn
of the twentieth century brought a wave of interest in communications
research; work that would enable the transmission of signals across long
distances. Much of the work in encoding/decoding was approached heuristically,
similarly to how deep learning is today. Shannon’s theory and maxim redirected
attention to characterizing what was fundamentally _possible_ or _impossible_
, in the absence of computational constraints. His theory guided the discovery
of algorithms which achieved these fundamental limits and eventually practical
implementations as well.

The aforementioned staggering feats of machine learning and artificial
intelligence have fueled optimism that anything is learnable with sufficient
data and computation. However, research directions have largely been informed
by informal reasoning supported by a plethora of empirical studies. While work
in statistics provides some guidance, the results for the most part lack the
generality required to explain the continuing onslaught of novel empirical
findings. This monograph aims to provide a general framework to elucidate what
is possible by studying how the limits of performance in machine learning
depend on the informational content of the data. Our framework is based on
Shannon’s information theory and characterizes the dependence of performance
on information in the absence of computational constraints. Concretely, we
characterize the performance of an optimal Bayesian learner that observes data
generated by a suite of data generating processes of increasing complexity. By
expressing what is fundamentally possible in machine learning, we aim to
develop intuition that can _guide_ fruitful investigation.

Our framework characterizes the performance of an optimal Bayesian learner,
which considers the fundamental limits of information. Unlike existing
analyses that weaken with increasing data complexity, our theoretical tools
provide accurate insights across diverse machine learning settings. For
example, previous theories about learning from sequential data rely on
specific and rigid mixing time assumptions. However, Jeon et al. [2024]
leverage our framework to arrive at more general results which characterize
the sample complexity of learning from sequences autoregressively generated by
transformers [Vaswani et al., 2017]. They further extend the techniques to
analyze hierarchical data generating processes which resemble meta-learning
and in-context learning in large language models (LLMs). That these analytic
techniques remarkably apply whether data is exchangeable or exhibits more
complex structure points to the fundamental nature of our findings.

In recent years, we have observed that training larger machine learning models
on more data continues to produce _significantly_ better performance. This
continual improvement indicates that the data generating processes that we
study are _more complex_ than the machine learning models which we fit. We
refer to this phenomenon as “misspecification” and it is prominently observed
in natural language processing (NLP), where researchers have tried to
mathematically characterize this improvement in performance [Kaplan et al.,
2020, Hoffmann et al., 2022]. The “neural scaling laws” of Kaplan et al.
[2020] and Hoffmann et al. [2022] characterize the rate at which out-of-sample
log-loss decreased with respect to more available compute and data. While
these works provide extensive empirical experimentation, their cursory
mathematical analysis leave open many questions regarding how scaling laws
change depending on the complexity of the data-generating process. Jeon and
Roy [2024] once again use the theoretical tools from this monograph to
rigorously characterize the error incurred by a misspecified algorithm. They
study a data-generating process which is identified by an single hidden-layer
network of _infinite_ width and characterize how an algorithm with finite
budget should optimally allocate between parameter count and dataset size.
These results notably are consistent (up to logarithmic factors) with the the
findings of Hoffmann et al. [2022], where the optimal dataset size and
parameter count exhibit a linear relationship.

Despite the fact that our theory does not address computational constraints,
empirical studies with neural networks suggest that practical stochastic
gradient algorithms suffice to attain the tradeoffs that our theory
establishes between information and performance [Zhu et al., 2022]. Throughout
this work, we derive very general theoretical results and apply them to derive
insights specific to settings ranging from data which is iid under an unknown
distribution to data which is sequential to data which exhibits hierarchical
structure amenable to meta-learning. We conclude with a section dedicated to
characterizing the performance of _suboptimal_ algorithms that are based on
_misspecified_ models, an exciting and relevant direction for future work.

##  2 Related Works

###  2.1 Frequentist and Bayesian Statistics

We begin with a discussion of frequentist statistics, the predominant
framework which encompasses existing theoretical results. As its name would
suggest, in frequentist statistics, probability describes how often an event
occurs if a procedure is repeated many times. For instance, suppose there
exists an _unknown_ parameter $\mu\in\Re$ and a sample of size $T$:
$(X_{1},X_{2},\ldots,X_{T})$ which is drawn iid $\mathcal{N}(\mu,1)$. After
observing the sample, the frequentist statistician may construct a $95\%$
confidence interval for the unknown $\mu$. However, recall that in
frequentism, probability is assigned to how often an event occurs if a
procedure is repeated many times. For our example, this entails that if random
samples of size $T$ were drawn repeatedly and their corresponding confidence
intervals constructed, then $95\%$ of those confidence intervals would contain
$\mu$. Note that the unknown parameter $\mu$ is _fixed_ and hence not a
_random variable_ in the frequentist framework. As a result, the frequentist
framework does not use the tools of probability to model uncertainty
pertaining to $\mu$.

In contrast, Bayesian statistics treats _all_ unknown quantities as random
variables. A consequence is that these quantities must be assigned subjective
probabilities which reflect one’s prior beliefs pertaining to their values.
Returning to our example, the Bayesian may assign a prior distribution
$\mathbb{P}(\mu\in\cdot)=\mathcal{N}(0,1)$ which reflects their beliefs prior
to observing the sample. After observing the sample
$(x_{1},x_{2},\ldots,x_{T})$, they may construct a 95% _credible_ interval for
$\mu$, an interval $(a,b)$ for which
$\mathbb{P}(\mu\in(a,b)|X_{1}=x_{1},X_{2}=x_{2},\ldots,X_{T}=x_{T})\geq 0.95$.
The posterior distribution
$\mathbb{P}(\mu\in\cdot|X_{1}=x_{1},X_{2}=x_{2},\ldots,X_{T}=x_{T})$ is
computed via Bayes rule. Note that unlike the frequentist confidence interval
which pertains to repeated experimentation, the Bayesian credible interval
states that for this particular sample, with 95% probability, $\mu\in(a,b)$.
However, we note that this probability is _subjective_ as it relies upon the
prior subjective probability $\mathbb{P}(\theta\in\cdot)$. While this
_subjectivism_ has been a topic of constant philosophical debate, we note that
in the realm of decision theory, it is well known that the choices of a
decision maker which abides by axioms of rationality can be explained as the
result of a utility function and subjective probabilities assigned to events
[Savage, 1972].

While the debate surrounding these two schools of thought have continued for
almost a century, it is prudent to consider the purpose for such theory. We
are reminded of Laplace’s prudent remark that “Probability theory is nothing
but common sense reduced to calculation”. Theory’s merit ought to stem from
the results it can provide for specific problems [Jaynes and Kempthorne,
1976]. Jaynes and Kempthorne [1976] espoused this viewpoint as their
background in physics led to their interest in the use of probability to
describe and predict phenomena of the physical world. Machine learning too is
is rooted in predictions based on data produced by the physical world.
Therefore, we argue that the merits of machine learning theory also ought to
stem from its ability to describe and predict phenomena of data generated by
the physical world. To this end, we believe that the results which we derive
via our framework both better reflect what is observed empirically and are
also general enough to unify many disparate areas of the field.

###  2.2 PAC Learning

The majority of existing theoretical results for the analysis of modern
machine learning are set in the probably approximately correct (PAC) learning
framework [Valiant, 1984]. In PAC learning, an algorithm is presented with a
sample of data and is tasked with returning a hypothesis from a hypothesis set
which can accurately perform predictions out-of-sample. The _probably
approximately correct_ come from the detail that these results are phrased as
follows: “For any data distribution, with probability at least $1-\delta$ over
the randomness of an iid sample, the excess out-of-sample error is
$\leq\epsilon$”. “Probably” refers to the $1-\delta$ probability and
“approximately correct” the $\epsilon$ tolerance of out-of-sample error. While
this framework has facilitated the development of influential theoretical
concepts such as VC dimension [Vapnik, 2013] and Rademacher complexity
[Bartlett and Mendelson, 2002], Zhang et al. [2021] have demonstrated that
these tools are inherently insufficient to explain modern empirical phenomena.
Namely, they demonstrate empirically that while the Rademacher complexity of a
deep neural networks leads to vacuous theoretical results, the observed out-
of-sample error of these deep neural networks is actually small.

We posit that the looseness of these theoretical results stems from the fact
that they hold for _any_ data distribution and _uniformly_ over the hypothesis
set. While it is true that Rademacher complexity depends on the distribution
of the inputs, it does _not_ depend on the joint distribution of the input
_and_ outputs. Meanwhile, data which we observe from the real world clearly
contains inherent structure between input and output which facilitate sample-
efficient learning. Suppose we perform binary classification with input
$X\sim\mathcal{N}(0,I_{d})$. In case $1$, consider a data generating process
in which the corresponding class $Y$ only depends on the first element of $X$.
In case $2$, consider a data generating process in which $Y$ depends on all
$d$ elements of $X$. Common sense would dictate that if we observed an equal
number of samples from each data generating process and considered the same
hypothesis spaces, the _generalization error_ of case $1$ ought to be lower
than that of case $2$. However, an analysis via VC dimension or Rademacher
complexity would result in the _same_ generalization bound for case $1$ and
$2$. This problem exacerbated by high dimensional input distributions and
overparameterized hypothesis classes, both of which are prevalent qualities of
deep learning.

Several lines of analysis have attempted to ameliorate this via _data
dependent_ bounds. While these results also hold for any data distribution,
the _choice_ of data distribution will impact the resulting error bound.
Therefore, such a result will be vacuous (as expected) for a problem instance
with unstructured data, but potentially much tighter for one which exhibits
structure. The main frameworks for data dependent PAC results involve PAC
Bayes [McAllester, 1998] and the information-theoretic framework of Xu and
Raginsky [2017]. Both frameworks involve an algorithm which produces a
predictive distribution of the hypothesis conditioned on the observed data
(hence they analyze a Bayesian algorithm under the PAC framework). The two
only differ in that PAC Bayes results hold with high probability over random
draws of the data while the information-theoretic results hold in expectation
over random draws of the data. Therefore, each result upper bounds
generalization error via the KL divergence or the mutual information between
the observed data and the hypothesis.

These data dependent results mark a significant step in understanding the
puzzling empirical success of deep learning. Notably, Dziugaite and Roy [2017]
establish PAC-Bayes results for deep neural networks which result in bounds
that dramatically improve upon those based on parameter count or VC dimension.
These results reflect the importance that the _data generating process_ has on
the generalization error. However, a limitation is the lack of theoretical
tools which facilitate analytic derivations. Namely, the aforementioned KL
divergence/mutual information which bound generalization cannot be computed
analytically outside of simple problem instances. This is because these
quantities involve the posterior distribution of the hypothesis conditioned on
the data, which cannot be expressed analytically outside of simple instances
which exhibit a conjugate distribution. In contrast, our results analyze these
quantities in a Bayesian setting, allowing us to develop general tools to
bound mutual information analytically without needing to write down these
complicated posterior distributions. The conciseness and generality of these
results lead us to believe that they are fundamental.

###  2.3 Information Theory

The results of this work elucidate the tight relation between error in
learning and information measures of Shannon’s theory [Shannon, 1948]. Prior
work establishes connections between information theory and parameter
estimation notably through _information-theoretic lower bounds_. Namely, the
global Fano method resembles a portion of the techniques which we will cover
in this monograph.

A widely known framework involving information theory and machine learning is
the information bottleneck method [Tishby et al., 2000]. On the surface, this
work exhibits many similarities to ours as it draws a connection between
information theory, rate-distortion theory and machine learning. However, the
two works diverge in their purpose. The information bottleneck framework
describes a learning objective rooted in information theory and prescribes a
learning algorithm to solve this optimization problem. While they leveraged
their framework to produce early work on generalization in deep neural
networks [Tishby and Zaslavsky, 2015], the results remained very abstract.
While they devised metrics which they approximate empirically, they do not
provide theoretical tools to analyze these metrics analytically. In contrast,
we present our framework with a collection of theoretical tools which
facilitate analytic solutions. This is an important property of a theoretical
framework as it allows the researcher to _forecast_ what ought to be possible
in practice.

As alluded to above, there exist notable information-theoretic generalization
results in the PAC learning framework introduced by Russo and Zou [2019] and
expanded upon by Xu and Raginsky [2017]. While our work shares similar
analytic techniques, we are able to strengthen the results and provide more
streamlined theoretical tools by framing results in a Bayesian setting. In
particular, this framing allows us to upper and lower bound the mutual
information between the data and a latent parameter via the rate-distortion
function, which we can characterize analytically for even complex data
generating processes. We find the results of our framing to be fundamental and
we hope that the readers share this sentiment. We also hope that provides the
reader with a new perspective on machine learning.

The recent advances in LLMs have incited an interest in the connection between
learning and _compression_. In particular, researchers have posited that
models which are better able to compress the observed data will achieve lower
out-of-sample error. This point is conveyed in [Deletang et al., 2024].
However, they do not provide a mathematically rigorous connection between
learning and compression. In this work we establish a rigorous connection
between learning and optimal _lossy_ compression. The loss incurred by an
optimal Bayesian learner is upper and lower bounded by appropriate expressions
containing the rate-distortion function (characterization of optimal lossy
compression). For this community, we hope that our work provides clarity to
this matter and informs future experimentation and algorithm design.

##  3 A Framework for Learning

###  3.1 Probabilistic Framework and Notation

In our work, we define all random variables with respect to a common
probability space $(\Omega,\mathbb{F},\mathbb{P})$. Recall that a random
variable $\theta$ is a measurable function $\Omega\mapsto\Theta$ from the
sample space $\Omega$ to a set $\Theta$.

The probability measure $\mathbb{P}:\mathbb{F}\mapsto[0,1]$ assigns
probabilities to events in the $\sigma-{\rm algebra}$ $\mathbb{F}$. In
particular, for any event $F\in\mathbb{F}$, $\mathbb{P}(F)$ denotes the
probability of the event. For events $F,G\in\mathbb{F}$ for which
$\mathbb{P}(G)>0$, $\mathbb{P}(F|G)$ denotes the probability of event $F$
conditioned on event $G$.

For each realization $z$ of a random variable $Z$, $\mathbb{P}(Z=z)$ is hence
a function of $z$. We denote the value of this function evaluated at $Z$ by
$\mathbb{P}(Z)$. Therefore, $\mathbb{P}(Z)$ is a random variable (since it
takes realizations in $[0,1]$ depending on the value of $Z$). Likewise for
realizations $(y,z)$ of random variables $Y,Z$, $\mathbb{P}(Z=z|Y=y)$ is a
function of $(y,z)$ and $\mathbb{P}(Z|Y)$ is a random variable which denotes
the value of this function evaluated at $(Y,Z)$.

If random variable $Z:\Omega\mapsto\Re^{K}$ has density $p_{Z}$ w.r.t the
Lebesgue measure, the conditional probability $\mathbb{P}(F|Z=z)$ is well-
defined despite the fact that for all $z$, $\mathbb{P}(Z=z)=0$. If function
$f(z)=\mathbb{P}(F|Z=z)$ and $Y:\Omega\mapsto\Re^{K}$ is a random variable
whose range is a subset of $Z$’s, then we use the $\leftarrow$ symbol with
$\mathbb{P}(F|Z\leftarrow Y)$ to denote $f(Y)$. Note that this is different
from $\mathbb{P}(F|Z=Y)$ since this conditions on the event $Z=Y$ while
$\mathbb{P}(F|Z\leftarrow Y)$ indicates a change of measure.

For any random variable $\theta$, we use the notation
$\mathbb{P}(\theta\in\cdot)$ to denote the _distribution_ of that random
variable i.e. $\mathbb{P}(\theta\in\cdot)=\mathbb{P}(\theta^{-1}(\cdot))$,
where $\theta^{-1}(\cdot)$ denotes the pre-image of $\cdot$ (the pre-image
must be $\in\mathbb{F}$ due to measurability). We make a clear distinction
between a random variable and its distribution in this way to provide accurate
definitions of information-theoretic quantities later in this work. As
mentioned in the introduction, our framework is Bayesian, and hence uses the
tools of probability to model uncertainty about the unknown value of a
variable of interest (for instance $\theta$). This involves treating $\theta$
as a random variable with a prior distribution $\mathbb{P}(\theta\in\cdot)$
which encodes the designer’s prior information about the value of this
variable. The designer will often never directly observe $\theta$, but rather
a stream of _data_ which will contain information about $\theta$. Machine
Learning is therefore the process of reducing uncertainty about $\theta$ in
ways that are relevant for making better predictions about the future of this
data stream.

###  3.2 Data Generating Process

In machine learning, we are interested in discerning the relationship between
input and output pairs $(X,Y)$. Most frameworks of machine learning focus on a
static dataset of fixed size and hope to characterize the performance of a
predictive algorithm which leverages the information from the dataset for
future predictions. However, any practical system will continually have access
to additional observations as it interacts with the environment. As a result,
it is prudent to consider a framework in which the data arrives in an online
fashion and the objective is to perform well across all time.

We consider a stochastic process which generates a sequence
$((X_{t},Y_{t+1}):t\in\mathbb{Z}_{+})$ of data pairs. For all $t$, we let
$H_{t}$ denote the history $(X_{0},Y_{1},\ldots,X_{t-1},Y_{t},X_{t})$ of
experience. We assume that there exists an underlying latent variable $\theta$
such that $(X_{0},X_{1},\ldots)\perp\theta$ and $\theta$ prescribes a
conditional probability measure $\theta(\cdot|H_{t})$ to the next label
$Y_{t+1}$. In the case of an _iid_ data generating process, this conditional
probability measure would only depend on $H_{t}$ via $X_{t}$. Furthermore,
such a latent variable $\theta$ must exist under an infinite exchangability
assumption on the sequence $((X_{t},Y_{t+1}):t\in\mathbb{Z}_{+})$ by de
Finetti’s Theorem. While we will first focus on this iid setting, we will also
study learning setting in which the future data may be arbitrarily dependent
on $H_{t}$ even when conditioned on $\theta$. As our framework is Bayesian, we
represent our uncertainty about $\theta$ by modeling it as a random variable
with prior distribution $\mathbb{P}(\theta\in\cdot)$.

###  3.3 Error

Our framework focuses on a particular notion of error which facilitates
analysis via Shannon-information theory. For all $t\in\mathbb{Z}_{+}$, our
algorithm is tasked with providing a predictive distribution $P_{t}$ of
$Y_{t+1}$ which may be derived from the history of data $H_{t}$ which has
already been observed. We denote such algorithm as $\pi$ for which for all
$t$, $P_{t}=\pi(H_{t})$. As aforementioned, an effective learning system ought
to leverage data as it becomes available. As a result, for any time horizon
$T\in\mathbb{Z}_{+}$, we are interested in quantifying the cumulative expected
log-loss:

$\mathbb{L}_{T,\pi}=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\pi}\left[-\ln
P_{t}(Y_{t+1})\right].$

As outlined in section 3.1, we take all random variables to be defined with
respect to a common probability space. As a result, the expectation
$\mathbb{E}$ integrates over all random variables which we do not condition
on. We use the subscript $\pi$ in $\mathbb{E}_{\pi}$ to specify that it is a
function of $\pi$ since for all $t$, $\pi$ produces $P_{t}$. As $Y_{t+1}$ is
the random variable which represents the next label that is generated by the
underlying stochastic process, $P_{t}(Y_{t+1})$ denotes the probability that
our prediction $P_{t}$ assigned to label $Y_{t+1}$.

This loss function is commonly referred to in the literature as “log-loss” or
“negative log-likelihood” and has become a cornerstone of classification
methods via neural networks. However, it is important to note that even for an
_optimal_ algorithm, the minimum achievable log-loss is not $0$. For instance,
consider an _omniscient_ algorithm in the classification setting which
produces for all $t$ the prediction
$P_{t}=\mathbb{P}(Y_{t+1}\in\cdot|\theta,H_{t})$. Even this agent incurs a
loss of:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\pi}\left[-\ln\mathbb{P}(Y_{t+1}|\theta,H_{t})\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{H}(Y_{t+1}|\theta,H_{t})$
$\displaystyle=\frac{\mathbb{H}(Y_{1:T}|\theta,X_{0:T-1})}{T},$

where our point follows from the fact that the conditional entropy of a
discrete random variable $Y_{1:T}$ is non-negative. As a result, we define the
_estimation error_ as:

$\mathcal{L}_{T,\pi}=\mathbb{L}_{T,\pi}-\frac{\mathbb{H}(Y_{1:T}|\theta,X_{0:T-1})}{T}.$

Estimation error represents the error which is reducible via learning. As
such, for a competent learning algorithm tasked with a learnable task,
$\mathcal{L}_{T,\pi}$ should decay to $0$ as $T$ goes to $\infty$.

###  3.4 Achievable Error

Since we are interested in characterizing the limits of what is possible via
machine learning, a natural question which arises is: For all $T$, which $\pi$
minimizes $\mathcal{L}_{T,\pi}$? Since log-loss is a proper scoring rule, the
optimal algorithm $\pi$ is one such that for all $t$,
$P_{t}=\mathbb{P}(Y_{t+1}\in\cdot|H_{t})$. This predictive distribution is
often referred to as the _Bayesian posterior_ and going forward we will denote
it by $\hat{P}_{t}$. The following result establishes optimality of
$\hat{P}_{t}$.

######  Lemma 1.

(Bayesian posterior is optimal) For all $t\in\mathbb{Z}_{+}$,

$\mathbb{E}\left[-\ln\hat{P}_{t}(Y_{t+1})\mid H_{t}\right]\ \overset{a.s.}{=}\
\min_{\pi}\ \mathbb{E}_{\pi}\left[-\ln P_{t}(Y_{t+1})\mid H_{t}\right].$

###### Proof.

$\displaystyle\mathbb{E}\left[-\ln P_{t}(Y_{t+1})|H_{t}\right]$
$\displaystyle\overset{a.s.}{=}\mathbb{E}\left[-\ln\hat{P}_{t}(Y_{t+1})+\ln\frac{\hat{P}_{t}(Y_{t+1})}{P_{t}(Y_{t+1})}\bigg{|}H_{t}\right]$
$\displaystyle\overset{a.s.}{=}\mathbb{E}\left[-\ln\hat{P}_{t}(Y_{t+1})|H_{t}\right]+{\mathbf{d}}_{\rm
KL}\left(\hat{P}_{t}\|P_{t}\right).$

The result follows from the fact that KL-divergence is non-negative and the
tower property. ∎

This result is rather convenient since it prescribes that across all problem
instances, the optimal prediction is $\hat{P}_{t}$. This is widely considered
an advantage of the Bayesianism as opposed to the frequentism; the Bayesian
need not specify an ad-hoc algorithm to analyze/solve a problem. While in
practice it may be intractable to compute $\hat{P}_{t}$ exactly, for the
purposes of characterizing _achievable_ error, it provides immense utility.
Going forward, we will restrict our attention to the _optimal achievable_
estimation error which we denote by:

$\mathcal{L}_{T}=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[-\ln\hat{P}_{t}(Y_{t+1})\right]-\frac{\mathbb{H}(Y_{1:T}|\theta,X_{0:T-1})}{T}.$

The process of learning should result in $\mathcal{L}_{T}$ vanishing to $0$ as
$T$ increase to $\infty$. While we have established that the Bayesian
posterior provides optimal predictions at each timestep, in its current form,
it is unclear how to characterize $\mathcal{L}_{T}$ for problems in which the
posterior distribution does not exhibit an analytic form. In section 5, we
will establish the connection between our learning framework and information
theory. This connection will facilitate the analysis of _arbitrary_ learning
problems, even those for which $\hat{P}_{t}$ cannot be expressed analytically.

In the following section, we overview requisite definitions and tools from
information theory to establish the connection between learning and
information theory. For readers who are new to information theory, we provide
the following section for completeness. Even for readers who are familiar with
information theory, there may be details or results is the following section
which may be worth revisiting.

### Summary

  * •

The algorithm’s observations through time $t$ form a history
$H_{t}=(X_{0},Y_{1},\ldots X_{t-1},Y_{t},X_{t})$.

  * •

The algorithm $\pi$ produces for all $t$ a predictive distribution $P_{t}$ of
$Y_{t+1}$ given the history $H_{t}$.

  * •

For any horizon $T\in\mathbb{Z}_{+}$, we define estimation error of an
algorithm $\pi$ as

$\mathcal{L}_{T,\pi}=\underbrace{\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\pi}\left[-\ln
P_{t}(Y_{t+1})\right]}_{\rm log-
loss}-\underbrace{\frac{\mathbb{H}(Y_{1:T}|\theta,X_{0:T-1})}{T}}_{\rm
irreducible\ error}.$

  * •

The optimal algorithm assigns for all $t$,

$P_{t}\leftarrow\hat{P}_{t}=\mathbb{P}(Y_{t+1}\in\cdot|H_{t}).$

  * •

We denote the estimation error incurred by the optimal algorithm by

$\mathcal{L}_{T}=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\pi}\left[-\ln\hat{P}_{t}(Y_{t+1})\right]-\frac{\mathbb{H}(Y_{1:T}|\theta,X_{0:T-1})}{T}.$

##  4 Requisite Information Theory

In this section we outline definitions and results from information theory
which we will refer to in later sections of this monograph. For a
comprehensive overview of the topic, we point the reader to [Cover and Thomas,
2012].

###  4.1 Entropy

In this text, $\mathbb{H}(X)$ denotes the _entropy_ of a discrete random
variable $X:\Omega\mapsto\mathcal{X}$. $\mathbb{H}$ is defined as follows:

$\mathbb{H}(X)=\sum_{x\in\mathcal{X}}\mathbb{P}(X=x)\ln\frac{1}{\mathbb{P}(X=x)}.$

Throughout this monograph, we use the convention that $0\ln 0=0$. While there
are many colloquial interpretations of entropy which describe it as the
expected “surprise” associated with outcomes of a random variable, we provide
a concrete motivation for entropy based on coding theory.

We begin our exposition of entropy with an introduction to coding theory. We
first define a code for a random variable.

######  Definition 2.

A code $C$ for random variable $X:\Omega\mapsto\mathcal{X}$ is a function
which maps $\mathcal{X}\mapsto\\{0,1\\}^{*}$, where $\\{0,1\\}^{*}$ denotes
the set of all binary strings.

When we send a text message to our friend, the characters that comprise of our
message can be thought of as the realizations of random variables. In many
applications involving digital data transfer, a message (outcome of a random
variable) is encoded into a binary string which is passed through a
communication channel, and decoded at an endpoint. Since the binary string
arrives in a stream, it would be convenient if the message could be uniquely
decoded as the data is arriving. A necessary and sufficient condition for this
is online decodability is to design a code $C$ which is _prefix-free_ i.e. no
element in the image of $C$ is a _prefix_ of another element in the image of
$C$. We use $\mathcal{C}_{X}$ to denote the set of prefix-free codes for a
random variable $X$

Since these codes are stored, transmitted, and decoded, the memory footprint
becomes a significant design consideration. A natural question which arises
is: “how do we devise _optimal_ prefix-free codes?” The notion of optimality
which gives rise to Shannon entropy is the following:

$\operatorname*{arg\,min}_{C\in\mathcal{C}_{X}}\
\sum_{x\in\mathcal{X}}\mathbb{P}(X=x)\cdot\frac{\text{len}\left(C(x)\right)}{\log_{2}(e)},$

where $\text{len}(c)$ denotes the length of binary string $c$. A prefix-free
code which minimizes this objective will on-average require the fewest number
of bits to store/transmit information. A naive prefix-free code is one which
maps each of the $|\mathcal{X}|$ outcomes of $X$ to a unique binary string of
length $\lceil\log_{2}|\mathcal{X}|\rceil$. While such a code would be
reasonable if all outcomes of $X$ were equally likely, such a code would be
highly suboptimal if some outcomes are much more/less likely than others. A
competent coding scheme ought to map more likely outcomes to _shorter_ strings
and less likely outcomes to _longer_ strings.

Figure 1: The English alphabet consists of characters of varying frequency
across common text corpuses. Notably, the vowels appear with greater
frequency. A coding scheme ought to map these more frequently appearing
characters to shorter strings.

The following result establishes the tight connection between the _entropy_ of
$X$ and its optimal prefix-free code.

######  Theorem 3.

(entropy characterizes optimal prefix-free code length) For all discrete
random variables $X:\Omega\mapsto\mathcal{X}$,

$\mathbb{H}(X)\ \leq\ \min_{C\in\mathcal{C}_{X}}\
\sum_{x\in\mathcal{X}}\mathbb{P}(X=x)\cdot\frac{{\rm len}(C(x))}{\log_{2}(e)}\
\leq\ \mathbb{H}(X)+\frac{1}{\log_{2}(e)}.$

This result demonstrates that the entropy of a random variable tightly
characterizes the fundamental limit to which it can be losslessly compressed.
As a result, the entropy reflects the inherent complexity of a random
variable. This connection is useful to keep in mind as there exist the
following analogies between our Bayesian and the frequentist frameworks:

frequentist $\displaystyle\mapsto\text{Bayesian}$ $\displaystyle\Theta$
$\displaystyle\mapsto\mathbb{P}(\theta\in\cdot)$ $\displaystyle|\Theta|$
$\displaystyle\mapsto\mathbb{H}(\theta),$

where $\theta:\Omega\mapsto\Theta$ and $|\Theta|$ denotes the cardinality of
$\Theta$.

###  4.2 Conditional Entropy

$\mathbb{H}(X|Y)$ denotes the _conditional entropy_ of a discrete random
variable $X:\Omega\mapsto\mathcal{X}$ conditioned on another discrete random
variable $Y:\Omega\mapsto\mathcal{Y}$. The conditional entropy is defined as
follows:

$\mathbb{H}(X|Y)=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{1}{\mathbb{P}(X=x|Y=y)}.$

Note that _unlike_ conditional expectation, conditional entropy is a _number_
(and not a random variable). Upon closer inspection it is clear that
conditional entropy is also always non-negative and is $0$ only when $Y$ fully
determines $X$. On the other hand, when $X\perp Y$, we have that
$\mathbb{H}(X|Y)=\mathbb{H}(X)$. We provide the following result which
facilitates mathematical manipulations involving the information-theoretic
quantities outlined thus far.

######  Lemma 4.

(chain rule of conditional entropy) For all discrete random variables
$X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y}$,

$\mathbb{H}(X,Y)\ =\ \mathbb{H}(X)+\mathbb{H}(Y|X)\ =\
\mathbb{H}(Y)+\mathbb{H}(X|Y).$

###### Proof.

$\displaystyle\mathbb{H}(X)+\mathbb{H}(Y|X)$
$\displaystyle=\sum_{x\in\mathcal{X}}\mathbb{P}(X=x)\ln\frac{1}{\mathbb{P}(X=x)}+\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{1}{\mathbb{P}(Y=y|X=x)}$
$\displaystyle=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{1}{\mathbb{P}(X=x)}+\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{\mathbb{P}(X=x)}{\mathbb{P}(X=x,Y=y)}$
$\displaystyle=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{1}{\mathbb{P}(X=x,Y=y)}$
$\displaystyle=\mathbb{H}(X,Y).$

The second equality in the lemma statement follows from the same technique
shown above. ∎

If $\mathbb{H}(X,Y)$ denotes the average length of a prefix-free code for
$(X,Y)$ jointly, Lemma 4 establishes that $\mathbb{H}(X|Y)$ reflects the
average length of a prefix-free code for $X$ after $Y$ is _already_ observed.
Evidently if $X\perp Y$, then observing $Y$ does not provide any information
which enables a shorter code for $X$ (hence, $\mathbb{H}(X|Y)=\mathbb{H}(X)$).
However, in the other extreme in which $X\overset{a.s.}{=}Y$, observing $Y$
means that $X$ is also known. As a result, a trivial code which maps every
outcome of $X$ to the null string $\emptyset$ will suffice (hence,
$\mathbb{H}(X|Y)=0$).

###  4.3 Mutual Information

$\mathbb{I}(X;Y)$ denotes the _mutual information_ between two random
variables $X:\Omega\mapsto\mathcal{X}$ and $Y:\Omega\mapsto\mathcal{Y}$.
Concretely,

$\mathbb{I}(X;Y)\ =\ {\mathbf{d}}_{\rm
KL}\left(\mathbb{P}((X,Y)\in\cdot)\|\mathbb{P}(X\in\cdot)\otimes\mathbb{P}(Y\in\cdot)\right),$

where $\mathbb{P}(X\in\cdot)\otimes\mathbb{P}(Y\in\cdot)$ denotes the outer
product distribution. Note that KL divergence is a non-symmetric function
which maps two _probability distributions_ to $\Re_{+}\cup\\{\infty\\}$. For
discrete random variables, we have the following equivalence between mutual
information and differences of (conditional) entropies:

$\mathbb{I}(X;Y)\ =\ \mathbb{H}(X)-\mathbb{H}(X|Y)\ =\
\mathbb{H}(Y)-\mathbb{H}(Y|X).$

Note that mutual information is symmetric i.e.
$\mathbb{I}(X;Y)=\mathbb{I}(Y;X)$ and it is also always non-negative (follows
directly as a consequence of Lemma 10). Intuitively, the mutual information
$\mathbb{I}(X;Y)$ represents the amount of information that $X$ conveys about
$Y$ and vice versa. As such, if $X$ fully determines $Y$, then
$\mathbb{I}(X;Y)=\mathbb{H}(X)=\mathbb{H}(Y)$. Meanwhile if $X\perp Y$, then
$\mathbb{I}(X;Y)=0$ as the two random variables convey no information about
each other. As with conditional entropy, we provide the following result which
facilitates mathematical analyses involving mutual information:

######  Lemma 5.

(chain rule of mutual information) For all random variables
$X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y},Z:\Omega\mapsto\mathcal{Z}$,

$\mathbb{I}(Y;Z|X)+\mathbb{I}(X;Z)=\mathbb{I}(X,Y;Z).$

###### Proof.

$\displaystyle\mathbb{I}(Y;Z|X)+\mathbb{I}(X;Z)$
$\displaystyle=\mathbb{H}(Z|X)-\mathbb{H}(Z|X,Y)+\mathbb{H}(Z)-\mathbb{H}(Z|X)$
$\displaystyle=\mathbb{H}(Z)-\mathbb{H}(Z|X,Y)$
$\displaystyle=\mathbb{I}(X,Y;Z).$

∎

Figure 2: This venn diagram illustrates the relationships between the
introduced information-theoretic quantities.

###  4.4 Differential Entropy

While we have defined information-theoretic quantities for discrete random
variables, outside of mutual information we have not broached a notion of
information regarding _continuous_ random variables. For a continuous random
variable $X:\Omega\mapsto\mathcal{X}$ with density $p_{X}$ (w.r.t the Lebesgue
measure), we denote the differential entropy of $X$ by

$\mathbf{h}(X)\ =\
\int_{x\in\mathcal{X}}p_{X}(x)\ln\frac{1}{p_{X}(x)}d\mu(x),$

where $\mu(\cdot)$ denotes the Lebesgue measure. While differential entropy
ostensibly resembles discrete entropy, the two are different in almost all
regards. For instance, while the discrete entropy of a random variable is
always non-negative, the differential entropy can often be negative. Look no
further than $X=\text{Uniform}([0,1/2])$. In this case,
$\mathbf{h}(X)=-\ln(2)$. Furthermore, while discrete entropy is invariant
under one-to-one transformations, the differential entropy is not. For
instance, $\mathbf{h}(2X)=\mathbf{h}(X)+\ln 2$. A measure of information
should _not_ be negative nor should it be dependent on _units_ used. For these
reasons, unlike discrete entropy, differential entropy is _not_ a meaningful
informational quantity by itself. The correct extension of discrete entropy to
continuous random variables exists via rate-distortion theory, which we will
present in the following section.

While differential entropy itself is not a meaningful measure of information,
_differences_ in (conditional) differential entropies are still equal to
mutual information. Concretely, for continuous random variables $X,Y$ with
finite (conditional) differential entropies,

$\mathbb{I}(X;Y)\ =\ \mathbf{h}(X)-\mathbf{h}(X|Y)\ =\
\mathbf{h}(Y)-\mathbf{h}(Y|X).$

###  4.5 Requisite Results from Information Theory

We now present an amalgamation of widely known and requisite results from
information theory. Various proofs throughout this monograph will refer to the
results of this section.

######  Lemma 6.

(log-sum inequality) For all $n\in\mathbb{Z}$, if $a_{1},\ldots,a_{n}\geq 0$,
$b_{1},\ldots,b_{n}\geq 0$, and $a=\sum_{i=1}^{n}a_{i},b=\sum_{i=1}^{n}b_{i}$,
then

$\sum_{i=1}^{n}a_{i}\ln\frac{a_{i}}{b_{i}}\geq a\ln\frac{a}{b}.$

###### Proof.

$\displaystyle\sum_{i=1}^{n}a_{i}\ln\frac{a_{i}}{b_{i}}$
$\displaystyle=\sum_{i=1}^{n}b_{i}\cdot\frac{a_{i}}{b_{i}}\ln\frac{a_{i}}{b_{i}}$
$\displaystyle=b\sum_{i=1}^{n}\frac{b_{i}}{b}\cdot\frac{a_{i}}{b_{i}}\ln\frac{a_{i}}{b_{i}}$
$\displaystyle\overset{(a)}{\geq}b\left(\sum_{i=1}^{n}\frac{b_{i}}{b}\cdot\frac{a_{i}}{b_{i}}\right)\ln\left(\sum_{i=1}^{n}\frac{b_{i}}{b}\cdot\frac{a_{i}}{b_{i}}\right)$
$\displaystyle=b\cdot\frac{a}{b}\ln\frac{a}{b}$
$\displaystyle=a\ln\frac{a}{b},$

where (a) follows from Jensen’s inequality applied to the function $x\ln x$. ∎

######  Lemma 7.

(conditioning reduces entropy) For all discrete random variables
$X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y}$,

$\mathbb{H}(X)\geq\mathbb{H}(X|Y).$

###### Proof.

$\displaystyle\mathbb{H}(X)$
$\displaystyle=\sum_{x\in\mathcal{X}}\mathbb{P}(X=x)\ln\frac{1}{\mathbb{P}(X=x)}$
$\displaystyle=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{1}{\mathbb{P}(X=x)}$
$\displaystyle\overset{(a)}{\geq}\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{\mathbb{P}(Y=y)}{\mathbb{P}(X=x,Y=y)}$
$\displaystyle=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{1}{\mathbb{P}(X=x|Y=y)}$
$\displaystyle=\mathbb{H}(X|Y),$

where $(a)$ follows from negating the log-sum inequality and setting
$a_{i}=\mathbb{P}(X=x,Y=y),b_{i}=\mathbb{P}(Y=y)$ and $a=\mathbb{P}(X=x),b=1$.
∎

######  Lemma 8.

(conditioning reduces differential entropy) For all continuous random
variables $X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y}$, if
$\mathbf{h}(X),\mathbf{h}(X|Y)$ exist and are both finite, then

$\mathbf{h}(X)\geq\mathbf{h}(X|Y).$

###### Proof.

The proof follows from the same reasoning as in Lemma 7 by constructing a
sequence of partitions of $\mathcal{X},\mathcal{Y}$ and taking the associated
limits. ∎

######  Lemma 9.

(equivalence of mutual information and KL-divergence) For all random variables
$X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y}$,

$\mathbb{I}(X;Y)=\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(Y\in\cdot|X)\ \|\ \mathbb{P}(Y\in\cdot)\right)\right].$

###### Proof.

We prove the result for discrete random variables $X,Y$. With appropriate
technical assumptions, the result can also be extended to continual random
variables which exhibit density functions.

$\displaystyle\mathbb{I}(X;Y)$
$\displaystyle=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{\mathbb{P}(X=x,Y=y)}{\mathbb{P}(X=x)\cdot\mathbb{P}(Y=y)}$
$\displaystyle=\sum_{x\in\mathcal{X}}\mathbb{P}(X=x)\sum_{y\in\mathcal{Y}}\mathbb{P}(Y=y|X=x)\ln\frac{\mathbb{P}(Y=y|X=x)}{\mathbb{P}(Y=y)}$
$\displaystyle=\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(Y\in\cdot|X)\ \|\ \mathbb{P}(Y\in\cdot)\right)\right].$

∎

######  Lemma 10.

(non-negativity of KL-divergence) For all probability distributions
$P(\cdot):\mathbb{F}\mapsto[0,1],Q(\cdot)\mathbb{F}\mapsto[0,1]$,

${\mathbf{d}}_{\rm KL}\left(P(\cdot)\ \|\ Q(\cdot)\right)\geq 0.$

Furthermore,

${\mathbf{d}}_{\rm KL}(\left(P(\cdot)\ \|\ Q(\cdot)\right)=0\iff\text{ for all
}\nu\in\mathbb{F},\left(P(\nu)>0\implies P(\nu)=Q(\nu)\right).$

###### Proof.

$\displaystyle{\mathbf{d}}_{\rm KL}\left(P(\cdot)\ \|\ Q(\cdot)\right)$
$\displaystyle=\sum_{\nu\in\mathbb{F}}P(\nu)\ln\frac{P(\nu)}{Q(\nu)}$
$\displaystyle=\sum_{\nu\in\mathbb{F}}-P(\nu)\ln\frac{Q(\nu)}{P(\nu)}$
$\displaystyle\overset{(a)}{\geq}-\ln\sum_{\nu\in\mathbb{F}}P(\nu)\cdot\frac{Q(\nu)}{P(\nu)}$
$\displaystyle=-\ln\sum_{\nu\in\mathbb{F}}Q(\nu)$ $\displaystyle=0.$

where $(a)$ follows from Jensen’s inequality. To prove the second result,
consider the case in which Jensen’s inequality holds with _equality_. This
occurs iff $Q(\nu)/P(\nu)=\sum_{\nu\in\mathbb{F}}P(\nu)\cdot Q(\nu)/P(\nu)=1$.
This occurs only when $Q(\nu)=P(\nu)$ for all $\nu\in\mathbb{F}$ for which
$P(\nu)>0$. ∎

######  Lemma 11.

(maximum differential entropy) For all density functions
$q:\Re^{d}\mapsto\Re_{+}$, for all $i,j\in[d]$, let
$\Sigma_{i,j}=\int_{x\in\Re^{d}}x_{i}x_{j}q(x)dx$. If
$X\sim\mathcal{N}(0,\Sigma)$, then

$\mathbf{h}(X)\geq\int_{x\in\Re^{d}}q(x)\ln\frac{1}{q(x)}dx.$

###### Proof.

Let $p$ denote the probability density function of $X$.

$\displaystyle\mathbf{h}(X)$
$\displaystyle=\int_{x\in\Re^{d}}-p(x)\left(\frac{1}{2}\ln(2\pi
e|\Sigma|)-\frac{x^{\top}\Sigma^{-1}x}{2}\right)dx$
$\displaystyle=-\frac{1}{2}\ln\left(2\pi
e|\Sigma|\right)+\int_{x\in\Re^{d}}p(x)\cdot\frac{x^{\top}\Sigma^{-1}x}{2}dx$
$\displaystyle\overset{(a)}{=}-\frac{1}{2}\ln\left(2\pi
e|\Sigma|\right)+\int_{x\in\Re^{d}}q(x)\cdot\frac{x^{\top}\Sigma^{-1}x}{2}dx$
$\displaystyle=\int_{x\in\Re^{d}}q(x)\ln\frac{1}{p(x)}dx$
$\displaystyle=\int_{x\in\Re^{d}}q(x)\ln\frac{1}{q(x)}dx+{\mathbf{d}}_{\rm
KL}\left(q(\cdot)\ \|\ p(\cdot)\right)$
$\displaystyle\overset{(b)}{\geq}\int_{x\in\Re^{d}}q(x)\ln\frac{1}{q(x)}dx$

where $(a)$ follows from the equivalence of covariances assumption and $(b)$
follows from Lemma 10. ∎

######  Lemma 12.

(data processing inequality) Let $X,Y,Z$ be random variables for which $X\perp
Z|Y$, then

$\mathbb{I}(X;Z)\leq\mathbb{I}(Y;Z),\ \mathbb{I}(X;Z)\leq\mathbb{I}(X;Y).$

$\displaystyle\mathbb{I}(X;Z)$ $\displaystyle\leq\mathbb{I}(X,Y;Z)$
$\displaystyle=\mathbb{I}(Y;Z)+\mathbb{I}(X;Z|Y)$
$\displaystyle\overset{(a)}{=}\mathbb{I}(Y;Z),$

where $(a)$ follows from the independence assumption. Similarly,

$\displaystyle\mathbb{I}(X;Z)$ $\displaystyle\leq\mathbb{I}(X;Y,Z)$
$\displaystyle=\mathbb{I}(X;Y)+\mathbb{I}(X;Z|Y)$
$\displaystyle=\mathbb{I}(X;Y).$

### Summary

  * •

The _entropy_ of a discrete random variable $X:\Omega\mapsto\mathcal{X}$ is

$\mathbb{H}(X)=\sum_{x\in\mathcal{X}}\mathbb{P}(X=x)\ln\frac{1}{\mathbb{P}(X=x)}.$

  * •

The _conditional entropy_ of a discrete random variable
$X:\Omega\mapsto\mathcal{X}$ conditioned on another discrete random variable
$Y:\Omega\mapsto\mathcal{Y}$ is

$\mathbb{H}(X|Y)=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\mathbb{P}(X=x,Y=y)\ln\frac{1}{\mathbb{P}(X=x|Y=y)}.$

  * •

The _mutual information_ between two random variables
$X:\Omega\mapsto\mathcal{X}$ and $Y:\Omega\mapsto\mathcal{Y}$ is

$\mathbb{I}(X;Y)\ =\ {\mathbf{d}}_{\rm
KL}\left(\mathbb{P}((X,Y)\in\cdot)\|\mathbb{P}(X\in\cdot)\otimes\mathbb{P}(Y\in\cdot)\right),$

where $\mathbb{P}(X\in\cdot)\otimes\mathbb{P}(Y\in\cdot)$ denotes the outer
product distribution. For discrete random variables,

$\mathbb{I}(X;Y)\ =\ \mathbb{H}(X)-\mathbb{H}(X|Y)\ =\
\mathbb{H}(Y)-\mathbb{H}(Y|X).$

  * •

(chain rule of mutual information) For all random variables
$X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y},Z:\Omega\mapsto\mathcal{Z}$,

$\mathbb{I}(Y;Z|X)+\mathbb{I}(X;Z)=\mathbb{I}(X,Y;Z).$

  * •

The _differential entropy_ of a continuous random variable
$X:\Omega\mapsto\mathcal{X}$ with density $p_{X}$ (w.r.t the Lebesgue measure
$\mu(\cdot)$) is

$\mathbf{h}(X)\ =\
\int_{x\in\mathcal{X}}p_{X}(x)\ln\frac{1}{p_{X}(x)}d\mu(x).$

  * •

Differential entropy can be negative and is unit-dependent.

  * •

For continuous random variables
$X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y}$,

$\mathbb{I}(X;Y)\ =\ \mathbf{h}(X)-\mathbf{h}(X|Y)\ =\
\mathbf{h}(Y)-\mathbf{h}(Y|X).$

##  5 Connecting Learning and Information Theory

In this section, we will leverage the requisite information-theoretic results
of section 4 to derive general upper and lower bounds for the estimation error
of the Bayesian posterior $(\mathcal{L}_{T})$. The results of this section
will facilitate the analysis of concrete problem instances in the following
sections.

###  5.1 Error is Information

We now establish the elegant connection between $\mathcal{L}_{T}$ and mutual
information.

######  Theorem 13.

(optimal error equals total information) For all $T\in\mathbb{Z}_{+}$,

$\mathcal{L}_{T}=\frac{\mathbb{I}(H_{T};\theta)}{T}.$

###### Proof.

$\displaystyle\mathcal{L}_{T}$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[-\ln\hat{P}_{t}(Y_{t+1})\right]-\frac{\mathbb{H}(Y_{1:T}|\theta,X_{0:T-1})}{T}$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\ln\frac{\mathbb{P}(Y_{t+1}|\theta,H_{t})}{\hat{P}_{t}(Y_{t+1})}\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(Y_{t+1}\in\cdot|\theta,H_{t})\ \|\
\mathbb{P}(Y_{t+1}\in\cdot|H_{t})\right)\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|H_{t})$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|H_{t})+\mathbb{I}(X_{t};\theta|H_{t-1},Y_{t})$
$\displaystyle=\frac{\mathbb{I}(H_{T};\theta)}{T}.$

∎

The estimation error incurred by an optimal algorithm over horizon $T$ is
_exactly_ equal to the total information acquired about $\theta$ from the
observing the data $H_{T}$. Every nat of _information_ about $\theta$ can only
be acquired via incurring _error_ on a prediction which relied on that
information. Evidently, an optimal algorithm never makes the same mistake
twice, hence resulting in the equality between total loss incurred and total
information acquired. Results of a similar flavor appear in the global Fano’s
method from the frequentist analysis of minimax lower bounds. However, the
following connections to rate-distortion theory are novel.

A natural question which may arise when inspecting Theorem 13 is: “Does
$\mathcal{L}_{T}$ decay to $0$ in $T$ and if so, at what rate?”. Ostensibly,
the numerator $\mathbb{I}(\theta;H_{T})$ appears to be _growing_ in $T$, so it
is not immediately obvious that even an optimal learner will experience
vanishing error. A simple instance to initially consider is $\theta$ which is
a discrete random variable. In such an instance, we can always provide the
upper bound:

$\mathcal{L}_{T}\leq\frac{\mathbb{H}(\theta)}{T}.$

Therefore, for any $\theta$ for which $\mathbb{H}(\theta)<\infty$, we have
that $\mathcal{L}_{T}=O(1/T)$.

However, what about a more realistic scenario in which $\theta$ is a
_continuous_ random variable? A naive idea would be to simply supplant the
discrete entropy $\mathbb{H}(\theta)$ with the _differential entropy_
$\mathbf{h}(\theta)$. However, while differences in conditional differential
entropy equal mutual information (just as with discrete entropy), differential
entropy does _not_ upper bound mutual information. This is because
differential entropy can be _negative_ (as discussed in section 4.4). The
appropriate extension of discrete entropy to continuous random variables can
be establish via _rate-distortion theory_.

###  5.2 Characterizing Error via Rate-Distortion Theory

We begin with the definition of the rate-distortion function.

######  Definition 14.

(rate-distortion function) Let $\epsilon\geq 0,\theta:\Omega\mapsto\Theta$ be
a random variable, and $\rho$ a distortion function which maps $\theta$ and
another random variable $\tilde{\theta}$ to $\Re_{+}$. The rate-distortion
function evaluated for random variable $\theta$ at tolerance $\epsilon$ is
defined as:

$\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon}}\underbrace{\mathbb{I}(\theta;\tilde{\theta})}_{\rm
rate},$

where

$\tilde{\Theta}_{\epsilon}=\left\\{\tilde{\theta}:\underbrace{\mathbb{E}\left[\rho(\theta,\tilde{\theta})\right]}_{\rm
distortion}\leq\epsilon\right\\}.$

Intuitively, one can think of $\tilde{\theta}$ as the result of passing
$\theta$ through a noisy channel, resulting in a lossy compression. The
objective $\mathbb{I}(\theta;\tilde{\theta})$, referred to as the _rate_ ,
characterizes the number of nats that $\tilde{\theta}$ retains about $\theta$.
meanwhile, the distortion function $\rho$ characterizes how lossy the
compression is. The rate-distortion function returns the minimum number of
nats necessary to achieve distortion at most $\epsilon$. In many ways this
generalizes the concept of an $\epsilon$-cover in frequentist statistics. For
the application of rate-distortion theory to the analysis of estimation error
in machine learning, we consider the following distortion function:

$\displaystyle\mathbb{E}\left[\rho_{t}(\theta,\tilde{\theta})\right]$
$\displaystyle=\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(Y_{t+1}\in\cdot|\theta,H_{t})\ \|\
\mathbb{P}(Y_{t+1}\in\cdot|\tilde{\theta},H_{t})\right)\right]$
$\displaystyle=\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},H_{t}),$

where the second equality follows from the fact that $\tilde{\theta}\perp
Y_{t+1}|(\theta,H_{t})$. This restriction ensure that $\tilde{\theta}$ does
not contain exogenous information about $Y_{t+1}$ such as aleatoric noise
which cannot be determined from $(\theta,H_{t})$. We use the notation
$\mathbb{H}_{\epsilon,T}(\theta)$ to denote the following rate-distortion
function:

$\mathbb{H}_{\epsilon,T}(\theta)=\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}}\
\mathbb{I}(\theta,\tilde{\theta}),$

where

$\tilde{\Theta}_{\epsilon,T}=\left\\{\tilde{\theta}:\tilde{\theta}\perp
H_{T}|\theta;\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}\leq\epsilon\right\\}.$

The following result upper and lower bounds the optimal estimation error in
terms of the rate-distortion function:

######  Theorem 15.

(rate-distortion estimation error bounds) For all $T\in\mathbb{Z}_{+}$,

$\sup_{\epsilon\geq 0}\
\min\left\\{\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T},\epsilon\right\\}\ \leq\
\mathcal{L}_{T}\ \leq\ \inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T}+\epsilon.$

###### Proof.

We begin with a proof of the upper bound.

$\displaystyle\mathcal{L}_{T}$
$\displaystyle=\frac{\mathbb{I}(H_{T};\theta)}{T}$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|H_{t})$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta,\tilde{\theta}|H_{t})$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\tilde{\theta}|H_{t})+\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle=\frac{\mathbb{I}(H_{T};\tilde{\theta})}{T}+\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle\overset{(a)}{\leq}\inf_{\epsilon\geq
0}\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}}\
\frac{\mathbb{I}(\theta;\tilde{\theta})}{T}+\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle=\inf_{\epsilon\geq
0}\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}}\
\frac{\mathbb{I}(\theta;\tilde{\theta})}{T}+\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}$
$\displaystyle\leq\inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T}+\epsilon$

where $(a)$ follows from the data processing inequality applied to the markov
chain $\tilde{\theta}\perp H_{T}|\theta$.

We now proceed with the lower bound. Suppose that
$\mathbb{I}(H_{T};\theta)<\mathbb{H}_{\epsilon,T}(\theta)$. Let
$\tilde{\theta}=\tilde{H}_{T}\notin\tilde{\Theta}_{\epsilon,T}$ where
$\tilde{H}_{T}$ is another history sampled in the same manner as $H_{T}$.

$\displaystyle\mathbb{I}(H_{T};\theta)$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|H_{t})$
$\displaystyle\overset{(a)}{\geq}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|\tilde{H}_{t},H_{t})$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle\overset{(b)}{\geq}\epsilon T,$

where $(a)$ follows from the fact that conditioning reduces entropy and that
$Y_{t+1}\perp\tilde{H}_{t}|(\theta,H_{t})$ and $(b)$ follows from the fact
that $\tilde{\theta}\notin\tilde{\Theta}_{\epsilon,T}$. Therefore, for all
$\epsilon\geq 0$, $\mathbb{I}(H_{T};\theta)\geq\min\\{H_{\epsilon,T},\epsilon
T\\}$. The result follows. ∎

Theorem 15 establishes the tight relation between estimation error and the
rate-distortion function. The result is very general and facilitates the
analysis of concrete problem instances in supervised learning. In the
following section, we will study 3 concrete instances of increasing complexity
to demonstrate how Theorem 15 facilitates analysis.

We also note the qualitative similarity between Theorem 15 and classical
results from PAC learning which all characterize estimation error as a
fraction involving a complexity function of the hypothesis space and the
dataset size (VC-dimension, Rademacher complexity, log-covering number). In
our framework, the rate-distortion function serves as the “complexity”
function which characterizes the difficulty of learning $\theta$ for the
purposes of prediction. In the following section, we will use this general
result to derive concrete error bounds for a suite of problems involving data
pairs which are iid when conditioned on $\theta$.

### Summary

  * •

(optimal estimation error equals total information) For horizon
$T\in\mathbb{Z}_{+}$, the estimation error of the optimal algorithm is denoted
as $\mathcal{L}_{T}$ and is

$\mathcal{L}_{T}=\frac{\mathbb{I}(\theta;H_{T})}{T}.$

  * •

For all $T\in\mathbb{Z}_{+}$,

$\mathcal{L}_{T}\leq\frac{\mathbb{H}(\theta)}{T}.$

Therefore, for a discrete random variable $\theta$ with finite entropy,
$\mathcal{L}_{T}=O(1/T)$.

  * •

The extension of this result to continuous random variables can be made via
rate-distortion theory.

  * •

(rate-distortion function) Let $\epsilon\geq 0,\theta:\Omega\mapsto\Theta$ be
a random variable, and $\rho$ a distortion function which maps $\theta$ and
another random variable $\tilde{\theta}$ to $\Re_{+}$. The rate-distortion
function evaluated for random variable $\theta$ at tolerance $\epsilon$ is
defined as:

$\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon}}\mathbb{I}(\theta;\tilde{\theta}),$

where

$\tilde{\Theta}_{\epsilon}=\left\\{\tilde{\theta}:\mathbb{E}\left[\rho(\theta,\tilde{\theta})\right]\leq\epsilon\right\\}.$

  * •

We use the notation $\mathbb{H}_{\epsilon,T}(\theta)$ to denote the following
rate-distortion function:

$\mathbb{H}_{\epsilon,T}(\theta)=\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}}\
\mathbb{I}(\theta,\tilde{\theta}),$

where

$\tilde{\Theta}_{\epsilon,T}=\left\\{\tilde{\theta}:\tilde{\theta}\perp
H_{T}|\theta;\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}\leq\epsilon\right\\}.$

  * •

(rate-distortion estimation error bounds) For all $T\in\mathbb{Z}_{+}$,

$\sup_{\epsilon\geq 0}\
\min\left\\{\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T},\epsilon\right\\}\ \leq\
\mathcal{L}_{T}\ \leq\ \inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T}+\epsilon.$

##  6 Learning from iid Data

In this section, we restrict our attention to the analysis of learning under
independently and identically distributed (iid) data. Concretely, we assume
that the random process representing the inputs: $(X_{0},X_{1},\ldots)$ is
iid. Each input $X_{t}$ is associated with a label $Y_{t+1}$ and we assume
infinite exchangeability of the sequence
$((X_{0},Y_{1}),(X_{1},Y_{1}),\ldots)$. By de Finetti’s theorem, there exists
a latent random variable, which we denote by $\theta$, for which conditioned
on $\theta$, the above sequence is iid. We further make the standard
assumption that the sequence of inputs $(X_{0},X_{1},\ldots)$ is independent
of $\theta$. As a result, $\theta$ is a random variable which represents for
all $t$ the conditional probability measure $\theta(\cdot|X_{t})$ of
$Y_{t+1}$. The process of learning involves the reduction of uncertainty about
$\theta$ in ways which are relevant for future predictions.

In the following section, we provide several results which follow as a
consequence of the above iid assumption. We dedicate the remaining sections to
studying 4 concrete problem instances of increasing complexity: $1)$ linear
regression, $2)$ logistic regression, $3)$ deep neural networks, $4)$ non-
parametric learning. We hope that this suite of examples provide the reader
with enough intuition and tools to analyze their own problems of interest.

###  6.1 Theoretical Results Tailored for iid Data

We begin with several intuitive theoretical results which follow as a result
of the iid assumptions on the data. The first result establishes monotonicity
of estimation error:

######  Lemma 16.

(monotonicity of per-timestep estimation error) If
$((X_{t},Y_{t+1}:t\in\mathbb{Z}_{+})$ is an iid stochastic process when
conditioned on $\theta$, then for all $t\in\mathbb{Z}_{+}$,

$\mathbb{I}(Y_{t+2};\theta|H_{t+1})\ \leq\ \mathbb{I}(Y_{t+1};\theta|H_{t}).$

###### Proof.

We have

$\displaystyle\mathbb{I}(\theta;Y_{t+2}|H_{t+1})$
$\displaystyle=\mathbf{h}(Y_{t+2}|H_{t+1})-\mathbf{h}(Y_{t+2}|\theta,H_{t+1})$
$\displaystyle\overset{(a)}{=}\mathbf{h}(Y_{t+2}|H_{t+1})-\mathbf{h}(Y_{t+2}|\theta,H_{t-1},Y_{t},X_{t+1})$
$\displaystyle\overset{(b)}{\leq}\mathbf{h}(Y_{t+2}|H_{t-1},Y_{t},X_{t+1})-\mathbf{h}(Y_{t+2}|\theta,H_{t-1},Y_{t},X_{t+1})$
$\displaystyle=\mathbb{I}(Y_{t+2};\theta|H_{t-1},Y_{t},X_{t+1})$
$\displaystyle\overset{(c)}{=}\mathbb{I}(Y_{t+1};\theta|H_{t-1},Y_{t},X_{t})$
$\displaystyle=\mathbb{I}(Y_{t+1};\theta|H_{t}),$

where $(a)$ follows since $Y_{t+2}\perp(X_{t},Y_{t+1})|(\theta,X_{t+1})$,
$(b)$ follows from the fact that conditioning reduces differential entropy,
and $(c)$ follows from the fact that $(X_{t},Y_{t+1})$ and $(X_{t+1},Y_{t+2})$
are identically distributed conditioned on $(H_{t-1},Y_{t})$. ∎

The above result establishes that when the data generating process is iid
conditioned on $\theta$, the optimal per-timestep estimation error is
monotonically non-increasing. This is intuitive, if the data is iid, the
future sequence is exchangeable and hence, conditioning on additional
information ($H_{t+1}$ as opposed to $H_{t}$) should only _improve_ our
ability to make predictions. A corollary of this result is that for iid data,
we can upper bound _distortion_ via an expression which is much simpler to
analyze.

######  Corollary 17.

(distortion upper bound) If $((X_{t},Y_{t+1}:t\in\mathbb{Z}_{+})$ is an iid
stochastic process when conditioned on $\theta$ and for all
$t\in\mathbb{Z}_{+}$, $Y_{t+1}\perp\tilde{\theta}|(\theta,X_{t})$, then for
all $T\in\mathbb{Z}_{++}$,

$\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}\ \leq\
\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0}).$

###### Proof.

$\displaystyle\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t},Y_{t+1};\theta|\tilde{\theta},H_{t-1},Y_{t})$
$\displaystyle\overset{(a)}{=}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle\overset{(b)}{\leq}\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0})$

where $(a)$ follows from the assumption that $X_{t}\perp\theta$ and $(b)$
follows from the same proof technique as in Lemma 16. ∎

In general, the expression $\mathbb{I}(H_{T};\theta|\tilde{\theta})$ is much
more cumbersome to deal with in comparison to
$\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0})$. Corollary 17 established a
suitable relationship between the two quantities. However, to facilitate the
analysis of rate-distortion lower bounds, it is fruitful to consider analysis
via a modified rate-distortion function tailored for iid data generating
processes. For all $\epsilon\geq 0$, we let

$\mathbb{H}_{\epsilon}(\theta)=\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon}}\mathbb{I}(\theta;\tilde{\theta}),$

where

$\tilde{\Theta}_{\epsilon}=\\{\tilde{\theta}:\tilde{\theta}\perp
H_{\infty}|\theta,\
\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0})\leq\epsilon\\}.$

Note that in contrast to the general rate-distortion formulation of section 5,
this modified rate-distortion does not depend on the time horizon $T$. We now
provide an estimation error lower bound in terms of
$\mathbb{H}_{\epsilon}(\theta)$ which applies for learning from iid data.

######  Lemma 18.

(estimation error lower bound for iid data) If
$((X_{t},Y_{t+1}:t\in\mathbb{Z}_{+})$ is an iid stochastic process when
conditioned on $\theta$, then for all $T\in\mathbb{Z}_{++},$

$\sup_{\epsilon\geq 0}\
\min\left\\{\frac{\mathbb{H}_{\epsilon}(\theta)}{T},\epsilon\right\\}\ \leq\
\mathcal{L}_{T}.$

###### Proof.

Fix $T\in\mathbb{Z}_{+}$. Let
$\tilde{\theta}=(\tilde{H}_{T-2},\tilde{Y}_{T-1})$ be independent from but
distributed identically with $(H_{T-2},Y_{T-1})$ when conditioned on $\theta$.

Fix $\epsilon\geq 0$. If $\mathcal{L}_{T}<\mathbb{H}_{\epsilon}(\theta)/T$
then

$\mathcal{L}_{T}<\mathbb{H}_{\epsilon}(\theta)/T\ \implies\
\mathbb{I}(H_{T};\theta)<\mathbb{H}_{\epsilon}(\theta)\ \implies\
\mathbb{I}(\tilde{\theta};\theta)<\mathbb{H}_{\epsilon}(\theta).$

Since the rate of $\tilde{\theta}$ is _lower_ than the rate-distortion
function $\mathbb{H}_{\epsilon}(\theta)$,
$\tilde{\theta}\notin\tilde{\Theta}_{\epsilon}$. As a result,

$\displaystyle\mathcal{L}_{T}$
$\displaystyle\overset{(a)}{=}\frac{\mathbb{I}(H_{T};\theta)}{T}$
$\displaystyle\overset{(b)}{=}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(Y_{t+1};\theta|H_{t})$
$\displaystyle\overset{(c)}{\geq}\mathbb{I}(Y_{T};\theta|H_{T-1})$
$\displaystyle=\mathbb{I}(Y_{T};\theta|\tilde{\theta},X_{T-1})$
$\displaystyle\overset{(d)}{>}\epsilon,$

where (a) follows from Lemma 13, (b) follows from the chain rule of mutual
information, (c) follows from Lemma 16, and (d) follows from the fact that
$\tilde{\theta}\notin\tilde{\Theta}_{\epsilon}$. Therefore,

$\mathcal{L}_{T}\geq\min\\{\mathbb{H}_{\epsilon}(\theta)/T,\ \epsilon\\}.$

Since this holds for any $\epsilon\geq 0$, the result follows. ∎

In the following $4$ sections we will apply our general results to concrete
problem instances. We begin with linear regression.

###  6.2 Linear Regression

Figure 3: We depict our linear regression data generating process above. It
consists of an input vector $X$ of dimension $d$, an unknown weight vector
$\theta$ of dimension $d$, and a final output $Y$ which is the sum of
$\theta^{\top}X$ and independent Gaussian noise $Z$.

####  6.2.1 Data Generating Process

In linear regression, the variable that we are interested in estimating is a
random vector $\theta\in\Re^{d}$. As our analytical tools are developed in a
Bayesian framework, we assume a known prior distribution
$\mathbb{P}(\theta\in\cdot)$ to model our uncertainty over the value of
$\theta$. For simplicity and concreteness, in this example, we assume that
$\mathbb{P}(\theta\in\cdot)=\mathcal{N}(0,I_{d}/d)$. For all
$t\in\mathbb{Z}_{+}$, inputs and outputs are generated according to a random
vector $X_{t}\overset{iid}{\sim}\mathcal{N}(0,I_{d})$ and

$Y_{t+1}=\theta^{\top}X_{t}+W_{t+1},$

where $W_{t}\overset{iid}{\sim}\mathcal{N}(0,\sigma^{2})$ for known variance
$\sigma^{2}$. We note that the results and techniques developed in this
section certainly extend to input and prior distributions which are not
Gaussian with slight modifications. We study the Gaussian case as it minimizes
ancillary clutter without compromising generality. In the following section,
we will establish a series of smaller results which will allow us to
streamline our error analysis using the tools established in section 5.

####  6.2.2 Theoretical Building Blocks

In this section we will establish $3$ relatively simple results which will
enable us to directly apply Theorem 15 and arrive at estimation error bounds
for linear regression. As such, the results will all involve characterizing
the rate-distortion function for this data generating process. We begin our
analysis with a result which establishes the threshold $\epsilon$ at which the
rate-distortion function is trivially $0$.

######  Lemma 19.

(linear regression 0 rate-distortion threshold) For all
$d\in\mathbb{Z}_{++},\sigma^{2}\in\Re_{++}$, if for all $t\in\mathbb{Z}_{+}$,
$(X_{t},Y_{t+1})$ are generated according to the linear regression process and
$\epsilon\geq\frac{1}{2}\ln(1+1/\sigma^{2})$, then for all
$T\in\mathbb{Z}_{++}$,

$\mathbb{H}_{\epsilon,T}(\theta)=0.$

###### Proof.

Let $\tilde{\theta}=\emptyset$. Then,

$\displaystyle\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}$
$\displaystyle\overset{(a)}{\leq}\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0})$
$\displaystyle=\mathbf{h}(Y_{1}|\tilde{\theta},X_{0})-\mathbf{h}(Y_{1}|\theta,\tilde{\theta},X_{0})$
$\displaystyle=\mathbf{h}(Y_{1}|X_{0})-\mathbf{h}(W)$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[\frac{1}{2}\ln\left(2\pi
e\left(\sigma^{2}+\text{Var}[\theta^{\top}X|X]\right)\right)\right]-\frac{1}{2}\ln\left(2\pi
e\sigma^{2}\right)$
$\displaystyle\overset{(c)}{=}\mathbb{E}\left[\frac{1}{2}\ln\left(2\pi
e\left(\sigma^{2}+\frac{\|X\|^{2}_{2}}{d}\right)\right)\right]-\frac{1}{2}\ln\left(2\pi
e\sigma^{2}\right)$ $\displaystyle\overset{(d)}{\leq}\frac{1}{2}\ln\left(2\pi
e\left(\sigma^{2}+\frac{\mathbb{E}\left[\|X\|^{2}_{2}\right]}{d}\right)\right)-\frac{1}{2}\ln\left(2\pi
e\sigma^{2}\right)$
$\displaystyle=\frac{1}{2}\ln\left(1+\frac{1}{\sigma^{2}}\right)$
$\displaystyle\leq\epsilon,$

where $(a)$ follows from Corollary 17, $(b)$ follows from Lemma 11, $(c)$
follows from the fact that $\theta$ has covariance matrix $I_{d}/d$, and $(d)$
follows from Jensen’s inequality. The above establishes that
$\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}$ for all $T$. The result follows
from the fact that $\mathbb{I}(\theta;\tilde{\theta})=0$. ∎

Intuitively, there should be a threshold of $\epsilon$ for which values
greater than $\epsilon$ result in a rate-distortion value of $0$. Evidently, a
$0$-bit quantization that solely relies on the prior distribution will result
in a suitable distortion value when the threshold $\epsilon$ is large enough.
This result characterizes the edge-case condition for the rate-distortion
function. The following result will provide an upper bound on the rate-
distortion function for the more interesting scenario in which the threshold
$\epsilon<1/2\ln(1+1/\sigma^{2})$.

######  Lemma 20.

(linear regression rate-distortion upper bound) For all $d\in\mathbb{Z}_{++}$,
$\sigma^{2}\in\Re_{++}$, and $\epsilon\in\Re_{++}$, if for all
$t\in\mathbb{Z}_{+}$, $(X_{t},Y_{t+1})$ are generated according to the linear
regression process, then for all $T$,

$\mathbb{H}_{\epsilon,T}(\theta)\leq\left(\frac{d}{2}\ln\left(\frac{1}{\sigma^{2}(e^{2\epsilon}-1)}\right)\right)_{+}.$

###### Proof.

Fix $\sigma^{2}\in\Re_{++}$. Let $\tilde{\theta}=\theta+V$, where
$V\sim\mathcal{N}(0,(\delta^{2}/d)I_{d})$ for
$\delta^{2}=\frac{\sigma^{2}(e^{2\epsilon}-1)}{1-\sigma^{2}(e^{2\epsilon}-1)}$
and $V\perp\theta$. Note that $\delta^{2}\geq 0$ for all
$0<\epsilon<\frac{1}{2}\ln\left(1+\frac{1}{\sigma^{2}}\right)$. We begin by
showing that $\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}$ for all $T$.

$\displaystyle\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}$
$\displaystyle\leq\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0})$
$\displaystyle=\mathbf{h}(Y_{1}|\tilde{\theta},X_{0})-\mathbf{h}(Y_{1}|\theta,\tilde{\theta},X_{0})$
$\displaystyle=\mathbf{h}(W_{1}+\theta^{\top}X|\tilde{\theta},X_{0})-\mathbf{h}(W_{1})$
$\displaystyle=\mathbf{h}\left(W_{1}+\theta^{\top}X_{0}-\frac{\tilde{\theta}^{\top}X_{0}}{1+\delta^{2}}\bigg{|}\tilde{\theta},X_{0}\right)-\mathbf{h}(W_{1})$
$\displaystyle=\mathbf{h}\left(W_{1}+\left(\frac{\delta^{2}}{1+\delta^{2}}\theta+\frac{1}{1+\delta^{2}}V\right)^{\top}X_{0}\Big{|}\tilde{\theta},X_{0}\right)-\mathbf{h}(W_{1})$
$\displaystyle\leq\mathbf{h}\left(W_{1}+\left(\frac{\delta^{2}}{1+\delta^{2}}\theta+\frac{1}{1+\delta^{2}}V\right)^{\top}X_{0}\Big{|}X_{0}\right)-\mathbf{h}(W_{1})$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\frac{1}{2}\ln\left(2\pi
e\left(\sigma^{2}+\left(\frac{\delta^{4}}{d(1+\delta^{2})^{2}}+\frac{\delta^{2}}{d(1+\delta^{2})^{2}}\right)\|X_{0}\|^{2}_{2}\right)\right)\right]-\frac{1}{2}\ln\left(2\pi
e\sigma^{2}\right)$
$\displaystyle=\mathbb{E}\left[\frac{1}{2}\ln\left(1+\frac{\delta^{2}\|X_{0}\|^{2}_{2}}{d(1+\delta^{2})\sigma^{2}}\right)\right]$
$\displaystyle\overset{(b)}{\leq}\frac{1}{2}\ln\left(1+\frac{\delta^{2}}{(1+\delta^{2})\sigma^{2}}\right)$
$\displaystyle=\frac{1}{2}\ln\left(e^{2\epsilon}\right)$
$\displaystyle=\epsilon,$

where $(a)$ follows from Lemma 11 and $(b)$ follows from Jensen’s inequality.
Next, we upper bound the rate of $\tilde{\theta}$:

$\displaystyle\mathbb{I}(\theta;\tilde{\theta})$
$\displaystyle=\mathbf{h}(\tilde{\theta})-\mathbf{h}(\tilde{\theta}|\theta)$
$\displaystyle=\mathbf{h}(\tilde{\theta})-\mathbf{h}(V)$
$\displaystyle\overset{(a)}{\leq}\frac{d}{2}\ln\left(2\pi
e\left(\frac{\delta^{2}+1}{d}\right)\right)-\frac{d}{2}\ln\left(2\pi
e\left(\frac{\delta^{2}}{d}\right)\right)$
$\displaystyle=\frac{d}{2}\ln\left(1+\frac{1}{\delta^{2}}\right)$
$\displaystyle=\frac{d}{2}\ln\left(\frac{1}{\sigma^{2}\left(e^{2\epsilon}-1\right)}\right),$

where $(a)$ follows from Lemma 11. The result follows from Lemma 19 and the
fact that $\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}$ for all
$T\in\mathbb{Z}_{++}$ and $\epsilon<1/2\ln(1+1/\sigma^{2})$. ∎

Note that above, we never explicitly relied on the assumption that
$\mathbb{P}(\theta\in\cdot)=\mathcal{N}(0,I_{d}/d)$. We simply needed the fact
that the elements of $\theta$ are independent with variances which sum to $1$
(for inequality $(a)$ above). To establish a _lower bound_ on the rate-
distortion function in the linear regression setting, we rely more on the
Gaussian prior assumption. Concrete details of the most general assumptions
required to arrive at such lower bounds can be found in Appendix A.

######  Lemma 21.

(linear regression rate-distortion lower bound) For all $d\in\mathbb{Z}_{++}$
s.t. $d>2$, $\sigma^{2}\in\Re_{++}$, and $\epsilon\in\Re_{++}$, if for all
$t\in\mathbb{Z}_{+}$, $(X_{t},Y_{t+1})$ are generated according to the linear
regression process, then

$\mathbb{H}_{\epsilon}(\theta)\ \geq\
\left(\frac{d}{2}\ln\left(\frac{1}{(8+\frac{d}{d-2}\sigma^{2})\epsilon}\right)\right)_{+}.$

###### Proof.

Fix $\sigma^{2}\in\Re_{++}$, $\epsilon\in\mathbb{Z}_{+}$
$T\in\mathbb{Z}_{++}$, and $\tilde{\theta}\in\tilde{\Theta}_{\epsilon,T}$.
Then,

$\displaystyle\epsilon$
$\displaystyle\overset{(a)}{\geq}\mathbb{I}(Y;\theta|\tilde{\theta},X)$
$\displaystyle\overset{(b)}{\geq}\mathbb{E}\left[\frac{\|X\|^{2}_{2}}{2(4\|X\|_{2}^{2}+d\sigma^{2})}\right]\mathbb{E}\left[\|\theta-\mathbb{E}[\theta|\tilde{\theta}]\|^{2}_{2}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{\frac{2(4\|X\|_{2}^{2}+d\sigma^{2})}{\|X\|_{2}^{2}}}\right]\mathbb{E}\left[\|\theta-\mathbb{E}[\theta|\tilde{\theta}]\|^{2}_{2}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{8+\frac{d\sigma^{2}}{\|X\|^{2}_{2}}}\right]\mathbb{E}\left[\|\theta-\mathbb{E}[\theta|\tilde{\theta}]\|^{2}_{2}\right]$
$\displaystyle\overset{(c)}{\geq}\frac{1}{\mathbb{E}\left[8+\frac{d\sigma^{2}}{\|X\|^{2}_{2}}\right]}\mathbb{E}\left[\|\theta-\mathbb{E}[\theta|\tilde{\theta}]\|^{2}_{2}\right]$
$\displaystyle\overset{(d)}{=}\frac{1}{8+\frac{d\sigma^{2}}{d-2}}\mathbb{E}\left[\|\theta-\mathbb{E}[\theta|\tilde{\theta}]\|^{2}_{2}\right]$
$\displaystyle\geq\frac{1}{8+\frac{d}{d-2}\sigma^{2}}\mathbb{E}\left[\|\theta-\mathbb{E}[\theta|\tilde{\theta}]\|^{2}_{2}\right]$

where $(a)$ follows from the fact that
$\tilde{\theta}\in\tilde{\Theta}_{\epsilon}$, $(b)$ follows from Lemma 63,
$(c)$ follows from Jensen’s inequality, and $(d)$ follows from the fact that
$\mathbb{E}[1/\chi^{2}(d)]=1/(d-2)$.

Since the above condition is an implication that holds for arbitrary
$\tilde{\theta}\in\tilde{\Theta}_{\epsilon}$, minimizing the rate
$\mathbb{I}(\theta;\tilde{\theta})$ over the set of proxies that satisfy
$\mathbb{E}[\|\theta-\mathbb{E}[\theta|\tilde{\theta}]\|^{2}_{2}]\leq(8+\frac{d}{d-2}\sigma^{2})\epsilon$
will provide a lower bound. However, this is simply the rate-distortion
problem for a multivariate source under squared error distortion. For this
problem there exists a well known lower bound (Theorem 10.3.3 of [Cover and
Thomas, 2006]). The lower bound follows as a result.
∎

####  6.2.3 Main Result

The rate-distortion bounds which we established in the previous section allow
us to directly apply Theorem 15 to arrive at a bound for estimation error.

######  Theorem 22.

(linear regression estimation error bounds) For all $d\in\mathbb{Z}_{++}$,
$\sigma^{2}\geq 0$, if for all $t$, $(X_{t},Y_{t+1})$ are generated according
to the linear regression processes, then for all $T$,

$\frac{d}{2T}W\left(\frac{2T}{d(8+\frac{d}{d-2}\sigma^{2})}\right)\ \leq\
\mathcal{L}_{T}\ \leq\
\left(\frac{d}{2T}\ln\left(\frac{T}{\sigma^{2}d}\right)\right)_{+}+\frac{1}{2T}\ln\left(1+\frac{d}{T}\right),$

where $W$ is the Lambert W function.

###### Proof.

$\displaystyle\mathcal{L}_{T}$
$\displaystyle\overset{(a)}{\leq}\inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T}+\epsilon$
$\displaystyle\overset{(b)}{\leq}\inf_{\epsilon\geq 0}\
\frac{\left(d\ln\left(\frac{1}{\sigma^{2}(e^{2\epsilon}-1)}\right)\right)_{+}}{2T}+\epsilon$
$\displaystyle\overset{(c)}{\leq}\frac{\left(d\ln\left(\frac{1}{\sigma^{2}\left(\left(1+\frac{d}{T}\right)^{T}-1\right)}\right)\right)_{+}}{2T}+\frac{1}{2T}\ln\left(1+\frac{d}{T}\right)$
$\displaystyle\leq\left(\frac{d}{2T}\ln\left(\frac{T}{\sigma^{2}d}\right)\right)_{+}+\frac{1}{2T}\ln\left(1+\frac{d}{T}\right),$

where $(a)$ follows from Theorem 15, $(b)$ follows from Lemma 20, and $(c)$
follows from setting $\epsilon=\frac{1}{2T}\ln\left(1+\frac{d}{T}\right)$.

$\displaystyle\mathcal{L}_{T}$ $\displaystyle\geq\sup_{\epsilon\geq 0}\
\min\left\\{\frac{\mathbb{H}_{\epsilon}(\theta)}{T},\epsilon\right\\}$
$\displaystyle\geq\sup_{\epsilon\geq 0}\
\min\left\\{\left(\frac{d}{2T}\ln\left(\frac{1}{(8+\frac{d}{d-2}\sigma^{2})\epsilon}\right)\right)_{+},\
\epsilon\right\\}$ $\displaystyle=\epsilon\text{ s.t.
}\left(\frac{d}{2T}\ln\left(\frac{1}{(8+\frac{d}{d-2}\sigma^{2})\epsilon}\right)\right)_{+}=\epsilon$
$\displaystyle\overset{(a)}{=}\frac{e^{-W\left(\frac{8+\frac{d}{d-2}\sigma^{2}}{2}\right)}}{\frac{2T}{d(8+\frac{d}{d-2}\sigma^{2})}}$
$\displaystyle\overset{(b)}{\geq}\frac{e^{-\ln\left(8+\frac{d}{d-2}\sigma^{2}\right)}}{\frac{2T}{d(8+\frac{d}{d-2}\sigma^{2})}}$
$\displaystyle=\frac{d}{2T},$

where in $(a)$, $W$ denotes the Lambert $W$ function and $(b)$ follows from
the fact that for all $x\geq e$, $W(x)\leq\ln(2x)$. ∎

Notably, this bound is consistent with classical results in statistics which
dictate that the estimation error grows linearly in the problem dimension $d$
and decays linearly in the number of samples observed $T$. In the following
section, we will observe that qualitatively similar results also hold for
logistic regression.

###  6.3 Logistic Regression

Figure 4: We depict our logistic regression data generating process above. It
consists of an input vector $X$ of dimension $d$, an unknown weight vector
$\theta$ of dimension $d$, and a final binary output $Y\in\\{0,1\\}$. $Y$ is
_sampled_ according to probabilities generated by the sigmoid function applied
to $\theta^{\top}X$.

####  6.3.1 Data Generating Process

We next study logistic regression to demonstrate the application of our tools
to _classification_. Just as in linear regression, in logistic regression, the
variable that we are interested in estimating is a random vector
$\theta\in\Re^{d}$. Again for simplicity and concreteness, we assume that
$\mathbb{P}(\theta\in\cdot)=\mathcal{N}(0,I_{d}/d)$. For all
$t\in\mathbb{Z}_{+}$, inputs and outputs are generated according to a random
vector $X_{t}\overset{iid}{\sim}\mathcal{N}(0,I_{d})$ and

$Y_{t+1}=\begin{cases}1&\text{ w.p. }\frac{1}{1+e^{-\theta^{\top}X_{t}}}\\\
0&\text{ otherwise}\end{cases}.$

####  6.3.2 Theoretical Building Blocks

We begin with the following result which upper bounds the binary KL-divergence
of a sigmoidal output via the squared difference between the logits.

######  Lemma 23.

(squared error upper bounds binary KL-divergence) For all $x,y\in\Re$,

$\frac{1}{1+e^{-x}}\ln\frac{1+e^{-y}}{1+e^{-x}}+\frac{1}{1+e^{x}}\ln\frac{1+e^{y}}{1+e^{x}}\leq\frac{(x-y)^{2}}{8}$

###### Proof.

∎

This upper bound facilitates the following upper bound on the rate-distortion
function.

######  Lemma 24.

(logistic regression rate-distortion upper bound) For all
$d\in\mathbb{Z}_{++}$ and $\epsilon\in\Re_{++}$, if for all
$t\in\mathbb{Z}_{+},(X_{t},Y_{t+1})$ are generated according to the logistic
regression process, then for all $T$,

$\mathbb{H}_{\epsilon,T}\ \leq\
\frac{d}{2}\ln\left(1+\frac{1}{8\epsilon}\right).$

###### Proof.

Let $\tilde{\theta}=\theta+Z$ where $Z\perp\theta$ and
$Z\sim\mathcal{N}(0,8\epsilon/d)$. Then,

$\displaystyle\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}$
$\displaystyle\leq\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0})$
$\displaystyle=\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(Y_{1}\in\cdot|\theta,X_{0})\ \|\
\mathbb{P}(Y_{1}\in\cdot|\tilde{\theta},X_{0})\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(Y_{1}\in\cdot|\theta,X_{0})\ \|\
\mathbb{P}(Y_{1}\in\cdot|\theta\leftarrow\tilde{\theta},X_{0})\right)\right]$
$\displaystyle=\mathbb{E}\left[\frac{\ln\left(\frac{1+e^{-\tilde{\theta}^{\top}X_{0}}}{1+e^{-\theta^{\top}X_{0}}}\right)}{1+e^{-\theta^{\top}X_{0}}}+\frac{\ln\left(\frac{1+e^{\tilde{\theta}^{\top}X_{0}}}{1+e^{\theta^{\top}X_{0}}}\right)}{1+e^{\theta^{\top}X_{0}}}\right]$
$\displaystyle\overset{(b)}{\leq}\frac{\mathbb{E}\left[\left(\theta^{\top}X_{0}-\tilde{\theta}^{\top}X_{0}\right)^{2}\right]}{8}$
$\displaystyle=\frac{\mathbb{E}\left[\|\theta-\tilde{\theta}\|^{2}_{2}\right]}{8}$
$\displaystyle=\epsilon,$

where $(a)$ follows from Lemma 57 and $(b)$ follows from Lemma 23.

We now upper bound the rate.

$\displaystyle\mathbb{I}(\theta;\tilde{\theta})$
$\displaystyle=\mathbf{h}(\tilde{\theta})-\mathbf{h}(\tilde{\theta}|\theta)$
$\displaystyle\overset{(a)}{\leq}\frac{d}{2}\ln\left(2\pi
e\left(\frac{1}{d}+\frac{8\epsilon}{d}\right)\right)-\frac{d}{2}\ln\left(2\pi
e\frac{8\epsilon}{d}\right)$
$\displaystyle=\frac{d}{2}\ln\left(1+\frac{1}{8\epsilon}\right),$

where $(a)$ follows from Lemma 11. The result follows. ∎

####  6.3.3 Main Result

With the rate-distortion upper bound in place, we establish the following
upper bound on estimation error.

######  Theorem 25.

(logistic regression estimation error upper bound) For all
$d\in\mathbb{Z}_{++}$, if for all $t$, $(X_{t},Y_{t+1})$ is generated
according to the logistic regression process, then for all $T,$

$\mathcal{L}_{T}\ \leq\
\frac{d}{2T}\left(1+\ln\left(1+\frac{T}{4d}\right)\right).$

###### Proof.

$\displaystyle\mathcal{L}_{T}$
$\displaystyle\overset{(a)}{\leq}\inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T}+\epsilon$
$\displaystyle\overset{(b)}{\leq}\inf_{\epsilon\geq 0}\
\frac{\frac{d}{2}\ln\left(1+\frac{d}{8\epsilon}\right)}{T}+\epsilon$
$\displaystyle\overset{(c)}{\leq}\frac{d}{2T}\ln\left(1+\frac{T}{4d}\right)+\frac{d}{2T},$

where $(a)$ follows from Theorem 15, $(b)$ follows from Lemma 24, and $(c)$
follows from setting $\epsilon=\frac{d}{2T}$. ∎

We observe that just as in linear regression, we observe an error bound which
is $\tilde{\mathcal{O}}(d/T)$. In the following section, we consider a much
more complex deep neural network data generating process.

###  6.4 Deep Neural Networks

Figure 5: We depict our deep neural network data generating process above. It
consists of input dimension $d$, width $N$, depth $L$, with output dimension
$1$, and ReLU activation units. We denote the weights at layer $\ell$ by
$A^{(\ell)}$ and the output of layer $\ell$ by $U^{(\ell)}$. We assume that
the final output $Y$ is the sum of the final network output $U^{(L)}$ and
independent Gaussian noise $Z$.

####  6.4.1 Data Generating Process

For a deep neural network, we are interested in estimating a collection of
random matrices $(A^{(1)},\ldots,A^{(L)})$ which represent the weights of the
network. We assume a known prior distribution $\mathbb{P}(A^{(1:L)}\in\cdot)$
to model our uncertainty over the network weights. For simplicity, we assume
that the width of every hidden layer is identically set to a positive integer
$N$ and that the network has input dimension $d$ and output dimension $1$. We
further assume the following prior distribution on the weights of the network.

$\mathbb{P}(A^{(\ell)})=\begin{cases}\mathcal{N}(0,\frac{I_{N\times
d}}{d})&\text{ if }\ell=1\\\ \mathcal{N}(0,\frac{I_{N\times N}}{N})&\text{ if
}2\leq\ell\leq L-1\\\ \mathcal{N}(0,\frac{I_{N}}{N})&\text{ if
}\ell=L\end{cases}.$

We further make the assumption that the weights _across_ layers are
independent. These Gaussian assumptions are again not necessary for the
following results (only the specified covariance structure is required), but
we provide the above instance for concreteness.

For all $t\in\mathbb{Z}_{+}$, inputs and outputs are generated according to a
random vector $X_{t}\overset{iid}{\sim}\mathcal{N}(0,I_{d})$ and

$\displaystyle U^{(0)}_{t}$ $\displaystyle=X_{t}$ $\displaystyle
U^{(\ell+1)}_{t}$
$\displaystyle=\text{ReLU}\left(A^{(\ell+1)}U^{(\ell)}_{t}\right)$
$\displaystyle Y_{t+1}$ $\displaystyle=U^{(L)}_{t}+W_{t+1},$

where $W_{t}\overset{iid}{\sim}\mathcal{N}(0,\sigma^{2})$ for known variance
$\sigma^{2}$.

####  6.4.2 Theoretical Building Blocks

In this section, we will cover several helpful lemmas which will allow us to
streamline the error analysis for neural networks. Lemma 29 establishes an
upper bound on the distortion function in the deep neural network setting.
This result allows us to easily derive upper bounds for the rate-distortion
function in Theorem 30. However, we begin with the following three Lemmas (26,
27, 28) which facilitate the derivation of distortion upper bound in Lemma 29.
We begin with an initial result which decomposes the total distortion
$\mathbb{I}(Y;A^{(1:L)}|\tilde{A}^{(1:L)},X)$ into a sum of simpler terms.

######  Lemma 26.

(distortion decomposition) If $(X,Y)$ are generated by the deep neural network
process and $\tilde{A}_{1},\ldots,\tilde{A}_{L}$ are independent random
variables such that, $Y\perp\tilde{A}^{(1:L)}|A^{(1:L)},X$, then

$\mathbb{I}(Y;A^{(1:L)}|\tilde{A}^{(1:L)},X)\ =\
\sum_{\ell=1}^{L}\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:\ell)},X).$

###### Proof.

$\displaystyle\mathbb{I}(Y;A^{(1:L)}|\tilde{A}^{(1:L)},X)$
$\displaystyle\overset{(a)}{=}\sum_{\ell=1}^{L}\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:L)},X)$
$\displaystyle\overset{(a)}{=}\sum_{\ell=1}^{L}\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:\ell)},X),$

where $(a)$ follows from the chain rule and $(b)$ follows from conditional
independence assumptions. ∎

With this decomposition in mind, we can derive a suitable upper bound for the
total distortion by deriving an upper bound for each _individual_ term of the
decomposition. The following two results establish such an upper bound for the
individual terms.

######  Lemma 27.

(more information with the true input) If $(X,Y)$ are generated by the deep
neural network process and $\tilde{A}_{1},\ldots,\tilde{A}_{L}$ are
independent random variables such that, $Y\perp\tilde{A}^{(1:L)}|A^{(1:L)},X$,
then for all $\ell\in\\{1,\ldots,L\\}$,

$\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:\ell)},X)\ \leq\
\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)},U^{(\ell-1)}).$

###### Proof.

$\displaystyle\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:\ell)},X)$
$\displaystyle=\mathbb{I}(Y,X,\tilde{A}^{(1:\ell-1)};A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)})-\mathbb{I}(X,\tilde{A}^{(1:\ell-1)};A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)})$
$\displaystyle=\mathbb{I}(Y,X,\tilde{A}^{(\ell-1:1)};A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)})$
$\displaystyle=\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)})+\mathbb{I}(X,\tilde{A}^{(1:\ell-1)};A^{(\ell)}|Y,A^{(\ell+1:L)},\tilde{A}^{(\ell)})$
$\displaystyle\overset{(a)}{\leq}\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)})+\mathbb{I}(X,A^{(1:\ell-1)};A^{(\ell)}|Y,A^{(\ell+1:L)},\tilde{A}^{(\ell)})$
$\displaystyle=\mathbb{I}(Y,X,A^{(1:\ell-1)};A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)})$
$\displaystyle\overset{(b)}{=}\mathbb{I}(Y;A^{(\ell)}|X,A^{(1:\ell-1)},A^{(\ell+1:L)},\tilde{A}^{(\ell)})$
$\displaystyle\overset{(c)}{=}\mathbb{I}(Y;A^{(\ell)}|U^{(\ell-1)},A^{(\ell+1:L)},\tilde{A}^{(\ell)}),$

where $(a)$ follows from the fact that
$A^{(\ell)}\perp\tilde{A}^{(1:\ell-1)}|(X,Y,A^{(1:\ell-1)})$ and the data
processing inequality, $(b)$ follows from the fact that
$\mathbb{I}(A^{(\ell)};A^{(1:\ell-1)},X|A^{(\ell+1:L)},\tilde{A}^{(\ell)})=0$,
and $(c)$ follows from the fact that $Y\perp(A^{(1:\ell-1)},X)|U^{(\ell-1)}$.
∎

This result states that more information is extracted about $A^{(\ell)}$ when
we condition on the true input to layer $\ell$ $(U^{(\ell-1)})$ as opposed to
the approximate input based on $(A^{(1:\ell-1)},X)$. This is a rather
intuitive result as having access to the _true_ input $U^{(\ell-1)}$ which
generated label $Y$ should allow us to extract more information about the
parameters $A^{(\ell)}$. This allows us to simplify our analysis since the RHS
of Lemma 27 only consists of one approximate term $\tilde{A}^{(\ell)}$ as
opposed to $\ell$ of them in the LHS. The following result leverages this
simplified form to derive an upper bound for each individual term in the
decomposition of Lemma 26.

######  Lemma 28.

For all $d,N,L\in\mathbb{Z}_{++},\sigma^{2}\in\Re_{++}$, if $(X,Y)$ are
generated according to the deep neural network process and
$\tilde{A}_{1},\ldots,\tilde{A}_{L}$ are independent random variables such
that for all $Y\perp\tilde{A}^{(1:L)}|(A^{(1:L)},X)$, then for all
$\ell\in[L]$,

$\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:\ell)},X)\ \leq\
\frac{1}{2}\ln\left(1+\frac{\mathbb{E}\left[\left\|(A^{(\ell)}-\tilde{A}^{(\ell)})U^{(\ell-1)}\right\|^{2}_{2}\right]}{\sigma^{2}N}\right).$

###### Proof.

In the proof below, we use the notation $f_{A^{(\ell:L)}}$ to denote the depth
$L+1-\ell$ MLP with ReLU activation units and weights parameterized by
$A^{(\ell:L)}$.

$\displaystyle\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:\ell)},X)$
$\displaystyle\overset{(a)}{\leq}\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(\ell)},U^{(\ell-1)})$
$\displaystyle=\mathbf{h}(Y|A^{(\ell+1:L)},\tilde{A}^{(\ell)},U^{(\ell-1)})-\mathbf{h}(Y|A^{(\ell+1:L)},U^{(\ell-1)})$
$\displaystyle=\mathbf{h}(Y|A^{(\ell+1:L)},\tilde{A}^{(\ell)},U^{(\ell-1)})-\frac{1}{2}\ln\left(2\pi
e\sigma^{2}\right)$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[\frac{1}{2}\ln\left(\frac{\mathbb{E}\left[\left(Y-f_{\tilde{A}^{(\ell)},A^{(\ell+1:L)}}\left(U^{(\ell-1)}\right)\right)^{2}\Big{|}A^{(\ell+1:L)},\tilde{A}^{(\ell)},U^{(\ell-1)}\right]}{\sigma^{2}}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{2}\ln\left(1+\frac{\left(f_{A^{(\ell:L)}}\left(U^{(\ell-1)}\right)-f_{\tilde{A}^{(\ell)},A^{(\ell+1:L)}}\left(U^{(\ell-1)}\right)\right)^{2}}{\sigma^{2}}\right)\right]$
$\displaystyle\overset{(c)}{\leq}\mathbb{E}\left[\frac{1}{2}\ln\left(1+\frac{\left(A^{(L)}A^{(L-1)}\ldots
A^{(\ell+1)}(A^{(\ell)}-\tilde{A}^{(\ell)})U^{(\ell-1)}\right)^{2}}{\sigma^{2}}\right)\right]$
$\displaystyle\overset{(d)}{\leq}\frac{1}{2}\ln\left(1+\frac{\mathbb{E}\left[\left(A^{(L)}A^{(L-1)}\ldots
A^{(\ell+1)}(A^{(\ell)}-\tilde{A}^{(\ell)})U^{(\ell-1)}\right)^{2}\right]}{\sigma^{2}}\right)$
$\displaystyle\overset{(e)}{=}\frac{1}{2}\ln\left(1+\frac{\mathbb{E}\left[\left\|(A^{(\ell)}-\tilde{A}^{(\ell)})U^{(\ell-1)}\right\|^{2}_{2}\right]}{\sigma^{2}N}\right)$

where $(a)$ follows from Lemma 27, $(b)$ follows from Lemma 11, $(c)$ comes
from the fact that for all $n$ and $x,y\in\Re^{n}$,
$\|x-y\|^{2}\geq\|\mathrm{ReLU}(x)-\mathrm{ReLU}(y)\|^{2}_{2}$, $(d)$ follows
from Jensen’s inequality, and $(e)$ follows from the independence and variance
assumptions of the deep neural network data generating process. ∎

With this upper bound in place, it becomes trivial to derive an upper bound
for the total distortion. We present this result now whose proof follows as a
direct application of the above established lemmas.

######  Lemma 29.

(distortion upper bound) For all
$d,N,L\in\mathbb{Z}_{++},\sigma^{2}\in\Re_{++}$, if $(X,Y)$ are generated
according to the deep neural network process and
$\tilde{A}_{1},\ldots,\tilde{A}_{L}$ are independent random variables such
that for all $Y\perp\tilde{A}^{(1:L)}|(A^{(1:L)},X)$, then

$\mathbb{I}(Y;A^{(1:L)}|\tilde{A}^{(1:L)},X)\ \leq\
\sum_{\ell=1}^{L}\frac{1}{2}\ln\left(1+\frac{\mathbb{E}\left[\left\|\left(A^{(\ell)}-\tilde{A}^{(\ell)}\right)U^{(\ell-1)}\right\|^{2}_{2}\right]}{\sigma^{2}N}\right).$

###### Proof.

$\displaystyle\mathbb{I}(Y;A^{(1:L)}|\tilde{A}^{(1:L)},X)$
$\displaystyle\overset{(a)}{=}\sum_{\ell=1}^{L}\mathbb{I}(Y;A^{(\ell)}|A^{(\ell+1:L)},\tilde{A}^{(1:\ell)},X)$
$\displaystyle\overset{(b)}{\leq}\sum_{\ell=1}^{L}\frac{1}{2}\ln\left(1+\frac{\mathbb{E}\left[\left\|\left(A^{(\ell)}-\tilde{A}^{(\ell)}\right)U^{(\ell-1)}\right\|^{2}_{2}\right]}{\sigma^{2}N}\right),$

where $(a)$ follows from Lemma 26 and $(b)$ follows from Lemma 28. ∎

We note that remarkably, the error in each term of the sum in the RHS does not
depend on $L$. This is a clear improvement upon the results based on VC
dimension [Bartlett et al., 1998, 2019] for which the term within the log
would contain the product of the operator norms of the matrices
$A^{(\ell+1:L)}$. The average-case framework allows us to not incur such a
penalty since for all $\ell$, $\mathbb{E}[A^{(\ell)\top}A^{(\ell)}]\propto I$.
Therefore, the resulting rate-distortion bound will depend only _linearly_ on
the parameter count of the network (as opposed to linearly in the _product_ of
parameter count and depth). With an upper bound on the total distortion in
place, we can easily derive an upper bound for the rate-distortion function
for the deep neural network data generating process.

######  Theorem 30.

(deep neural network rate-distortion upper bound) For all
$d,N,L\in\mathbb{Z}_{++},\sigma^{2},\epsilon\in\Re_{++}$, if $(X,Y)$ are
generated according to the deep neural network process, then

$\mathbb{H}_{\epsilon}(A^{(1:L)})\ \leq\
\left(\frac{(L-2)N^{2}+N+dN}{2}\right)\ln\left(1+\frac{1}{\sigma^{2}\left(e^{\frac{2\epsilon}{L}}-1\right)}\right).$

###### Proof.

For all $\ell\in[L]$, let $\tilde{A}^{(\ell)}=A^{(\ell)}+Z^{(\ell)}$ where
$Z^{(\ell)}\perp A^{(\ell)}$ and each element of $Z^{(\ell)}$ is
$\overset{iid}{\sim}\mathcal{N}(0,\delta^{2})$, where
$\delta^{2}=\sigma^{2}(e^{2\epsilon/L}-1)/d^{(\ell-1)}$ and $d^{(\ell-1)}$
denotes the dimension of $U^{(\ell-1)}$. Then,

$\displaystyle\mathbb{I}(Y;A^{(1:L)}|\tilde{A}^{(1:L)},X)$
$\displaystyle\leq\sum_{\ell=1}^{L}\frac{1}{2}\ln\left(1+\frac{\mathbb{E}\left[\left\|\left(A^{(\ell)}-\tilde{A}^{(\ell)}\right)U^{(\ell-1)}\right\|^{2}_{2}\right]}{\sigma^{2}N}\right)$
$\displaystyle=\sum_{\ell=1}^{L}\frac{1}{2}\ln\left(1+\frac{\mathbb{E}\left[\left\|Z^{(\ell)}U^{(\ell-1)}\right\|^{2}_{2}\right]}{\sigma^{2}N}\right)$
$\displaystyle=\sum_{\ell=1}^{L}\frac{1}{2}\ln\left(1+\frac{\sigma^{2}N(e^{\frac{2\epsilon}{L}}-1)\mathbb{E}\left[\|U^{(\ell-1)}\|^{2}_{2}\right]}{\sigma^{2}Nd^{(\ell-1)}}\right)$
$\displaystyle=\epsilon,$

where $(a)$ follows from Lemma 29, and $(b)$ follows from the fact that
$\mathbb{E}[Z^{(\ell)\top}Z^{(\ell)}]=\frac{\sigma^{2}N(e^{2\epsilon/L}-1)}{d^{(\ell-1)}}I_{d^{(\ell-1)}}$.

$\displaystyle\mathbb{I}(A^{(1:L)};\tilde{A}^{(1:L)})$
$\displaystyle=\sum_{\ell=1}^{L}\ \mathbb{I}(A^{(\ell)};\tilde{A}^{(\ell)})$
$\displaystyle=\sum_{\ell=1}^{L}\
\mathbf{h}(\tilde{A}^{(\ell)})-\mathbf{h}(\tilde{A}^{(\ell)}|A^{(\ell)})$
$\displaystyle\overset{(a)}{\leq}\sum_{\ell=1}^{L}\frac{d^{(\ell-1)}d^{(\ell)}}{2}\ln\left(2\pi
e\left(\delta^{2}+\frac{1}{d^{(\ell-1)}}\right)\right)-\frac{d^{(\ell-1)}d^{(\ell)}}{2}\ln\left(2\pi
e\delta^{2}\right)$
$\displaystyle=\sum_{\ell=1}^{L}\frac{d^{(\ell-1)}d^{(\ell)}}{2}\ln\left(1+\frac{1}{\delta^{2}d^{(\ell-1)}}\right)$
$\displaystyle=\sum_{\ell=1}^{L}\frac{d^{(\ell-1)}d^{(\ell)}}{2}\ln\left(1+\frac{1}{\sigma^{2}(e^{\frac{2\epsilon}{L}}-1)}\right)$
$\displaystyle=\left(\frac{(L-2)N^{2}+N+dN}{2}\right)\ln\left(1+\frac{1}{\sigma^{2}\left(e^{\frac{2\epsilon}{L}}-1\right)}\right),$

where $(a)$ follows from Lemma 11. The result follows from the definiton of
the rate-distortion function. ∎

Note that the bound in Theorem 30 is only _linear_ in the parameter count of
the network. In a setting in which we assume an independent prior on the
weights of the network, such a result is the best that one could expect. In
the following subsection, we will leverage this rate-distortion upper bound
and Theorem 15 to arrive at an upper bound for the estimation error for the
deep neural network setting.

####  6.4.3 Main Result

With the theoretical tools developed in the previous section, we now establish
the main result, which upper bounds the estimation error of an optimal agent
learning from data generated by the deep neural network process.

######  Theorem 31.

(deep neural network estimation error upper bound) For all
$d,N,L\in\mathbb{Z}_{++},\sigma^{2}\in\Re_{++}$, if for all $t$,
$(X_{t},Y_{t+1})$ are generated according to the deep neural network process,
then for all $T$,

$\mathcal{L}_{T}\ \leq\
\frac{P}{2T}\left(1+\ln\left(1+\frac{2LT}{\sigma^{2}P}\right)\right),$

where $P=(L-2)N^{2}+N+dN$ denotes the total parameter count of the network.

###### Proof.

$\displaystyle\mathcal{L}_{T}$
$\displaystyle\overset{(a)}{\leq}\inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon}(A^{(1:L)})}{T}+\epsilon$
$\displaystyle\overset{(b)}{\leq}\inf_{\epsilon\geq 0}\
\frac{P\ln\left(1+\frac{1}{\sigma^{2}\left(e^{\frac{2\epsilon}{L}}-1\right)}\right)}{2T}+\epsilon$
$\displaystyle\overset{(c)}{\leq}\frac{P\left(1+\ln\left(1+\frac{1}{\sigma^{2}\left(e^{\frac{P}{2LT}}-1\right)}\right)\right)}{2T}$
$\displaystyle\overset{(d)}{\leq}\frac{P}{2T}\left(1+\ln\left(1+\frac{2LT}{\sigma^{2}P}\right)\right),$

where $(a)$ follows from Theorem 15, $(b)$ follows from Theorem 30, $(c)$
follows by setting $\epsilon=P/2T$, and $(d)$ follows from the fact that for
all $x\in\Re_{+}$,

$\ln\left(1+\frac{1}{\sigma^{2}(e^{x}-1)}\right)\leq\ln\left(1+\frac{1}{\sigma^{2}x}\right).$

∎

Notably, Theorem 31 establishes an upper bound which is only _linear_ in the
total parameter count of the network ($O(P)$). This notably improves upon
existing results from the frequentist line of analysis [Bartlett et al., 1998,
Harvey et al., 2017] which derive an upper bound which is $\tilde{O}(PL)$. As
mentioned in the previous section, we are able to arrive at these stronger
results by leveraging an expectation with respect to the prior distribution as
opposed to a worst-case assumption over the hypotheses in a set.

Since we observe empirically that _deep_ neural networks are able to
effectively learn even in the presence of limited data, our error analysis in
the Bayesian framework provides results which are closer to qualitative
observations of empirical studies. However, the results of this section are
not sufficient to explain how learning may be possible when the dataset size
is _smaller_ than the parameter count of the model which generated the data.
Such results will require stronger assumptions surrounding the _dependence_
between weights in the neural network. In the following section, we explore
this phenomenon in a nonparametric setting in which the neural network which
generated the data may consist of _infinitely_ many parameters, but good
performance can be obtained with relatively modest amounts of data.

###  6.5 Nonparametric Learning

Figure 6: We depict our nonparametric data generating process above. It
consists of input dimension $d$, an infinite number of hidden units with ReLU
activations, and output dimension $1$. We denote the weights of the first
layer via an infinite dimensional matrix $A$ and the weights of the output
layer by an infinite dimensional vector $\theta$. To enforce structure which
enables learning, we assume an appropriate prior distribution which results in
a _concentration_ of the weights of $\theta$ as depicted by the solid (as
opposed to dotted) lines in the above diagram. We assume that the final output
$Y$ is the sum of the final network output and independent Gaussian noise $Z$.

In this section, we study a nonparameteric data generating process which can
be parameterized by a two-layer neural network of _infinite_ width. While the
results we present in this section are limited to a two-layer example, the
techniques derived in this section are general enough to be applied to
appropriate instances of nonparameteric _deep_ neural networks as well.

####  6.5.1 Data Generating Process

For a nonparametric neural network, we are interested in estimating a function
which can be uniquely identified by an infinite-dimensional matrix
$A\in\Re^{\infty\times d}$ which represents the first-layer weights, and an
infinite-dimensional vector $\theta\in\Re^{\infty}$ which denotes the output-
layer weights. As in prior examples, we assume a known prior distribution
$\mathbb{P}((A,\theta)\in\cdot)$. The neural network has input dimension $d$
and output dimension $1$. In this analysis, we restrict our attention to a
particular prior distribution on the weights of the network. This prior
distribution is describe by a _Dirichlet process_ which detail next.

A Dirichlet process is a stochastic process whose realizations are probability
mass functions over a countable (often infinite) support. The Dirichlet
process takes as input a _scale parameter_ $K$, and a base distribution $P$.
Its realizations are hence probability mass functions with support on a
countable subset of the set defined by the base distribution $P$. In our
problem, we will take this base distribution to be
$\text{Unif}(\mathbb{S}^{d-1})$, the uniform distribution over the unit sphere
of dimension $d$. As a result, realizations of the Dirichlet process will be
probability mass functions over a countable subset of $\mathbb{S}^{d-1}$.

As such, a realization of a Dirichlet process exhibits a parameterization via
a vector in $\bar{\theta}\in\Re^{\infty}$ which denotes the frequencies of
each outcome along with the collection of vectors in
$A_{n}\in\mathbb{S}^{d-1}$ for $n\in\mathbb{Z}_{++}$, which comprise of the
support. With this parameterization, we can construct the following data
generating process. For all $t$, let
$X_{t}\overset{iid}{\sim}\mathcal{N}(0,I_{d})$ and

$Y_{t+1}=W_{t+1}+\sqrt{K}\cdot\sum_{n=1}^{\infty}\theta_{n}\mathrm{ReLU}(A_{n}^{\top}X_{t}),$
$\theta_{n}=\begin{cases}\bar{\theta}_{n}&\text{ w.p. }0.5\\\
-\bar{\theta}_{n}&\text{ w.p. }0.5\\\ \end{cases},$

where $\bar{\theta}_{n}$ denotes the frequency associated with the outcome
denoted by $A_{n}$ and for all $t$,
$W_{t}\overset{iid}{\sim}\mathcal{N}(0,\sigma^{2})$ denotes independent
additive Gaussian noise of known variance $\sigma^{2}$.

We now speak about the scale parameter $K$. Evidently, $\bar{\theta}$, though
in $\Re^{\infty}$, is limited in complexity by the fact that for all $n$,
$\bar{\theta}_{n}\geq 0$ and $\sum_{n=1}^{\infty}\bar{\theta}_{n}=1$. The
scale parameter $K$ induces additional structure in the form of
_concentration_. The Dirichlet process inherently assumes a degree of
concentration from the fact that its realizations are in a _countable_ subset
of $\mathbb{S}^{d-1}$. However, the scale parameter induces further
concentration to create a _sparsity-like_ structure in the outcomes. Without
such structure, effective learning in the presence of finite compute and
memory may be infeasible. Therefore, despite the fact that this neural network
is parameterized by an _infinite_ number of parameters, the structure induced
by Dirichlet prior and finite scale parameter $K$ will allow us to reason
about the achievable performance of an optimal learning algorithm.

####  6.5.2 Theoretical Building Blocks

In prior sections, we often derived the appropriate rate-distortion result by
simply devising a compression which adds independent Gaussian noise to the
parameters. This will no longer suffice as the parameters of interest are
_infinite_ -dimensional and would hence result in an infinite rate. We
introduce a proof technique derived from early results by Barron [1993] in his
seminal work on the approximation rates of neural networks. The key insight is
that if one _samples_ $m$ times from the categorical distribution induced by
$\bar{\theta},A$ and simply construct a function which averages the observed
outcomes, the approximation error (in our case, distortion) would decay
_linearly_ in $m$. The following theoretical result concretely establishes
this idea.

######  Lemma 32.

(approximation via multinomial) For all $K,m\in\mathbb{Z}_{++},$ let
$(A,\bar{\theta})\sim\mathcal{D}\mathcal{P}(K,{\rm Unif}(\mathbb{S}^{d-1}))$
and for all $n\in\mathbb{Z}_{++}$,

$\theta_{n}=\begin{cases}\bar{\theta}_{n}&\text{ w.p. }0.5\\\
-\bar{\theta}_{n}&\text{ w.p. }0.5\\\ \end{cases}.$

If for all $i\in[m]$, $c_{i}\overset{iid}{\sim}{\rm
Categorical}(\bar{\theta})$ and $\tilde{A}_{i}=A_{c_{i}}$, then

$\mathbb{E}\left[\left(\underbrace{\sqrt{K}\cdot\sum_{n=1}^{\infty}\theta_{n}\mathrm{ReLU}(A_{n}^{\top}X_{t})}_{\rm
true\ function}-\underbrace{\frac{\sqrt{K}}{m}\sum_{i=1}^{m}{\rm
sign}(\theta_{c_{i}})\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X_{t})}_{\rm
approximation}\right)^{2}\right]\ \leq\ \frac{K}{m}.$

###### Proof.

$\displaystyle\quad\mathbb{E}\left[\left(\sqrt{K}\cdot\sum_{n=1}^{\infty}\theta_{n}\mathrm{ReLU}(A_{n}^{\top}X_{t})-\frac{\sqrt{K}}{m}\sum_{i=1}^{m}{\rm
sign}(\theta_{c_{i}})\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X_{t})\right)^{2}\right]$
$\displaystyle\overset{(a)}{=}\mathbb{E}\left[\left(\frac{\sqrt{K}}{m}\sum_{i=1}^{m}{\rm
sign}(\theta_{c_{i}})\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X_{t})\right)^{2}-\left(\sqrt{K}\cdot\sum_{n=1}^{\infty}\theta_{n}\mathrm{ReLU}(A_{n}^{\top}X_{t})\right)^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(\frac{\sqrt{K}}{m}\sum_{i=1}^{m}{\rm
sign}(\theta_{c_{i}})\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X_{t})\right)^{2}\right]$
$\displaystyle\overset{(b)}{=}\frac{K}{m^{2}}\sum_{i=1}^{m}\mathbb{E}\left[(\mathrm{ReLU}(\tilde{A}_{i}^{\top}X_{t}))^{2}\right]$
$\displaystyle\leq\frac{K}{m^{2}}\sum_{i=1}^{m}\mathbb{E}\left[(\tilde{A}_{i}^{\top}X_{t})^{2}\right]$
$\displaystyle=\frac{K}{m},$

where $(a)$ follows from the fact that the two expressions in the difference
have the same expectation and $(b)$ follows from the fact that the $c_{i}$’s
are independent and $\mathbb{E}[{\rm sign}(\theta_{c_{i}})]=0$. ∎

This result establishes that despite the fact that this data generating
process ostensibly has infinite complexity, there exist good approximations
which only require finite information about the data generating process. The
above result will allow us to establish bounds on the _distortion_ of a
suitable compression. The following result will allow us to establish
favorable bounds on the _rate_ of the compression.

######  Lemma 33.

(Dirichlet-multinomial concentration) For all $K,m\in\mathbb{Z}_{++}$, let
$(A,\bar{\theta})\sim\mathcal{D}\mathcal{P}(K,{\rm Unif}(\mathbb{S}^{d-1}))$.
If for all $i\in[m]$, $c_{i}\overset{iid}{\sim}{\rm
Categorical}(\bar{\theta})$ and $N_{m}$ denotes the random variable which
represents the number of _unique_ categories draw in $(c_{1},\ldots,c_{m})$,
then

$\mathbb{E}\left[N_{m}\right]\ \leq\ K\ln\left(1+\frac{n}{K}\right).$

###### Proof.

As the proof of this result requires significant mathematical machinery, we
refer the reader to Appendix B for the result. ∎

Lemma 33 establishes that the approximation studied above also has favorable
informational complexity. Suppose we construct a compression of $(\theta,A)$
as in the statement of Lemma 32, however, instead of setting
$\tilde{A}_{i}=A_{c_{i}}$, we instead use a _quantization_ of
$\mathbb{S}^{d-1}$. Let $\mathcal{A}_{\epsilon}$ denote an $\epsilon$-cover of
$\mathbb{S}^{d-1}$ with respect to $\|\cdot\|^{2}_{2}$. Furthermore, let

$\bar{A}_{i,\epsilon}=\operatorname*{arg\,min}_{a\in\mathcal{A}_{\epsilon}}\
\|A_{i}-a\|^{2}_{2}.$

Suppose we construct a compression for which
$\tilde{A}_{i}=\bar{A}_{c_{i},\epsilon}$. Then, the collection
$(\tilde{A}_{1},\ldots,\tilde{A}_{m})$ will have _finite_ entropy since it
consists of a finite collection of discrete random variables defined on the
finite set $\mathcal{A}_{\epsilon}$. However, a naive calculation of the
entropy will result in a sub-optimal bound on the rate. We arrive at a tighter
bound by considering a loss-less compression of
$(\tilde{A}_{1},\ldots,\tilde{A}_{m})$ and leveraging the insight of Theorem 3
that entropy is upper bounded by the average length of an optimal prefix-free
code.

######  Theorem 34.

(Dirichlet process rate-distortion upper bound) For all
$d,K\in\mathbb{Z}_{++}$ and $\sigma^{2},\epsilon\in\Re_{++}$, if $(X,Y)$ are
generated according to the Dirichlet neural network process with parameters
$\theta,A$, then

$\mathbb{H}_{\epsilon}(\theta,A)\ \leq\
K\ln\left(1+\frac{2}{\sigma^{2}\epsilon}\right)\ln\left(\frac{2K}{\sigma^{2}\epsilon}\right)+2dK\ln\left(1+\frac{2}{\sigma^{2}\epsilon}\right)\ln\left(1+\frac{4}{\epsilon}\right).$

###### Proof.

Suppose we set $\epsilon^{\prime}=m\sigma^{2}(e^{2K/(m\sigma^{2})}-1)/2K-1\geq
0$ and $m=\lceil\frac{K}{\sigma^{2}\epsilon}\rceil$. For all $i\in[m]$, let
$c_{i}\overset{iid}{\sim}{\rm Categorical}(\bar{\theta})$. Let
$\mathcal{A}_{\epsilon}$ denote an $\epsilon^{\prime}$-cover of
$\mathbb{S}^{d-1}$ with respect to $\|\cdot\|^{2}_{2}$ and for all
$i\in\mathbb{Z}_{++}$, let

$\bar{A}_{i,\epsilon}=\operatorname*{arg\,min}_{a\in\mathcal{A}_{\epsilon}}\
\|A_{i}-a\|^{2}_{2}.$

Recall that $N_{m}$ denotes the number of _unique_ outcomes in
$(c_{1},\ldots,c_{m})$. Let $\mathcal{I}=(I_{1},\ldots,I_{N_{m}})$ denote an
ordered set which consists of the unique outcomes. Let
$(\tilde{\theta},\tilde{A})=(\tilde{\theta}_{1},\tilde{A}_{1},\ldots,\tilde{\theta}_{N_{m}},\tilde{A}_{N_{m}})$
be a collection of random variable such that

$\tilde{A}_{i}=\bar{A}_{I_{i},\epsilon};\quad\tilde{\theta}_{i}=\sum_{j=1}^{m}{\rm
sign}(\theta_{I_{i}})\cdot\mathbbm{1}[c_{j}=I_{i}].$

Therefore, $\tilde{\theta}$ consists of $N_{m}$ integers in $\pm[m]$ and
$\tilde{A}$ consists of $N_{m}$ outcomes from the set
$\mathcal{A}_{\epsilon}$. We begin by upper bounding the distortion of
$(\tilde{\theta},\tilde{A})$.

$\displaystyle\mathbb{I}(Y;\theta,A|\tilde{\theta},\tilde{A},X)$
$\displaystyle=\mathbf{h}(Y|\tilde{\theta},\tilde{A},X)-\mathbf{h}(Y|\theta,A)$
$\displaystyle=\mathbf{h}\left(Y-\frac{\sqrt{K}}{m}\sum_{i\in\mathcal{I}}\tilde{\theta}_{i}\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X)\bigg{|}\tilde{\theta},\tilde{A}\right)-\mathbf{h}(W)$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\frac{1}{2}\ln\left(\frac{\left(Y-\frac{\sqrt{K}}{m}\sum_{i\in\mathcal{I}}\tilde{\theta}_{i}\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X)\right)^{2}}{\sigma^{2}}\right)\right]$
$\displaystyle\overset{(b)}{\leq}\frac{1}{2}\ln\left(\frac{\mathbb{E}\left[\left(Y-\frac{\sqrt{K}}{m}\sum_{i\in\mathcal{I}}\tilde{\theta}_{i}\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X)\right)^{2}\right]}{\sigma^{2}}\right)$
$\displaystyle=\frac{1}{2}\ln\left(1+\frac{\left(\sqrt{K}\cdot\sum_{n=1}^{\infty}\theta_{n}\mathrm{ReLU}(A_{n}^{\top}X)-\frac{\sqrt{K}}{m}\sum_{i=1}^{m}{\rm
sign}(\theta_{c_{i}})\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X)\right)^{2}}{\sigma^{2}}\right)$
$\displaystyle\overset{(c)}{\leq}\frac{1}{2}\ln\left(1+\frac{\frac{2K}{m}+\frac{2K}{m^{2}}\mathbb{E}\left[\left(\sum_{i=1}^{m}{\rm
sign}(\theta_{c_{i}})\mathrm{ReLU}(A_{i}^{\top}X)-\sum_{i=1}^{m}{\rm
sign}(\theta_{c_{i}})\cdot\mathrm{ReLU}(\tilde{A}_{i}^{\top}X)\right)^{2}\right]}{\sigma^{2}}\right)$
$\displaystyle=\frac{1}{2}\ln\left(1+\frac{\frac{2K}{m}+\frac{2K}{m^{2}}\sum_{i=1}^{m}\mathbb{E}\left[(\mathrm{ReLU}(A^{\top}_{i}X)-\mathrm{ReLU}(\tilde{A}_{i}^{\top}X))^{2}\right]}{\sigma^{2}}\right)$
$\displaystyle\overset{(d)}{\leq}\frac{1}{2}\ln\left(1+\frac{\frac{2K}{m}+\frac{2K}{m}\mathbb{E}\left[(A^{\top}_{i}X-\tilde{A}_{i}^{\top}X)^{2}\right]}{\sigma^{2}}\right)$
$\displaystyle\overset{(e)}{\leq}\frac{1}{2}\ln\left(1+\frac{2K(1+\epsilon^{\prime})}{\sigma^{2}m}\right)$
$\displaystyle=\frac{K}{\sigma^{2}m}$ $\displaystyle\leq\epsilon,$

where $(a)$ follows from Theorem 11 and the fact that conditioning reduces
differential entropy, $(b)$ follows from Jensen’s inequality, $(c)$ follows
from Lemma 32 and the fact that for all $x,y,z\in\Re$, $(x-y)^{2}\leq
2(x-z)^{2}+2(z-y)^{2}$, $(d)$ follows from the fact that for all $x,y\in\Re,\
(x-y)^{2}\geq(\mathrm{ReLU}(x)-\mathrm{ReLU}(y))^{2}$, and $(e)$ follows from
the fact that $\tilde{A}_{i}$ is the closest element in an $\epsilon^{\prime}$
cover of $\mathbb{S}^{d-1}$.

We now upper bound the rate of $(\tilde{\theta},\tilde{A})$

$\displaystyle\mathbb{I}(\theta,A;\tilde{\theta},\tilde{A})$
$\displaystyle\leq\mathbb{H}(\tilde{\theta},\tilde{A})$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[N_{m}\cdot\left(\ln(2m)+\ln(|\mathcal{A}_{\epsilon^{\prime}}|)\right)\right]$
$\displaystyle\overset{(b)}{\leq}K\ln\left(1+\frac{m}{K}\right)\left(\ln
2m+d\ln\frac{3}{{\epsilon^{\prime}}^{2}}\right)$
$\displaystyle\overset{(c)}{\leq}K\ln\left(1+\frac{2}{\sigma^{2}\epsilon}\right)\left(\ln\frac{2K}{\sigma^{2}\epsilon}+2d\ln\left(\frac{\epsilon\sqrt{3}}{e^{\epsilon}-1-\epsilon}\right)\right)$
$\displaystyle\overset{(d)}{\leq}K\ln\left(1+\frac{2}{\sigma^{2}\epsilon}\right)\ln\left(\frac{2K}{\sigma^{2}\epsilon}\right)+2dK\ln\left(1+\frac{2}{\sigma^{2}\epsilon}\right)\ln\left(1+\frac{4}{\epsilon}\right),$

where $(a)$ follows from Theorem 3 and the fact that a realization
$(\tilde{\theta},\tilde{A})$ can be mapped to a codeword of length
$N_{m}(\ln(2m)+\ln(|\mathcal{A}_{\epsilon^{\prime}}|))$ by using $\ln(2m)$
nats to encode each of $\tilde{\theta}_{1},\ldots,\tilde{\theta}_{N_{m}}$, and
$\ln(|\mathcal{A}_{\epsilon^{\prime}}|)$ to encode each of
$\tilde{A}_{1},\ldots,\tilde{A}_{N_{m}}$, $(b)$ follows from Lemma 33 and the
fact that
$|\mathcal{A}_{\epsilon^{\prime}}|\leq(3/{\epsilon^{\prime}}^{2})^{d}$, $(c)$
follows by upper bounding the quantity via $m=2K/(\sigma^{2}\epsilon)$ as
opposed to $\lceil K/(\sigma^{2}\epsilon)\rceil$, and $(d)$ follows from the
fact that for all $\epsilon\geq 0$,
$\ln(\epsilon\sqrt{3}/(e^{\epsilon}-1-\epsilon))\leq\ln(1+4/\epsilon)$. ∎

####  6.5.3 Main Result

With the theoretical tools derived in the previous section, we now establish
the following upper bound on the estimation error of an optimal agent learning
from data generated by the Dirichlet process.

######  Theorem 35.

(Dirichlet process estimation error upper bound) For all
$d,K\in\mathbb{Z}_{++}$, if for all $t$, $(X_{t},Y_{t+1})$ are generated
according to the Dirichlet neural network process, then for all $T$,

$\mathcal{L}_{T}\ \leq\
\frac{K}{T}\ln\left(1+\frac{T}{\sigma^{2}d}\right)\ln\left(\frac{T}{\sigma^{2}d}\right)+\frac{2dK}{T}\left(1+\ln\left(1+\frac{T}{\sigma^{2}d}\right)\ln\left(1+\frac{T}{dK}\right)\right).$

###### Proof.

The result follows from Theorems 15 and 34 and setting $\epsilon=2dk/T$. ∎

Notably, this result is $\tilde{\mathcal{O}}(dK/T)$ despite the fact that the
Dirichlet neural network process is described by a neural network with
_infinite_ width. The scale parameter $K$ determines the degree of
concentration which occurs in the output-layer weights of the network and
hence controls the difficult of learning. This example of learning under data
generated by a nonparametric process further demonstrates the flexibility and
ingenuity of proof techniques which are encompassed in our framework. We hope
that the suite of examples provided in this section enables the reader to
analyze whichever complex processes they may have in mind.

### Summary

  * •

(monotonicity of per-timestep estimation error) If for all
$s\in\mathbb{Z}_{+}$, $(X_{s},Y_{s+1})$ is sampled iid from some distribution
$\mathbb{P}(\cdot|\theta)$, then for all $t\in\mathbb{Z}_{+}$,

$\mathbb{I}(Y_{t+2};\theta|H_{t+1})\ \leq\ \mathbb{I}(Y_{t+1};\theta|H_{t}).$

  * •

For all $\epsilon\geq 0$, we let

$\mathbb{H}_{\epsilon}(\theta)=\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon}}\mathbb{I}(\theta;\tilde{\theta}),$

where

$\tilde{\Theta}_{\epsilon}=\\{\tilde{\theta}:\tilde{\theta}\perp
H_{\infty}|\theta,\
\mathbb{I}(Y_{1};\theta|\tilde{\theta},X_{0})\leq\epsilon\\}.$

Note that in contrast to the general rate-distortion formulation of section 5,
this modified rate-distortion does not depend on the time horizon $T$.

  * •

(linear regression estimation error bounds) For all input dimensions
$d\in\mathbb{Z}_{++}$ and noise variance $\sigma^{2}\geq 0$, if for all $t$,
$(X_{t},Y_{t+1})$ are generated according to the linear regression processes,
then for all $T$,

$\frac{d}{2T}W\left(\frac{2T}{d(8+\frac{d}{d-2}\sigma^{2})}\right)\ \leq\
\mathcal{L}_{T}\ \leq\
\left(\frac{d}{2T}\ln\left(\frac{T}{\sigma^{2}d}\right)\right)_{+}+\frac{1}{2T}\ln\left(1+\frac{d}{T}\right),$

where $W$ is the Lambert W function.

  * •

(logistic regression estimation error upper bound) For all input dimensions
$d\in\mathbb{Z}_{++}$, if for all $t$, $(X_{t},Y_{t+1})$ is generated
according to the logistic regression process, then for all $T,$

$\mathcal{L}_{T}\ \leq\
\frac{d}{2T}\left(1+\ln\left(1+\frac{T}{4d}\right)\right).$

  * •

(deep neural network estimation error upper bound) For all input dimensions
$d$, widths $N$, and depths $L$ each $\in\mathbb{Z}_{++}$, and noise variances
$\sigma^{2}\in\Re_{++}$, if for all $t$, $(X_{t},Y_{t+1})$ are generated
according to the deep neural network process, then for all $T$,

$\mathcal{L}_{T}\ \leq\
\frac{P}{2T}\left(1+\ln\left(1+\frac{2LT}{\sigma^{2}P}\right)\right),$

where $P=(L-2)N^{2}+N+dN$ denotes the total parameter count of the network.

  * •

(Dirichlet process estimation error upper bound) For all input dimensions $d$,
scale parameters $K$, each $\in\mathbb{Z}_{++}$, if for all $t$,
$(X_{t},Y_{t+1})$ are generated according to the Dirichlet neural network
process, then for all $T$,

$\mathcal{L}_{T}\ \leq\
\frac{K}{T}\ln\left(1+\frac{T}{\sigma^{2}d}\right)\ln\left(\frac{T}{\sigma^{2}d}\right)+\frac{2dK}{T}\left(1+\ln\left(1+\frac{T}{\sigma^{2}d}\right)\ln\left(1+\frac{T}{dK}\right)\right).$

##  7 Learning from Sequences

In the previous section, we focused on the special case of learning from an
(infintely) exchangeable sequence of data (iid when conditioned on $\theta$).
However, in general, machine learning systems will have to reason about data
which does not obey this rigid structure. For instance, suppose that
$X_{0},X_{1},X_{2},\ldots$ describes a sequence of text tokens from a book.
It’s clear that such a sequence would not exhibit _exchangeability_ as the
order of the tokens plays a critical role in deriving meaning. Existing
frameworks for analyzing machine learning can only reason about learning from
sequential data under rigid and contrived notions of mixing time for the data
generating process. However, in our framework, Theorem 15 does not make any
explicit assumptions on the structure of the data. In this section, we will
demonstrate that Theorem 15 seamlessly extends to the analysis of learning
from data generated by an auto-regressive process.

###  7.1 Data Generating Process

Let $X_{0},X_{1},X_{2},$ be a sequence of random variables representing
observations. We assume that this sequence is generated by an _autoregressive_
model which is parameterized by a random variable $\theta$. As a result, for
all $t$, $X_{t+1}$ is drawn according to a probability distribution which
depends on $\theta$ and the history $H_{t}=(X_{0},X_{1},\ldots,X_{t})$. In
this section, we will analyze learning under two concrete autoregressive data
generating processes. The first involves a binary AR(K) process and the second
a transformer model with context length $K$.

###  7.2 Binary AR(K) Process

####  7.2.1 Data Generating Process

We begin with a simple AR(K) process over a binary alphabet. We aim to
demonstrate that our framework can easily adapt to machine learning from
_sequential_ data. In this problem, we are interested in estimating random
vectors $\theta_{1},\ldots,\theta_{K}\in\Re^{d}$ from data which is generated
in the following way. Let $(X_{0},X_{1}\ldots,X_{K-1})\sim{\rm
Unif}(\\{0,1\\}^{K})$. Furthermore, consider known vectors
$\Phi_{0},\Phi_{1}\in\Re^{d}$ of $L2$ norm equal to $1$ which correspond to
vector embedding of the binary outcomes $0$ and $1$ respectively. For brevity
of notation, we use $\phi_{t}$ to denote $\Phi_{X_{t}}$.

For all $t\geq K$, let

$X_{t+1}=\begin{cases}1&\text{ w.p.
}\sigma\left(\sum_{k=1}^{K}\theta_{k}^{\top}\phi_{t-k+1}\right)\\\ 0&\text{
otherwise}\end{cases},$

where $\sigma$ denotes the sigmoid function. For all $k$, we assume the
independent prior distributions
$\mathbb{P}(\theta_{k})=\mathcal{N}(0,I_{d}/(K))$.

####  7.2.2 Preliminary Theoretical Results

As in all prior examples, our strategy is to leverage rate-distortion theory
to arrive at an estimation error upper bound. We begin with the following
result which upper bounds the rate-distortion function in the binary AR(K)
problem setting.

######  Lemma 36.

(binary AR(K) rate-distortion upper bound) For all $d,K\in\mathbb{Z}_{++}$ and
$\epsilon\in\Re_{++}$, if for all $t\in\mathbb{Z}_{+},X_{t}$ is generated
according to the binary AR(K) process, then for all $T$,

$\mathbb{H}_{\epsilon,T}(\theta_{1:K})\ \leq\
\frac{dK}{2}\ln\left(1+\frac{1}{8\epsilon}\right).$

###### Proof.

For $k\in\\{0,1,\ldots,K-1\\}$, let $\tilde{\theta}_{k}=\theta_{k}+Z_{k}$
where $Z_{k}\perp\theta_{k}$ and $Z_{k}\sim\mathcal{N}(0,I_{d}\cdot
8\epsilon/K)$. For all $t$, let $H_{t}$ denote $(X_{0},X_{1},\ldots,X_{t})$.
Then,

$\displaystyle\frac{\mathbb{I}(H_{T};\theta_{1:K}|\tilde{\theta}_{1:K})}{T}$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta_{1:K}|\tilde{\theta}_{1:K},H_{t})$
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta_{1:K}|\tilde{\theta}_{1:K},X_{t:t-K+1})$
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(X_{t+1}\in\cdot|\theta_{1:K},X_{t:t-K+1})\ \|\
\mathbb{P}(X_{t+1}\in\cdot|\tilde{\theta}_{1:K},X_{t:t-K+1})\right)\right]$
$\displaystyle\overset{(a)}{\leq}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(\mathbb{P}(X_{t+1}\in\cdot|\theta_{1:K},X_{t:t-K+1})\ \|\
\mathbb{P}(X_{t+1}\in\cdot|\theta_{1:K}\leftarrow\tilde{\theta}_{1:K},X_{t:t-K+1})\right)\right]$