Skip to yearly menu bar Skip to main content


Poster

Nearly Optimal Catoni’s M-estimator for Infinite Variance

Sujay Bhatt · Guanhua Fang · Ping Li · Gennady Samorodnitsky

Hall E #1312

Keywords: [ MISC: Online Learning, Active Learning and Bandits ] [ T: Online Learning and Bandits ]


Abstract: In this paper, we extend the remarkable M-estimator of Catoni~\citep{Cat12} to situations where the variance is infinite. In particular, given a sequence of i.i.d random variables~{Xi}ni=1{Xi}ni=1 from distribution~DD over~R with mean~μ, we only assume the existence of a known upper bound~υε>0 on the~(1+ε)th central moment of the random variables, namely, for~ε(0,1] EX1D|X1μ|1+ευε. The extension is non-trivial owing to the difficulty in characterizing the roots of certain polynomials of degree smaller than~2. The proposed estimator has the same order of magnitude and the same asymptotic constant as in~\citet{Cat12}, but for the case of bounded moments. We further propose a version of the estimator that does not require even the knowledge of~υε, but adapts the moment bound in a data-driven manner. Finally, to illustrate the usefulness of the derived non-asymptotic confidence bounds, we consider an application in multi-armed bandits and propose best arm identification algorithms, in the fixed confidence setting, that outperform the state of the art.

Chat is not available.