Aug, 2017

一种基于Frank-Wolfe的迹范数球线性收敛算法

HTML
PDF
TL;DR本研究通过使用秩-$k$变体的Frank-Wolfe算法对迹范数球上的凸优化问题进行求解，其将Frank-Wolfe中的$1$-SVD替换为$top-k$ SVD算法。实验表明，当目标函数是平滑的并且强凸的，且最优解的秩最多为$k$时，该算法具有线性收敛率，从而提高了Frank-Wolfe算法及其变体的收敛速度和总时间复杂度。
发现论文，激发创造
  • Frank-Wolfe方法在强凸集合上的更快收敛速率

    在本篇论文中，我们考虑了在强凸集上进行的优化的特殊情况。我们证明，与一般情况的收敛速度为1/t相比，vanila FW方法以1/t²的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导FW方法的多个快速收敛结果。

    Jun, 2014

  • 关于凸优化和非凸优化的在线Frank-Wolfe算法

    探讨在线变体的Frank-Wolfe算法，包括简单迭代更新和非自适应步长规则，研究凸和非凸损失的多个新结果，并基于对随机Frank-Wolfe算法的改进分析得出在强凸随机成本时的遗憾界和任何时刻的最优性为O(log^3T/T)和O(log^2T/T) ; 此外，该在线算法即使在损失非凸的情况下也能收敛，以速率O(1/T的平方根)找到时变/随机损失的稳态点。

    Oct, 2015

  • 关于Frank-Wolfe优化变量的全局线性收敛性

    本文研究了Frank-Wolfe算法，提出了几个变体并分别给出了全局线性收敛性证明，证明了不同算法的收敛速度取决于几何量与条件数的乘积，这些算法在机器学习，子模优化等领域取得了实际应用。

    Nov, 2015

  • Frank-Wolfe算法在非凸目标中的收敛速率

    该研究提供了一个简单的证明，表明Frank-Wolfe算法在具有Lipschitz连续梯度的非凸目标上，以O（1 / sqrt {t}）的速率获得静止点。

    Jul, 2016

  • 广义匹配追踪和Frank-Wolfe的统一优化视角

    该论文研究了贪婪优化的两个基本原型：匹配追踪和Frank-Wolfe算法。根据这两种方法，本文首次明确了通用原子集合条件下匹配追踪方法的收敛速率。作者推导了这两种方法在一般平滑目标上的次线性（$1/t$）收敛，以及在强凸目标上的线性收敛，并提出了一个算法变化的清晰对应关系。而且这些算法和收敛速率是仿射不变的，不需要任何互不相关或稀疏性假设。

    Feb, 2017

  • 针对强凸约束集的无投影优化的重新审视

    本文探讨了强凸约束条件下的Frank-Wolfe（FW）优化，展示了一个比标准FW更快的变体的更快收敛速度，证明了即使对于非凸而是半凸和局部Lipschitz的平滑函数，FW也可以通过线搜索收敛到全局最优解，并且展示了在强凸约束集下，对于一般情况（平滑）的非凸函数，FW带有线搜索以高概率收敛到一个$O(1/t)$的速率上。

    Nov, 2018

  • 关于使用低秩投影的投影梯度方法收敛于迹范数球约束下的平滑凸规划及相关问题

    本文介绍了一种使用低秩SVD计算的简单启发式算法，使得标准一阶方法可以实现局部收敛，并可用于平滑凸规划的计算，以及带缩放梯度正则化和约束半正定矩阵上的计算。这些计算为机器学习，信号处理和统计学等领域中底秩矩阵恢复问题提供了实质性帮助。

    Feb, 2019

  • 无强凸性情况下Frank-Wolfe算法在秩一矩阵恢复中的线性收敛

    研究了低秩矩阵恢复问题的凸松弛问题，给出了使问题具有唯一秩为1的最优解的充分条件，并使用Frank-Wolfe方法和单个秩为1 SVD计算每个迭代来找到一个近似解。

    Dec, 2019

  • 多面体问题下的Frank-Wolfe算法：严格互补性和稀疏性的再探讨

    本文介绍了一种带有机械销为严格互补条件的Frank-Wolfe算法，证明了在该条件下该算法的收敛速度具有线性，并且仅取决于最优面的维度。

    May, 2020

  • 解决MAP-MRF问题的松弛问题：组合内向Frank-Wolfe方向

    本研究旨在提高解决基于最大后验马尔可夫随机场的LP松弛的问题的效率，并提出了一种基于面内Frank-Wolfe方向的高效实现方法，实验结果表明，该方法是当前某些问题类的最先进LP解决器。

    Oct, 2020