An emerging line of work has shown that machine-learned predictions are useful to warm-start algorithms for discrete optimization problems, such as bipartite matching. Previous studies have shown time complexity bounds proportional to some distance between a prediction and an optimal solution, which we can approximately minimize by learning predictions from past optimal solutions. However, such guarantees may not be meaningful when multiple optimal solutions exist. Indeed, the dual problem of bipartite matching and, more generally, $\text{L}$-/$\text{L}^\natural$-convex function minimization have arbitrarily many optimal solutions, making such prediction-dependent bounds arbitrarily large. To resolve this theoretically critical issue, we present a new warm-start-with-prediction framework for $\text{L}$-/$\text{L}^\natural$-convex function minimization. Our framework offers time complexity bounds proportional to the distance between a prediction and the set of all optimal solutions. The main technical difficulty lies in learning predictions that are provably close to sets of all optimal solutions, for which we present an online-gradient-descent-based method. We thus give the first polynomial-time learnability of predictions that can provably warm-start algorithms regardless of multiple optimal solutions.
翻译:正在出现的工作线表明,机器学的预测有助于为离散优化问题(如双方匹配)进行热启动算法。 以往的研究显示,时间复杂性的界限与预测和最佳解决方案之间的一定距离成比例, 我们可以从过去的最佳解决方案中学习预测, 将其缩小到最小。 但是, 当存在多种最佳解决方案时, 这样的保证可能没有意义。 事实上, 双方匹配的双重问题, 以及更一般而言, $\ text{L}- $/\ text{L}_ $/ $\ text{ natural$- convex 函数最小化。 主要的技术困难在于学习与所有最佳解决方案组合相近的预测, 使这种依赖预测的界限任意大。 为了解决这一理论上的关键问题, 我们为 $\ text{L} $/ $\\ $\\\ text{ { { { natural- convex 函数最小化, 我们提出了一个新的热源启动框架框架。 我们因此, 能够以多种最优化的热度的算算法 。