Nearly Optimal Catoni’s M-estimator for Infinite Variance

Sujay Bhatt; Guanhua Fang; Ping Li; Gennady Samorodnitsky

Nearly Optimal Catoni’s M-estimator for Infinite Variance

Sujay Bhatt, Guanhua Fang, Ping Li, Gennady Samorodnitsky

Proceedings of the 39th International Conference on Machine Learning, PMLR 162:1925-1944, 2022.

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

$\{X_i\}_{i=1}^n$ from distribution

$\mathcal{D}$ over

$\mathbb{R}$ with mean

$\mu$ , we only assume the existence of a known upper bound

$\upsilon_{\varepsilon} > 0$ on the

$(1+\varepsilon)^{th}$ central moment of the random variables, namely, for

$\varepsilon \in (0,1]$

$\mathbb{E}_{X_1 \sim \mathcal{D}} \Big| X_1 - \mu \Big|^{1+\varepsilon} \leq \upsilon_{\varepsilon}.$ {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

$\upsilon_{\varepsilon}$ , 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.

Cite this Paper

BibTeX


@InProceedings{pmlr-v162-bhatt22b,
  title = 	 {Nearly Optimal Catoni’s M-estimator for Infinite Variance},
  author =       {Bhatt, Sujay and Fang, Guanhua and Li, Ping and Samorodnitsky, Gennady},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {1925--1944},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/bhatt22b/bhatt22b.pdf},
  url = 	 {https://proceedings.mlr.press/v162/bhatt22b.html},
  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 $\{X_i\}_{i=1}^n$ from distribution $\mathcal{D}$ over $\mathbb{R}$ with mean $\mu$, we only assume the existence of a known upper bound $\upsilon_{\varepsilon} > 0$ on the $(1+\varepsilon)^{th}$ central moment of the random variables, namely, for $\varepsilon \in (0,1]$ \[ \mathbb{E}_{X_1 \sim \mathcal{D}} \Big| X_1 - \mu \Big|^{1+\varepsilon} \leq \upsilon_{\varepsilon}. \]{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 $\upsilon_{\varepsilon}$, 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.}
}

Endnote

%0 Conference Paper
%T Nearly Optimal Catoni’s M-estimator for Infinite Variance
%A Sujay Bhatt
%A Guanhua Fang
%A Ping Li
%A Gennady Samorodnitsky
%B Proceedings of the 39th International Conference on Machine Learning
%C Proceedings of Machine Learning Research
%D 2022
%E Kamalika Chaudhuri
%E Stefanie Jegelka
%E Le Song
%E Csaba Szepesvari
%E Gang Niu
%E Sivan Sabato	
%F pmlr-v162-bhatt22b
%I PMLR
%P 1925--1944
%U https://proceedings.mlr.press/v162/bhatt22b.html
%V 162
%X 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 $\{X_i\}_{i=1}^n$ from distribution $\mathcal{D}$ over $\mathbb{R}$ with mean $\mu$, we only assume the existence of a known upper bound $\upsilon_{\varepsilon} > 0$ on the $(1+\varepsilon)^{th}$ central moment of the random variables, namely, for $\varepsilon \in (0,1]$ \[ \mathbb{E}_{X_1 \sim \mathcal{D}} \Big| X_1 - \mu \Big|^{1+\varepsilon} \leq \upsilon_{\varepsilon}. \]{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 $\upsilon_{\varepsilon}$, 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.

APA


Bhatt, S., Fang, G., Li, P. & Samorodnitsky, G.. (2022). Nearly Optimal Catoni’s M-estimator for Infinite Variance. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:1925-1944 Available from https://proceedings.mlr.press/v162/bhatt22b.html.

Related Material

Download PDF