ANZIAM J. 46(E) pp.C1205--C1221, 2005.

Additive models in high dimensions

Markus Hegland

Vladimir Pestov
(Received 12 November 2004, revised 31 October 2005)

Abstract

Additive decompositions are established tools in nonparametric statistics and effectively address the curse of dimensionality. For the analysis of the approximation properties of additive decompositions, we introduce a novel framework which includes the number of variables as an ingredient in the definition of the smoothness of the underlying functions. This approach is motivated by the effect of concentration of measure in high dimensional spaces. Using the resulting smoothness conditions, convergence of the additive decompositions is established. Several examples confirm the error rates predicted by our error bounds. Explicit expressions for optimal additive decompositions (in an $L_2$ sense) are given which can be seen as a generalisation of multivariate Taylor polynomials where the monomials are replaced by higher order interactions. The results can be applied to the numerical approximation of functions with hundreds of variables.

Download to your computer

Authors

Markus Hegland
CMA, Mathematical Sciences Institute, Australian National University, Canberra, Australia. mailto:markus.hegland@anu.edu.au
Vladimir Pestov
Department of Mathematics and Statistics, University of Ottawa, Ottawa, Canada. mailto:vpest283@uottawa.ca

Published November 14, 2005. ISSN 1446-8735

References

  1. R. E. Bellman, Adaptive Control Processes: A Guided Tour, Princeton University Press, Princeton, 1961.
  2. B. Efron and C. Stein, The jackknife estimate of variance, Annals of Statistics 9 (3), 1981, 586--596. http://www.jstor.org/view/00905364/di983909/98p0170d/0
  3. J. H. Friedman, Multivariate adaptive regression splines (with discussion), Annals of Statistics 19 1991, 1--141. http://www.jstor.org/view/00905364/di983949/98p0128u/0
  4. M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, Progress in Mathematics 152, Birkhauser Verlag, 1999.
  5. T. J. Hastie and R. J. Tibshirani, Generalized Additive Models, Monographs on Statistics and Applied Probability 43, Chapman & Hall, London a.o., 1990.
  6. M. Hegland, Computational challenges in data mining, in: Proceedings of the Computational Techniques and Applications Conference CTAC'99, ANZIAM Journal 42 (2000--2001), Part C, pp. C1--C43. http://anziamj.austms.org.au/V42/CTAC99/AHeg
  7. F. J. Hickernell, Quadrature Error Bounds with Applications to Lattice Rules, SIAM J. Num. Anal. 33 (5) (1996), 1995--2016.
  8. V. D. Milman, The heritage of P. Levy in geometric functional analysis, Asterisque 157--158 (1988), 273--301.
  9. A. B. Owen, Orthogonal Arrays for Computer Experiments, Integration and Visualisation, Statistica Sinica 2 (1992), 439--452.
  10. V. Pestov, On the geometry of similarity search: dimensionality curse and concentration of measure, Inform. Proc. Letters 73 (2000), 47--51.
  11. I. H. Sloan and H. Wozniakowski, When are Quasi-Monte Carlo algorithms efficient for high dimensional integrals, J. Complexity 14, (1998), 1--33.
  12. M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. IHES 81 (1995), 73--205.
  13. G. Wahba, Spline models for observational data, CBMS-NSF Reg. Conf. Ser. Appl. Math. 59, SIAM, 1990.
Copyright Austral. Mathematical Soc.; prepared November 14, 2005, from Hegl.tex with anziamje.sty (v2.3k)