Research map / Bandits and online learning / Online convex optimization and games

Learning Augmented Exact Exponential Algorithms

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Learning-augmented online algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes learning-augmented exact exponential-time algorithms for NP-hard subset selection problems, using noisy element-wise predictions (correct with probability 1/2+ε) to shrink the search space of exhaustive search and monotone local search, giving running times like (2-Ω(ε²))^n.

Problem

Exact exponential-time algorithms for NP-hard subset selection problems (e.g., Feedback Vertex Set, Hitting Set) have base-α running times that are hard to improve; the question is whether machine-learned predictions about the optimal solution can speed them up.

Approach

Query a noisy predictor once per element to split the universe into predicted-in and predicted-out sets, then bias the sampling of monotone local search seeds toward the predicted split; a binomial-ratio bound shows this gives an exponential-in-t saving under only pairwise independence, and a geometric guessing schedule handles unknown ε.

Key results

• Exhaustive search with noisy predictions runs in (2-Ω(ε²))^n·n^O(1) time, strictly beating 2^n for any ε>0.
• Prediction-guided monotone local search improves the (2-1/c)^n bound to (2-1/c-Ω_c(ε²))^n under pairwise independence.
• With unknown ε under mutual independence, expected running times (2-ε²/4)^n for exhaustive search and (2-1/c-Ω(ε²))^n for MLS are achieved via geometrically decreasing ε guesses.

Surprising findings

• A predictor only marginally better than random guessing (1/2+ε) suffices to get exponential savings over exponential-time search, despite only n bits of advice.

Limitations

• Assumes an oracle/FPT subroutine for extension problem; improvements are in the base only, with constants depending on c and ε.
• Pairwise independence alone gives only 1/(ε²n) failure probability, so high-probability guarantees require mutual independence or large n.
• Unknown-ε results require mutual independence and rely on the predictor's solution being a valid solution to stop.

Experimental setup

Metrics: worst-case running time base

Baselines: brute-force 2^n enumeration monotone local search (2-1/c)^n

Builds on: monotone local search representative set families learning-augmented algorithms

Closest papers by meaning

• Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems (ICML 2024 · similarity 0.86)
• Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.85)
• Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.85)
• Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.85)
• Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.85)
• Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.84)