平方和证明及其应用于最优算法问题的探索
本文介绍了 DSOS 和 SDSOS 最优化算法作为线性规划和二阶锥规划的替代方法,以允许一个在计算时间与解决方案质量之间进行权衡的选择,并且用多个应用领域的数值实验表明,我们可以在目前传统的平方和算法难以实现的规模上处理问题。
Jun, 2017
本文基于 Sum of Squares 方法,探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法,进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计,我们的方法多次突破优化算法的极限。
Nov, 2017
运用代数学方法,本文研究了利用函数多项式下水平集进行三维空间推理的问题,包括两个基本半代数凸集之间互相包含的相关计算、相交的两个半代数凸集之间的分离、多个半代数集合与一个凸集的紧凑包含等,并且我们将这些任务的求解转化为小型半定规划并进行了实验验证。
Nov, 2016
通过转换一个分布映射算法为一个近似解,我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法,并应用于 3 个已知问题的改进,分别是:低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。
Dec, 2013
在存在对抗离群值的情况下,我们开发了有效的算法来估计未知分布的低阶矩。这些算法的保证在许多情况下显著优于 Diakonikolas 等人、Lai 等人和 Charikar 等人的最佳先前算法,同时我们还展示了这些算法的保证与我们考虑的分布类别的信息论下界相匹配,这些改进的保证使我们能够在存在离群值的情况下提供改进的独立成分分析和学习混合高斯的算法,我们的算法基于对下面概念简单优化问题的标准平方和松弛:在所有矩与未知分布相同的分布中,找到与对抗性污染样本的经验分布在统计距离上最接近的分布。
Nov, 2017
本文研究使用凸松弛法解决高维机器学习问题时,统计与计算的权衡。对稀疏主成分分析(Sparse PCA)问题和 Sum-of-Squares(即 Lasserre / Parillo)凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况,为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限,说明它们存在困难问题。
Jul, 2015
研究线性算子 2->q 范数的计算复杂性,该范数定义为 ||A||_{2->q}=sup_v||Av||_q/||v||_2,以及这个问题与量子信息理论和 Khot 的唯一游戏猜想 (UGC) 的问题之间的联系。
May, 2012
研究使用多项式表示数据点云时,一种与特定和坐标轴相关的 SOS 多项式可以准确捕获云的形状,同时对正交多项式的极值属性进行了推广和解释,具有广泛的应用潜力,例如网络入侵检测。
Jun, 2016