Affine Invariant Covariance Estimation for Heavy-Tailed Distributions

Dmitrii M. Ostrovskii; Alessandro Rudi

Affine Invariant Covariance Estimation for Heavy-Tailed Distributions

Dmitrii M. Ostrovskii, Alessandro Rudi

Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:2531-2550, 2019.

Abstract

In this work we provide an estimator for the covariance matrix of a heavy-tailed multivariate distribution. We prove that the proposed estimator

$\widehat{\mathbf{S}}$ admits an \textit{affine-invariant} bound of the form

$(1-\varepsilon) \mathbf{S} \preccurlyeq \widehat{\mathbf{S}} \preccurlyeq (1+\varepsilon) \mathbf{S}$ {in} high probability, where

$\mathbf{S}$ is the unknown covariance matrix, and

$\preccurlyeq$ is the positive semidefinite order on symmetric matrices. The result only requires the existence of fourth-order moments, and allows for

$\varepsilon = O(\sqrt{\kappa^4 d\log(d/\delta)/n})$ where

$\kappa^4$ is a measure of kurtosis of the distribution,

$d$ is the dimensionality of the space,

$n$ is the sample size, and

$1-\delta$ is the desired confidence level. More generally, we can allow for regularization with level

$\lambda$ , then

$d$ gets replaced with the degrees of freedom number. Denoting

$\text{cond}(\mathbf{S})$ the condition number of

$\mathbf{S}$ , the computational cost of the novel estimator is

$O(d^2 n + d^3\log(\text{cond}(\mathbf{S})))$ , which is comparable to the cost of the sample covariance estimator in the statistically interesing regime

$n \ge d$ . We consider applications of our estimator to eigenvalue estimation with relative error, and to ridge regression with heavy-tailed random design.

Cite this Paper

BibTeX


@InProceedings{pmlr-v99-ostrovskii19a,
  title = 	 {Affine Invariant Covariance Estimation for Heavy-Tailed Distributions},
  author =       {Ostrovskii, Dmitrii M. and Rudi, Alessandro},
  booktitle = 	 {Proceedings of the Thirty-Second Conference on Learning Theory},
  pages = 	 {2531--2550},
  year = 	 {2019},
  editor = 	 {Beygelzimer, Alina and Hsu, Daniel},
  volume = 	 {99},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {25--28 Jun},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v99/ostrovskii19a/ostrovskii19a.pdf},
  url = 	 {https://proceedings.mlr.press/v99/ostrovskii19a.html},
  abstract = 	 {In this work we provide an estimator for the covariance matrix of a heavy-tailed multivariate distribution. We prove that the proposed estimator $\widehat{\mathbf{S}}$ admits an \textit{affine-invariant} bound of the form \[ (1-\varepsilon) \mathbf{S} \preccurlyeq \widehat{\mathbf{S}} \preccurlyeq (1+\varepsilon) \mathbf{S} \]{in} high probability, where $\mathbf{S}$ is the unknown covariance matrix, and $\preccurlyeq$ is the positive semidefinite order on symmetric matrices. The result only requires the existence of fourth-order moments, and allows for $\varepsilon = O(\sqrt{\kappa^4 d\log(d/\delta)/n})$ where $\kappa^4$ is a measure of kurtosis of the distribution, $d$ is the dimensionality of the space, $n$ is the sample size, and $1-\delta$ is the desired confidence level. More generally, we can allow for regularization with level $\lambda$, then $d$ gets replaced with the degrees of freedom number. Denoting $\text{cond}(\mathbf{S})$ the condition number of $\mathbf{S}$, the computational cost of the novel estimator is $O(d^2 n + d^3\log(\text{cond}(\mathbf{S})))$, which is comparable to the cost of the sample covariance estimator in the statistically interesing regime $n \ge d$. We consider applications of our estimator to eigenvalue estimation with relative error, and to ridge regression with heavy-tailed random design.}
}

Endnote

%0 Conference Paper
%T Affine Invariant Covariance Estimation for Heavy-Tailed Distributions
%A Dmitrii M. Ostrovskii
%A Alessandro Rudi
%B Proceedings of the Thirty-Second Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2019
%E Alina Beygelzimer
%E Daniel Hsu	
%F pmlr-v99-ostrovskii19a
%I PMLR
%P 2531--2550
%U https://proceedings.mlr.press/v99/ostrovskii19a.html
%V 99
%X In this work we provide an estimator for the covariance matrix of a heavy-tailed multivariate distribution. We prove that the proposed estimator $\widehat{\mathbf{S}}$ admits an \textit{affine-invariant} bound of the form \[ (1-\varepsilon) \mathbf{S} \preccurlyeq \widehat{\mathbf{S}} \preccurlyeq (1+\varepsilon) \mathbf{S} \]{in} high probability, where $\mathbf{S}$ is the unknown covariance matrix, and $\preccurlyeq$ is the positive semidefinite order on symmetric matrices. The result only requires the existence of fourth-order moments, and allows for $\varepsilon = O(\sqrt{\kappa^4 d\log(d/\delta)/n})$ where $\kappa^4$ is a measure of kurtosis of the distribution, $d$ is the dimensionality of the space, $n$ is the sample size, and $1-\delta$ is the desired confidence level. More generally, we can allow for regularization with level $\lambda$, then $d$ gets replaced with the degrees of freedom number. Denoting $\text{cond}(\mathbf{S})$ the condition number of $\mathbf{S}$, the computational cost of the novel estimator is $O(d^2 n + d^3\log(\text{cond}(\mathbf{S})))$, which is comparable to the cost of the sample covariance estimator in the statistically interesing regime $n \ge d$. We consider applications of our estimator to eigenvalue estimation with relative error, and to ridge regression with heavy-tailed random design.

APA


Ostrovskii, D.M. & Rudi, A.. (2019). Affine Invariant Covariance Estimation for Heavy-Tailed Distributions. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:2531-2550 Available from https://proceedings.mlr.press/v99/ostrovskii19a.html.

Related Material

Download PDF