论文标题
基于离散征轴 - 分析的框架，用于预测的热启动算法
Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
论文作者
论文摘要
通过学习的预测增强算法是超越最坏情况界限的一种有希望的方法。 Dinitz，IM，Lavastida，Moseley和Vassilvitskii〜（2021）已经证明，学习的双重解决方案的温暖开端可以改善匈牙利方法的时间复杂性，以加重完美的双方匹配。我们通过\ textIt {iNCETE cONVEX Analysis}（DCA）以原则性的方式扩展并改善了它们的框架，这是一个离散的凸分析类似物。我们通过将基于DCA的框架应用于加权的完美两分匹配，加权矩阵交叉点以及用于计算机视觉的离散能量最小化，从而展示了基于DCA的框架的实用性。我们基于DCA的框架产生的时间复杂性界限取决于$ \ ell_ \ indy $ distance从预测的解决方案到最佳解决方案，相对于先前的$ \ ell_1 $ distance依赖性界限具有两个优点：时间复杂性范围较小，并且对预测的学习较小。我们还从DCA的角度讨论了是学习原始解决方案还是双重解决方案。
Augmenting algorithms with learned predictions is a promising approach for going beyond worst-case bounds. Dinitz, Im, Lavastida, Moseley, and Vassilvitskii~(2021) have demonstrated that a warm start with learned dual solutions can improve the time complexity of the Hungarian method for weighted perfect bipartite matching. We extend and improve their framework in a principled manner via \textit{discrete convex analysis} (DCA), a discrete analog of convex analysis. We show the usefulness of our DCA-based framework by applying it to weighted perfect bipartite matching, weighted matroid intersection, and discrete energy minimization for computer vision. Our DCA-based framework yields time complexity bounds that depend on the $\ell_\infty$-distance from a predicted solution to an optimal solution, which has two advantages relative to the previous $\ell_1$-distance-dependent bounds: time complexity bounds are smaller, and learning of predictions is more sample efficient. We also discuss whether to learn primal or dual solutions from the DCA perspective.
