# An Information-Theoretic View for Deep Learning

Jingwei Zhang Tongliang Liu11footnotemark: 1 Dacheng Tao11footnotemark: 1
UBTECH Sydney AI Centre and the School of Information Technologies in the
Faculty of Engineering and Information Technologies at The University of
Sydney, NSW, 2006, Australia<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Deep learning has transformed computer vision, natural language processing,
and speech recognition[2, 5, 14, 8]. However, two critical questions remain
obscure: (1) why do deep neural networks generalize better than shallow
networks; and (2) does it always hold that a deeper network leads to better
performance? Specifically, letting $L$ be the number of convolutional and
pooling layers in a deep neural network, and $n$ be the size of the training
sample, we derive an upper bound on the expected generalization error for this
network, i.e.,

$\displaystyle\mathbb{E}[R(W)-R_{S}(W)]\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}$

where $\sigma>0$ is a constant depending on the loss function, $0<\eta<1$ is a
constant depending on the information loss for each convolutional or pooling
layer, and $I(S,W)$ is the mutual information between the training sample $S$
and the output hypothesis $W$. This upper bound shows that as the number of
convolutional and pooling layers $L$ increases in the network, the expected
generalization error will decrease exponentially to zero. Layers with strict
information loss, such as the convolutional layers, reduce the generalization
error for the whole network; this answers the first question. However,
algorithms with zero expected generalization error does not imply a small test
error or $\mathbb{E}[R(W)]$. This is because $\mathbb{E}[R_{S}(W)]$ is large
when the information for fitting the data is lost as the number of layers
increases. This suggests that the claim “the deeper the better” is conditioned
on a small training error or $\mathbb{E}[R_{S}(W)]$. Finally, we show that
deep learning satisfies a weak notion of stability and the sample complexity
of deep neural networks will decrease as $L$ increases.

##  1 Introduction

We study the standard statistical learning framework, where the instance space
is denoted by $\mathcal{Z}$ and the hypothesis space is denoted by
$\mathcal{W}$. The training sample is denoted by
$S=\\{Z_{1},Z_{2},...,Z_{n}\\}$, where each element $Z_{i}$ is drawn i.i.d.
from an unknown distribution $D$. A learning algorithm
$\mathcal{A}:S\rightarrow\mathcal{W}$ can be regarded as a randomized mapping
from the training sample space $\mathcal{Z}^{n}$ to the hypothesis space
$\mathcal{W}$. The learning algorithm $\mathcal{A}$ is characterized by a
Markov kernel $P_{W|S}$, meaning that, given training sample $S$, the
algorithm picks a hypothesis in $\mathcal{W}$ according to the conditional
distribution $P_{W|S}$.

We introduce a loss function $\ell:\mathcal{W}\times Z\to\mathbb{R}^{+}$ to
measure the quality of a prediction w.r.t. a hypothesis. For any learned
hypothesis $W$ by $S$, we define the expected risk

$R(W)=\mathbb{E}_{Z\sim D}[\ell(W,Z)]~{},$ (1.1)

and the empirical risk

$R_{S}(W)=\frac{1}{n}\sum_{i=1}^{n}\ell(W,Z_{i})~{}.$ (1.2)

For a learning algorithm $\mathcal{A}$, the generalization error is defined as

$G_{S}(D,P_{W|S})=R(W)-R_{S}(W)~{}.$ (1.3)

A small generalization error implies that the learned hypothesis will have
similar performances on both the training and test datasets.

In this paper, we study the following expected generalization error for deep
learning:

$G(D,P_{W|S})=\mathbb{E}[R(W)-R_{S}(W)]~{},$ (1.4)

where the expectation is over the joint distribution $P_{W,S}=D^{n}\times
P_{W|S}$.

We have the following decomposition:

$\displaystyle\mathbb{E}[R(W)]=G(D,P_{W|S})+\mathbb{E}[R_{S}(W)]~{},$ (1.5)

where the first term on the right-hand side is the expected generalization
error, and the second term reflects how well the learned hypothesis fits the
training data from an expectation view.

When designing a learning algorithm, we want the expectation of the expected
risk, i.e., $\mathbb{E}[R(W)]$, to be as small as possible. However, obtaining
small values for the expected generalization error $G(D,P_{W|S})$ and the
expected empirical risk $\mathbb{E}[R_{S}(W)]$ at the same time is difficult.
Usually, if a model fits the training data too well, it may generalize poorly
on the test data; this is known as the bias-variance trade-off problem [4].
Surprisingly, deep learning has empirically shown their power for
simultaneously minimizing $G(D,P_{W|S})$ and $\mathbb{E}[R_{S}(W)]$. They have
small $\mathbb{E}[R_{S}(W)]$ because neural networks with deep architectures
can efficiently compactly represent highly-varying functions [18]. However,
the theoretical justification for their small expected generalization errors
$G(D,P_{W|S})$ remains elusive.

In this paper, we study the expected generalization error for deep learning
from an information-theoretic point of view. We will show that, as the number
of layers grows, the expected generalization error $G(D,P_{W|S})$ decreases
exponentially to zero111 We have $I(S,W)\leq H(S)$, which is independent of
$L$. Detailed discussions will be in Section 4 and Section 6 .. Specifically,
in Theorem 1, we prove that

$\displaystyle G(D,P_{W|S})=\mathbb{E}[R(W)-R_{S}(W)]$
$\displaystyle\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}~{},$

where $L$ is the number of information loss layers in deep neural networks
(DNNs), $0<\eta<1$ is a constant depending on the average information loss of
each layer, $\sigma>0$ is a constant depending on the loss function, $n$ is
the size of the training sample $S$, and $I(S,W)$ is the mutual information
between the input training sample $S$ and the output hypothesis $W$. The
advantage of using the mutual information between the input and output to
bound the expected generalization error [15, 19] is that it depends on almost
every aspects of the learning algorithm, including the data distribution, the
complexity of the hypothesis class, and the property of the learning algorithm
itself.

Our result is consistent with the bias-variance trade-off. Although the
expected generalization error decreases exponentially to zero as the number of
information loss layers increases, the expected empirical risk
$\mathbb{E}[R_{S}(W)]$ increases since the information loss is harmful to data
fitting. This implies that, when designing deep neural networks, greater
efforts should be made to balance the information loss and expected training
error.

We also provide stability and risk bound analyses for deep learning. We prove
that deep learning satisfies a weak notion of stability, which we term average
replace-one hypothesis stability, implying that the output hypothesis will not
change too much by expectation when one point in the training sample is
replaced. Under the assumption that the algorithm mapping is deterministic,
the notion of average replace-one hypothesis stability will degenerate to the
case of average replace-one stability, as proposed by [16], which has been
identified as a necessary condition for learnability in the general learning
setting introduced by Vapnik.

We further provide an expected excess risk bound for deep learning and show
that the sample complexity of deep learning will decrease as $L$ increases,
which surprisingly indicates that by increasing $L$, we need a smaller sample
complexity for training. However, this does not imply that increasing the
number of layers will always help. An extreme case is that, as $L$ goes to
infinity, the output feature will lose all predictive information and no
training sample is needed because random-guessing is optimal. We also derive
upper bounds of the expected generalization error for some specific deep
learning algorithms, such as noisy stochastic gradient decent (SGD) and binary
classification for deep learning. We further show that these two algorithms
are PAC-learnable with sample complexities of
$\widetilde{\mathcal{O}}(\frac{1}{\sqrt{n}})$.

The remainder of this paper is organized as follows. In Section 2, we relate
DNNs to Markov chains. Section 3 exploits the strong data processing
inequality to derive how the mutual information, between intermediate features
representations and the output, varies in DNNs. Our main results are given in
Section 4, which gives an exponential generalization error bound for DNNs in
terms of the depth $L$; we then analyze the stability of deep learning in
Section 5 and the learnability for deep learning with noisy SGD and binary
classification in Section 6; Section 7 makes some discussions; all the proofs
are provided in Section 8; finally, we conclude our paper and highlight some
important implications in Section 9 .

##  2 The Hierarchical Feature Mapping of DNNs and Its Relationship to Markov
Chains

Figure 1: Hierarchical Feature Mapping of Deep Neural Networks with L Hidden
Layers Figure 2: The Feature Mapping of Deep Neural Networks Forms a Markov
Chain, when given $w_{1},\ldots,w_{L}$.

We first introduce some notations for deep neural networks (DNNs). As shown in
Figure 1, a DNN with $L$ hidden layers can be seen as $L$ feature maps that
sequentially conduct feature transformations $L$ times on the input $Z$. After
$L$ feature transformations, the learned feature will be the input of a
classifier (or regressor) at the output layer. If the distribution on a single
input is $D$, then we denote the distribution after going through the $k$-th
hidden layer as $D_{k}$ and the corresponding variable as $\widetilde{Z}_{k}$
where $k=1,\ldots,L$. The weight of the whole network is denoted by
$W=[w_{1},\ldots,w_{L};h]\in\mathcal{W}$, where $\mathcal{W}$ is the space of
all possible weights. As shown in Figure 2, the input $S$ is transformed layer
by layer and the output of the $k$-th hidden layer is $T_{k}$, where
$k=1,\ldots,L$. We also denote the $j$-th sample after going through the
$k$-th hidden layer by $Z_{k_{j}}$. In other words, we have the following
relationships:

$\displaystyle Z\sim D,$ (2.1) $\displaystyle\widetilde{Z}_{k}\sim D_{k},\quad
for\quad k=1,\ldots,L,$ (2.2) $\displaystyle S=\\{Z_{1},\ldots,Z_{n}\\}\sim
D^{n},$ (2.3) $\displaystyle T_{k}=\\{Z_{k_{1}},\ldots,Z_{k_{n}}\\}\sim
D_{k}^{n},$ $\displaystyle when~{}~{}given~{}~{}w_{1},\ldots,w_{k},\quad
for\quad k=1,\ldots,L.$ (2.4)

We now have a Markov model for DNNs, as shown in Figure 2. From the Markov
property, we know that if $U\rightarrow V\rightarrow W$ forms a Markov chain,
then $W$ is conditionally independent of $U$ given $V$. Furthermore, from the
data processing inequality [3], we have $I(U,W)\leq I(U,V)$, and the equality
holds if and only if $U\rightarrow W\rightarrow V$ also forms a Markov chain.
Applying the data processing inequality to the Markov chain in Figure 2, we
have,

$\displaystyle I(T_{L},h|w_{1},\ldots,w_{L})\leq
I(T_{L-1},h|w_{1},\ldots,w_{L})$ $\displaystyle\leq
I(T_{L-2},h|w_{1},\ldots,w_{L})\leq\ldots\leq I(S,h|w_{1},\ldots,w_{L})$
$\displaystyle=I(S,W|w_{1},\ldots,w_{L})~{}.$ (2.5)

This means that the mutual information between input and output is non-
increasing as it goes through the network layer by layer. As the feature map
in each layer is likely to be non-invertible, the mutual information between
the input and output is likely to strictly decrease as it goes through each
layer. This encourages the study of the strong data processing inequality [12,
1]. In the next section, we prove that the strong data processing inequality
holds for DNNs in general.

##  3 Information Loss in DNNs

In the previous section, we model a DNN as a Markov chain and conclude that
the mutual information between input and output in DNNs is non-increasing by
using the data processing inequality. The equalities in equation (2) will not
hold for most cases because the feature mapping is likely to be non-
invertible, and therefore we can apply the strong data processing inequality
to achieve tighter inequalities.

For a Markov chain $U\rightarrow V\rightarrow W$, the random transformation
$P_{W|V}$ can be seen as a channel from an information-theoretic point of
view. Strong data processing inequalities (SDPIs) quantify an intuitive
observation that the noise inside channel $P_{W|V}$ will reduce the mutual
information between $U$ and $W$. That is, there exists $0\leq\eta<1$, such
that

$\displaystyle I(U,W)\leq\eta I(U,V)~{}.$ (3.1)

Formally,

######  Theorem 1.

[1] Consider a Markov chain $W\rightarrow X\rightarrow Y$ and the
corresponding random mapping $P_{Y|X}$. If the mapping $P_{Y|X}$ is noisy
(that is, we cannot recover $X$ perfectly from the observed random variable
$Y$), then there exists $0\leq\eta<1$, such that

$\displaystyle I(W,Y)\leq\eta I(W,X)$ (3.2)

More details can be found in a comprehensive survey on SDPIs [12].

Let us consider the $k$-th hidden layer ($1\leq k\leq L$) in Figure 1. This
can be seen as a randomized transformation
$P_{\widetilde{Z}_{k}|\widetilde{Z}_{k-1}}$ mapping from one distribution
$D_{k-1}$ to another distribution $D_{k}$ (when $k=1$, we denote $D=D_{0}$ ).
We then denote the parameters of the $k$-th hidden layer by $w_{k}$222The bias
for each layer can be included in $w_{k}$ via homogeneous coordinates..
Without loss of generality, let $w_{k}$ be a matrix in
$\mathbb{R}^{d_{k}\times d_{k-1}}$. Also, we denote the activation function in
this layer by $\sigma_{k}(\cdot)$.

######  Definition 1 (Contraction Layer).

A layer in a deep neural network is called a contraction layer if it causes
information loss.

We now give the first result, which quantifies the information loss in DNNs.

######  Corollary 1 (Information Loss in DNNs).

Consider a DNN as shown in Figure 1 and its corresponding Markov model in
Figure 2. If its $k$-th ($1\leq k\leq L$ ) hidden layer is a contraction
layer, then there exists $0\leq\eta_{k}<1$, such that

$\displaystyle
I(T_{k},h|w_{1},\ldots,w_{L})\leq\eta_{k}I(T_{k-1},h|w_{1},\ldots,w_{L})~{}.$
(3.3)

We show that the most used convolutional and pooling layers are contraction
layers.

######  Lemma 1 (proved in 8.1).

For any layer in a DNN, with parameters $w_{k}\in\mathbb{R}^{d_{k}\times
d_{k-1}}$, if $rank(w_{k})<d_{k-1}$, it is a contraction layer.

Corollary 1 shows that the mutual information
$I(T_{k-1},h|w_{1},\ldots,w_{L})$ decreases after it goes through a
contraction layer. From Lemma 1, we know that the convolutional and pooling
layers are guaranteed to be contraction layers. Besides, when the shape of the
weight $w_{k}$ satisfies $d_{k}<d_{k-1}$, it also leads to a contraction
layer. For a fully connected layer with shape $d_{k}\geq d_{k-1}$, the
contraction property sometimes may not hold because when the weight matrix is
of full column rank with probability $1$, it will leads to a noiseless and
invertible mapping. However, the non-invertible activation function (e.g. ReLU
activation) employed sub-sequentially can contribute to forming a contraction
layer. Without loss of generality, in this paper, we let all $L$ hidden layers
be contraction layers, e.g., convolutional or pooling layers.

##  4 Exponential Bound on the Generalization Error of DNNs

Before we introduce our main theorem, we need to restrict the loss function
$\ell(W,Z)$ to be $\sigma$-sub-Gaussian with respect to $(W,Z)$ given any
$w_{1},\ldots,w_{L}$.

######  Definition 2 ($\sigma$-sub-Gaussian).

A random variable X is said to be $\sigma$-sub-Gaussian if the following
inequality holds for any $\lambda\in\mathbb{R}$,

$\displaystyle\mathbb{E}[\exp\left(\lambda(X-\mathbb{E}[X])\right)]\leq\exp\left(\frac{\sigma^{2}\lambda^{2}}{2}\right)~{}.$
(4.1)

We now present our main theorem, which gives an exponential bound for the
expected generalization error of deep learning.

######  Theorem 1 (proved in 8.2).

For a DNN with $L$ hidden layers, input $S$, and parameters $W$, assume that
the loss function $\ell(W,Z)$ is $\sigma$-sub-Gaussian with respect to $(W,Z)$
given any $w_{1},\ldots,w_{L}$. Without loss of generality, let all $L$ hidden
layers be contraction layers. Then, the expected generalization error can be
upper bounded as follows,

$\displaystyle\mathbb{E}[R(W)-R_{S}(W)]\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}$
(4.2)

where $\eta<1$ is the geometric mean of information loss factors of all L
contraction layers, that is

$\displaystyle\eta=\left(\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\prod_{k=1}^{L}\eta_{k}\right)\right)^{\frac{1}{L}}~{}.$
(4.3)

The upper bound in Theorem 1 may be loose w.r.t. the mutual information
$I(S,W)$ since we used the inequality $I_{cond}(S,W|w_{1},\ldots,w_{L})\leq
I(S,W)$ in the proof. We also have that

$\displaystyle I(S,W)\leq H(S)~{}.$ (4.4)

By definition, $\eta<1$ holds uniformly for any given $L$ and $\eta^{L}$ is a
strictly decreasing function of $L$. These imply that as the number of
contraction layers $L$ increases, the expected generalization error will
decrease exponentially to zero.

Theorem 1 implies that deeper neural networks will improve the generalization
error. However, this does not mean that the deeper the better. Recall that
$\mathbb{E}[R(W)]=G(D,P_{W|S})+\mathbb{E}[R_{S}(W)]$; a small $G(D,P_{W|S})$
does not imply a small $\mathbb{E}[R(W)]$, since the expected training error
$\mathbb{E}[R_{S}(W)]$ increases due to information loss. Specifically, if the
information about the relationship between the observation $X$ and the target
$Y$ is lost, fitting the training data will become difficult and the expected
training error will increase. Our results highlight a new research direction
for designing deep neural networks, namely that we should increase the number
of contraction layers while keeping the expected training error small.

Information loss factor $\eta$ plays an essential role in the generalization
of deep learning. A successful deep learning model should filter out redundant
information as much as possible while retaining sufficient information to fit
the training data. The functions of some deep learning tricks, such as
convolution, pooling, and activation, are very good at filtering out some
redundant information. The implication behind our theorem somewhat coincides
the information-bottleneck theory [17], namely that with more contraction
layers, more redundant information will be removed while predictive
information is preserved.

##  5 Stability and Risk Bound of Deep Learning

It is known that the expected generalization error is equivalent to the notion
of stability of the learning algorithm [16]. In this section, we show that
deep learning satisfies a weak notion of stability and, further, show that it
is a necessary condition for the learnability of deep learning. We first
present a definition of stability, as proposed by [16].

######  Definition 3.

[16] A learning algorithm $\mathcal{A}:S\to\mathcal{W}$ is _average replace-
one stable_ with rate $\alpha(n)$ under distribution $D$ if

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S\sim
D^{n},Z_{i}^{\prime}\sim
D}\left[\ell(W,Z_{i}^{\prime})-\ell(W^{i},Z_{i}^{\prime})\right]\right|\leq\alpha(n)~{}.$
(5.1)

For deep learning, we define another notion of stability, that we term
_average replace-one hypothesis stability_.

######  Definition 4 (average replace-one hypothesis stability).

A learning algorithm $\mathcal{A}:S\to\mathcal{W}$ is _average replace-one
hypothesis stable_ with rate $\beta(n)$ under distribution $D$ if

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S\sim
D^{n},Z_{i}^{\prime}\sim D,W\sim P_{W|S},W^{i}\sim
P_{W^{i}|S^{i}}}\left[\ell(W,Z_{i}^{\prime})-\ell(W^{i},Z_{i}^{\prime})\right]\right|\leq\beta(n)~{}.$
(5.2)

The difference between average replace-one hypothesis stability and average
replace-one stability is that the former one also takes an expectation over
$W\sim P_{W|S}$ and $W^{i}\sim P_{W^{i}|S^{i}}$, which is weaker than average
replace-one stability. It can clearly be seen that average replace-one
stability with rate $\alpha(n)$ implies average replace-one hypothesis
stability with rate $\alpha(n)$. We now prove that deep learning is average
replace-one hypothesis stable.

######  Theorem 1 (proved in 8.3).

Deep learning is average replace-one hypothesis stable with rate

$\displaystyle\beta(n)=\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}~{}.$
(5.3)

Deep learning algorithms are average replace-one hypothesis stable, which
means that replacing one training example does not alter the output too much
as shown in Theorem 1.

As concluded by [16], the property of average replace-one stability is a
necessary condition for characterizing learnability. We have also shown that
average replace-one stability implies average replace-one hypothesis
stability. Therefore, the property of average replace-one hypothesis stability
is a necessary condition for the learnability of deep learning. However, it is
not a sufficient condition. Finding a necessary and sufficient condition for
characterizing learnability for deep learning remains unsolved.

##  6 Learnability, Sample Complexity, and Risk Bound for Deep Learning

We have derived an exponential upper bound of the expected generalization
error for deep learning. In this section, we further derive the excess risk
bound and analyze the sample complexity and learnability for deep learning in
a general setting. We can roughly bound $I(S,W)$ by $H(S)$, which will be
large when the input tends to be uniformly distributed. Nevertheless, for some
specific deep learning algorithms, a much tighter upper bound of the mutual
information can be obtained. Here, we consider two cases where a tighter bound
can be achieved. That is noisy SGD and binary classification in deep learning.
We also derive the sample complexity for these two algorithms.

###  6.1 Learnability and Risk Bound for Deep Learning

This subsection provides a qualitative analysis on the expected risk bound of
deep learning. By picking any global expected risk minimizer,

$\displaystyle W^{*}=\arg\min_{W\in\mathcal{W}}R(W)$ (6.1)

and picking any empirical risk minimizer

$\displaystyle W=\arg\min_{W\in\mathcal{W}}R_{S}(W)~{},$ (6.2)

we have

$\displaystyle\mathbb{E}_{W,S}[R_{S}(W)]\leq\mathbb{E}_{W,S}[R_{S}(W^{*})]$
$\displaystyle=\mathbb{E}_{S}[R_{S}(W^{*})]=R(W^{*})~{}.$ (6.3)

Note that a global expected risk minimizer $W^{*}$ is neither dependent on $S$
nor a random variable, while $W$ is dependent on $S$. As mentioned before, we
consider the case when $W$ is a random variable drawn according to the
distribution $P_{W|S}$.

Therefore, by combining (4.2) and (6.1), we obtain an expected excess risk
bound as follows,

$\displaystyle\mathbb{E}_{W,S}[R(W)]-R^{*}\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}$
(6.4)

where $R^{*}=R(W^{*})$.

It is worth noticing that $R^{*}$ is a non-decreasing function of $L$, because
the rule constructed over the space $\widetilde{Z}_{L}$ cannot be better than
the best possible rule in $\widetilde{Z}_{L-1}$, since all information in
$\widetilde{Z}_{L}$ originates from space $\widetilde{Z}_{L-1}$. We now reach
two conclusions:

  * •

As the number of contraction layers $L$ goes to infinity, then both the excess
risk and generalization error will decrease to zero. By strong data processing
inequalities, $I(T_{L},h|w_{1},\ldots,w_{L})$ will also decrease to zero333See
8.2 for more details., which means that the output feature $T_{L}$ will lose
all predictive information. Therefore, no samples are needed for training, as
any learned predictor over the transformed feature $T_{L}$ will perform no
better than random guessing. In this case, although the sample complexity is
zero, the optimal risk $R^{*}$ reaches its worst case.

  * •

As we increase the number of contraction layers $L$, the sample complexity
will decrease. The result is surprising when $R^{*}$ is not increasing. This
finding implies that if we could efficiently find a global empirical risk
minimizer, we need smaller sample complexities when increasing the number of
contraction layers. Besides, when these added contraction layers only filter
out redundant information, $R^{*}$ will be not increasing. However, it is not
easy to find the global empirical risk minimizer and control all contraction
layers such that they only filter out redundant information. A promising new
research direction is to increase the number of contraction layers while
keeping a small $R^{*}$ or $\mathbb{E}[R_{S}(W)]$ or $R_{S}(W)$.

We now discuss whether the deep learning is learnable in general. From
equation (6.4) and using Markov inequality, we have that with probability at
least $1-\delta$,

$R(W)-R^{*}\leq\frac{1}{\delta}\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}~{}.$
(6.5)

We know that the notion of PAC-learnability in traditional learning theory
must hold for any distribution $D$ over the instance space $\mathcal{Z}$.
However, for the general case as presented in our main result, with different
distribution $D$, an upper bound of the term $I(S,W)$ can vary and sometimes
may be quite large even of the order $\mathcal{O}(n)$ (e.g. $I(S,W)\leq
H(S)\leq n\log|\mathcal{X}||\mathcal{Y}|$). In this case, a sample complexity
is $\mathcal{O}(\frac{1}{n^{0}})$, which is trivial and cannot guarantee the
learnability as $n$ increases. In the next two subsections, we will show that
for some specific deep learning algorithms, a tighter excess risk bound can be
achieved and the sample complexity will be the order of
$\widetilde{\mathcal{O}}(\frac{1}{\sqrt{n}})$.

###  6.2 Generalization Error Bound With Noisy SGD in Deep Learning

Consider the problem of empirical risk minimization (ERM) via noisy mini-batch
SGD in deep learning, where the weight $W$ is updated successively based on
samples drawn from the training set $S$ and with a noisy perturbation. The
motivations of adding noise in SGD are mainly to prevent the learning
algorithm from overfitting the training data and to avoid an exponential time
to escape from saddle points [7].

Denote the weight of a DNN at the time step $t$ by
$W_{t}=[w_{1_{t}},\ldots,w_{L_{t}};h_{t}]$ and
$\mathbb{Z}_{t}=\\{Z_{t_{1}},\ldots,Z_{t_{m}}\\}\subset S$ is the mini-batch
with batch size $m$ at the $t$-th iteration444With some abuse of notations,
$Z_{k_{j}}$ also denotes the $j$-th sample after going through the $k$-th
hidden layer, where $k=1,\ldots,L$ , but it is not hard to distinguish them
from the context.. Then we have the updating rules
$h_{t}=h_{t-1}-~{}\alpha_{t}\left[\frac{1}{m}\sum_{i=1}^{m}\nabla_{h}\ell(W_{t-1},Z_{t_{i}})\right]+n_{t}$
and
$w_{k_{t}}=w_{k_{t-1}}-\beta_{k_{t}}\left[\frac{1}{m}\sum_{i=1}^{m}\nabla_{w_{k}}\ell(W_{t-1},Z_{t_{i}})\right]+n_{k_{t}}$
where $k=1,\ldots,L$; $\alpha_{t}$ and $\beta_{k_{t}}$ denote the learning
rates at the time step $t$ for each layer;
$n_{t}\sim\mathcal{N}(0,\sigma_{t}^{2}\mathbb{I}_{d})$ and
$n_{k_{t}}\sim\mathcal{N}(0,\sigma_{k_{t}}^{2}\mathbb{I}_{d_{k}})$ are noisy
terms that add a white Gaussian noise to each element of the update
independently. Here, we assume that the updates of $h$ have bounded second
moment. That is, there exists $0<M<\infty$, such that
$\mathbb{E}\left[\left|\left|\frac{1}{m}\sum_{i=1}^{m}\nabla_{h}\ell(W_{t-1},Z_{t_{i}})\right|\right|^{2}\right]\leq
M$ for all $t>0$. We have the following generalization error bound.

######  Theorem 1 (proved in 8.4).

For noisy SGD with bounded second moment in updates and $T$ iterations, the
expected generalization error of deep learning can be upper bounded by

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)]\right|$
$\displaystyle\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{\sigma^{2}}{n}\sum_{i=1}^{T}\frac{M^{2}\alpha_{i}^{2}}{\sigma_{i}^{2}}}~{}.$
(6.6)

With the theorem above, we further prove the learnability and sample
complexity of the noisy SGD in deep learning.

######  Theorem 2 (proved and further discussed in 8.6).

The noisy SGD with bounded second moment in updates for deep learning is
learnable, with the sample complexity of
$\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$ .

###  6.3 Generalization Error Bound for Binary Classification in Deep Learning

This subsection gives an upper bound of the expected generalization error for
deep learning in the case of binary classification. For binary classification,
we denote the function space of the classifier $h$ of the output layer by
$\mathcal{H}$ and its VC-dimension by $\hat{d}$. The training set is
$S=\\{Z_{1},\ldots,Z_{n}\\}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}\in\mathcal{X}^{n}\times\mathcal{Y}^{n}$.
When given $w_{1},\ldots,w_{L}$, we have the transformed training set after
$L$ feature mappings
$T_{L}=\\{(x_{L{{}_{1}}},y_{1}),\ldots,(x_{L_{n}},y_{n})\\}\in\mathcal{X}_{L}^{n}\times\mathcal{Y}^{n}$
and $\mathcal{H}$ is a class of functions from $\mathcal{X}_{L}$ to
$\\{0,1\\}$. For any integer $m\geq 0$, we present the definition of the
growth function of $\mathcal{H}$ as in [10].

######  Definition 5 (Growth Function).

The growth function of a function class $\mathcal{H}$ is defined as

$\Pi_{\mathcal{H}}(m)=\max_{x_{1},\ldots,x_{m}\in\mathcal{X}}\left|\\{(h(x_{1}),\ldots,h(x_{m})):h\in\mathcal{H}\\}\right|~{}.$
(6.7)

Now, we give a generalization error bound and a sample complexity for binary
classification in deep learning in the following two theorems.

######  Theorem 3 (proved in 8.5).

For binary classification in deep learning, the upper bound of the expected
generalization error is given by

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)]\right|\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}\hat{d}}{n}}~{}~{}for~{}~{}n\leq\hat{d}$
(6.8)

and

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)]\right|\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}\hat{d}}{n}\log\left(\frac{en}{\hat{d}}\right)}~{}~{}for~{}~{}n>\hat{d}~{}.$
(6.9)

######  Theorem 4 (proved in 8.7).

The binary classification in deep learning is learnable, with the sample
complexity of
$\widetilde{\mathcal{O}}\left(\sqrt{\frac{\hat{d}}{n}}\right)$555 We use the
notation $\widetilde{\mathcal{O}}$ to hide constants and poly-logarithmic
factors of $d$ and $n$..

##  7 Discussions

###  7.1 Data-fitting and Generalization Trade-off in Deep Learning

In previous sections, we derived an upper bound on the expected generalization
error of deep learning via exploiting the mutual information between the input
training set and the output hypothesis. Here, the mutual information
quantifies the degree to which the output hypothesis depends on the training
data. If the mutual information is small, the output will rely less on the
training data, resulting in a better generalization to unseen test data ( i.e.
small $G(D,P_{W|S})$ ). However, a small mutual information is not helpful to
the fitting of training data and thus may lead to a worse expected training
error (i.e. large $\mathbb{E}[R_{S}(W)]$ ).

Our goal is to minimize the expected risk
$\mathbb{E}[R(W)]=G(D,P_{W|S})+\mathbb{E}[R_{S}(W)]$ in deep learning. In
other words, we need to find a right balance between the data fitting and
generalization such that the sum of expected generalization error and expected
training error is as small as possible. Figure 3 illustrates a qualitative
relationship between the mutual information and errors of a learning
algorithm. Similar to the bias-variance trade-off in traditional learning
theory, we need to control the mutual information between the input and output
hypothesis such that the expected risk is small in deep learning.

We have also derived the expected generalization error bound for noisy SGD in
deep learning. The injection of Gaussian noise in the updates of the weight
$W$ is helpful to reduce the dependence of the output hypothesis on the
training data. Therefore, it controls the mutual information and prevents the
deep learning algorithm from overfitting. There are also many others ways to
control the mutual information between the input and output hypothesis in deep
learning, such as dropout and some data augmentation tricks. For example, we
can inject noise in the training set ( i.e. $S\to\widetilde{S}$ ) and use it
to train the deep learning model. By applying the data processing inequality
on the Markov chain $S\to\widetilde{S}\to W$, it concludes that the mutual
information between the input and output $I(S,W)$ will be smaller and thus
achieves a better generalization error. Many other ways for data augmentation
can also be interpreted by our theorem, such as random cropping, rotation, and
translation of the input images.

Figure 3: Data-fitting and Generalization Trade-off

###  7.2 The Relationship to Algorithmic Hypothesis Class

The use of mutual information to upper bound the expected generalization error
has many advantages in deep learning. It is known that deep models often have
unreasonably large parameter space and therefore the predefined hypothesis
class of a deep learning model is very large. If we use the complexity of the
predefined hypothesis class to upper bound the expected generalization error
of deep learning algorithms, the upper bound will be loose. To address this
problem, [9] introduce the notion of _algorithmic hypothesis class_ , which is
a subset of the predefined hypothesis class that the learning algorithm is
likely to output with high probability.

As shown in Figure 4, the algorithmic hypothesis class is often much smaller
than the predefined hypothesis class because a good learning algorithm always
tends to output the hypothesis that fits the input distribution relatively
well. Therefore, a tighter generalization bound can be achieved by using the
complexity of algorithmic hypothesis class. Our results also adopt the idea of
algorithmic hypothesis complexity because the mutual information $I(S,W)$
contains the distribution $P_{W|S}$, which is the subset of predefined
hypothesis class that the deep learning algorithm is likely to output.

Figure 4: The Implication of Mutual Information on Algorithmic Hypothesis
Class

##  8 Proofs

###  8.1 Proof of Lemma 1

For the $k$-th hidden layer, fixing $w_{1},\ldots,w_{k}$ and considering any
input $(x_{k-1},\cdot)\sim D_{k-1}$ and the corresponding output
$(x_{k},\cdot)\sim P_{D_{k}|D_{k-1}}$, we have

$\displaystyle x_{k}=\sigma_{k}(w_{k}x_{k-1})~{}.$ (8.1)

Because $rank(w_{k})<d_{k-1}$, the dimension of its right null space is
greater than or equal to $1$. Denoting the right null space of $w_{k}$ by
$RNULL(w_{k})$, then we can pick a non-zero vector $\alpha\in RNULL(w_{k})$
such that $w_{k}\alpha=0$.

Then, we have

$\displaystyle\sigma_{k}(w_{k}(x_{k-1}+\alpha))=\sigma_{k}(w_{k}x_{k-1})=x_{k}~{}.$
(8.2)

Therefore, for any input $x_{k-1}\sim D_{k-1}$ of the $k$-th hidden layer,
there exists $x_{k-1}^{\prime}=x_{k-1}+\alpha$ such that their corresponding
outputs are the same. That is, for any $x_{k-1}$, we cannot recover it
perfectly.

We conclude that the mapping $P_{D_{k}|D_{k-1}}$ is noisy and the
corresponding layer will cause information loss.

###  8.2 Proof of Theorem 1

First, by the smoothness of conditional expectation, we have,

$\displaystyle\mathbb{E}[R(W)-R_{S}(W)]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]\right]~{}.$
(8.3)

We now give an upper bound on $\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]$.

######  Lemma 1.

Under the same conditions as in Theorem 1, the upper bound of
$\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]$ is given by

$\displaystyle\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}}{n}I\left(T_{L},h|w_{1},\ldots,w_{L}\right)}~{}.$
(8.4)

###### Proof.

We have,

$\displaystyle\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]$
$\displaystyle=\mathbb{E}_{h,S}\left[\mathbb{E}_{Z\sim
D}[\ell(W,Z)]-\frac{1}{n}\sum_{i=1}^{n}\ell(W,Z_{i})|w_{1},\ldots,w_{L}\right]$
$\displaystyle=\mathbb{E}_{h,T_{L}}\left[\mathbb{E}_{\widetilde{Z}_{L}\sim
D_{L}}[\ell(h,\widetilde{Z}_{L})]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}})|w_{1},\ldots,w_{L}\right]~{}.$
(8.5)

We are now going to upper bound

$\displaystyle\mathbb{E}_{h,T_{L}}\left[\mathbb{E}_{\widetilde{Z}_{L}\sim
D_{L}}[\ell(h,\widetilde{Z}_{L})]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}})|w_{1},\ldots,w_{L}\right]~{}.$

Note that $T_{L}\sim D_{L}^{n}$ when given $w_{1},\dots,w_{L}$, because $T\sim
D^{n}$ and the mappings of hidden layers are given. We adopt the classical
idea of ghost sample in statical learning theory. That is, we sample another
$T_{L}^{\prime}$:

$\displaystyle
T_{L}^{\prime}=\left\\{Z_{L_{1}}^{\prime},\ldots,Z_{L_{n}}^{\prime}\right\\}$
(8.6)

where each element $Z_{L_{i}}^{\prime}$ is drawn i.i.d. from the distribution
$D_{L}$. We now have,

$\displaystyle\mathbb{E}_{h,T_{L}}\left[\mathbb{E}_{\widetilde{Z}_{L}\sim
D_{L}}[\ell(h,\widetilde{Z}_{L})]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}})|w_{1},\ldots,w_{L}\right]$
$\displaystyle=\mathbb{E}_{h,T_{L}}\left[\mathbb{E}_{T_{L}^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}}^{\prime})\right]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}})|w_{1},\ldots,w_{L}\right]$
$\displaystyle=\mathbb{E}_{h,T_{L},T_{L}^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}}^{\prime})|w_{1},\ldots,w_{L}\right]$
$\displaystyle-\mathbb{E}_{h,T_{L}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}})|w_{1},\ldots,w_{L}\right]~{}.$
(8.7)

We denote the joint distribution of $h$ and $T_{L}$ by
$P_{h,T_{L}}=P_{h|T_{L}}\times P_{T_{L}}$, and the marginal distribution of
$h$ and $T_{L}$ by $P_{h}$ and $P_{T_{L}}$ respectively. Therefore, we have,

$\displaystyle\mathbb{E}_{h,T_{L},T_{L}^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}}^{\prime})|w_{1},\ldots,w_{L}\right]-\mathbb{E}_{h,T_{L}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}})|w_{1},\ldots,w_{L}\right]$
$\displaystyle=\mathbb{E}_{h^{\prime}\sim P_{h},T_{L}^{\prime}\sim
P_{T_{L}}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(h^{\prime},Z_{L_{i}}^{\prime})|w_{1},\ldots,w_{L}\right]-\mathbb{E}_{(h,T_{L})\sim
P_{h,T_{L}}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(h,Z_{L_{i}})|w_{1},\ldots,w_{L}\right]$
$\displaystyle=\mathbb{E}_{h^{\prime}\sim P_{h},Z_{L}^{\prime}\sim
P_{D_{L}}}\left[\ell(h^{\prime},Z_{L}^{\prime})|w_{1},\ldots,w_{L}\right]-\mathbb{E}_{(h,Z_{L})\sim
P_{h,D_{L}}}\left[\ell(h,Z_{L})|w_{1},\ldots,w_{L}\right]~{}.$ (8.8)

We now bound the above term by the mutual information
$I(D_{L},h|w_{1},\ldots,w_{L})$ by employing the following lemma.

######  Lemma 2.

[6] Let P and Q be two probability distributions on the same measurable space
$\\{\Omega,\mathcal{F}\\}$. Then the KL-divergence between P and Q can be
represented as,

$\displaystyle
D(P||Q)=\sup_{F}\left[\mathbb{E}_{P}[F]-\log\mathbb{E}_{Q}[e^{F}]\right]$
(8.9)

where the supremum is taken over all measurable functions
$F:\Omega\rightarrow\mathbb{R}$ such that $\mathbb{E}_{Q}[e^{F}]<\infty$.

Using lemma 2, we have,

$\displaystyle I(D_{L},h|w_{1},\ldots,w_{L})$
$\displaystyle=D(P_{h,D_{L}}||P_{h}\times P_{D_{L}}|w_{1},\ldots,w_{L})$
$\displaystyle=\sup_{F}\left[\mathbb{E}_{P_{h,D_{L}}}\left[F|w_{1},\ldots,w_{L}\right]-\log\mathbb{E}_{P_{h}\times
P_{D_{L}}}\left[e^{F}|w_{1},\ldots,w_{L}\right]\right]$
$\displaystyle\geq\mathbb{E}_{(h,Z_{L})\sim
P_{h,D_{L}}}\left[\lambda\ell(h,Z_{L})|w_{1},\ldots,w_{L}\right]$
$\displaystyle-\log\mathbb{E}_{h^{\prime}\sim P_{h},Z_{L}^{\prime}\sim
P_{D_{L}}}\left[e^{\lambda\ell(h^{\prime},Z_{L_{i}}^{\prime})}|w_{1},\ldots,w_{L}\right]~{}.$
(8.10)

As the loss function $\ell(h^{\prime},Z_{L}^{\prime})$ is $\sigma$-sub-
Gaussian w.r.t. $(h^{\prime},Z_{L}^{\prime})$, given any $w_{1},\ldots,w_{L}$.
By definition, we have,

$\displaystyle\log\mathbb{E}_{h^{\prime}\sim P_{h},Z_{L}^{\prime}\sim
P_{D_{L}}}\left[e^{\lambda\ell(h^{\prime},Z_{L}^{\prime})}|w_{1},\ldots,w_{L}\right]$
$\displaystyle\leq\frac{\sigma^{2}\lambda^{2}}{2}+\mathbb{E}_{h^{\prime}\sim
P_{h},Z_{L}^{\prime}\sim
P_{D_{L}}}\left[\lambda\ell(h^{\prime},Z_{L}^{\prime})|w_{1},\ldots,w_{L}\right]~{}.$
(8.11)

Substituting inequality (1) into inequality (1), we have,

$\displaystyle\mathbb{E}_{(h,Z_{L})\sim
P_{h,D_{L}}}\left[\lambda\ell(h,Z_{L})|w_{1},\ldots,w_{L}\right]-\frac{\sigma^{2}\lambda^{2}}{2}-$
$\displaystyle\mathbb{E}_{h^{\prime}\sim P_{h},Z_{L}^{\prime}\sim
P_{D_{L}}}\left[\lambda\ell(h^{\prime},Z_{L}^{\prime})|w_{1},\ldots,w_{L}\right]-I(D_{L},h|w_{1},\ldots,w_{L})$
$\displaystyle=-\frac{\sigma^{2}\lambda^{2}}{2}+\left[\mathbb{E}_{(h,Z_{L})\sim
P_{h,D_{L}}}\left[\ell(h,Z_{L})|w_{1},\ldots,w_{L}\right]\right.$
$\displaystyle\left.-\mathbb{E}_{h^{\prime}\sim P_{h},Z_{L}^{\prime}\sim
P_{D_{L}}}\left[\ell(h^{\prime},Z_{L}^{\prime})|w_{1},\ldots,w_{L}\right]\right]\lambda-I(D_{L},h|w_{1},\ldots,w_{L})\leq
0.$ (8.12)

The left side of the above inequality is a quadratic curve about $\lambda$ and
is always less than or equal to zero. Therefore we have,

$\displaystyle\left|\mathbb{E}_{(h,Z_{L})\sim
P_{h,D_{L}}}\left[\ell(h,Z_{L})|w_{1},\ldots,w_{L}\right]-\mathbb{E}_{h^{\prime}\sim
P_{h},Z_{L}^{\prime}\sim
P_{D_{L}}}\left[\ell(h^{\prime},Z_{L}^{\prime})|w_{1},\ldots,w_{L}\right]\right|^{2}$
$\displaystyle\leq 2\sigma^{2}I(D_{L},h|w_{1},\ldots,w_{L})~{}.$ (8.13)

As $T_{L}\sim D_{L}^{n}$ given $w_{1},\ldots,w_{L}$, we have,666Here, the
conditional entropy
$H_{cond}(Z_{L_{1}},..,\ldots,Z_{L_{n}}|w_{1},\ldots,w_{L};h)$ and
$H_{cond}(Z_{L_{i}}|w_{1},\ldots,w_{L};h,Z_{L_{i-1}},\ldots,Z_{L_{1}})$ only
take expectation over $h$ and $(h,Z_{L_{i-1}},\ldots,Z_{L_{1}})$ respectively.
In other words, $w_{1},\ldots,w_{L}$ are given.

$\displaystyle I(T_{L},h|w_{1},\ldots,w_{L})$
$\displaystyle=I(Z_{L_{1}},..,\ldots,Z_{L_{n}};h|w_{1},\ldots,w_{L})$
$\displaystyle=H(Z_{L_{1}},..,\ldots,Z_{L_{n}}|w_{1},\ldots,w_{L})-H_{cond}(Z_{L_{1}},..,\ldots,Z_{L_{n}}|w_{1},\ldots,w_{L};h)$
$\displaystyle=\sum_{i=1}^{n}H(Z_{L_{i}}|w_{1},\ldots,w_{L})-\sum_{i=1}^{n}H_{cond}(Z_{L_{i}}|w_{1},\ldots,w_{L};h,Z_{L_{i-1}},\ldots,Z_{L_{1}})$
$\displaystyle\geq\sum_{i=1}^{n}H(Z_{L_{i}}|w_{1},\ldots,w_{L})-\sum_{i=1}^{n}H_{cond}(Z_{L_{i}}|w_{1},\ldots,w_{L};h)$
$\displaystyle=nI(Z_{L};h|w_{1},\ldots,w_{L})$
$\displaystyle=nI(D_{L};h|w_{1},\ldots,w_{L})~{}.$ (8.14)

In other words, we have

$\displaystyle
I(D_{L};h|w_{1},\ldots,w_{L})\leq\frac{I(T_{L},h|w_{1},\ldots,w_{L})}{n}~{}.$
(8.15)

We finish the proof by substituting (8.15) into (1). ∎

By Theorem 1, we can use the strong data processing inequality for the Markov
chain in Figure 2 recursively. Thus, we have,

$\displaystyle\sqrt{\frac{2\sigma^{2}}{n}I\left(T_{L},h|w_{1},\ldots,w_{L}\right)}$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}}{n}\eta_{L}I\left(T_{L-1},h|w_{1},\ldots,w_{L}\right)}$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}}{n}\eta_{L}\eta_{L-1}I\left(T_{L-2},h|w_{1},\ldots,w_{L}\right)}$
$\displaystyle\leq\ldots\leq\sqrt{\frac{2\sigma^{2}}{n}\left(\prod_{k=1}^{L}\eta_{k}\right)I\left(S,h|w_{1},\ldots,w_{L}\right)}~{}.$
(8.16)

We then have

$\displaystyle\mathbb{E}[R(W)-R_{S}(W)]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]\right]$
$\displaystyle\leq\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\sqrt{\frac{2\sigma^{2}}{n}\left(\prod_{k=1}^{L}\eta_{k}\right)I\left(S,h|w_{1},\ldots,w_{L}\right)}\right)$
$\displaystyle=\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\sqrt{\prod_{k=1}^{L}\eta_{k}}\sqrt{\frac{2\sigma^{2}}{n}I(S,(w_{1},\ldots,w_{L},h)|w_{1},\ldots,w_{L})}\right)$
$\displaystyle=\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\sqrt{\prod_{k=1}^{L}\eta_{k}}\sqrt{\frac{2\sigma^{2}}{n}I(S,W|w_{1},\ldots,w_{L})}\right)$
$\displaystyle\leq\sqrt{\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\prod_{k=1}^{L}\eta_{k}\right)}\sqrt{\frac{2\sigma^{2}}{n}\mathbb{E}_{w_{1},\ldots,w_{L}}[I(S,W|w_{1},\ldots,w_{L})]}$
(8.17)

As conditions reduce the entropy, we have the following relations

$\displaystyle\mathbb{E}_{w_{1},\ldots,w_{L}}\left[I(S,W|w_{1},\ldots,w_{L})\right]$
$\displaystyle=I_{cond}(S,W|w_{1},\ldots,w_{L})$
$\displaystyle=H_{cond}(S|w_{1},\ldots,w_{L})-H_{cond}(S|W,w_{1},\ldots,w_{L})$
$\displaystyle\leq H(S)-H_{cond}(S|W)=I(S,W)~{}.$ (8.18)

Therefore, we have

$\displaystyle\sqrt{\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\prod_{k=1}^{L}\eta_{k}\right)}\sqrt{\frac{2\sigma^{2}}{n}\mathbb{E}_{w_{1},\ldots,w_{L}}[I(S,W|w_{1},\ldots,w_{L})]}$
$\displaystyle\leq\sqrt{\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\prod_{k=1}^{L}\eta_{k}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}$
$\displaystyle=\sqrt{\eta^{L}}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}$
$\displaystyle=\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}~{}.$
(8.19)

where

$\displaystyle\eta=\left(\mathbb{E}_{w_{1},\ldots,w_{L}}\left(\prod_{k=1}^{L}\eta_{k}\right)\right)^{\frac{1}{L}}<1~{}.$
(8.20)

It’s worth mentioning that the information loss factor $\eta_{k}$ has been
taken an expectation w.r.t. the weight $w_{1},\ldots,w_{L}$, which further
implies that the information loss can be applied to the fully connected layer
$w_{k}$ even with $d_{k}\geq d_{k-1}$, as long as $rank(w_{k})<d_{k-1}$ holds
for some value of $w_{1},\ldots,w_{L}$ with non-zero probability.

###  8.3 Proof of Theorem 1

Let $S^{\prime}=(Z_{1}^{\prime},\cdots,Z_{n}^{\prime})$ be a ghost sample of
$S$. We have

$\displaystyle\mathbb{E}[R(W)-R_{S}(W)]$ $\displaystyle=\mathbb{E}_{W\sim
P_{W|S}}\left[\mathbb{E}_{S,S^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(W,Z_{i}^{\prime})\right]-\mathbb{E}_{S}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(W,{Z}_{i})\right]\right]$
$\displaystyle=\mathbb{E}_{W\sim
P_{W|S}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S,Z_{i}^{\prime}}\left[\ell(W,Z_{i}^{\prime})\right]-\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S}\left[\ell(W,{Z}_{i})\right]\right]$
$\displaystyle=\mathbb{E}_{W\sim
P_{W|S}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S,Z_{i}^{\prime}}\left[\ell(W,Z_{i}^{\prime})\right]-\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S,Z_{i}^{\prime},W^{i}\sim
P_{W^{i}|S^{i}}}\left[\ell(W^{i},Z_{i}^{\prime})\right]\right]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S,Z_{i}^{\prime},W\sim
P_{W|S},W^{i}\sim
P_{W^{i}|S^{i}}}\left[\ell(W,Z_{i}^{\prime})-\ell(W^{i},Z_{i}^{\prime})\right],$
(8.21)

where $W^{i}$ stands for the output of the learning algorithm when the input
is $S^{i}=(Z_{1},\cdots,Z_{i-1},Z_{i}^{\prime},$ $Z_{i+1},\cdots,Z_{n})$ and
$Z_{i}^{\prime}$, and $Z_{i}$ ($i=1,\ldots,n$) are i.i.d. examples.
From equation (1) and (8.15), we have

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]\right|\leq\sqrt{\frac{2\sigma^{2}}{n}I\left(T_{L},h|w_{1},\ldots,w_{L}\right)}~{}.$
(8.22)

Using similar proofs as in Theorem 1, we have

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)]\right|\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}~{}.$
(8.23)

Note that the difference between the above inequality and our main theorem is
that the absolute value is adopted for the expected generalization error,
which may be slightly tighter, but the conclusions are almost the same.
Combining (8.3) and (8.23), we have

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S\sim
D^{n},Z_{i}^{\prime}\sim D,W\sim P_{W|S},W^{i}\sim
P_{W^{i}|S^{i}}}\left[\ell(W,Z_{i}^{\prime})-\ell(W^{i},Z_{i}^{\prime})\right]\right|$
$\displaystyle\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}}{n}I(S,W)}$
(8.24)

which ends the proof.

###  8.4 Proof of Theorem 1

By (1), (8.15), and (8.2), we have,

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]\right|\leq\sqrt{\prod_{k=1}^{L}\eta_{k}}\sqrt{\frac{2\sigma^{2}}{n}I(S,h|w_{1},\ldots,w_{L})}~{}.$
(8.25)

We now bound the expectation of the right side of the above inequality and use
the smoothness of conditional expectation. Then the theorem can be proved. Our
analysis here is based on the work of [13] and [11].

At the final iteration, we have $t=T$ and the algorithm outputs $W=W_{T}$. We
have the following Markov relationship when given $w_{1},\ldots,w_{L}$ and the
initialization $W_{0}$ is known,

$\displaystyle D\rightarrow
S\rightarrow[\mathbb{Z}_{1},\ldots,\mathbb{Z}_{T}]\rightarrow[W_{1},\ldots,W_{T}]\rightarrow[h_{1},\ldots,h_{T}]\rightarrow
h_{T}~{}.$ (8.26)

Therefore, we have,

$\displaystyle\mathbb{E}_{w_{1},\ldots,w_{L}}[I(S,h|w_{1},\ldots,w_{L})]$
$\displaystyle=I_{cond}(S,h|w_{1},\ldots,w_{L})$
$\displaystyle=I_{cond}(S,h_{T}|w_{1},\ldots,w_{L})$ $\displaystyle\leq
I_{cond}(S;h_{1},\ldots,h_{T}|w_{1},\ldots,w_{L})$ $\displaystyle\leq
I_{cond}(\mathbb{Z}_{1},\ldots,\mathbb{Z}_{T};h_{1},\ldots,h_{T}|w_{1},\ldots,w_{L})~{}.$
(8.27)

Using the chain rule of mutual information, we have

$\displaystyle
I_{cond}(\mathbb{Z}_{1},\ldots,\mathbb{Z}_{T};h_{1},\ldots,h_{T}|w_{1},\ldots,w_{L})=$
$\displaystyle\sum_{i=1}^{T}I_{cond}(\mathbb{Z}_{1},\ldots,\mathbb{Z}_{T};h_{i}|h_{i-1},\ldots,h_{1};w_{1},\ldots,w_{L}).$
(8.28)

By definition, we have

$\displaystyle
I_{cond}(\mathbb{Z}_{1},\ldots,\mathbb{Z}_{T};h_{i}|h_{i-1},\ldots,h_{1};w_{1},\ldots,w_{L})$
$\displaystyle=H_{cond}(h_{i}|h_{i-1},\ldots,h_{1};w_{1},\ldots,w_{L})-H_{cond}(h_{i}|\mathbb{Z}_{1},\ldots,\mathbb{Z}_{T};h_{i-1},\ldots,h_{1};w_{1},\ldots,w_{L})$
$\displaystyle=H_{cond}(h_{i}|h_{i-1};w_{1},\ldots,w_{L})-H_{cond}(h_{i}|h_{i-1};\mathbb{Z}_{i};w_{1},\ldots,w_{L})$
$\displaystyle\leq
H_{cond}(h_{i}|h_{i-1})-H_{cond}\left(h_{i-1}-\alpha_{i}\left[\frac{1}{m}\sum_{j=1}^{m}\nabla_{h}\ell(W_{i-1},Z_{i_{j}})\right]+n_{i}|h_{i-1};\mathbb{Z}_{i};w_{1},\ldots,w_{L}\right)$
$\displaystyle=H_{cond}(h_{i}|h_{i-1})-H_{cond}(n_{i}|h_{i-1};\mathbb{Z}_{i})$
$\displaystyle=H_{cond}(h_{i}-h_{i-1}|h_{i-1})-H(n_{i})$ (8.29)

where the last equality follows from the fact that translation does not affect
the entropy of a random variable. From updating rules, we have

$\displaystyle\mathbb{E}\left[||h_{i}-h_{i-1}||^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left|\left|-\alpha_{i}\left[\frac{1}{m}\sum_{j=1}^{m}\nabla_{h}\ell(W_{i-1},Z_{i_{j}})\right]+n_{i}\right|\right|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left|\left|-\alpha_{i}\left[\frac{1}{m}\sum_{j=1}^{m}\nabla_{h}\ell(W_{i-1},Z_{i_{j}})\right]\right|\right|^{2}+\left|\left|n_{i}\right|\right|^{2}\right]$
$\displaystyle\leq M^{2}\alpha_{i}^{2}+d\sigma_{i}^{2}~{}.$ (8.30)

It is known that for a random variable with constraints up to the second
moment, the Gaussian distribution reaches the maximum entropy [3]. For a
Gaussian random variable $X\sim\mathcal{N}(0,\sigma^{2}\mathbb{I}_{d})$ , the
entropy of $X$ is

$H(X)=\frac{d}{2}\log(2\pi e\sigma^{2})~{}.$ (8.31)

Therefore, we have,

$\displaystyle H_{cond}(h_{i}-h_{i-1}|h_{i-1})\leq\frac{d}{2}\log\left(2\pi
e\left(\frac{\alpha_{i}^{2}M^{2}}{d}+\sigma_{i}^{2}\right)\right)~{}.$ (8.32)

We also have,

$H(n_{i})=\frac{d}{2}\log(2\pi e\sigma_{i}^{2})~{}.$ (8.33)

Substituting (8.32) and (8.33) into (8.4), we have,

$\displaystyle
I_{cond}(\mathbb{Z}_{1},\ldots,\mathbb{Z}_{T};h_{i}|h_{i-1},\ldots,h_{1};w_{1},\ldots,w_{L})$
$\displaystyle\leq\frac{d}{2}\log\left(2\pi
e\left(\frac{\alpha_{i}^{2}M^{2}}{d}+\sigma_{i}^{2}\right)\right)-\frac{d}{2}\log(2\pi
e\sigma_{i}^{2})$
$\displaystyle=\frac{d}{2}\log\left(\frac{\alpha_{i}^{2}M^{2}}{d\sigma_{i}^{2}}+1\right)\leq\frac{\alpha_{i}^{2}M^{2}}{2\sigma_{i}^{2}}~{}.$
(8.34)

By (8.25), (8.4), (8.4), and (8.4), similar to the steps of (8.2) and (8.2),
we have

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)]\right|$
$\displaystyle=\left|\mathbb{E}\left[\mathbb{E}\left[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}\right]\right]\right|$
$\displaystyle\leq\left|\sqrt{\mathbb{E}\left[\prod_{k=1}^{L}\eta_{k}\right]}\sqrt{\frac{2\sigma^{2}}{n}I_{cond}(S,h|w_{1},\ldots,w_{L})}\right|$
$\displaystyle\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{\sigma^{2}}{n}\sum_{i=1}^{T}\frac{M^{2}\alpha_{i}^{2}}{\sigma_{i}^{2}}}$
(8.35)

which completes the proof.

###  8.5 Proof of Theorem 3

From (8.25), we have

$\displaystyle\left|\mathbb{E}[R(W)-R_{S}(W)|w_{1},\ldots,w_{L}]\right|$
$\displaystyle\leq\sqrt{\prod_{k=1}^{L}\eta_{k}}\sqrt{\frac{2\sigma^{2}}{n}I(S,h|w_{1},\ldots,w_{L})}$
$\displaystyle\leq\sqrt{\prod_{k=1}^{L}\eta_{k}}\sqrt{\frac{2\sigma^{2}}{n}H(\mathcal{H})}$
$\displaystyle\leq\sqrt{\prod_{k=1}^{L}\eta_{k}}\sqrt{\frac{2\sigma^{2}}{n}\log\Pi(n)}~{}.$
(8.36)

Using Sauer’s Lemma presented in [10], we have

$\displaystyle\Pi(n)\leq 2^{n}\leq 2^{\hat{d}}\quad for\quad n\leq\hat{d}~{},$
(8.37) $\displaystyle\Pi(n)\leq\left(\frac{en}{\hat{d}}\right)^{\hat{d}}\quad
for\quad n>\hat{d}~{}.$ (8.38)

Substituting (8.37) and (8.38) into (8.5), and using the smoothness of
conditional expectation as in (8.2), one can complete the proof.

###  8.6 Learnability of Noisy SGD for Deep Learning

For the case of noisy SGD in deep learning, following Theorem 1 and similar
steps of deriving equation (6.4), we have

$\mathbb{E}_{W,S}[R(W)]-R^{*}\leq\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{\sigma^{2}}{n}\sum_{i=1}^{T}\frac{M^{2}\alpha_{i}^{2}}{\sigma_{i}^{2}}}~{}.$
(8.39)

Similar to previous proofs, by Markov inequality, we have that with
probability at least $1-\delta$

$R(W)-R^{*}\leq\frac{1}{\delta}\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{\sigma^{2}}{n}\sum_{i=1}^{T}\frac{M^{2}\alpha_{i}^{2}}{\sigma_{i}^{2}}}~{}.$
(8.40)

If we set the learning rate and the variance of noise as $\alpha_{i}=C/i^{2}$
and $\sigma_{i}=\sqrt{C/i^{2}}$, we have that, with probability at least
$1-\delta$,

$\displaystyle
R(W)-R^{*}\leq\frac{1}{\delta}\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{CM^{2}\sigma^{2}}{n}\sum_{i=1}^{T}\frac{1}{i^{2}}}$
$\displaystyle\leq\frac{1}{\delta}\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{CM^{2}\sigma^{2}\pi^{2}}{6n}}$
(8.41)

where the last inequality is obtained by the analytic continuation of Riemann
zeta function $\zeta(s)$ at $s=2$,

$\displaystyle\sum_{i=1}^{T}\frac{1}{i^{2}}\leq\sum_{i=1}^{\infty}\frac{1}{i^{2}}=\zeta(2)=\frac{\pi^{2}}{6}~{}.$
(8.42)

In this case, the noisy SGD in deep learning is learnable with sample
complexity $\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$.

###  8.7  Learnability of Binary Classification in Deep Learning

Similar to the case of noisy SGD, based on Theorem 3 and following similar
steps of deriving equation (6.4) and using Markov inequality, we have that
with probability at least $1-\delta$,

$\displaystyle
R(W)-R^{*}\leq\frac{1}{\delta}\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}\hat{d}}{n}}\quad
for\quad n\leq\hat{d}$ (8.43)

and

$\displaystyle
R(W)-R^{*}\leq\frac{1}{\delta}\exp{\left(-\frac{L}{2}\log{\frac{1}{\eta}}\right)}\sqrt{\frac{2\sigma^{2}\hat{d}}{n}\log\left(\frac{en}{\hat{d}}\right)}~{}~{}~{}for\quad
n>\hat{d}~{}.$ (8.44)

Therefore, the binary classification in deep learning is learnable with sample
complexity $\widetilde{\mathcal{O}}\left(\sqrt{\frac{\hat{d}}{n}}\right)$ .

##  9 Conclusions

In this paper, we obtain an exponential-type upper bound for the expected
generalization error of deep learning and prove that deep learning satisfies a
weak notion of stability. Besides, we also prove that deep learning algorithms
are learnable in some specific cases such as employing noisy SGD and for
binary classification. Our results have valuable implications for other
critical problems in deep learning that require further investigation. (1)
Traditional statistical learning theory can validate the success of deep
neural networks, because (i) the mutual information between the learned
feature and classifier $I(T_{L},h|w_{1},\ldots,w_{L})$ decreases with
increasing number of contraction layers $L$, and (ii) smaller mutual
information implies higher algorithmic stability [13] and smaller complexity
of the algorithmic hypothesis class [9]. (2) The information loss factor
$\eta<1$ offers the potential to explore the characteristics of various
convolution, pooling, and activation functions as well as other deep learning
tricks; that is, how they contribute to the reduction in the expected
generalization error. (3) The weak notion of stability for deep learning is
only a necessary condition for learnability [16] and deep learning is
learnable in some specific cases. It would be interesting to explore a
necessary _and_ sufficient condition for the learnability of deep learning in
a general setting. (4) When increasing the number of contraction layers in
DNNs, it is worth further exploring: how to filter out redundant information
while keep the useful part intact.

## References

  * Ahlswede and Gács, [1976] Ahlswede, R. and Gács, P. (1976).  Spreading of sets in product spaces and hypercontraction of the Markov operator.  The annals of probability, pages 925–939.
  * Badrinarayanan et al., [2017] Badrinarayanan, V., Kendall, A., and Cipolla, R. (2017).  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(12):2481–2495.
  * Cover and Thomas, [2012] Cover, T. M. and Thomas, J. A. (2012).  Elements of information theory.  John Wiley & Sons.
  * Domingos, [2000] Domingos, P. (2000).  A unified bias-variance decomposition.  In Proceedings of 17th International Conference on Machine Learning, pages 231–238.
  * Dong et al., [2016] Dong, C., Loy, C. C., He, K., and Tang, X. (2016).  Image super-resolution using deep convolutional networks.  IEEE transactions on Pattern Analysis and Machine Lntelligence, 38(2):295–307.
  * Donsker and Varadhan, [1983] Donsker, M. D. and Varadhan, S. S. (1983).  Asymptotic evaluation of certain Markov process expectations for large time. iv.  Communications on Pure and Applied Mathematics, 36(2):183–212.
  * Du et al., [2017] Du, S. S., Jin, C., Lee, J. D., Jordan, M. I., Singh, A., and Poczos, B. (2017).  Gradient descent can take exponential time to escape saddle points.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems 30, pages 1067–1077. Curran Associates, Inc.
  * Ji et al., [2013] Ji, S., Xu, W., Yang, M., and Yu, K. (2013).  3d convolutional neural networks for human action recognition.  IEEE transactions on Pattern Analysis and Machine Intelligence, 35(1):221–231.
  * Liu et al., [2017] Liu, T., Lugosi, G., Neu, G., and Tao, D. (2017).  Algorithmic stability and hypothesis complexity.  In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2159–2167. PMLR.
  * Mohri et al., [2012] Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2012).  Foundations of machine learning.  MIT press.
  * Pensia et al., [2018] Pensia, A., Jog, V., and Loh, P.-L. (2018).  Generalization Error Bounds for Noisy, Iterative Algorithms.  ArXiv e-prints.
  * Polyanskiy and Wu, [2015] Polyanskiy, Y. and Wu, Y. (2015).  Strong data-processing inequalities for channels and Bayesian networks.  ArXiv e-prints.
  * Raginsky et al., [2016] Raginsky, M., Rakhlin, A., Tsao, M., Wu, Y., and Xu, A. (2016).  Information-theoretic analysis of stability and bias of learning algorithms.  In Information Theory Workshop (ITW), 2016 IEEE, pages 26–30. IEEE.
  * Ren et al., [2017] Ren, S., He, K., Girshick, R., and Sun, J. (2017).  Faster r-cnn: towards real-time object detection with region proposal networks.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(6):1137–1149.
  * Russo and Zou, [2015] Russo, D. and Zou, J. (2015).  How much does your data exploration overfit? Controlling bias via information usage.  ArXiv e-prints.
  * Shalev-Shwartz et al., [2010] Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. (2010).  Learnability, stability and uniform convergence.  Journal of Machine Learning Research, 11(Oct):2635–2670.
  * Shwartz-Ziv and Tishby, [2017] Shwartz-Ziv, R. and Tishby, N. (2017).  Opening the Black Box of Deep Neural Networks via Information.  ArXiv e-prints.
  * Sonoda and Murata, [2015] Sonoda, S. and Murata, N. (2015).  Neural network with unbounded activation functions is universal approximator.  arXiv preprint arXiv:1505.03654.
  * Xu and Raginsky, [2017] Xu, A. and Raginsky, M. (2017).  Information-theoretic analysis of generalization capability of learning algorithms.  In Advances in Neural Information Processing Systems 30, pages 2524–2533. Curran Associates, Inc.


Send correspondence to Benjamin L. Gerard<EMAIL_ADDRESS>
# The Bright Pyramid Wavefront Sensor

Benjamin L. Gerard  University of California Observatories, CA, USA
University of California Santa Cruz, CA, USA  Vincent Chambouleyron  Aix
Marseille Univ, CNRS, CNES, LAM, Marseille, France  DOTA, ONERA, Université
Paris Saclay, F-91123 Palaiseau, France  Rebecca Jensen-Clem  University of
California Santa Cruz, CA, USA  University of California Observatories, CA,
USA  Jean-François Sauvage  Aix Marseille Univ, CNRS, CNES, LAM, Marseille,
France  DOTA, ONERA, Université Paris Saclay, F-91123 Palaiseau, France

###### Abstract

Extreme adaptive optics (AO) is crucial for enabling the contrasts needed for
ground-based high contrast imaging instruments to detect exoplanets. Pushing
exoplanet imaging detection sensitivities towards lower mass, closer
separations, and older planets will require upgrading AO wavefront sensors
(WFSs) to be more efficient. In particular, future WFS designs will aim to
improve a WFS’s measurement error (i.e., the wavefront level at which photon
noise, detector noise, and/or sky background limits a WFS measurement) and
linearity (i.e., the wavefront level, in the absence of photon noise,
aliasing, and servo lag, at which an AO loop can close and the corresponding
closed-loop residual level). We present one such design here called the bright
pyramid WFS (bPWFS), which improves both the linearity and measurement errors
as compared to the non-modulated pyramid WFS (PWFS). The bPWFS is a unique
design that, unlike other WFSs, doesn’t sacrifice measurement error for
linearity, potentially enabling this WFS to (a) close the AO loop on open loop
turbulence utilising a tip/tilt modulation mirror (i.e., a modulated bPWFS;
analogous to the procedure used for the regular modulated PWFS), and (b) reach
deeper closed-loop residual wavefront levels (i.e., improving both linearity
and measurement error) compared to the regular non-modulated PWFS. The latter
approach could be particularly beneficial to enable improved AO performance
using the bWFS as a second stage AO WFS. In this paper we will present an AO
error budget analysis of the non-modulated bPWFS as well as supporting AO
testbed results from the Marseille Astrophysics Laboratory.

###### keywords:

Adaptive Optics, Wavefront Sensing

##  1 INTRODUCTION

Astronomical adaptive optics (AO) systems have evolved in the past three
decades from providing barely diffraction-limited wavefronts at near infrared
science wavelengths[1] to “extreme” Strehl ratios up to 90%[2, 3], as a result
now enabling new exoplanet imaging science[4]. Because of such progress and
developments, this Extreme AO (ExAO) field is now limited by AO error budget
components that were previously negligible with past-generation non-ExAO
systems, which in turn limits the mass, separations, and ages of self-luminous
exoplanets that ExAO-based exoplanet imaging instruments can detect and
characterize[5]. In particular, the Pyramid wavefront sensor (PWFS)[6] has
revolutionized the field of Fourier-based AO wavefront sensing, enabling
significant gains in wavefront measurement errors due to photon noise and
aliasing, but at the cost of increased WFS non-linearities. A tip/tilt
modulator mirror in the WFS path of an AO system decreases PWFS non-
linearities, but this modulation comes with a trade-off of decreased
efficiency to other measurement error terms[7, 8].

More recently it has been generalized that non-modulated Fourier-based
WFSs—which includes the PWFS, Zernike WFS[9, 10], iQuad WFS[11], and more
generally any WFS involving a phase mask in the upstream focal plane of a
pupil imager—can be designed either (1) to be more linear (i.e., how well a
WFS can reconstruct a given input wavefront, which is itself a function of
input aberration strength) but at the cost of degrading measurement errors
(i.e., the wavefront level at which photon noise, detector noise, and/or sky
background limits a WFS measurement) or (2) to enable improved measurement
errors but at the cost of degrading linearity[8]. However, in this paper we
propose two new Fourier-based WFSs called the bright and dark PWFS (bPWFS and
dPWFS, respectively), modifying the PWFS design to enable—for the bPWFS—both
improved measurement errors and linearity. In §2 we present simulations of
this concept and a corresponding error budget analysis compared to the regular
PWFS. In §3 we present preliminary validation of these bPWFS and dPWFS
concepts from the AO testbed at the Marseille Astrophysics Laboratory[12]. We
discuss further implications of these results and future work in §4, and we
conclude in §5.

##  2 SIMULATIONS

###  2.1 Concept

Fig. 1 illustrates the bPWFS and dPWFS concepts.

(a)

(b)

Figure 1: (a) Illustration of the bright and dark PWFS concepts. The columns
within each row are shown on the same linear contrast scale. The first row is
displayed between -1 and +1 $\lambda/D$ in both x and y directions. The bright
PWFS applies an added piston phase shift to the regular PWFS tilt angles of
1.7$\pi$ radians (in this case showing -0.3 rad for display purposes) within a
0.5 $\lambda/D$ radius from the pyramid apex/optical axis. The dark PWFS
applies the same concept but instead with a piston phase value of 0.8$\pi$
radians. The bottom row displays the differential pupil intensity images
between (1) propagated images for a 100 nm rms (at $\lambda=1.6\mu$m;
normalized over 32 cycles/pupil), -2 power law phase screen realization (i.e.,
the same realization is used for all columns) and (2) the respective
diffraction-limited images in the middle row. (b) Illustration of the
diffractive nature of an additive variable piston phase shift to the PWFS tilt
angles (for a diffraction-limited input wavefront). The y-axis is a metric,
m1, determining how much flux is distributed beyond the four pupil footprints
(i.e., in the absence of diffraction) relative total flux in the image: the
lower the y axis value, the more relative flux is diffracted within the four
pupil footprints. The dotted red line shows the value of m1 at piston phase
shift of 0=2$\pi$ radians. When the curve is below the red dashed line, more
light is diffracted within the pupil footprint than the regular PWFS; when the
curve is instead above the red dashed line (which is the case for the majority
of piston phases), more light light is diffracted outside of the pupil
footprints compared to the regular PWFS.

As shown, the bright and dark PWFSs are different additive piston phase
offsets to the regular PWFS tilt angles, such that

$\displaystyle\phi_{\mathrm{bPWFS}}$
$\displaystyle=\phi_{\mathrm{PWFS}}+\phi_{\mathrm{b}},\;\mathrm{with}$ (1)
$\displaystyle\phi_{\mathrm{b}}$
$\displaystyle=1.7\pi\;[\mathrm{rad}]\;\forall\;r\leq
0.5\;\lambda/D,\;\mathrm{and}$ $\displaystyle\phi_{\mathrm{b}}$
$\displaystyle=0\;[\mathrm{rad}]\;\forall\;r>0.5\;\lambda/D,$

where $\phi_{\mathrm{PWFS}}$ is the regular PWFS focal plane phase shift tilt
angles, $\phi_{\mathrm{b}}$ is the additive phase component for the bPWFS, and
$r$ is a radial polar grid in natural units of $\lambda/D$. In general the
complex electric field at the focal plane of the bPWFS optic is represented by
$A_{\mathrm{sys}}\;e^{i(\phi_{\mathrm{sys}}+\phi_{\mathrm{bPWFS}})}$, where
$|A_{\mathrm{sys}}\;e^{i\;\phi_{\mathrm{sys}}}|^{2}$ is the system point
spread function (PSF) if imaged on a dector placed in that focal plane. For
the dPWFS, the analogous $\phi_{\mathrm{dPWFS}}$ term is identical to equation
1 other than $\phi_{\mathrm{d}}=0.8\pi\;[\mathrm{rad}]\;\forall\;r\leq
0.5\;\lambda/D$. As shown in Fig. 1b, the value of this piston offset produces
drastically different pupil images compared to the regular PWFS, some with
more light diffracted into the pyramid pupil footprints (the bPWFS) and some
with less light diffracted into the footprints (the dPWFS). Fig. 2 then shows
how this diffractive modification to the PWFS pupil images changes with the
tilt angle defining the pupil separations,

Figure 2: Dependence of PWFS tilt angle on m1 vs. additive piston phase curve
(as in Fig. 1b). The pupil intensity image for the additive piston phase at
which m1 is minimized is shown above each corresponding curve. All images are
displayed on the same relative contrast scale.

illustrating that increased pupil “throughput” (i.e., a decreased value of m1)
with this bright PWFS concept relative to the regular PWFS is only achieved
when the pupil separations are less than about 1 pupil diameter from one
another. This effect is to be expected; effectively, this additive phase shift
is acting as a Roddier&Roddier coronagraph[13] or a Zernike WFS[9] on the four
pupils, depending on the value of additive piston applied to the central
$\lambda/D$ diameter region. When the four pupils are separated by more than
one pupil diameter form one another, the central dark “coronagraphic” pupil
from the bPWFS no longer redistributes light from within this central pupil
footprint into the four pupils from the PWFS tilt angles. However, a more
complex numerical optimization should further investigate the limits of this
approach (see §5). Regardless, a separation between the four PWFS pupils is
still generally a desired trait, enabling (1) an increased achievable pupil
sampling for use with higher order deformable mirrors (DMs) and/or to reduce
aliasing in WFS measurement errors, and/or (2) decreasing the required sub-
array/detector size to readout, enabling higher accessible loop speeds and/or
lower detector read noise.

###  2.2 Error Budget Analysis

Instead of considering a full end-to-end closed-loop error budget analysis, in
this paper we only implement a differential analysis to compare performance
between the regular PWFS and bPWFS (both without tip/tilt modulation).
Although this approach cannot be used to predict achievable closed-loop Strehl
ratios, it gives insight into how a bPWFS could improve closed-loop wavefront
errors over the non-modulated PWFS (i.e., using modulation to close the loop
initially, but then subsequently not using modulation; also see §4.1).

The setup of our differential error budget analysis is identical to Ref. 14
(Sec. 2.3) and also briefly summarized here. We first describe our simulation
and calibration assumptions. We use a 1024$\times$1024 pixel image with a 191
pixel diameter to simulate the entrance pupil wavefront, assuming a square DM
with 32 actuators across the pupil diameter. We use the same tilt angle/pupil
separation as illustrated in Fig. 1. A monochromatic wavelength of 1.65 $\mu$m
is assumed to convert between radians and nm of wavefront error. Input
residual atmospheric phase screens are generated assuming a -2 power law and
random phase, normalized to 100 nm root mean square (rms) within the DM
control region. An 8m diameter telescope is assumed with no secondary
obscuration or spiders for simplicity. Assumed transmission through the
atmosphere, instrument throughput, and detector quantum efficiency are 90%,
80%, and 80%, respectively. A 1% bandpass is assumed for flux calculation
purposes with an otherwise monochromatic Fraunhofer propagation simulation
(see §4.2). To generate a command matrix, we use a classical zonal control
approach, assuming perfect uncoupled Gaussian DM actuator influence functions
whose full width at half maximum (FWHM) are one actuator pitch. The pixel
values within the four pupil footprints in the PWFS/bPWFS detector plane for a
push minus pull of each DM actuator are used to generate an interaction
matrix. The singular value decomposition cutoff of the matrix inversion is
separately optimized for both the PWFS and bPWFS to enable the lowest total
residual wavefront error after one iteration on the above-described input 100
nm rms phase screen. An input target image to be multiplied by the command
matrix to generate DM commands is a differential measurement, in this case the
difference between the target WFS image and the diffraction-limited WFS image
for the corresponding Fourier-based WFS phase mask.

Fig. 3 shows the results of our differential error budget analysis, comparing
the PWFS and bPWFS.

(a)

(b)

Figure 3: AO error budget, comparing the regular PWFS (solid lines) and bright
PWFS (dashed lines). In both panels the y axis shows wavefront error for a
given spatial frequency bin, identical to the definition in equation 1 of Ref.
15. (a) A breakdown of output residuals, after 3 iterations using a unity gain
integral controller, into components for photon noise, alaising, and non-
linearities, comparing the PWFS and bPWFS for each component. Each curve shown
is from a median over 100 different uncorrelated wavefront realizations (where
in each case the input is normalized to 100 nm rms as described in the text).
(b) Error budget comparison of reconstructed photon noise for the PWFS and
bPWFS, both for an input diffraction-limited (i.e., zero phase) wavefront.
Each curve is medianed over 100 individual photon noise realizations.

The three non-linearities, aliasing, and photon noise curves are calculated as
follows (again only briefly summarized here; see Ref. 14 for a full
description).

  1. 1.

Non-linearities are defined as the residual wavefront when no photon noise is
included in the simulation and an algorithmic anti-aliasing filter on the
entrance pupil wavefront error is applied.

  2. 2.

The aliasing term is the differential measurement between the residual
wavefront without an anti-aliasing filter (aliasing + non-linearities) and
with an anti-aliasing filter (non-linearities), resulting in only the aliasing
component (in both cases without including simulated photon noise).

  3. 3.

The photon noise term is the differential wavefront between the residual
wavefront with photon noise simulated (photon noise + non-linearities) and
with no photon noise simulated (non-linearities), in both cases with an anti-
aliasing filter applied.

Figure 3 clearly shows the gain in all error budget terms from the bPWFS over
the PWFS: the overall residual wavefront in panel a is lower, with relatively
less contributions from non-linearities, aliasing, and photon noise. Panel b
shows that for the same number of input photons, the measurement error due to
photon noise for a diffraction-limited wavefront (i.e., no aliasing and
minimal non-linearities) is about 20% lower for the bPWFS vs. PWFS. These
performance gains can be interpreted as follows.

  1. 1.

Non-linearities and aliasing. The bPWFS phase mask diffracts more light into
the four pupil footprints and enables that increased light to display entrance
pupil phase aberations as intensity variations on the WFS detector, which
causes less signal from the input wavefront error to be spatially
redistributed beyond such footprints. More diffracted light outside the pupil
footprints leads to increased non-linearities, particularly for larger
wavefront errors. More diffracted light/light redistribution also has the
potential to optically redistribute higher order un-correctable wavefront
errors to look like correctable ones and vice versa.

  2. 2.

Photon noise. More photons within the pupil footprints that show signal from
entrance pupil phase aberration as intensity variations increases the signal-
to-noise ratio (S/N) of a given wavefront error proportional to the square
root of the number of photons. A higher S/N WFS measurement of a given
wavefront error results in less noise being propagated onto the DM from the
WFS reconstruction and ultimately a lower achievable residual wavefront error.

Also note that this same error budget analysis for the dPWFS showed the
opposite of what we presented here for the bPWFS: all error terms for the
dPWFS perform worse than the PWFS. This is consistent with the above
interpretation, illustrating that when more light is diffracted outside the
pupil footprints which would otherwise be entrance pupil phase aberrations
converted to intensity variations on the WFS detector, expected performance is
worse.

##  3 LABORATORY TESTS

###  3.1 The LOOPS Testbed

Figure 4: Preliminary Laboratory validation of the bright PWFS concept with
the LOOPS testbed at LAM, using an SLM in the focal plane to modulate the
added focal plane piston phase shift within the central 0.5 $\lambda/D$ of the
optical axis. (a) The regular PWFS (i.e., no added piston). (b) the bright
PWFS: 1.7 $\pi$ rad added piston. (c) the dark PWFS: 0.6 $\pi$ added piston.

The LOOPS—LAM (Laboratoire d’Astrophysique de Marseille)/ONERA (Office
National d’Études et de Recherches en Aérospatiales) On-sky Pyramid
Sensor—testbed is a laboratory at LAM developed to test new AO technologies,
described in Ref. 12 and references therein. Although many new AO technologies
have been deployed and tested on this bench, for the purposes of this paper
there are three relevant hardware sources on the LOOPS bench (introduced in
the order of light propagation): (1) a $\lambda$=635nm laser diode light
source conjugated at infinity, (2) a downstream 1024$\times$1280 pixel
Hamamatsu Spatial Light Modulator (SLM; LCOS-SLM X13138) conjugated to a focal
plane at f/264111See Ref. 12 for a detailed description of the steps taken to
limit SLM-based systematics (such as polarization-dependent and filling-factor
errors), ensuring custom focal plane phase shifts can be applied without
interference from these effects., and (3) a further downstream a
2048$\times$2048 pixel Hamamatsu ORCA-Flash 4.0 v2 pupil imaging detector,
sampling around 300 pixels across the pupil diameter.

###  3.2 Preliminary Results

The LOOPS focal plane SLM described in §3.1 enables applying the phase masks
for the PWFS, bPWFS, and dPWFS, with all other testbed parameters unchanged
between masks. The results of this are shown in Fig. 4. Consistent with
simulations in Fig. 1a, Fig. 4 clearly shows less light between the four
pupils for the bPWFS vs. regular PWFS and conversely more light between pupils
for the dPWFS.

##  4 DISCUSSION AND FUTURE WORK

###  4.1 Modulation and Linearity

Implementing the modulated PWFS is a key next step to validating the benefit
of the bPWFS over the PWFS. We expect that for modulation radii greater than
about 1 $\lambda/D$, the modulated bPWFS performance will be identical to the
modulated PWFS, since the bPWFS piston mask only extents radially to 0.5
$\lambda/D$. However, a key question to answer is whether or not switching
from a modulated to un-modulated bPWFS in closed-loop will enable improved
closed-loop performance. Future simulations and/or laboratory tests should
therefore investigate this further.

Alternatively, another approach to considering the benefit of the bPWFS is
it’s use as a second stage AO WFS (i.e., both a first stage AO WFS, such as a
modulated PWFS or a Shack Hartmann WFS, and a second stage bPWFS control the
same common path DM). In this configuration, although a more optically complex
system with multiple WFSs, we have essentially already demonstrated the
benefit of this approach in Fig. 3a, showing that for input 100 nm rms
realizations (i.e., ExAO-level first stage wavefront residuals) the bPWFS
consistently enables better achievable residual wavefront errors after a
second stage correction than the PWFS. However, to be fair this comparison
does not include other Fourier-based WFSs that require a diffraction-limited
input wavefront, such as the Zernike[10] or iQuad[11] WFS. Also note that a
first and second stage WFS both controlling a common DM requires a more
advanced control framework to ensure that any differential NCPA and/or
chromaticity (if the two WFSs are operating with different bandpasses) doesn’t
cause instability; Ref. 14 has investigated this problem and published
preliminary solutions that would define non-conflicting spatio-temporal
control authorities for each WFS.

###  4.2 Chromaticity and Fabrication

Two forms of wavelength-dependent wavefront evolution (i.e., chromaticity)
must be addressed in order to enable this technique operational over a
reasonable bandpass: (1) PSF magnification with wavelength on the bPWFS focal
plane phase mask and (2) scalar piston evolution with wavelength. We address
each point below.

  1. 1.

PSF magnification. In principle, a Wynne corrector[16] could remove this
effect, although it would then cause a corresponding downstream pupil
magnification with wavelength, which could then be mitigated by a second
“inverse” Wynne corrector. However, PSF magnification at 0.5 $\lambda/D$
radius is a weak effect: a $\Delta\lambda/\lambda\sim 60\%$ bandpass from
500-900 nm would move the piston masks’ radial edge between 0.65 and 0.3
$\lambda/D$ at 500 and 900 nm, respectively. This is a minimal change in
radius that would likely not significantly modify the bPWFS’s diffractive
effect, but should be invenstigated further in simulation to confirm.

  2. 2.

Scalar piston phase chromaticity. If the bPWFS were fabricated as a scalar
mask (e.g., via etching, metal deposition, and/or other similar depth-
dependent methods), the applied piston offset in radians would be chromatic:
ignoring PSF magnification effects, for the same 60% bandpass from the
previous point a 1.7$\pi$ rad phase shift at 700 nm would vary between
1.2$\pi$ and $2.2\pi=0.2\pi$ rad at 500 and 900 nm, respectively. Fig. 1b
already shows that this effect would completely un-do the bPWFS benifits, on
average over the full bandpass causing more light to be diffracted outside the
pupil footprints compared to the regular PWFS. Therefore, an achromatic phase
piston shift must be applied instead, likely requiring a “two stage” PWFS
system (i.e., one intermediate focal plane for the achromatic piston phase
mask and second separate intermediate focal plane the pyramid phase mask). At
least two phase mask technologies exist that could be used to fabricate the
above-described achromatic bPWFS piston mask: sub-wavelength gratings[17] and
liquid crystals[18].

##  5 CONCLUSION

In this paper we have introduced a new modification to the Pyramid wavefront
sensor (PWFS) phase mask called the bright PWFS (bPWFS). This bPWFS phase
mask, which simply adds a 1.7$\pi$ radian piston phase shift within a 0.5
$\lambda/D$ radius of the optical axis on top of the existing PWFS tilt
angles, leverages the diffractive nature of a Fourier-based WFS to increase
the total amount of light collected within the four PWFS pupil footprints,
described further in §2.1. Using this design, we showed the following.

  1. 1.

A simulated error budget analysis in §2.2 illustrated that the bPWFS compared
to the PWFS enables a residual wavefront error with relatively lower impact
from non-linearities, aliasing, and photon noise, all of which can be
attributed to the boosted cumulative intensity within the WFS pupil
footprints.

  2. 2.

In §3.2 we validate the bPWFS concept on the LOOPS testbed at LAM, which
includes a focal plane spatial light modulator to enable a comparison with the
same system between the PWFS and bPWFS. Recorded PWFS and bPWFS pupil images
confirm that the bPWFS increases cumulative intensity within the pupil
footprints, consistent with simulations.

Lastly, in §4 we outlined further steps to consider in deploying this
technology into real AO systems, including use of a modulation tip/tilt mirror
and/or second stage WFS (§4.1) and addressing potential issues of chromaticity
and possible optical and fabrication solutions (§4.2).

More generally, the simple additive piston phase mask design presented here
for the bPWFS is by no means fully-optimized. Numerical coronagraph design
optimization is a mature field of research[19]; similar techniques should be
explored for Fourier-based pupil plane WFS design (e.g., considering options
for complex phase masks, multiple pupil and/or focal planes, etc., analagous
to current numerical approaches to coronagraph design), with the difference
that measurement errors, non-linearities, aliasing, and other error budget
terms be optimally minimized (i.e., in contrast to minimizing stellar
throughput while maximizing exoplanet throughput for coronagraph design
techniques).

## Acknowledgments

We gratefully acknowledge research support of the University of California
Observatories for funding this research. We thank Benoît Neichel, Dominic
Sanchez, Phil Hinz, Thiery Fusco, Maaike van Kooten, and Jules Fowler for
comments, suggestions, and discussions that have contributed to this
manuscript.

## References

  * [1] Herriot, G. and Morris, S., “Gemini Adaptive Optics System,” in [Optical Telescopes of Today and Tomorrow ], Ardeberg, A. L., ed., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 2871, 816–826 (Mar. 1997).
  * [2] Poyneer, L. A., Palmer, D. W., Macintosh, B., Savransky, D., Sadakuni, N., Thomas, S., Véran, J.-P., Follette, K. B., Greenbaum, A. Z., Mark Ammons, S., Bailey, V. P., Bauman, B., Cardwell, A., Dillon, D., Gavel, D., Hartung, M., Hibon, P., Perrin, M. D., Rantakyrö, F. T., Sivaramakrishnan, A., and Wang, J. J., “Performance of the Gemini Planet Imager’s adaptive optics system,” Applied Optics 55, 323 (Jan. 2016).
  * [3] Fusco, T., Sauvage, J. F., Mouillet, D., Costille, A., Petit, C., Beuzit, J. L., Dohlen, K., Milli, J., Girard, J., Kasper, M., Vigan, A., Suarez, M., Soenke, C., Downing, M., N’Diaye, M., Baudoz, P., Sevin, A., Baruffolo, A., Schmid, H. M., Salasnich, B., Hugot, E., and Hubin, N., “SAXO, the SPHERE extreme AO system: on-sky final performance and future improvements,” in [Adaptive Optics Systems V ], Marchetti, E., Close, L. M., and Véran, J.-P., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 9909, 99090U (July 2016).
  * [4] Macintosh, B., Graham, J. R., Barman, T., De Rosa, R. J., Konopacky, Q., Marley, M. S., Marois, C., Nielsen, E. L., Pueyo, L., Rajan, A., Rameau, J., Saumon, D., Wang, J. J., Patience, J., Ammons, M., Arriaga, P., Artigau, E., Beckwith, S., Brewster, J., Bruzzone, S., Bulger, J., Burningham, B., Burrows, A. S., Chen, C., Chiang, E., Chilcote, J. K., Dawson, R. I., Dong, R., Doyon, R., Draper, Z. H., Duchêne, G., Esposito, T. M., Fabrycky, D., Fitzgerald, M. P., Follette, K. B., Fortney, J. J., Gerard, B., Goodsell, S., Greenbaum, A. Z., Hibon, P., Hinkley, S., Cotten, T. H., Hung, L. W., Ingraham, P., Johnson-Groh, M., Kalas, P., Lafreniere, D., Larkin, J. E., Lee, J., Line, M., Long, D., Maire, J., Marchis, F., Matthews, B. C., Max, C. E., Metchev, S., Millar-Blanchaer, M. A., Mittal, T., Morley, C. V., Morzinski, K. M., Murray-Clay, R., Oppenheimer, R., Palmer, D. W., Patel, R., Perrin, M. D., Poyneer, L. A., Rafikov, R. R., Rantakyrö, F. T., Rice, E. L., Rojo, P., Rudy, A. R., Ruffio, J. B., Ruiz, M. T., Sadakuni, N., Saddlemyer, L., Salama, M., Savransky, D., Schneider, A. C., Sivaramakrishnan, A., Song, I., Soummer, R., Thomas, S., Vasisht, G., Wallace, J. K., Ward-Duong, K., Wiktorowicz, S. J., Wolff, S. G., and Zuckerman, B., “Discovery and spectroscopy of the young jovian planet 51 Eri b with the Gemini Planet Imager,” Science 350, 64–67 (Oct. 2015).
  * [5] Nielsen, E. L., De Rosa, R. J., Macintosh, B., Wang, J. J., Ruffio, J.-B., Chiang, E., Marley, M. S., Saumon, D., Savransky, D., Ammons, S. M., Bailey, V. P., Barman, T., Blain, C., Bulger, J., Burrows, A., Chilcote, J., Cotten, T., Czekala, I., Doyon, R., Duchêne, G., Esposito, T. M., Fabrycky, D., Fitzgerald, M. P., Follette, K. B., Fortney, J. J., Gerard, B. L., Goodsell, S. J., Graham, J. R., Greenbaum, A. Z., Hibon, P., Hinkley, S., Hirsch, L. A., Hom, J., Hung, L.-W., Dawson, R. I., Ingraham, P., Kalas, P., Konopacky, Q., Larkin, J. E., Lee, E. J., Lin, J. W., Maire, J., Marchis, F., Marois, C., Metchev, S., Millar-Blanchaer, M. A., Morzinski, K. M., Oppenheimer, R., Palmer, D., Patience, J., Perrin, M., Poyneer, L., Pueyo, L., Rafikov, R. R., Rajan, A., Rameau, J., Rantakyrö, F. T., Ren, B., Schneider, A. C., Sivaramakrishnan, A., Song, I., Soummer, R., Tallis, M., Thomas, S., Ward-Duong, K., and Wolff, S., “The Gemini Planet Imager Exoplanet Survey: Giant Planet and Brown Dwarf Demographics from 10 to 100 au,” Astronomical Journal 158, 13 (July 2019).
  * [6] Ragazzoni, R., “Pupil plane wavefront sensing with an oscillating prism,” Journal of Modern Optics 43, 289–293 (Feb. 1996).
  * [7] Correia, C. M., Fauvarque, O., Bond, C. Z., Chambouleyron, V., Sauvage, J.-F., and Fusco, T., “Performance limits of adaptive-optics/high-contrast imagers with pyramid wavefront sensors,” Monthly Notices of the Royal Astronomical Society 495, 4380–4391 (July 2020).
  * [8] Fauvarque, O., Neichel, B., Fusco, T., Sauvage, J.-F., and Girault, O., “General formalism for Fourier-based wave front sensing,” Optica 3, 1440 (Dec. 2016).
  * [9] Zernike, F., “Diffraction theory of the knife-edge test and its improved form, the phase-contrast method,” Monthly Notices of the Royal Astronomical Society 94, 377–384 (Mar. 1934).
  * [10] Chambouleyron, V., Fauvarque, O., Sauvage, J. F., Dohlen, K., Levraud, N., Vigan, A., N’Diaye, M., Neichel, B., and Fusco, T., “Variation on a Zernike wavefront sensor theme: Optimal use of photons,” Astronomy and Astrophysics 650, L8 (June 2021).
  * [11] Fauvarque, O., Hutterer, V., Janin-Potiron, P., Duboisset, J., Correia, C., Neichel, B., Sauvage, J. F., Fusco, T., Shatokhina, I., Ramlau, R., Chambouleyron, V., and Brûlé, Y., “The ıQuad sensor: a new Fourier-based wave front sensor derived from the 4 quadrants coronagraph,” Proc. AO4ELT6 401-Pdyj-81 (2019).
  * [12] Janin-Potiron, P., Chambouleyron, V., Schatz, L., Fauvarque, O., Bond, C. Z., Abautret, Y., Muslimov, E., El-Hadi, K., Sauvage, J.-F., Dohlen, K., Neichel, B., Correia, C. M., and Fusco, T., “Adaptive optics with programmable Fourier-based wavefront sensors: a spatial light modulator approach to the LAM/ONERA on-sky pyramid sensor testbed,” Journal of Astronomical Telescopes, Instruments, and Systems 5, 039001 (July 2019).
  * [13] Roddier, F. and Roddier, C., “Stellar Coronograph with Phase Mask,” Publications of the Astronomical Society of the Pacific 109, 815–820 (July 1997).
  * [14] Gerard, B. L., Véran, J.-P., Singh, G., Herriot, G., Lardière, O., and Marois, C., “Fast focal plane wavefront sensing as a second stage adaptive optics wavefront sensor,” in [Adaptive Optics Systems VII ], Schreiber, L., Schmidt, D., and Vernet, E., eds., 11448, 483 – 499, International Society for Optics and Photonics, SPIE (2021).
  * [15] Vigan, A., N’Diaye, M., Dohlen, K., Sauvage, J. F., Milli, J., Zins, G., Petit, C., Wahhaj, Z., Cantalloube, F., Caillat, A., Costille, A., Le Merrer, J., Carlotti, A., Beuzit, J. L., and Mouillet, D., “Calibration of quasi-static aberrations in exoplanet direct-imaging instruments with a Zernike phase-mask sensor. III. On-sky validation in VLT/SPHERE,” A&A 629, A11 (Sept. 2019).
  * [16] Wynne, C. G., “Extending the bandwidth of speckle interferometry.,” Optics Communications 28, 21–25 (1979).
  * [17] König, L., Absil, O., Delacroix, C., Lobet, M., Karlsson, M., Vargas Catalán, E., Orban de Xivry, G., Loicq, J., and Habraken, S., “Vortex phase masks of topological charge 4 and higher with diamond subwavelength gratings,” in [Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series ], Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 11451, 1145144 (Dec. 2020).
  * [18] Doelman, D. S., Snik, F., Por, E. H., Bos, S. P., Otten, G. P. P. L., Kenworthy, M., Haffert, S. Y., Wilby, M., Bohn, A. J., Sutlieff, B. J., Miller, K., Ouellet, M., de Boer, J., Keller, C. U., Escuti, M. J., Shi, S., Warriner, N. Z., Hornburg, K., Birkby, J. L., Males, J., Morzinski, K. M., Close, L. M., Codona, J., Long, J., Schatz, L., Lumbres, J., Rodack, A., Van Gorkom, K., Hedglen, A., Guyon, O., Lozi, J., Groff, T., Chilcote, J., Jovanovic, N., Thibault, S., de Jonge, C., Allain, G., Vallée, C., Patel, D., Côté, O., Marois, C., Hinz, P., Stone, J., Skemer, A., Briesemeister, Z., Boehle, A., Glauser, A. M., Taylor, W., Baudoz, P., Huby, E., Absil, O., Carlomagno, B., and Delacroix, C., “Vector-apodizing phase plate coronagraph: design, current performance, and future development [Invited],” Applied Optics 60, D52 (July 2021).
  * [19] Ruane, G., Riggs, A., Mazoyer, J., Por, E. H., N’Diaye, M., Huby, E., Baudoz, P., Galicher, R., Douglas, E., Knight, J., Carlomagno, B., Fogarty, K., Pueyo, L., Zimmerman, N., Absil, O., Beaulieu, M., Cady, E., Carlotti, A., Doelman, D., Guyon, O., Haffert, S., Jewell, J., Jovanovic, N., Keller, C., Kenworthy, M. A., Kuhn, J., Miller, K., Sirbu, D., Snik, F., Wallace, J. K., Wilby, M., and Ygouf, M., “Review of high-contrast imaging systems for current and future ground- and space-based telescopes I: coronagraph design methods and optical performance metrics,” in [Space Telescopes and Instrumentation 2018: Optical, Infrared, and Millimeter Wave ], Lystrup, M., MacEwen, H. A., Fazio, G. G., Batalha, N., Siegler, N., and Tong, E. C., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 10698, 106982S (Aug. 2018).