Is adaptive early stopping possible in statistical inverse problems?

Gilles Blanchard (Universität Potsdam)
Markus Reiß (Humboldt-Universität zu Berlin)
Wednesday, April 27, 2016 - 10:00am
WIAS, Erhard-Schmidt-Saal, Mohrenstraße 39, 10117 Berlin

We consider a standard setting of statistical inverse problem, taking the form of the Gaussian sequence model with D observed noisy coefficients. Consider the simple family of keep or kill estimators depending on a cutoff index k_0.
For the choice of the cutoff index, there exist a number of well-known methods achieving oracle adaptivity (i.e. data-dependent choice of k0 whose performance is comparable to the unknown optimal one), such as penalization and Lepskis method. However, they have in common that the estimators for all values of k_0 have to be computed first and compared to each other in some way. Contrast this to an early stopping approach where we would like to compute iteratively the estimators for k_0 = 1,2,... and have to decide to stop at some point without being allowed to compute the following estimators. Is oracle adaptivity possible then? This question is motivated by settings where computing estimators for larger k0 requires more computational cost; furthermore some form of early stopping is most often used in practice. We propose a precise mathematical formulation of this question and provide upper and lower bounds on what is achievable.