Multivariate mean estimation with direction-dependent accuracy

• URL: http://arxiv.org/abs/2010.11921v1
• Date: Thu, 22 Oct 2020 17:52:45 GMT
• Title: Multivariate mean estimation with direction-dependent accuracy
• Authors: Gabor Lugosi and Shahar Mendelson
• Abstract summary: We consider the problem of estimating the mean of a random vector based on $N$ independent, identically distributed observations. We prove an estimator that has a near-optimal error in all directions in which the variance of the one dimensional marginal of the random vector is not too small.
• Score: 8.147652597876862
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of estimating the mean of a random vector based on $N$ independent, identically distributed observations. We prove the existence of an estimator that has a near-optimal error in all directions in which the variance of the one dimensional marginal of the random vector is not too small: with probability $1-\delta$, the procedure returns $\wh{\mu}_N$ which satisfies that for every direction $u \in S^{d-1}$, \[ \inr{\wh{\mu}_N - \mu, u}\le \frac{C}{\sqrt{N}} \left( \sigma(u)\sqrt{\log(1/\delta)} + \left(\E\|X-\EXP X\|_2^2\right)^{1/2} \right)~, \] where $\sigma^2(u) = \var(\inr{X,u})$ and $C$ is a constant. To achieve this, we require only slightly more than the existence of the covariance matrix, in the form of a certain moment-equivalence assumption. The proof relies on novel bounds for the ratio of empirical and true probabilities that hold uniformly over certain classes of random variables.

Related papers

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models [12.746888269949407]
  We consider a high-dimensional mean estimation problem over a binary hidden Markov model. We establish a nearly minimax optimal (up to logarithmic factors) estimation error rate, as a function of $|theta_*|,delta,d,n$.
  arXiv  Detail & Related papers  (2022-06-06T09:34:04Z)
• Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
  This paper considers learning of the graphical structure of a $p$-dimensional random vector $X in Rp$ using both parametric and non-parametric methods. Under mild conditions, we show that our graph-structure estimator can obtain the correct structure.
  arXiv  Detail & Related papers  (2022-05-06T19:24:44Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Nonasymptotic one-and two-sample tests in high dimension with unknown covariance structure [0.0]
  We consider the problem of testing if $mu is $eta-close to zero, i.e. $|mu| leq eta against $|mu| geq (eta + delta)$. The aim of this paper is to obtain nonasymptotic upper and lower bounds on the minimal separation distancedelta$ such that we can control both the Type I and Type II errors at a given level.
  arXiv  Detail & Related papers  (2021-09-01T06:22:53Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
  arXiv  Detail & Related papers  (2020-11-24T22:39:21Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices. We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
  arXiv  Detail & Related papers  (2020-11-21T01:33:15Z)
• Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  We present a novel estimator with sub-Gaussian convergence. Our estimator does not require prior knowledge of the variance. Our estimator construction and analysis gives a framework generalizable to other problems.
  arXiv  Detail & Related papers  (2020-11-17T02:47:24Z)
• Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model [28.839136703139225]
  We study mean estimation for entangled single-sample Gaussians with a common mean but different unknown variances. We show that the method achieves error $O left(fracsqrtnln nmright)$ with high probability when $m=Omega(sqrtnln n)$. We further prove lower bounds, showing that the error is $Omegaleft(left(fracnm4right)1/6right)$ when $m$ is between $Omega(n
  arXiv  Detail & Related papers  (2020-07-10T18:25:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.