In this work, we present a sampling algorithm for single hidden layer neural networks. This algorithm is built upon a recursive series of Bayesian posteriors using a method we call Greedy Bayes. Sampling of the Bayesian posterior for neuron weight vectors$w$of dimension$d$is challenging because of its multimodality. Our algorithm to tackle this problem is based on a coupling of the posterior density for$w$with an auxiliary random variable ξ. The resulting reverse conditional$w$| ξ of neuron weights given auxiliary random variable is shown to be log concave. In the construction of the posterior distributions we provide some freedom in the choice of the prior. In particular, for Gaussian priors on$w$with suitably small variance, the resulting marginal density of the auxiliary variable ξ is proven to be strictly log concave for all dimensions$d$. For a uniform prior on the unit$\ell_{1}$ball, evidence is given that the density of ξ is again strictly log concave for sufficiently large$d$. The score of the marginal density of the auxiliary random variable ξ is determined by an expectation over$w$| ξ and thus can be computed by various rapidly mixing Markov Chain Monte Carlo methods. Moreover, the computation of the score of ξ permits methods of sampling ξ by a stochastic diffusion (Langevin dynamics) with drift function built from this score. With such dynamics, information-theoretic methods pioneered by Bakry and Emery show that accurate sampling of ξ is obtained rapidly when its density is indeed strictly log-concave. After which, one more draw from w|ξ, produces neuron weights$w$whose marginal distribution is from the desired posterior.

The MDL estimators for density estimation, which are defined by two-part codes for universal coding, are analyzed. We give a two-part code for mixture families whose regret is close to the minimax regret, where regret of a code with respect to a target family ℳ is the difference between the codelength of the code and the ideal codelength achieved by an element in ℳ. Our code is constructed using a probability density in an enlarged family of ℳ (a bundle of local exponential families of ℳ) for data description. This result gives a tight upper bound on the risk of the MDL estimator defined by the two-part code, based on the theory introduced by Barron and Cover in 1991.

We establish L∞and L2error bounds for functions of many variables that are approximated by linear combinations of rectified linear unit (ReLU) and squared ReLU ridge functions with ℓ1and ℓ0controls on their inner and outer parameters. With the squared ReLU ridge function, we show that the L2approximation error is inversely proportional to the inner layer ℓ0sparsity and it need only be sublinear in the outer layer ℓ0sparsity. Our constructions are obtained using a variant of the Maurey-Jones-Barron probabilistic method, which can be interpreted as either stratified sampling with proportionate allocation or two-stage cluster sampling. We also provide companion error lower bounds that reveal near optimality of our constructions. Despite the sparsity assumptions, we showcase the richness and flexibility of these ridge combinations by defining a large family of functions, in terms of certain spectral conditions, that are particularly well approximated by them.

Estimation of functions of d variables is considered using ridge combinations of the form Σm k=1 c 1, k φ(Σd j=1 c 0, j, k x j -b k ) where the activation function φ is a function with bounded value and derivative. These include single-hidden layer neural networks, polynomials, and sinusoidal models. From a sample of size n of possibly noisy values at random sites X ∊ B = [−1, 1]d, the minimax mean square error is examined for functions in the closure of the l 1 hull of ridge functions with activation ϕ. It is shown to be of order d/n to a fractional power (when d is of smaller order than n), and to be of order (log d)/n to a fractional power (when d is of larger order than n). Dependence on constraints v 0 and v 1 on the l 1 norms of inner parameter co and outer parameter c 1 , respectively, is also examined. Also, lower and upper bounds on the fractional power are given. The heart of the analysis is development of information-theoretic packing numbers for these classes of functions.

This paper introduces a convenient strategy for coding and predicting sequences of independent, identically distributed random variables generated from a large alphabet of size m. In particular, the size of the sample is allowed to be variable. The employment of a Poisson model and tilting method simplifies the implementation and analysis through independence. The resulting strategy is optimal within the class of distributions satisfying a moment condition, and it is close to optimal for the class of all i.i.d distributions on strings of a given length. The method also can be used to code and predict strings with a condition on the tail of the ordered counts, and it can be applied to distributions in an envelope class. Moreover, we show that our model permits exact computation of the minimax optimal code, for all alphabet sizes, when conditioning on the size of the sample.

The normalized maximized likelihood (NML) provides the minimax regret solution in universal data compression, gambling, and prediction, and it plays an essential role in the minimum description length (MDL) method of statistical modeling and estimation. Here we show that when the sample space is finite, a generic condition on the linear independence of the component models implies that the normalized maximum likelihood has an exact Bayes-like representation as a mixture of the component models, even in finite samples, though the weights of linear combination may be both positive and negative. This addresses in part the relationship between MDL and Bayes modeling. The representation also has the practical advantage of speeding the calculation of marginals and conditionals required for coding and prediction applications.

Building upon past work, which developed information theoretic notions of when a penalized likelihood procedure can be interpreted as codelengths arising from a two stage code and when the statistical risk of the procedure has a redundancy risk bound, we present new results and risk bounds showing that the l1penalty in Gaussian Graphical Models fits the above story. We also show how the traditional l0penalty times plus lower order terms which stay bounded on the whole parameter space has a conditional two stage description length interpretation.

We study the problems of data compression, gambling and prediction of a string xn= x1x2...xnfrom an alphabet X, in terms of regret with respect to models with hidden variables including general mixture families. When the target class is a non-exponential family, a modification of Jeffreys prior which has measure outside the given family of densities was introduced to achieve the minimax regret [8], under certain regularity conditions. In this paper, we show that the models with hidden variables satisfy those regularity conditions, when the hidden variables' model is an exponential family. In paticular, we do not have to restrict the class of data strings so that the MLE is in the interior of the parameter space for the case of the general mixture family.

This paper considers coding and predicting sequences of random variables generated from a large alphabet. We start from the i.i.d model and propose a simple coding distribution formulated by a product of tilted Poisson distributions which achieves close to optimal performance. Then we extend to Markov models, and in particular, tree sources. A context tree based algorithm is designed according to the frequency of various contexts in the data. It is a greedy algorithm which seeks for the greatest savings in codelength when constructing the tree. Compression and prediction of individual counts associated with the contexts again uses a product of tilted Poisson distributions. Implementing this method on a Chinese novel, about 20.56% savings in codelength is achieved compared to the i.i.d model.

We study the problem of data compression, gambling and prediction of strings xn= x1x2...xnin terms of coding regret, where the tree model is assumed as a target class. We apply the minimax Bayes strategy for curved exponential families to this problem and show that it achieves the minimax regret without restriction on the data strings. This is an extension of the minimax result by (Takeuchi et al. 2013) for models of kth order Markov chains and determines the constant term of the Stochastic Complexity for the tree model.

For the additive white Gaussian noise channel with average codeword power constraint, sparse superposition codes are developed. These codes are based on the statistical high-dimensional regression framework. In a previous paper, we investigated decoding using the optimal maximum-likelihood decoding scheme. Here, a fast decoding algorithm, called the adaptive successive decoder, is developed. For any rate R less than the capacity C, communication is shown to be reliable with nearly exponentially small error probability. Specifically, for blocklength n, it is shown that the error probability is exponentially small in n/logn.

We study the problems of data compression, gambling and prediction of a sequence xn= x1x2...xnfrom an alphabet X, in terms of regret with respect to various families of probability distributions. It is known that the regret of the Bayes mixture with respect to a general exponential families asymptotically achieves the minimax value when variants of Jeffreys prior are used, under the condition that the maximum likelihood estimate is in the interior of the parameter space. We discuss a modification of Jeffreys prior which has measure outside the given family of densities, to achieve minimax regret with respect to non-exponential type families, e.g. curved exponential families and mixture families. These results also provide characterization of Rissanen's stochastic complexity for those classes.

We discuss the properties of Jeffreys mixture for a Markov model. First, we show that a modified Jeffreys mixture asymptotically achieves the minimax coding regret for universal data compression, where we do not put any restriction on data sequences. Moreover, we give an approximation formula for the prediction probability of Jeffreys mixture for a Markov model. By this formula, it is revealed that the prediction probability by Jeffreys mixture for the Markov model with alphabet$\{0,1\}$is not of the form$(n_{x \vert s}+\alpha)/(n_{s}+\beta)$, where$n_{x \vert s}$is the number of occurrences of the symbol$x$following the context$s \in \{0,1\}$and$n_{s}=n_{0 \vert s}+n_{1 \vert s}$. Moreover, we propose a method to compute our minimax strategy, which is a combination of a Monte Carlo method and the approximation formula, where the former is used for earlier stages in the data, while the latter is used for later stages.

Recently sparse superposition codes with iterative term selection have been developed which are mathematically proven to be fast and reliable at any rate below the capacity for the additive white Gaussian noise channel with power control. We improve the performance using a soft decision decoder with Bayes optimal statistics at each iteration, followed by thresholding only at the final step. This presentation includes formulation of the statistics, proof of their distributions, numerical simulations of the performance improvement, and useful identities relating a squared error risk to a posterior probability of error.

For the additive white Gaussian noise channel with average codeword power constraint, coding methods are analyzed in which the codewords are sparse superpositions, that is, linear combinations of subsets of vectors from a given design, with the possible messages indexed by the choice of subset. Decoding is by least squares (maximum likelihood), tailored to the assumed form of codewords being linear combinations of elements of the design. Communication is shown to be reliable with error probability exponentially small for all rates up to the Shannon capacity.

This paper investigates polar coding schemes achieving capacity for the AWGN channel. The approaches using a multiple access channel with a large number of binary-input users and a single-user channel with a large prime-cardinality input are compared with respect to complexity attributes. The problem of finding discrete approximations to the Gaussian input is then investigated, and it is shown that a quantile quantizer achieves a gap to capacity which decreases like 1/q (where q is the number of constellation points), improving on the 1/log(q) decay achieved with a binomial (central limit theorem) quantizer.

Sparse superposition codes with a fast adaptive successive decoder for the additive white Gaussian noise channel were introduced last year by the authors, along with presentation of reliability at rates approaching capacity. The present work presents ingredients of the distributional analysis of the decoder.

Sparse superposition codes are developed for the additive white Gaussian noise channel with average codeword power constraint. Codewords are linear combinations of subsets of vectors, with the possible messages indexed by the choice of subset. Decoding is by least squares, tailored to the assumed form of linear combination. Communication is shown to be reliable with error probability exponentially small for all rates up to the Shannon capacity.

For the additive Gaussian noise channel with average codeword power constraint, sparse superposition codes and adaptive successive decoding is developed. Codewords are linear combinations of subsets of vectors, with the message indexed by the choice of subset. A feasible decoding algorithm is presented. Communication is reliable with error probability exponentially small for all rates below the Shannon capacity.

Consider a situation involving many sources of finite-length data, with buyers potentially interested in purchasing data from any bundle (subset) of the sources. A principled way is presented to assign a price to each source, when the value of the data is measured in terms of how much information about an underlying location parameter can be extracted from it. Apart from the operational relevance to data pricing, these results also have relevance to sensor network theory.

We determine, for both countable and uncountable collections of functions, information-theoretic conditions on a penalty pen(f) such that the optimizer f of the penalized log likelihood criterion log 1/likelihood(f)+pen(f) has risk not more than the index of resolvability corresponding to the accuracy of the optimizer of the expected value of the criterion. If F is the linear span of a dictionary of functions, traditional description-length penalties are based on the number of non-zero terms (the lscr0norm of the coefficients). We specialize our general conclusions to show the lscr1norm of the coefficients times a suitable multiplier lambda is also an information-theoretically valid penalty.

New families of Fisher information and entropy power inequalities for sums of independent random variables are presented. These inequalities relate the information in the sum of n independent random variables to the information contained in sums over subsets of the random variables, for an arbitrary collection of subsets. As a consequence, a simple proof of the monotonicity of information in central limit theorems is obtained, both in the setting of independent and identically distributed (i.i.d.) summands as well as in the more general setting of independent summands with variance-standardized sums.

We provide a simple proof of the monotonicity of information in the central limit theorem for i.i.d. summands. Extensions to the more general case of independent, not identically distributed summands are also presented. New families of Fisher information and entropy power inequalities are discussed

For Gaussian regression, we develop and analyze methods for combining estimators from various models. For squared-error loss, an unbiased estimator of the risk of the mixture of general estimators is developed. Special attention is given to the case that the component estimators are least-squares projections into arbitrary linear subspaces, such as those spanned by subsets of explanatory variables in a given design. We relate the unbiased estimate of the risk of the mixture estimator to estimates of the risks achieved by the components. This results in simple and accurate bounds on the risk and its estimate, in the form of sharp and exact oracle inequalities. That is, without advance knowledge of which model is best, the resulting performance is comparable to or perhaps even superior to what is achieved by the best of the individual models. Furthermore, in the case that the unknown parameter has a sparse representation, our mixture estimator adapts to the underlying sparsity. Simulations show that the performance of these mixture estimators is better than that of a related model-selection estimator which picks a model with the highest weight. Also, the connection between our mixtures with Bayes procedures is discussed

For Gaussian regression, we develop and analyse methods for combining estimators from various models. For squared-error loss, an unbiased estimator of the risk of a mixture of general estimators is developed. Special attention is given to the case that the components are least-squares projections into arbitrary linear subspaces. We relate the unbiased risk estimate for the mixture estimator to estimates of the risks achieved by the components. This results in accurate bounds on the risk and its unbiased estimate - without advance knowledge of which model is best, the resulting performance is comparable to what is achieved by the best of the individual models

For location and scale families of distributions and related settings of linear regression, we determine minimax procedures for predictive density estimation, for universal data compression, and for the minimum description length (MDL) criterion for model selection. The analysis gives the best invariant and indeed minimax procedure for predictive density estimation by directly verifying extended Bayes properties or, alternatively, by general aspects of decision theory on groups which are shown to simplify in the case of Kullback-Leibler loss. An exact minimax rule is generalized Bayes using a uniform (Lebesgue measure) prior on the location and log-scale parameters, which is made proper by conditioning on an initial set of observations.

For problems of data compression, gambling, and prediction of individual sequences x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/ the following questions arise. Given a target family of probability mass functions p(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/|/spl theta/), how do we choose a probability mass function q(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/) so that it approximately minimizes the maximum regret/belowdisplayskip10ptminus6pt max (log1/q(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/)-log1/p(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/|/spl theta//spl circ/)) and so that it achieves the best constant C in the asymptotics of the minimax regret, which is of the form (d/2)log(n/2/spl pi/)+C+o(1), where d is the parameter dimension? Are there easily implementable strategies q that achieve those asymptotics? And how does the solution to the worst case sequence problem relate to the solution to the corresponding expectation version min/sub q/ max/sub 0/ E/sub 0/(log1/q(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/)-log1/p(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/|/spl theta/))? In the discrete memoryless case, with a given alphabet of size m, the Bayes procedure with the Dirichlet(1/2, /spl middot//spl middot//spl middot/, 1/2) prior is asymptotically maximin. Simple modifications of it are shown to be asymptotically minimax. The best constant is C/sub m/=log(/spl Gamma/(1/2)/sup m//(/spl Gamma/(m/2)) which agrees with the logarithm of the integral of the square root of the determinant of the Fisher information. Moreover, our asymptotically optimal strategies for the worst case problem are also asymptotically optimal for the expectation version. Analogous conclusions are given for the case of prediction, gambling, and compression when, for each observation, one has access to side information from an alphabet of size k. In this setting the minimax regret is shown to be k(m-1)/2logn/2/spl pi/k+kC/sub m/+o(1).

We deal with function estimation by neural networks. Mean square error bounds are given for the case when the target function is in the convex hull of ellipsoids multiplied by a scalar constant. When the target function is not in this class but is bounded, we bound the difference between the mean square prediction error compared to the best approximation error of the target function (the expected regret). We also give a general theorem that gives the convergence rate of the expected regret when the functions are estimated by penalized least squares criteria.

We review the principles of minimum description length and stochastic complexity as used in data compression and statistical modeling. Stochastic complexity is formulated as the solution to optimum universal coding problems extending Shannon's basic source coding theorem. The normalized maximized likelihood, mixture, and predictive codings are each shown to achieve the stochastic complexity to within asymptotically vanishing terms. We assess the performance of the minimum description length criterion both from the vantage point of quality of data compression and accuracy of statistical inference. Context tree modeling, density estimation, and model selection in Gaussian linear regression serve as examples.

Probability models are estimated by use of penalized log-likelihood criteria related to Akaike (1973) information criterion (AIC) and minimum description length (MDL). The accuracies of the density estimators are shown to be related to the tradeoff between three terms: the accuracy of approximation, the model dimension, and the descriptive complexity of the model classes. The asymptotic risk is determined under conditions on the penalty term, and is shown to be minimax optimal for some cases. As an application, we show that the optimal rate of convergence is simultaneously achieved for log-densities in Sobolev spaces W/sub 2//sup s/(U) without knowing the smoothness parameter s and norm parameter U in advance. Applications to neural network models and sparse density function estimation are also provided.

Let X/sup n/=(X/sub 1/,...,X/sub n/) be a memoryless source with unknown distribution on a finite alphabet of size k. We identify the asymptotic minimax coding redundancy for this class of sources, and provide a sequence of asymptotically minimax codes. Equivalently, we determine the limiting behavior of the minimax relative entropy min/sub QXn/ max/sub pXn/ D(P/sub Xn//spl par/Q/sub Xn/), where the maximum is over all independent and identically distributed (i.i.d.) source distributions and the minimum is over all joint distributions. We show in this paper that the minimax redundancy minus ((k-1)/2) log(n/(2/spl pi/e)) converges to log/spl int//spl radic/(det I(/spl theta/))d/spl theta/=log (/spl Gamma/(1/2)/sup k///spl Gamma/(k/2)), where I(/spl theta/) is the Fisher information and the integral is over the whole probability simplex. The Bayes strategy using Jeffreys' prior is shown to be asymptotically maximin but not asymptotically minimax in our setting. The boundary risk using Jeffreys' prior is higher than that of interior points. We provide a sequence of modifications of Jeffreys' prior that put some prior mass near the boundaries of the probability simplex to pull down that risk to the asymptotic minimax level in the limit.

Approximation properties of a class of artificial neural networks are established. It is shown that feedforward networks with one layer of sigmoidal nonlinearities achieve integrated squared error of order O(1/n), where n is the number of nodes. The approximated function is assumed to have a bound on the first moment of the magnitude distribution of the Fourier transform. The nonlinear parameters associated with the sigmoidal nodes, as well as the parameters of linear combination, are adjusted in the approximation. In contrast, it is shown that for series expansions with n terms, in which only the parameters of linear combination are adjusted, the integrated squared approximation error cannot be made smaller than order 1/n/sup 2/d/ uniformly for functions satisfying the same smoothness assumption, where d is the dimension of the input to the function. For the class of functions examined, the approximation rate and the parsimony of the parameterization of the networks are shown to be advantageous in high-dimensional settings.>

The problem of the nonparametric estimation of a probability distribution is considered from three viewpoints: the consistency in total variation, the consistency in information divergence, and consistency in reversed-order information divergence. These types of consistencies are relatively strong criteria of convergence, and a probability distribution cannot be consistently estimated in either type of convergence without any restrictions on the class of probability distributions allowed. Histogram-based estimators of distribution are presented which, under certain conditions, converge in total variation, in information divergence, and in reversed-order information divergence to the unknown probability distribution. Some a priori information about the true probability distribution is assumed in each case. As the concept of consistency in information divergence is stronger than that of convergence in total variation, additional assumptions are imposed in the cases of informational divergences.>

The authors introduce an index of resolvability that is proved to bound the rate of convergence of minimum complexity density estimators as well as the information-theoretic redundancy of the corresponding total description length. The results on the index of resolvability demonstrate the statistical effectiveness of the minimum description-length principle as a method of inference. The minimum complexity estimator converges to true density nearly as fast as an estimator based on prior knowledge of the true subclass of densities. Interpretations and basic properties of minimum complexity estimators are discussed. Some regression and classification problems that can be examined from the minimum description-length framework are considered.>

In the absence of knowledge of the true density function, Bayesian models take the joint density function for a sequence of n random variables to be an average of densities with respect to a prior. The authors examine the relative entropy distance D/sub n/ between the true density and the Bayesian density and show that the asymptotic distance is (d/2)(log n)+c, where d is the dimension of the parameter vector. Therefore, the relative entropy rate D/sub n//n converges to zero at rate (log n)/n. The constant c, which the authors explicitly identify, depends only on the prior density function and the Fisher information matrix evaluated at the true parameter value. Consequences are given for density estimation, universal data compression, composite hypothesis testing, and stock-market portfolio selection.>

It is shown that each bit of information at most doubles the resulting wealth in the general stock-market setup. This information bound on the growth of wealth is actually attained for certain probability distributions on the market investigated by J. Kelly (1956). The bound is shown to be a special case of the result that the increase in exponential growth of wealth achieved with true knowledge of the stock market distribution F over that achieved with incorrect knowledge G is bounded above by the entropy of F relative to G.>