Jan, 2024

利用半定规划进行人群聚类的去偏置和局部分析

PDF
TL;DR本文讨论了从一个混合的子高斯分布中抽取的规模为 n 的小数据样本的分区问题，并分析了同一作者提出的计算有效算法，通过一个小样本按照其来源人群将数据大致分为两组。从这篇论文中，我们得出结论：当信噪比 s^2 被一个常数下界限时，误分类错误以指数形式衰减。我们还讨论了平衡分区的一个变体，并证明了新估计量具有卓越的去偏性。
partitioningsub-gaussian distributionsclusteringtradeoffsmisclassification error
发现论文，激发创造
  • 通过半正定规划实现精确群集恢复阈值：扩展

    通过对 Semidefinite Programming（SDP）放松的最大似然估计进行研究，本文论证了 SDP 放松技术在社区检测中的可行性和通用性。

    Feb, 2015

  • 混合模型、鲁棒性和平方和证明

    本文基于 Sum of Squares 方法，探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法，进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计，我们的方法多次突破优化算法的极限。

    Nov, 2017

  • 稀疏随机图上的半定规划及其在社区发现中的应用

    研究了 Erdos-Renyi 图和随机图在半定规划过程中的类似行为，用一些新的工具进行了证明，证明了 SDP 检测带有信息隐匿的随机图中的对称社区检测问题达到了信息论阈值。

    Apr, 2015

  • 通过 Grothendieck 不等式解同步和 MaxCut 问题的 SDP

    通过引入非凸约束形式并应用 Riemannian trust-region 方法，该论文研究了 MaxCut 和同步问题中的秩约束半定规划，并建立了一个 Grothendieck 型不等式证明局部最大值和危险鞍点都在离全局最大值一个小倍数距离的情况下，SDPs 可以在已知精度内得到解决。

    Mar, 2017

  • 最优二分网络聚类

    本文提出一种基于谱初始化和伪似然分类器的两阶段快速过程，用于网络双分区检测或更一般地解决网络双聚类问题。该程序是弱一致的，同时在双分块随机模型下建立。通过数值模拟，证明了这种程序的有效性。

    Mar, 2018

  • 度相关随机块模型中的密度演化

    本文考虑二元随机块模型，研究平均误分类顶点的最小分数，结果表明，当群集大小平衡且 μ≠ν 时，平均误分类顶点数量的最小分数由 Q（sqrt（v *））给出，并由局部算法（即置信传播）在边数线性时间内实现，证明技巧基于将群集恢复问题与树重建问题相连，分析置信传播在具有高斯近似的树上的密度演化。

    Sep, 2015

  • 半定规划层次结构在图模型推断中的应用

    本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。

    Sep, 2017

  • 半定规划多参考序列比对

    该研究提供了一种基于半定规划松弛的多参考点对齐问题的最大似然估计的近似算法，并在应用中表现良好，并提供了稳定性保证。

    Aug, 2013

  • 对于块模型的半定松弛

    提出了一种新的半定规划解决方案（SDP-1）以适应随机块模型（SBM）中的社区检测问题，可以放宽之前提出的 SDP 方法中的一些条件，并且是适合拟合网络直方图的理想工具。

    Jun, 2014

  • 一种罚款的多类半监督算法的 Rademacher 复杂性界

    该研究提出了一种基于两步半监督模型的多类分类器的 Rademacher 复杂性界，通过聚类技术和较少的带标签数据来训练分类器，并得到包含泛化误差界的数据相关收敛速度的理论结果。

    Jul, 2016