Jun, 2023
学习有界协方差高斯混合模型的 SQ 下界
SQ Lower Bounds for Learning Bounded Covariance GMMs
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
TL;DR本论文研究了学习具有相同未知有界协方差矩阵的分离高斯混合模型的复杂性,证明了该问题的任何统计查询算法至少需要 d 的阶次 1/ε 的复杂度,这为已知算法的最佳性提供了证据。
Abstract
We study the complexity of learning mixtures of separated Gaussians with
common unknown bounded covariance matrix. Specifically, we focus on learning
→
发现论文,激发创造
高维高斯分布和高斯混合模型的鲁棒估计的统计查询下限
本文提出了一种统计查询下限技术,用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题,并得出了样本复杂度和计算复杂度之间存在的超多项式差距,同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。
Nov, 2016
混合模型、鲁棒性和平方和证明
本文基于 Sum of Squares 方法,探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法,进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计,我们的方法多次突破优化算法的极限。
Nov, 2017
学习高斯半空间问题中随机分类噪声的近最优界
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
学习两个高斯混合的紧密界限
本文介绍了一种基于矩估计的计算方法,并应用新颖且简单的降维技术将上界推广到任意维数 $d>1$,同时发现了一些样本复杂度较小的特殊情况,同时我们的结果也适用于在总变异距离上学习混合物的每个组件,其中我们的算法显著提高了样本复杂度。
Apr, 2014
在最优分离下聚类有界协方差分布混合
研究了混合有界协方差分布的聚类问题,使用细粒度分离假设;提供了用于聚类任务的多项式时间算法,并指出了在细粒度均值分离假设下精确聚类是信息理论上不可能的;引入了聚类细化的概念并证明了可以高效计算出样本的精确聚类细化;此外,根据先前工作中的一个变体条件,我们的算法输出准确聚类,甚至适用于一般权重的混合物。
Dec, 2023
用多项式数量的样本来隐私学习高斯混合模型
在满足差分隐私的约束下,研究了估计混合高斯模型问题。通过使用新的框架,证明了高斯模型类的混合模型是可私密学习的,得到了估计混合高斯模型所需的样本数量的有界性,且不对 GMMs 作出任何结构性假设。
Sep, 2023