ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

12. Probability and Statistics

1991 MS Classification: 62G07,62G20,62C20 Johnstone, Iain, Stanford University, USA Oracle Inequalities and Nonparametric Function Estimation

Statistical theory aims in part to articulate when and why certain applied methods of data analysis succeed. With emergence of large, often instrumentally acquired datasets, recent decades have seen a focus on “nonparametric” models in which the number of model parameters grows with the size of available data. A common caricature is to posit observed data y ∈ R^{n} with structure y = Kθ+ϵz, Here θ is an unknown function which one desires to “estimate” or “recover”, K is a linear operator and z ∈ R^{n} is a vector of standard Gaussian noise of known scale ϵ. An estimator θ̂(y) is evaluated in terms of, for example, its mean squared error, or “risk” R(θ̂, θ) = E_{θ}|θ̂(y) − θ|^{2}, where E_{θ} denotes expectation with respect to the probability distribution of y given θ and | · | denotes Euclidean distance. A class of models {M_{J}, J ∈ J } is given. Typically M_{J} are subsets, often linear, of R^{n} to which θ might belong. For each model J, there is a “natural” estimator θ̂_{J} with risk R(θ̂_{J}, θ). For a fixed, unknown θ, the “ideal risk” would be inf_{J} R(θ̂_{J}, θ). This risk would be attainable with the aid of an oracle who divulges the optimal J. Lacking access to oracles, we seek estimators θ̂(y) with risk properties that mimick the ideal risk as closely as possible. Here is one example of such an inequality. Suppose that K is the identity on R^{n} and that the data model is expressed in terms of coefficients in an orthonormal basis {ψ_{i}} :

y_{i} = θ_{i} + ϵz_{i} i = 1, … n.

Here z_{i} are independent Gaussian noises of mean zero and variance one. Let an estimator θ̂_{λ} be built componentwise via soft thresholding of the observed data: θ̂_{λ,i}(y) equals 0 if |y_{i}| ≤ λ and equals y_{i} − λ sgny_{i} otherwise. Set λ = ϵ\sqrt{2 log n}. Then, whatever be θ ∈ R^{n} and ϵ > 0,

E_{θ} ∑_{1}^{n}(θ̂_{λ,i}(y) − θ_{i})^{2} ≤ (2 log n + 1)[ϵ^{2} + ∑_{1}^{n} min(θ_{i}^{2}, ϵ^{2})].

From the inequality, one learns, for example (i) the ideal risk ∑_{1}^{n} min(θ_{i}^{2}, ϵ^{2}) connects compressibility of the signal θ in basis {ψ_{i}} with the quality of estimation/recovery. It also establishes a link with approximation theory, (ii) near minimax optimality properties simultaneously over a class of parameter spaces Θ, and (iii) the factor 2 log n cannot be improved: a heuristic limiting the detection of sparse signals in Gaussian noise shows why. Time permitting, we will discuss two other such oracle inequalities: (i) a linear shrinkage inequality involving the classical James-Stein estimator, and (ii) an oracle inequality for “empirical atomic decomposition” in which the orthobasis {ψ_{i}, i = 1, … n} is replaced by a possibly highly redundant dictionary, such as might be approriate when the class of models for the signal θ is not well represented in terms of unconditional bases.