证明了所有中心化亚高斯分布都可被多项式平方和验证，从而实现高效统计学习。
SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
- 用多项式平方和构造方法验证亚高斯分布的性质
- 首次实现对任意亚高斯分布的近最优高效估计
- 适合关注高维统计推断与算法保障的研究者
我们证明存在一个全局常数 $C>0$，使得对任意维度 $d o bN$、任意中心化亚高斯分布 $bD$ on $bR^d$，以及任意偶数 $p o bN$，多项式 $(Cp)^{p/2} imes orm{v}_2^p - bE_{X ilde{bD}} raket{v,X}^p$ 均为多项式平方和。这表明每个亚高斯分布都是‘SoS可认证亚高斯’的——该性质可导出一系列高效学习算法，适用于多种高维统计任务。作为直接推论，当给定任意亚高斯分布的样本时，我们可获得具有近最优保证的计算高效算法，涵盖鲁棒均值估计、列表解码均值估计、均值分离混合模型聚类、鲁棒协方差感知均值估计、鲁棒协方差估计及鲁棒线性回归。
原文摘要 · Abstract (English)
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 $(Cp)^{p/2} \cdot \|v\|_{2}^p - \mathbb E_{X \sim \mathcal D} \langle v,X\rangle^p$ is a sum of square polynomials. This establishes that every subgaussian distribution is \emph{SoS-certifiably subgaussian} -- a condition that yields efficient learning algorithms for a wide variety of high-dimensional statistical tasks. As a direct corollary, we obtain computationally efficient algorithms with near-optimal guarantees for the following tasks, when given samples from an arbitrary subgaussian distribution: robust mean estimation, list-decodable mean estimation, clustering mean-separated mixture models, robust covariance-aware mean estimation, robust covariance estimation, and robust linear regression. Our proof makes essential use of Talagrand's generic chaining/majorizing measures theorem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。