高效的非高斯集中度证书

May, 2024

Efficient Certificates of Anti-Concentration Beyond Gaussians

Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan

TL;DR利用新的反集中形式，我们提供了准多项式时间可验证的反集中积分证书，适用于包括反集中有界产品分布和 $L_p$ 球以及其仿射变换在内的广泛非高斯分布，将算法鲁棒统计的结果升级和扩展到这些分布。

Abstract

A set of high dimensional points $X=\{x_1, x_2,\ldots, x_n\} \subset R^d$ in isotropic position is said to be $\delta$-anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying $|\langle x_i,v \rangle |\leq \delta$ is at most $O(\delta)$. Motivated by applications to list-decodable learning and clustering, recent works have consi

anti-concentration certificates gaussian distribution non-gaussian distributions sum-of-squares relaxation

发现论文，激发创造

独立随机变量多项式的反集中

该研究论文的主要研究领域和主题为：独立随机变量的多项式抗集中性质证明、计算机复杂度理论中的下界问题和随机图中固定图的数量的反集中性结论。

Jul, 2015

非球形混合物的异常值鲁棒聚类

本研究提出了一种新的检测离群值的高效算法，用于聚类混合的高斯模型，这种方法是鲁棒的，可以处理在数据中有少部分的失真或错误，它依赖于 TV 距离和方差有限度等假定条件，并使用极小化两种偏差的方法来修复度量误差和离群值异常。

May, 2020

关于伊辛模型中多项式集中度的注记

本文提出了精确的多层指数集中不等式，其适用于满足 Dobrushin 条件的 Ising 模型中的多项式。此外，我们还证明了凸函数的集中性结果和非负定二次型的估计。

Sep, 2018

收缩 Ising 模型的多项式的浓度不等式

研究了 N 个自旋的度为 d 的多项式在单点 Glauber 动力学收缩的情况下的浓度，其中对于 d = 1，根据 Marton（1996）和 Samson（2000），凸 Lipschitz 函数的浓度的特殊情况是高斯浓度；对于 d = 2，Marton（2003）在晶格上证明了指数浓度。

May, 2017

α- 次指数随机变量的多项式集中不等式

通过证明 Hanson-Wright-type 不等式，在独立随机变量的多项式函数中推出多级浓度不等式，得出了一些关于二次形式、线性回归等方面的各种浓度不等式。

Mar, 2019

投影的集中定理

通过实验探索了线性投影、球形高斯分布、比例混合、偏心系数等相关问题。

Jun, 2012

利用半空间在 $l_p$- 范数距离度量下改进浓度估计

通过理论分析、提出半空间方法，更加有效地测量数据集的浓缩程度，从而得到更紧密的原始鲁棒性下限，并证明这些更紧密的下限进一步排除了基于数据集浓缩的假说，该假说被认为是解释现有分类器使之易受到对抗攻击的可能原因。

Mar, 2021

列表可解线性回归

该研究为第一篇在 list-decodable 设置中，给出了一种鲁棒的回归问题的多项式时间算法，当假设内点分布是 certifiably anti-concentrated 分布时，该算法能够成功地给出一个接近于真解的目标函数。

May, 2019

高维分布的线性映射小球概率

研究随机向量的集中性质，其中 X =（X1，...，Xn）具有独立坐标，而 A 是给定的矩阵。我们证明，只要 X 的分布在线上很好地分布，AX 的分布就会在空间中得到很好的展开。

Feb, 2014

高斯点云中可以在多项式时间内找到的例外低维投影

通过研究高斯向量、比例渐近性、经验分布、随机子空间和随机最优控制问题，我们证明了一类分布可以通过迭代算法实现，并获得了关于这个问题的对偶表述和拓展帕里西公式的变分原理。

Jun, 2024