Research map / Bandits and online learning / Online convex optimization and games
Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case
Taihei Oki, Shinsaku Sakaue
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| initialize greedy algorithm with learned predictions (Learn) instead of cold start | greedy M-convex minimization on staff-assignment Laminar instances · Staff assignment, n=128, R=12800, sigma in {1,5,10,20} | greedy iterations | Improved |
| initialize with Learn instead of Relax (continuous relaxation solved with Gurobi) | greedy M-convex minimization · Staff assignment, sigma <= 10 | greedy iterations | Improved |
| initialize with Learn instead of Relax at high noise | greedy M-convex minimization · Staff assignment, sigma = 20 | greedy iterations | No clear effect |
| increase noise strength sigma of instance coefficients | Learn initialization · Staff assignment, sigma 1 to 20 | greedy iterations advantage over baselines | Hurt |
Closest papers by meaning
- Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster $\text{L}$-/$\text{L}^\natural$-Convex Function Minimization (ICML 2023 · similarity 0.89)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.87)
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization (NeurIPS 2024 · similarity 0.86)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.86)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.86)
- Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization, and Tracing (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
