Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
复制标题
DOI：
10.48550/arxiv.2205.09961
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Shinsaku Sakaue;Taihei Oki
中科院分区：
文献类型：
--
作者：
Shinsaku Sakaue;Taihei Oki
用学习的预测来增强算法是一种很有前途的方法，可以超越最坏情况的界限。Dinitz、Im、Lavastida、莫斯利和Vassilvitskii~（2021）已经证明，使用学习的对偶解进行热启动可以改善加权完美二分匹配的匈牙利方法的时间复杂度。我们扩展和改进他们的框架原则性的方式通过\textit{离散凸分析}（DCA），凸分析的离散模拟。我们将其应用于加权完美二分匹配，加权拟阵交集，和离散能量最小化的计算机视觉的有用性，我们的基于DCA的框架。我们的基于DCA的框架产生的时间复杂度界限，依赖于从预测的解决方案到最优解决方案的$\ell_\infty$-距离，相对于以前的$\ell_1 $-距离依赖的界限，它有两个优点：时间复杂度界限更小，预测的学习更有样本效率。我们还讨论了从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.