The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?
Open accessAbstract
Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Aronszajn, N. (1950) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1950-0051437-7 · Cited by 5,380
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
A Note on the Generation of Random Normal Deviates
Box, G. E. P., & Muller, M. E. (1958) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177706645 · Cited by 3,401
Random Number Generation and Quasi-Monte Carlo Methods.
Collings, B. J., & Niederreiter, H. (1993) · Journal of the American Statistical Association · doi:10.2307/2290359 · Cited by 2,884
Random Number Generation and Quasi-Monte Carlo Methods
Niederreiter, H. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970081 · Cited by 2,770
The art of computer programming. Vol.2: Seminumerical algorithms
Knuth, D. E. (1981) · Virtual Defense Library (Ministerio de Defensa) · Cited by 1,232
Sequences, Discrepancies and Applications
Drmota, M., & Tichy, R. F. (1997) · Lecture Notes in Mathematics · doi:10.1007/bfb0093404 · Cited by 832
Lattice Methods for Multiple Integration
Sloan, I. H., & Joe, S. (1994) · doi:10.1093/oso/9780198534723.001.0001 · Cited by 750
Self-citationA generalized discrepancy and quadrature error bound
Hickernell, F. (1998) · Mathematics of Computation · doi:10.1090/s0025-5718-98-00894-1 · Cited by 724
Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension
Caflisch, R. E., Morokoff, W. J., & Owen, A. B. (1997) · The Journal of Computational Finance · doi:10.21314/jcf.1997.005 · Cited by 516
Cited by
Raissi, M., Perdikaris, P., & Karniadakis, G. E. (2019) · Journal of Computational Physics · doi:10.1016/j.jcp.2018.10.045 · Cited by 20,384
Discrete Choice Methods with Simulation
Train, K. E. (2001) · doi:10.1017/cbo9780511805271 · Cited by 7,784
Oseledets, I. V. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/090752286 · Cited by 2,636
Centroidal Voronoi Tessellations: Applications and Algorithms
Du, Q., Faber, V., & Gunzburger, M. (1999) · SIAM Review · doi:10.1137/s0036144599352836 · Cited by 2,244
Quasi-random maximum simulated likelihood estimation of the mixed multinomial logit model
Bhat, C. R. (2001) · Transportation Research Part B: Methodological · doi:10.1016/s0191-2615(00)00014-x · Cited by 1,010
Metadata
- Authors
- Sloan, I. H., & Woźniakowski, H.
- Venue
- Journal of Complexity
- Publisher
- Elsevier BV
- Published
- 1998-03
- Volume
- 14
- Issue
- 1
- Pages
- 1-33
- ISSN
- 0885-064X (ISSN-L)
- OpenAlex
- W1981743146
- Cited by
- 606
- References
- 18
- FWCI
- 19.35
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals? https://app.cochat.ai/papers/10.1006/jcom.1997.0463
- The paper
- Sloan, I. H., & Woźniakowski, H. (1998). When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals? Journal of Complexity. https://doi.org/10.1006/jcom.1997.0463
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.