Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction

• URL: http://arxiv.org/abs/2204.02323v1
• Date: Tue, 5 Apr 2022 16:29:09 GMT
• Title: Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction
• Authors: Amir-Hossein Bateni, Arshak Minasyan, Arnak S. Dalalyan
• Abstract summary: We study the problem of robust estimation of the mean vector of a sub-Gaussian distribution. We introduce an estimator based on spectral dimension reduction (SDR) and establish a finite sample upper bound on its error. We prove that the breakdown point of the SDR estimator is equal to $1/2$, the highest possible value of the breakdown point.
• Score: 5.414308305392762
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of robust estimation of the mean vector of a sub-Gaussian distribution. We introduce an estimator based on spectral dimension reduction (SDR) and establish a finite sample upper bound on its error that is minimax-optimal up to a logarithmic factor. Furthermore, we prove that the breakdown point of the SDR estimator is equal to $1/2$, the highest possible value of the breakdown point. In addition, the SDR estimator is equivariant by similarity transforms and has low computational complexity. More precisely, in the case of $n$ vectors of dimension $p$ -- at most $\varepsilon n$ out of which are adversarially corrupted -- the SDR estimator has a squared error of order $\big(\frac{r_\Sigma}{n} + \varepsilon^2\log(1/\varepsilon)\big){\log p}$ and a running time of order $p^3 + n p^2$. Here, $r_\Sigma\le p$ is the effective rank of the covariance matrix of the reference distribution. Another advantage of the SDR estimator is that it does not require knowledge of the contamination rate and does not involve sample splitting. We also investigate extensions of the proposed algorithm and of the obtained results in the case of (partially) unknown covariance matrix.

Related papers

• Fast and Robust: Computationally Efficient Covariance Estimation for Sub-Weibull Vectors [0.0]
  In this work, we target the specific regime of textbfSub-Weibull (characterized by stretched exponential tails $exp(-t)$)<n>Unlike element-wise truncation, our approach preserves the spectral geometry while requiring $O(Nd2)$ operations.<n>We derive non-asymptotic error bounds showing that our estimator recovers the optimal sub-Gaussian rate $tildeO(sqrtr()/N)$ with high probability.
  arXiv  Detail & Related papers  (2025-12-19T14:34:30Z)
• Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
  We study the problem of distributed mean estimation with 1-bit communication constraints.<n>Our estimator is $(epsilon, delta)$-PAC for all distributions with bounded mean ($-lambda le mathbbE(X) le lambda $) and variance ($mathrmVar(X) le sigma2$) for some known parameters.
  arXiv  Detail & Related papers  (2025-09-26T06:22:57Z)
• Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians [2.311583680973075]
  We study the problem of computationally efficient robust estimation of the covariance/scatter matrix of elliptical distributions. We obtain the first efficiently computable, nearly optimal robust covariance estimators that extend beyond the Gaussian case.
  arXiv  Detail & Related papers  (2025-02-10T15:31:57Z)
• 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)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Near-Optimal differentially private low-rank trace regression with guaranteed private initialization [0.0]
  We study differentially private (DP) estimation of a rank-$r$ matrix $M in RRd_1times d$ under the trace regression model. We also propose a differentially private algorithm for estimating $M$ based on Riemannian optimization (DP-RGrad) It is shown that the estimator given by DP-RGrad attains the optimal convergence rate in a weaker notion of differential privacy.
  arXiv  Detail & Related papers  (2024-03-24T03:57:21Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  We consider the problem of partitioning a small data sample of size $n$ drawn from a mixture of 2 sub-gaussian distributions in $mathbbRp$. We use semidefinite programming relaxations of an integer quadratic program that is formulated as finding the maximum cut on a graph.
  arXiv  Detail & Related papers  (2024-01-16T03:14:24Z)
• Estimation of entropy-regularized optimal transport maps between non-compactly supported measures [15.857723276537248]
  This paper addresses the problem of estimating entropy-regularized optimal transport maps with squared-Euclidean cost between source and target measures that are subGaussian.
  arXiv  Detail & Related papers  (2023-11-20T17:18:21Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  We study the problem of high-dimensional sparse mean estimation in the presence of an $epsilon$-fraction of adversarial outliers. Our algorithms follow the Sum-of-Squares based, to algorithms approach.
  arXiv  Detail & Related papers  (2022-06-07T16:49:54Z)
• Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers [13.244654316770815]
  We develop machinery to design efficiently computable and consistent estimators. For sparse regression, we achieve consistency for optimal sample size $ngsim (klog d)/alpha2$. In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix.
  arXiv  Detail & Related papers  (2021-11-04T15:59:44Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.of estimating the partition of the lattice induced by the constancy regions of the unknown signal. We prove that a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigma2 k*
  arXiv  Detail & Related papers  (2021-05-27T23:41:01Z)
• 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 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)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

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.