List-decodable covariance estimation
List-decodable covariance estimation
复制标题
列表可解码协方差估计
DOI：
10.1145/3519935.3520006
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kothari, Pravesh K.
中科院分区：
文献类型：
--
作者：
Ivkov, Misha;Kothari, Pravesh K.
给出了列表可解码协方差估计的第一个多项式时间算法。对于任意一个α >，该算法取一个样本y≥≥dpoly(1/α)，该样本y≥≥dpoly（1/α）的输入，该样本y≥≥dpoly（1/α）是通过对抗性地破坏一个样本y≥≥1的n个点，该样本y≥≥1的大小来自于一个均值μ *、协方差Σ*未知的高斯分布。在poly（1/α）时间内，它输出k=k(α)= (1/α)个poly（1/α）候选参数的恒定大小列表，这些候选参数很可能包含一个（µ，Σ），使得总变异距离etv （N（µ*，Σ*），N（µ，Σ））<1−Oα(1)。这是一个统计上最强烈的距离概念，并意味着乘谱和相对Frobenius距离近似与维无关的误差。我们的算法更普遍地适用于任何具有两种自然解析性质的低次平方和证明的分布：1)一维边缘的反集中和2)2次多项式的超收缩性。在我们的工作之前，在列表可解码设置中估计协方差的唯一已知结果是列表可解码线性回归和子空间恢复的特殊情况[karmalkar - klivvans - kothari 2019， Bakshi-Kothari 2020, Raghavendra-Yau ' 19,20]。即使对于这些特殊情况，已知的误差保证也很弱，特别是，对于自然规范中的任何次常数（维度）目标误差，算法都需要超多项式时间。作为推论，我们的结果产生了用于列表可解码线性回归和子空间恢复的第一个多项式时间精确算法，特别是在底层维度中获得多项式时间的2−(d)误差。
We give the first polynomial time algorithm forlist-decodable covariance estimation. For any α > 0, our algorithm takes input a sampleY⊆dof sizen≥dpoly(1/α)obtained by adversarially corrupting an (1−α)npoints in an i.i.d. sampleXof sizenfrom the Gaussian distribution with unknown mean µ*and covariance Σ*. Innpoly(1/α)time, it outputs a constant-size list ofk=k(α)= (1/α)poly(1/α)candidate parameters that, with high probability, contains a (µ,Σ) such that the total variation distanceTV(N(µ*,Σ*),N(µ,Σ))<1−Oα(1). This is a statistically strongest notion of distance and implies multiplicative spectral and relative Frobenius distance approximation with dimension independent error. Our algorithm works more generally for any distributionDthat possesses low-degree sum-of-squares certificates of two natural analytic properties: 1) anti-concentration of one-dimensional marginals and 2) hypercontractivity of degree 2 polynomials.Prior to our work, the only known results for estimating covariance in the list-decodable setting were for the special cases of list-decodable linear regression and subspace recovery [Karmalkar-Klivans-Kothari 2019, Bakshi-Kothari 2020, Raghavendra-Yau’19, 20]. Even for these special cases, the known error guarantees are weak and in particular, the algorithms need super-polynomial time for any sub-constant (in dimensiond) target error in natural norms. Our result, as a corollary, yields the first polynomial timeexactalgorithm for list-decodable linear regression and subspace recovery that, in particular, obtain 2−(d)error in polynomial-time in the underlying dimension.
登录
查看更多内容
列表可解码线性回归
DOI：
--
发表时间：
2019
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Karmalkar, Sushrut;Klivans, Adam;Kothari, Pravesh
通讯作者：
Kothari, Pravesh
通过平方和进行异常值稳健矩估计
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
Pravesh Kothari;David Steurer
通讯作者：
David Steurer
非球形混合物的异常值稳健聚类
DOI：
--
发表时间：
2020
期刊：
arXiv.org
影响因子：
--
作者：
Ainesh Bakshi;Pravesh Kothari
通讯作者：
Pravesh Kothari
DOI：
10.1145/3188745.3188758
发表时间：
2017-11
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
DOI：
10.1145/3357713.3384329
发表时间：
2019-12
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Yeshwanth Cherapanamjeri;Samuel B. Hopkins;Tarun Kathuria;P. Raghavendra;Nilesh Tripuraneni
通讯作者：
Yeshwanth Cherapanamjeri;Samuel B. Hopkins;Tarun Kathuria;P. Raghavendra;Nilesh Tripuraneni