The problem of approximating locally smooth multivariate functions by linear combinations of elements from an affine-invariant redundant dictionary is considered. Augmenting previous upper bound results for approximation, we establish lower bounds on the performance of such schemes. The lower bounds are tight to within a logarithmic factor in the number of elements used in the approximation. Using a previously introduced notion of nonlinear approximation, we show that the approximation ability may be completely characterized by the pseudodimension of the approximation space with respect to a finite set of points. This result establishes a useful link between the problems of approximation and estimation, or learning, the latter often being conveniently characterized, at least in terms of upper bounds, by the pseudodimension.

The problem of approximating functions by neural networks using incremental algorithms is studied. For functions belonging to a rather general class, characterized by certain smoothness properties with respect to the L2 norm, we compute upper bounds on the approximation error where error is measured by the Lq norm, 1< or =q< or =infinity. These results extend previous work, applicable in the case q=2, and provide an explicit algorithm to achieve the derived approximation error rate. In the range q< or =2 near-optimal rates of convergence are demonstrated. A gap remains, however, with respect to a recently established lower bound in the case q>2, although the rates achieved are provably better than those obtained by optimal linear approximation. Extensions of the results from the L2 norm to Lp are also discussed. A further interesting conclusion from our results is that no loss of generality is suffered using networks with positive hidden-to-output weights. Moreover, explicit bounds on the size of the hidden-to-output weights are established, which are sufficient to guarantee the established convergence rates.

Upper and lower bounds are presented for the distortion of the optimal N-point vector quantizer applied to k-dimensional signals. Under certain smoothness conditions on the source distribution, the bounds are shown to hold for each and every value of N, the codebook size. These results extend bounds derived in the high-resolution limit, which assume that the number of code vectors is arbitrarily large. Two approaches to the upper bound are presented. The first, constructive construction, achieves the correct asymptotic rate of convergence as well as the correct dependence on the source density, although leading to an inferior value for the constant. The second construction, based on a random coding argument, is shown to additionally achieve a value of the constant which is much closer to the best known result derived within the asymptotic theory. Lower bound results derived in the correspondence are again shown to possess the correct asymptotic form and yield a constant which is almost indistinguishable from the best value achieved in the asymptotic regime. Finally, application of the results to the problem of source coding yields upper bounds on the distortion rate function for a wide class of processes.

We compute upper and lower bounds on the VC dimension and pseudo-dimension of feedforward neural networks composed of piecewise polynomial activation functions. We show that if the number of layers is fixed, then the VC dimension and pseudo-dimension grow as WlogW, where W is the number of parameters in the network. This result stands in opposition to the case where the number of layers is unbounded, in which case the VC dimension and pseudo-dimension grow as W2. We combine our results with recently established approximation error rates and determine error bounds for the problem of regression estimation by piecewise polynomial networks with unbounded weights.

We examine some mathematical aspects of learning unknown mappings with the mixture of experts model (MEM). Specifically, we observe that the MEM is at least as powerful as a class of neural networks, in a sense that will be made precise. Upper bounds on the approximation error are established for a wide class of target functions. The general theorem states that /spl par/f-f/sub n//spl par//sub p//spl les/c/n/sup r/d/ for f/spl isin/W/sub p//sup r/(L) (a Sobolev class over [-1,1]/sup d/), and f/sub n/ belongs to an n-dimensional manifold of normalized ridge functions. The same bound holds for the MEM as a special case of the above. The stochastic error, in the context of learning from independent and identically distributed (i.i.d.) examples, is also examined. An asymptotic analysis establishes the limiting behavior of this error, in terms of certain pseudo-information matrices. These results substantiate the intuition behind the MEM, and motivate applications.

We consider the approximation of smooth multivariate functions in C(IRd) by feedforward neural networks with a single hidden layer of nonlinear ridge functions. Under certain assumptions on the smoothness of the functions being approximated and on the activation functions in the neural network, we present upper bounds on the degree of approximation achieved over the domain IRd, thereby generalizing available results for compact domains. We extend the approximation results to the so-called mixture of expert architecture, which has received considerable attention in recent years, showing that the same type of approximation bound may be achieved.

this paper we extend on previous work [17] and introduce a novel model selection criterion, based on combining two recent chains of thought. In particular we make use of the powerful framework of uniform convergence of empirical processes pioneered by Vapnik and Chernovenkins [23], combined with recent results concerning the approximation ability of non-linear manifolds of functions, focusing in particular on feedforward neural networks. The main contributions of this work are twofold: (i) Conceptual - elucidating a coherent and robust framework for model selection, (ii) Technical - the main contribution here is a lower bound on the approximation error (Theorem 10), which holds in a well specified sense for most functions of interest. As far as we are aware, this result is new in the field of function approximation. The remainder of the paper is organized as follows. In