Can Adaption Help on the Average?
We study adaptive information for approximation of linear problems in a separable Hilbert space equipped with a probability measure Î¼. It is known that adaption does not help in the worst case for linear problems. We prove that adaption also does not help on the average. That is, there exists nonadaptive information which is as powerful as adaptive information. This result holds for "orthogonally invariant" measures. We provide necessary and sufficient conditions for a measure to be orthogonally invariant. Examples of orthogonally invariant measures include Gaussian measures and, in the finite dimensional case, weighted Lebesgue measures.
- cucs-080-83.pdf application/x-pdf 665 KB Download File
More About This Work
- Academic Units
- Computer Science
- Department of Computer Science, Columbia University
- Columbia University Computer Science Technical Reports, CUCS-080-83
- Published Here
- October 26, 2011