Geodesic
On numerical methods for functions depending on a very large number of variables
Matematičeskoe modelirovanie, Tome 29 (2017) no. 2, pp. 135-138.

Voir la notice de l'article provenant de la source Math-Net.Ru

The question under discussion is why do optimal algorithms on classes of functions sometimes become useless in practice. As an example let's consider the class of functions which satisfy a general Lipschitz condition. The methods of integral evaluation over a unit cube of $d$ dimensions, where $d$ is significantly large, are discussed. It is assumed that the integrand is square integrable. A crude Monte Carlo estimation can be used. In that case the probable error of estimation is proportional $1/\sqrt{N}$, where $N$ is the number of values of the integrand. If we use a quasi-Monte Carlo method instead of Monte Carlo one, then the error does not depend on the dimension $d$, numerous examples show that it depends on the average dimension $\hat{d}$ of the integrand. For small $\hat{d}$ the order of the error is close to $1/N$.
Mots-clés : optimal algorithm
Keywords: Lipschitz condition, Monte Carlo method, quasi-Monte Carlo method, the average dimension. 
@article{MM_2017_29_2_a10,
     author = {I. M. Sobol},
     title = {On numerical methods for functions depending on a very large number of variables},
     journal = {Matemati\v{c}eskoe modelirovanie},
     pages = {135--138},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/}
}
TY  - JOUR
AU  - I. M. Sobol
TI  - On numerical methods for functions depending on a very large number of variables
JO  - Matematičeskoe modelirovanie
PY  - 2017
SP  - 135
EP  - 138
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/
LA  - ru
ID  - MM_2017_29_2_a10
ER  - 
%0 Journal Article
%A I. M. Sobol
%T On numerical methods for functions depending on a very large number of variables
%J Matematičeskoe modelirovanie
%D 2017
%P 135-138
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/
%G ru
%F MM_2017_29_2_a10
I. M. Sobol. On numerical methods for functions depending on a very large number of variables. Matematičeskoe modelirovanie, Tome 29 (2017) no. 2, pp. 135-138. http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/

[1] Dzh. Traub, Kh. Vozhniakovskii, Obshchaia teoriia optimalnykh algoritmov, Mir, M., 1983

[2] S. M. Nikolskii, Kvadraturnye formuly, Fizmatgiz, M., 1958

[3] I. M. Sobol, “Determination of the extremal values of a function of several variables Satisfying a generalized Lipschitz condition”, USSR Computational Mathematics and Mathematical Physics, 28:2 (1988), 112–118 | DOI | Zbl

[4] I. M. Sobol, “Quadrature formulae for functions of several variables satisfying a general Lipschitz condition”, USSR Computational Math. and Mathematical Physics, 29:3 (1989), 201–206 | DOI | MR | Zbl

[5] I. M. Sobol', D. Asotsky, A. Kreinin, S. Kucherenko, “Construction and comparison of high-dimensional Sobol' generators”, Wilmott Mag., 2011:56 (2011), 64–79 | DOI

[6] R. Liu, A. B. Owen, “Estimating mean dimensionality of analysis of variance decompositions”, J. Amer. Statist. Assoc., 101:474 (2006), 712–721 | DOI | MR | Zbl

[7] D. Asotsky, E. Myshetskaya, I. M. Sobol', “The average dimension of a multidimensional function for quasi-Monte Carlo estimates of an integral”, Comp. Math. Math. Phys., 46:12 (2006), 2061–2067 | DOI | MR

[8] A. B. Owen, Variance components and generalized Sobol' indices, Technical report, Stanford University, 2012 | MR

[9] I. M. Sobol', B. V. Shukhman, “Quasi-Monte Carlo: A high-dimensional experiment”, Monte Carlo Methods Appl., 20:3 (2014), 167–171 | DOI | MR | Zbl

[10] B. V. Shukhman, I. M. Sobol', “A limit theorem for average dimensions”, Monte Carlo Methods Appl., 21:2 (2015), 175–178 | DOI | MR | Zbl