通过 Frank-Wolfe 的改进 Metarounding 算法
本文研究了Frank-Wolfe算法,提出了几个变体并分别给出了全局线性收敛性证明,证明了不同算法的收敛速度取决于几何量与条件数的乘积,这些算法在机器学习,子模优化等领域取得了实际应用。
Nov, 2015
提出了一种通用的双升算法框架来处理组合问题的Lagrangean decomposition,表现出明显的效能优势,可用于图匹配和多切问题等多种应用。
Dec, 2016
本文讨论在线线性优化问题,考虑可行操作集通过近似线性优化预言机具有α乘性逼近保证的情况,给出了新算法并提出了显著改进甚至多项式对数的预言机复杂度,同时得到了常数c>0的alpha遗憾界。
Sep, 2017
利用鲁棒的学习算法,我们研究了如何适应任意目标函数的采样分布以寻找良好的局部最优解。我们的研究结果表明,我们的自适应采样器可以为实践中出现的组合优化问题提供有效的解决方案。
Feb, 2018
本文提出了一种名为Frank-Wolfe Augmented Lagrangian (FW-AL)算法的优化方法,该算法利用线性一致性约束来优化在相交凸集中的光滑函数,仅需要对单个约束的线性最小化预言机进行访问,并证明了该算法在一般凸紧集和多面体上的收敛率。
Apr, 2018
本文提出一种针对一类非光滑复合问题的贪心更新规则,其中包括$L1$-正则化问题,SVM等应用程序。我们提供了独立于$n$的首个线性收敛速度,并且证明了我们的贪心更新规则提供了类似于光滑情况下所获得的速度提升。此外,我们还展示了我们的新选择规则可以映射到最大内积搜索实例中,从而利用标准最近邻算法来加速实现。通过广泛的数值实验证明了该方法的有效性。
Oct, 2018
针对拥有大规模实例的问题,本文提出了第一个自适应复杂度为 O(log n),且求解非单调子模问题的背包约束问题的常数因子逼近算法,该算法提出了一个子线性适应性的组合方法,其查询值仅为O(n)。
Feb, 2021
本文从最近使用机器学习来解决约束优化问题的尝试入手,重点调查了将组合求解器和优化方法与机器学习架构集成的工作。这些方法有望开发新的混合机器学习和优化方法,以快速预测组合问题的近似解并启用结构逻辑推理。本文概述了这一新兴领域的最新进展。
Mar, 2021