On the power of iid information for linear approximation

This survey is concerned with the power of random information for approximation in the (deterministic) worst-case setting, with special emphasis on information that is obtained independently and identically distributed (iid) from a given distribution on a class of admissible information. We present a general result based on a weighted least squares method and derive consequences for special cases. Improvements are available if the information is "Gaussian" or if we consider iid function values for Sobolev spaces. We include open questions to guide future research on the power of random information in the context of information-based complexity.Comment: 61 page