Near optimal estimation of the mean in Hilbert space

Dia 2020-10-16 10:30:00-03:00
Hora 2020-10-16 10:30:00-03:00

Near optimal estimation of the mean in Hilbert space

Roberto Imbuzeiro Oliveira (IMPA)

In this talk, we discuss an estimator that, given a n-point i.i.d. sample from a distribution P over Hilbert space (with finite second moment), produces an estimate of the sample mean with the following properties.

(P0) The estimator does not require knowledge of distribution parameters.

(P1) Fix a confidence level 1-\alpha. Fix also 0<\delta<1/2 and assume an adversarial contamination model where up to \delta n sample points may be modified arbitrarily. Our estimator achieves (non-asymptotically) the minimax-optimal error for this problem, up to a constant factor.

(P2) Our estimator can be computed in a number of Hilbert space operations that grows at most polynomially in n.

A recent construction due to Lugosi and Mendelson gives an estimator satisfying (P0) and (P1), but not (P2). Other estimators had been shown to satisfy (P1) and (P2), but not (P0). It had been conjectured that no near-minimax estimator could satisfy the three properties. A novel "PAC-Bayesian" analysis will show that the conjecture is false, and that a variant of previous estimator actually works. The idea behind our estimator is based on the standard "trimmed mean".