Monte Carlo Methods for Uniform Approximation on Periodic Sobolev Spaces with Mixed Smoothness

Glenn Byrenheid, Robert J. Kunsch, Van Kien Nguyen

Published 2017-09-11Version 1

We consider the order of convergence for linear and nonlinear Monte Carlo approximation of compact embeddings from Sobolev spaces of dominating mixed smoothness defined on the torus $\mathbb{T}^d$ into the space $L_{\infty}(\mathbb{T}^d)$ via methods that use arbitrary linear information. These cases are interesting because we can gain a speedup of up to $1/2$ in the main rate compared to the worst case approximation. In doing so we determine the rate for some cases that have been left open by Fang and Duan.