Robust subgaussian estimation with VC-dimension
Median-of-means (MOM) based procedures provide non-asymptotic and strong deviation bounds even when data are heavy-tailed and/or corrupted. This work proposes a new general way to bound the excess risk for MOM estimators. The core technique is the use of VC-dimension (instead of Rademacher complexity) to measure the statistical complexity. In particular, this allows to give the first robust estimators for sparse estimation which achieves the so-called subgaussian rate only assuming a finite second moment for the uncorrupted data. By comparison, previous works using Rademacher complexities required a number of finite moments that grows logarithmically with the dimension. With this technique, we derive new robust sugaussian bounds for mean estimation in any norm. We also derive a new robust estimator for covariance estimation that is the first to achieve subgaussian bounds without $L_4-L_2$ norm equivalence.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
We prove that there is a universal constant $C>0$ so that for every $d \in \mathbb N$, every centered subgaussian distribution $\mathcal D$ on $\mathbb R^d$, and every even $p \in \mathbb N$, the $d$-variate polynomial $…
Outlier Robust Mean Estimation with Subgaussian Rates via Stability
We study the problem of outlier robust high-dimensional mean estimation under a finite covariance assumption, and more broadly under finite low-degree moment assumptions. We consider a standard stability condition from t…
Lasso Guarantees for Time Series Estimation Under Subgaussian Tails and $ β$-Mixing
Many theoretical results on estimation of high dimensional time series require specifying an underlying data generating model (DGM). Instead, along the footsteps of~\cite{wong2017lasso}, this paper relies only on (strict…
Time SeriesTime Series AnalysisUniform Inference in High-Dimensional Threshold Regression Models
We develop uniform inference for high-dimensional threshold regression parameters, allowing for either cross-sectional or time series data. We first establish Oracle inequalities for prediction errors and $\ell_1$ estima…
regressionTime SeriesvalidOn the Subgaussianity of Quantized Linear Maps: An AI-Assisted Note
This short note presents a dimension-independent subgaussian concentration bound for Gaussian vectors under coordinate-wise nonlinear mappings. Discovered by Gemini 3.5 Flash, this result applies to any bounded function …