通过放松张量范数实现更好的不可知聚类
本文基于 Sum of Squares 方法,探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法,进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计,我们的方法多次突破优化算法的极限。
Nov, 2017
在存在对抗离群值的情况下,我们开发了有效的算法来估计未知分布的低阶矩。这些算法的保证在许多情况下显著优于 Diakonikolas 等人、Lai 等人和 Charikar 等人的最佳先前算法,同时我们还展示了这些算法的保证与我们考虑的分布类别的信息论下界相匹配,这些改进的保证使我们能够在存在离群值的情况下提供改进的独立成分分析和学习混合高斯的算法,我们的算法基于对下面概念简单优化问题的标准平方和松弛:在所有矩与未知分布相同的分布中,找到与对抗性污染样本的经验分布在统计距离上最接近的分布。
Nov, 2017
提出了一种新的框架,以将鲁棒性的凸松弛算法修改为满足适当参数规范的强最坏情况稳定性保证。通过这一框架,提出了一个可以在存在恶意数据干扰下实现微分隐私的高阶矩的鲁棒估计的算法,包括均值和协方差的估计。该算法成功地应用于成族分布,并在适当参数范数下提供恢复和维度参数的从容保证。
Dec, 2021
本研究提出了一种新的检测离群值的高效算法,用于聚类混合的高斯模型,这种方法是鲁棒的,可以处理在数据中有少部分的失真或错误,它依赖于 TV 距离和方差有限度等假定条件,并使用极小化两种偏差的方法来修复度量误差和离群值异常。
May, 2020
本文研究使用凸松弛法解决高维机器学习问题时,统计与计算的权衡。对稀疏主成分分析(Sparse PCA)问题和 Sum-of-Squares(即 Lasserre / Parillo)凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况,为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限,说明它们存在困难问题。
Jul, 2015
该论文证明了一个简单的聚类算法可以在不假设任何生成模型的情况下运作,只需要假定一种叫做 “接近条件” 的规律。该算法依赖于著名的 k-means 算法,能够产生大多数现有生成模型的结果,同时提出了一种新的技术来提高间距与标准差之比。
Apr, 2010
研究了在高维高斯混合假设下,少量数据受到对手损坏的情况下的高效可学习性,提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时,该问题是可多项式学习的;这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法,并使用基于 Sum-of-Squares 证明算法的技术,提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。
May, 2020
研究了混合有界协方差分布的聚类问题,使用细粒度分离假设;提供了用于聚类任务的多项式时间算法,并指出了在细粒度均值分离假设下精确聚类是信息理论上不可能的;引入了聚类细化的概念并证明了可以高效计算出样本的精确聚类细化;此外,根据先前工作中的一个变体条件,我们的算法输出准确聚类,甚至适用于一般权重的混合物。
Dec, 2023