On the necessity of low-effective dimension

DOI10.1016/J.JCO.2005.05.004MaRDI QIDQ2576277zbMATH OpenOpenAlexFDO

Authors Shu Tezuka

Publication date 27 December 2005

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2005.05.004

zbMATH Keywords

analysis of varianceANOVAdecomposition methodeffective dimensiongeneralized Sobol' sequencesglobal sensibilityhigh-dimensional integralsMonte Carlo methodquasi-Monte Carlo methodWalsh functions

Mathematics Subject Classification ID

Pseudo-random numbers; Monte Carlo methods (11K45) Analysis of variance and covariance (ANOVA) (62J10) Applications of statistics to actuarial sciences and financial mathematics (62P05) Monte Carlo methods (65C05) Numerical methods (including Monte Carlo methods) (91G60)

Review text

This paper deals with the problem of necessity condition for the low-effective dimension, which is essentially involved in the process of understanding why quasi-Monte Carlo (QMC), the deterministic version of Monte Carlo (MC) method, is proved to outperform MC by a wide margin for certain very high-dimensional integrals. \textit{I. M. Sobol'} [Mat. Model. 2, No.~1, 112--118 (1990; Zbl 0974.00506)] introduced in 1990 the notion of global sensitivity for the analysis of nonlinear mathematical problems. \textit{R. E. Caflisch, W. Morokoff} and \textit{A. B. Owen} [Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance 1, 27--46 (1997)] were the first who formally defined the notion of effective dimension using the ANOVA (ANalysis Of VAriance) decomposition method, and attempted to show empirically that low-effective dimension may provide the key to understanding the relationship between QMC and MC methods. \textit{A. B. Owen} [Necessity of low effective dimension, manuscript (2002)] pointed out that low-effective dimension is not a sufficient condition that QMC beats MC, and conjectured that low-effective dimension could be a necessary condition that explains why QMC behaves better than MC. Now, the main result of this article is to prove that Owen's conjecture is not true, i.e. low-effective dimension is also not a necessary condition that QMC is better than MC. This result is obtained as follows: the author introduces a class of functions in high-dimensions, which have the maximum-effective dimension. Then the generalized Sobol' sequences are proved to provide the \(O(N^{-1})\) convergence rate for the integration of the introduced class of functions, with \(N\) being the natural number rank of the integration error.

Recommendations

• The truth about the effective dimension
• Lowness for effective Hausdorff dimension
• On the dimensional reduction procedure
• Correspondence principles for effective dimensions
• scientific article; zbMATH DE number 2086652
• Dimensional reduction of the effective action and the multiplicative anomaly
• scientific article; zbMATH DE number 107645
• Essential dimension: a survey
• Low-dimensional models from upper bound theory
• On the dimensional reduced theories

Cites work

• Average case complexity of multivariate integration
• Geometric discrepancy. An illustrated guide
• Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1222809 (Why is no real title available?)
• scientific article; zbMATH DE number 1246219 (Why is no real title available?)
• scientific article; zbMATH DE number 1246224 (Why is no real title available?)
• scientific article; zbMATH DE number 1246413 (Why is no real title available?)
• scientific article; zbMATH DE number 1790429 (Why is no real title available?)
• scientific article; zbMATH DE number 1894664 (Why is no real title available?)
• scientific article; zbMATH DE number 781100 (Why is no real title available?)
• scientific article; zbMATH DE number 1425054 (Why is no real title available?)
• scientific article; zbMATH DE number 236854 (Why is no real title available?)
• Monte Carlo Variance of Scrambled Net Quadrature
• On the distribution of points in a cube and the approximate evaluation of integrals
• Quasi-Monte Carlo methods for financial applications.
• Sequences, discrepancies and applications
• Sufficient conditions for fast quasi-Monte Carlo convergence
• The price of pessimism for multidimensional quadrature
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cited in

(8)

• Effective discrepancy and numerical experiments
• scientific article; zbMATH DE number 5899260 (Why is no real title available?)
• How do path generation methods affect the accuracy of quasi-Monte Carlo methods for problems in finance?
• scientific article; zbMATH DE number 1894664 (Why is no real title available?)
• Explaining effective low-dimensionality
• The average dimension of a multidimensional function for quasi-Monte Carlo estimates of an integral
• Quasi-Monte Carlo: a high-dimensional experiment
• Exact cubature for a class of functions of maximum effective dimension

This page was built for publication: On the necessity of low-effective dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2576277)