To investigate the theoretical foundations of deep learning from the view points of the minimum description length (MDL) principle, we analyse the risk bounds on MDL estimators for simple two-layers neural networks (NNs) with ReLU activation. For that purpose, we construct a two-stage code with small redundancy based on the fact that the eigenvalue distribution of the Fisher information matrix of the NNs is strongly biased, which was recently shown by Takeishi et al. (2023). This means that the MDL estimator induced by the two-stage code enjoys a tight upper bound on its risk, which is a direct consequence of the theory on MDL estimators originated by Barron and Cover (1991). The target NNs consist of$d$nodes in the input layer,$p$nodes in the hidden layer, and one output node. The object of estimation is only the$p$weights from the hidden layer to the output node. In the context of the large-scale neural networks of interest to us, it is assumed that$p\gg d$. Note that the leading term of our risk bound is$O(d^{2}\log n/n)$, independent of$p$.

We argue the Fisher information matrix (FIM) of one hidden layer networks with the ReLU activation function. For a network, let W denote the d×p weight matrix from the d-dimensional input to the hidden layer consisting of p neurons, and v the p-dimensional weight vector from the hidden layer to the scalar output. We focus on the FIM of v, which we denote as I. Under certain conditions, we characterize the first three clusters of eigenvalues and eigenvectors of the FIM. Specifically, we show that the following approximately holds. (1) Since I is non-negative owing to the ReLU, the first eigenvalue is the Perron-Frobenius eigenvalue. (2) For the cluster of the next maximum values, the eigenspace is spanned by the row vectors of W. (3) The direct sum of the eigenspace of the first eigenvalue and that of the third cluster is spanned by the set of all the vectors obtained as the Hadamard product of any pair of the row vectors of W. We confirmed by numerical calculation that the above is approximately correct when the number of hidden nodes is about 10000.

Fisher information of simple neural networks with the softplus activation function is argued. We show that, under certain conditions, FIMs of simple models have the similar interesting spectral structure as the one shown by Takeishi et al (2021) for networks with ReLU. This work helps us to understand why the FIM has such the structure.

For the additive white Gaussian noise channel with average power constraint, it is shown that sparse superposition codes, proposed by Barron and Joseph in 2010, achieve the capacity. We study the upper bounds on its block error probability with least squares decoding when a dictionary with which we make codewords is drawn from an unbiased Bernoulli distribution. We improve the upper bounds shown by Takeishi et.al. in 2014 with fairly simplified form.

For the additive white Gaussian noise channel with average power constraint, sparse superposition codes with least squares decoding are proposed by Barron and Joseph in 2010. The codewords are designed by using a dictionary each entry of which is drawn from a Gaussian distribution. The error probability is shown to be exponentially small for all rates up to the capacity. This paper proves that when each entry of the dictionary is drawn from a Bernoulli distribution, the error probability is also exponentially small for all rates up to the capacity. The proof is via a central limit theorem-type inequality, which we show for this analysis.

For the additive white Gaussian noise channel with average power constraint, sparse superposition codes with least squares decoding were proposed by Barron and Joseph in 2010. The codewords are designed by using a dictionary which is drawn from a Gaussian distribution. The error probability is shown to be exponentially small in code length for all rates up to the capacity. This paper proves that when the dictionary is drawn from a Bernoulli distribution, the error probability is also exponentially small for all rates up to the capacity.