We consider the problem of recovering a function $f\colon \Omega\to \mathbf C$ belonging to some class $F$ based on a finite number of samples. The class $F$ reflects our a priori knowledge about the function. Here, $\Omega$ is any compact domain or manifold and $F$ is any compact subset of $C(\Omega)$. The error is measured in a worst case scenario (over the function class) and with respect to the $L_2$-distance. The following general result was recently obtained by the authors:
If the Kolmogorov widths of $F$ show a polynomial decay of order $s>1/2$, then there is a weighted least squares estimator that achieves the same rate of convergence.
We discuss this result and address the following questions: What does the algorithm look like? What can be said in the case $s\le 1/2$? What results do we obtain for the tractability of the problem in high dimensional settings? We also relate to recent results of Nagel/Schaefer/Ullrich, Temlyakov and Cohen/Dolbeault.