Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
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.