mlsanityData to 14 Oct 2026

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

arXiv 2306.05865 ↗First posted 9 Jun 2023cs.LG cs.DScited by 3

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 19 of its 49 references that are in the map. First posted on arXiv 9 Jun 2023.

Builds on

19 of 49 references.

References · 19

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  2. 2018Competitive caching with machine learned advicecited by 195
  3. 2020Algorithms with Predictionscited by 153
  4. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
  5. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 77
  6. 2021Faster Matchings via Learned Dualscited by 56
  7. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  8. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  9. 2021Online Graph Algorithms with Predictionscited by 25
  10. 2022Learning Predictions for Algorithms with Predictionscited by 25
  11. 2023Predictive Flows for Faster Ford-Fulkersoncited by 20
  12. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
7 more
  1. 2022Learning-Augmented Maximum Flowcited by 11
  2. 2014Provable Submodular Minimization using Wolfe's Algorithmcited by 10
  3. 2020On a reduction for a class of resource allocation problemscited by 6
  4. 2023Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimizationcited by 3
  5. 2017Separable Convex Optimization with Nested Lower and Upper Constraintscited by 2
  6. 2018M-convex Function Minimization Under L1-Distance Constraintcited by 2
  7. 2020A fast algorithm for quadratic resource allocation problems with nested constraintscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 1.

3 papers.

  1. 2026Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Setscited by 8
  2. 2024Warm-starting Push-Relabelcited by 2
  3. 2024No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Settingcited by 1