Mathematical Foundations of Computing
Complexity of approximation on generalized Hölder classes
Wan Li, Peixin Ye
Abstract
We study the approximation of functions from the generalized Hölder classes $ B(H_{\Omega}^{k}([0,1]^{d})) $ in the $ L_{p}([0,1]^{d}) $ metric for all $ 1\leq p\leq \infty $. We establish the exact orders of complexity for this problem in the deterministic, randomized and quantum settings. The optimal convergence rates in all three settings are $ \Omega(n^{-1/d}) $, where $ n $ is the number of function evaluations involved in the computational process. The results show that quantum and randomized algorithms yield no improvement in terms of the optimal convergence rates. Furthermore, we apply our general result to the special case $ \Omega(t) = t^{a}\left(\log_{2}\left(2+\frac{1}{t}\right)\right)^{b} $ with $ 0<a<k $ and $ b\in\mathbb{R} $, and derive the corresponding complexity orders.