用度量的 Dikin Walk 高效采样 PSD 空间锥
研究了一种用于半定规划问题(SDOs)的切平面方法,证明了该方法基于有界性假设的收敛性。通过将该方法的收敛速度与初始外近似的直径联系起来,我们证明了当使用二阶锥逼近而不是线性逼近时该方法的表现更好。我们将该方法用于提供数千个协变量的稀疏 PCA 问题的边界间隙,并解决了 500x500 矩阵上的核范数问题。
Oct, 2019
本研究提出了利用随机梯度下降中的小批量和自适应采样两种策略来有效地减少 DML 的计算复杂度,证明了这些方法的理论保证,并进行了广泛的实证研究以验证所提出算法的有效性。
Apr, 2013
我们开发了一种实用的半定规划 (SDP) 面部缩减程序,该程序利用了正半定锥的计算有效近似。该方法通过求解一系列较容易的优化问题简化 SDP,并可作为 SDP 求解器的有用预处理技术。我们展示了该方法在实践中应用的有效性,并描述了我们公开可用的软件实现。我们还展示了如何在我们的 PSD 锥近似中找到最大秩矩阵,并给出了一个基于面部缩减的预处理技术的双重解恢复的后处理过程。最后,我们展示如何选择逼近值以保留问题的稀疏性。
Aug, 2014
该研究提出并分析了两种新的 MCMC 抽样算法,即 Vaidya walk 和 John walk,用于从多面体上生成样本。其中提出的 Vaidya walk 算法的混合时间比过去的 Dikin walk 的混合时间少得多,混合时间上界为 O (n^0.5*d^1.5)。在数值例子中,Vaidya 步行的加速超过了 Dikin 步行。
Oct, 2017
本文提出了解决在信号处理、机器学习、统计学等领域中经常出现的各种凸锥问题的通用框架,包括决定问题的锥形公式,确定其对偶,应用平滑,使用一阶最优方法解决,以及一些新技术贡献,如新的连续方案、控制步长的新方法等,并通过数值实验表明该框架具有稳定和计算高效的特点,并发行了一套软件。
Sep, 2010
对于一种新颖的分区约束 DPPs,我们提出了第一个多项式时间的算法,以在约束下准确地从中进行抽样,并发现这种方法比 k-DPPs 和其朴素扩展提供更多的灵活性和多样性。同时,我们通过实验发现,简单的贪心初始化和局部搜索可以提高从 k-DPPs 的 MAP 推断问题的近似保证,特别是在较大的 k 下。
Jul, 2016
通过对第一阶锥下降(CD)求解器进行直观性、理论性和算法实现方面的改进研究,发现 CD 可以通过对偶问题的几何推导得到直观的解释,从而为新算法设计打开了大门,其中包括动量变量 MOCO。进一步深入研究了 CD 和 MOCO 的对偶行为,揭示了解析合理的停止准则和设计预处理器以加快对偶收敛的潜力。最后,为了扩展半定规划(SDP)的规模,特别是对于低秩解,开发了一个内存高效的 MOCO 变体,并得到了数值验证。
Aug, 2023
本文讨论了从一个混合的子高斯分布中抽取的规模为 n 的小数据样本的分区问题,并分析了同一作者提出的计算有效算法,通过一个小样本按照其来源人群将数据大致分为两组。从这篇论文中,我们得出结论:当信噪比 s^2 被一个常数下界限时,误分类错误以指数形式衰减。我们还讨论了平衡分区的一个变体,并证明了新估计量具有卓越的去偏性。
Jan, 2024