该研究为第一篇在 list-decodable 设置中,给出了一种鲁棒的回归问题的多项式时间算法,当假设内点分布是 certifiably anti-concentrated 分布时,该算法能够成功地给出一个接近于真解的目标函数。
May, 2019
本文基于 Sum of Squares 方法,探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法,进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计,我们的方法多次突破优化算法的极限。
Nov, 2017
探讨在机器学习中存在恶意数据时的问题,其中的 list-decodable learning 和 semi-verified learning model 框架及稳健学习算法提供强大的解决方案。
Nov, 2016
使用多项式技术来移除高维数据集中的异常值,同时提出了非常有效的算法,大大改进了高斯均值估计和学习混合球形高斯问题的保障性能。
研究列表可解的高斯协方差估计问题,提出了基于谱技术的多滤波方法,解决了高斯混合模型偏差聚类的问题并得到了最新 GMM 学习方法的解。
May, 2023
本文提出了一种新的方法用于词典学习即稀疏编码的问题,其中,算法能够在噪声张量分解方面解决任意泊松(Poisson)噪声情况,并且本算法同样适用于具有更高的稀疏度,并且基于一个使用和分析半正定规划的 Sum of Squares 层次结构的新方法。
Jul, 2014
本文首次给出了一个多项式时间算法,用于在示例和标签中对抗性堕落下执行线性或多项式回归,并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。
Mar, 2018
针对模型类如何拟合标记数据的问题,我们提出了一种计算学习能力的方法,可以使用较小的数据量得出精确结果。该方法也适用于二元分类问题,并在多种真实和合成数据集上得到了验证。
May, 2018
在存在对抗离群值的情况下,我们开发了有效的算法来估计未知分布的低阶矩。这些算法的保证在许多情况下显著优于 Diakonikolas 等人、Lai 等人和 Charikar 等人的最佳先前算法,同时我们还展示了这些算法的保证与我们考虑的分布类别的信息论下界相匹配,这些改进的保证使我们能够在存在离群值的情况下提供改进的独立成分分析和学习混合高斯的算法,我们的算法基于对下面概念简单优化问题的标准平方和松弛:在所有矩与未知分布相同的分布中,找到与对抗性污染样本的经验分布在统计距离上最接近的分布。
通过转换一个分布映射算法为一个近似解,我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法,并应用于 3 个已知问题的改进,分别是:低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。
Dec, 2013