Faster Matchings via Learned Duals
Faster Matchings via Learned Duals
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
M. Dinitz;Sungjin Im;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii
中科院分区：
文献类型：
--
作者：
M. Dinitz;Sungjin Im;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii
最近的一系列研究调查了如何用机器学习的预测来增强算法，以克服最坏情况下的下限。这一领域揭示了有趣的算法见解的问题，特别是成功的设计有竞争力的在线算法。然而，通过预测来改善算法运行时间的问题在很大程度上尚未被探索。我们在这个方向上迈出了第一步，将机器学习预测的想法与“热启动”原始对偶算法的想法相结合。我们考虑组合优化中最重要的基元之一：加权二部匹配及其推广到$B$-匹配。我们确定了三个关键的挑战时，使用学习的对偶变量的原始对偶算法。首先，预测的不可行解可能是不可行的，因此我们给出了一个算法，有效地映射预测的不可行解附近的可行解。第二，一旦可行，他们可能不是最佳的，所以我们表明，他们可以用来快速找到一个最佳的解决方案。最后，这样的预测是有用的，只有当他们可以学习，所以我们表明，学习匹配的问题具有较低的样本复杂度。我们验证我们的理论研究结果，通过实验上的真实的和合成数据。因此，我们给出了一个严格的，实用的，经验有效的方法来计算二部匹配。
A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algorithmic insights into problems, with particular success in the design of competitive online algorithms. However, the question of improving algorithm running times with predictions has largely been unexplored. We take a first step in this direction by combining the idea of machine-learned predictions with the idea of"warm-starting"primal-dual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to $b$-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predicted duals may be infeasible, so we give an algorithm that efficiently maps predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may not be optimal, so we show that they can be used to quickly find an optimal solution. Finally, such predictions are useful only if they can be learned, so we show that the problem of learning duals for matching has low sample complexity. We validate our theoretical findings through experiments on both real and synthetic data. As a result we give a rigorous, practical, and empirically effective method to compute bipartite matchings.