Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case

Understand

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.