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] EX1∼D|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.