  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.
