Lower bounds for the complexity of Monte Carlo function approximation

DOI10.1016/0885-064X(92)90027-9zbMath0768.46020MaRDI QIDQ1201159

Publication date: 17 January 1993

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

Full work available at URL: https://doi.org/10.1016/0885-064x(92)90027-9

zbMATH Keywords

Sobolev space; Gaussian measures; embedding operator; information operator; average Gelfand and approximation numbers; Mayorov discretisation technique; Monte Carlo approximations for linear operators

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65C05: Monte Carlo methods

46E35: Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems

47B06: Riesz operators; eigenvalue distributions; approximation numbers, (s)-numbers, Kolmogorov numbers, entropy numbers, etc. of operators

47B80: Random linear operators

41A46: Approximation by arbitrary nonlinear expressions; widths and entropy

Related Items

Discontinuous information in the worst case and randomized settings, Randomized approximation numbers on Besov classes with mixed smoothness, Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure, Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods, The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear Monte Carlo methods, On the power of standard information for \(L_{\infty}\) approximation in the randomized setting, Linear average and stochastic \(n\)-widths of Besov embeddings on Lipschitz domains, Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness, Linear widths of a multivariate function space equipped with a Gaussian measure, The recovery of ridge functions on the hypercube suffers from the curse of dimensionality, Exact asymptotic orders of various randomized widths on Besov classes, The randomized information complexity of elliptic PDE, Approximation characteristics for diagonal operators in different computational settings, The information-based complexity of approximation problem by adaptive Monte Carlo methods, Kolmogorov and Linear Widths on Generalized Besov Classes in the Monte Carlo Setting, Some Results on the Complexity of Numerical Integration, Bernstein Numbers and Lower Bounds for the Monte Carlo Error, The power of standard information for multivariate approximation in the randomized setting

Cites Work