Faster Discrete Convex Function Minimization with Predictions: The
  M-Convex Case
Taihei Oki Shinsaku Sakaue
Recent years have seen a growing interest in accelerating optimization
algorithms with machine-learned predictions. Sakaue and Oki (NeurIPS 2022) have
developed a general framework that warm-starts the L-convex function
minimization method with predictions, revealing the idea's usefulness for
various discrete optimization problems. In this paper, we present a framework
for using predictions to accelerate M-convex function minimization, thus
complementing previous research and extending the range of discrete
optimization algorithms that can benefit from predictions. Our framework is
particularly effective for an important subclass called laminar convex
minimization, which appears in many operations research applications. Our
methods can improve time complexity bounds upon the best worst-case results by
using predictions and even have potential to go beyond a lower-bound result.