Breaking the Curse of Dimensionality

This paper proposes a new nonparametric estimator for general regression functions with multiple regressors. The method used here is motivated by a remarkable result derived by Kolmogorov (1957) and later tightened by Lorentz (1966). In short, any continuous function f(x_1,...,x_d) has the representation G[a_1 P_1(x_1) + ... + a_d P_1(x_d)] + ... + G[a_1 P_m(x_1) + ... + a_d P_m(x_d)], m = 2d+1, where G(.) is a continuous function, P_k(.), k=1,...,2d+1, is Lipschitz of order one and strictly increasing, and a_j, j=1,...,d, is some constant. Generalizing this result, we propose the following estimator, g_1[a_1,1 p_1(x_1) + ... + a_d,1 p_1(x_d)] + ... + g_m[a_1,d P_m(x_1) + ... + a_d,d p_m(x_d)], where both g_k(.) and p_k(.) are twice continuously differentiable. These functions are estimated using regression cubic B-splines, which have excellent numerical properties. This problem has been previously intractable because there existed no method for imposing monotonicity on the p_k(.)'s, a priori, such that the estimator is dense in the set of all monotonic cubic B-splines. We derive a method that only requires 2(r+1)+1 restrictions, where r is the number of interior knots. Rates of convergence in L_2 are the same as the optimal rate for the one-dimensional case. A simulation experiment shows that the estimator works well when optimization is performed by using the back-fitting algorithm. The monotonic restriction has many other applications besides the one presented here, such as estimating a demand function. With only r+2 more constraints, it is also possible to impose concavity.