2021/08/04 by David Krieg, Krieg, David, Erich Novak +3 · 3 citations
Computer Science · Mathematics · #41A63 #65C05 (Primary) 41A25 #65D15 #65D30 #65Y20 (Secondary) #Applied mathematics #Computer science #Convergence (economics) #Domain (mathematical analysis) #FOS: Mathematics #Importance sampling #Key (lock) #Logarithm #Machine Learning and Algorithms #Mathematical Approximation and Integration #Mathematical analysis #Mathematical optimization #Mathematics #Monte Carlo method #Numerical Analysis (math.NA) #Omega #Physics #Rate of convergence #Sample (material) #Sampling (signal processing) #Sobolev space #Space (punctuation) #Statistical Methods and Inference #Statistics #cs.NA #math.NA #msc:41A25 #msc:41A63 #msc:65C05 #msc:65D15 #msc:65D30 #msc:65Y20
paper · pdf · doi:10.48550/arxiv.2108.02055
published in arXiv (Cornell University) (Cornell University) · 28 pages
arxiv created 2021/08/04 · openalex publication_date 2021/08/04 · arxiv updated 2021/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We study Lq-approximation and integration for functions from the Sobolev space Wsp(Ω) and compare optimal randomized (Monte Carlo) algorithms with algorithms that can only use iid sample points, uniformly distributed on the domain. The main result is that we obtain the same optimal rate of convergence if we restrict to iid sampling, a common assumption in learning and uncertainty quantification. The only exception is when p=q=∞, where a logarithmic loss cannot be avoided.