Learning-Augmented Algorithms

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 39

Oct 1, 2026cs.LG

Robust Non-Clairvoyant Scheduling with Classification Models

We study the classical single-machine scheduling problem of minimizing the sum of completion times of jobs in a non-clairvoyant setting, where the processing time of each job remains unknown until its completion. This is a hard problem for which no constant competitive algorithm is possible. Inspired by robust optimization and learning-augmented algorithms, we introduce a novel robustness framework that leverages structural information provided by a classification model to overcome this limitation. Specifically, we assume that jobs are partitioned into classes and we have access to the confusion matrix of the classifier, whose entry

(k,\ell)

indicates the number of jobs predicted to belong to class~

k

but that actually belong to class~

\ell

. In this manner, we are able to characterize uncertainty as a set of permutations within each predicted class, rather than as a collection of discrete numerical scenarios, avoiding the computational difficulty of classical robust metrics, such as Min-Max and Min-Max Regret. In addition to these worst-case metrics, we also consider the expected objective over all scenarios. We first propose an optimal non-adaptive strategy that is oblivious with respect to all three robust criteria. We then investigate adaptive and randomized algorithms, showing that they can outperform the optimal non-adaptive strategy when the matrix exhibits particular structural properties.

Anthony Dugois, Vincent Fagnon, Giorgio Lucarelli

Univ. Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F-25000 Besançon, France · Université de Lorraine, LCOMS, Metz, France

Robust Optimization Learning-Augmented Algorithms

Sep 28, 2026cs.LG

Predictive Dual Smoothing for Column Generation

Solving large-scale linear programs efficiently is an important challenge in many optimization settings. A key technique is column generation, which alternates between solving the master problem over a restricted subset of the variables, and using a pricing subproblem to identify new variables to add. The pricing subproblem is guided by the dual solution of the current restricted master problem, but oscillations in these dual solutions can substantially slow convergence. Dual stabilization methods address this issue. Dual smoothing is a common stabilization method, which guides the pricing subproblem using a combination of the current dual solution and duals from previous iterations. However, while past dual solutions can stabilize the dual trajectory, they do not necessarily guide pricing towards useful new variables. We therefore introduce predictive dual smoothing, which instead combines the current dual solution with a learned prediction of future duals to steer pricing towards variables that are more useful in subsequent iterations. The predictor is trained offline using supervision extracted from standard column generation trajectories and is used only to modify the pricing subproblem's objective function, while exact reduced-cost checks and fallback pricing with the unsmoothed duals preserve correctness. Experiments on cutting stock and generalized assignment problems show that predictive dual smoothing substantially reduces generated columns and wall-clock time relative to standard column generation and existing classical and learned stabilization methods. These gains extend to out-of-distribution instance sizes, and predictive smoothing provides further improvements when combined with strong classical stabilization.

Senne Berden, Noah Schutte, Andrea Lodi +1

KU Leuven · TU Delft · Cornell Tech

Primal-Dual Optimization Linear Programming Learning-Augmented Algorithms

Sep 27, 2026cs.LG

Compressing Value Predictions for Learning-Augmented Metrical Task Systems

Learning-augmented algorithms for metrical task systems (MTS) can exploit predictions of canonical dual values, but existing formulations typically require a prediction for every state. We study whether these predictions can be compressed to a small set of representative states while retaining their algorithmic value. We introduce landmark-compressed value predictions, in which the predictor reports predicted dual values only at

m

landmarks and the remaining values are reconstructed by a Lipschitz extension. Our algorithm achieves additive excess cost

O(T\,r(L) + \sum_t δ_t)

, where

r(L)

is the covering radius of the landmarks and

δ_t

measures prediction error up to additive shifts; local and value-dependent bounds refine this guarantee. For sparse landmark sets on unit-spaced finite lines, we prove a matching

Ω(T r_m)

lower bound for every randomized algorithm using fixed landmarks, even with advance access to their entire exact absolute-value table. The prediction interface also matters: on two states with one landmark, exact absolute values permit horizon-independent excess, whereas exact relative values force worst-case expected excess linear in

T

. We give PAC guarantees for learning compressed prediction tables, with efficient empirical-risk minimization for fixed landmarks. Our results connect metric coverage, prediction interfaces, and learning guarantees for compressed predictions in online MTS.

Sizhe Li, Yecheng Li, Kun He

School of Artificial Intelligence and Automation Huazhong University of Science and Technology Wuhan, Hubei 430074, China · School of Computer Science and Technology Huazhong University of Science and Technology Wuhan, Hubei 430074, China

Learning-Augmented Algorithms

Sep 21, 2026cs.LG

Augmented Hypothesis Testing with Persona-Based LLM Simulations

A/B testing requires large sample sizes, long timelines, and significant costs. When auxiliary predictions of experimental outcomes are available from machine learning models, uncertain prediction quality precludes replacing human experiments entirely, yet these predictions may still contain useful signal. We propose a principled framework for learning-augmented hypothesis testing that leverages predictions of unknown quality to reduce sample sizes while maintaining statistical validity. Predictions naturally vary in granularity, from coarse aggregate signals to fine-grained individual-level estimates, and our framework addresses both ends of this spectrum: (1) for population-level directional predictions, where only a binary signal on the treatment effect sign is available, we use an asymmetric test and prove consistency and robustness bounds within the learning-augmented algorithms paradigm; (2) for individual-level predictions, we introduce Generalized PPI++ (GPPI), extending Prediction-Powered Inference to handle nonlinear prediction errors through higher-dimensional transformations. Both methods benefit from accurate predictions while remaining robust to inaccurate or adversarial ones. We validate our framework using persona-based LLM simulations, where AI agents equipped with user personas predict individual behavior, as a natural prediction source spanning both granularity levels. Experiments on four real-world datasets demonstrate that our methods, combined with persona-based predictions, substantially reduce experimental costs while preserving rigorous statistical validity.

Ziyad Benomar, Aymen Al Marjani, Paul Missault +1

Amazon Luxembourg, Luxembourg · Amazon Barcelona, Spain

A/b Testing Learning-Augmented Algorithms Prediction-Powered Inference

Sep 14, 2026math.OC

Learning-Augmented Optimization for Strategic Two-Echelon Spare Parts Network Design

We study the strategic design of a two-echelon spare-parts inventory network where evaluating each candidate topology requires an expensive inventory optimization model. The design partitions hundreds of sites into feasible clusters and selects a central replenishment site for each cluster to reduce costs while maintaining service levels. Because the optimizer favors candidates with high predicted savings, it can exploit optimistic surrogate errors. We develop a conservative framework combining a graph neural network ensemble, variable neighborhood search, and set-partitioning recombination. The surrogate is trained on exact cluster evaluations, while a lower quantile of ensemble-predicted savings guides the search to limit optimism. Clusters found during the search are recombined through set partitioning using surrogate-based objective coefficients. The resulting network is evaluated with the exact inventory model, and only this evaluation is used to report performance. In a case study of 246 fulfillment centers in Amazon's North American network, the framework improves combined savings by 30.5% over an optimization baseline based entirely on exact cluster evaluations, while maintaining approximately 99.8% service across six independent replications. Under equal computational budgets, graph-surrogate-guided search achieves higher mean exact savings than a tabular alternative under both scoring schemes. Conservative scoring improves mean savings for both surrogate classes and reduces the share of final-network clusters overestimated by the graph surrogate from 68% to 28%. Predictive and ranking accuracy deteriorate among search-generated candidates with high surrogate scores, indicating that random holdout performance can incompletely characterize surrogate quality during optimization.

Donato Maragno, Marco Caserta, Alberto Sinigaglia +3

Amazon RME · IE University, Department of Operations · Reinforcement Learning Research Lab, UniPD

Surrogate-Assisted Optimization Metaheuristic Optimization Supply Chain Management Learning-Augmented Algorithms

Sep 1, 2026cs.DS

Prediction-Assisted Pricing and Admission for LLM APIs with Stochastic Token Consumption

An LLM application often sells or internally allocates several service products: a small or premium model, a short or long token cap, and possibly multiple posted prices. The operational decision is not merely which model answers a prompt. A price changes purchase probability, a token cap changes both user value and the tail of resource consumption, and accepted requests compete for shared compute and premium-model capacity. Demand and output length are initially uncertain, while an offline model may provide useful but imperfect predictions. We formulate sequential pricing and admission with stochastic resource consumption. Each arriving request belongs to an observable segment. The platform chooses a product--price pair or makes no offer; purchase, revenue, and resource use are then random. An offline predictor supplies a uniform, validated error radius for every segment--product cell. We propose Prediction-Clipped UCB (PCUCB), which intersects the offline prediction interval with an online confidence interval, evaluates products using resource shadow prices, and reserves a sample-path envelope before commitment. The prior gives a fast start when accurate, while online learning protects the platform when predictions are coarse. The analysis is modular. On a simultaneous confidence event, regret against a buffered fluid benchmark is bounded by a pacing term plus the cumulative diameter of the intersected intervals. For

J

segment-product cells and prediction radius

\varepsilon

, this yields

\widetilde O\left( \sqrt{T}+(1+\barΛ) \min\{T\varepsilon,\sqrt{JT}\} \right),

where

\barΛ

bounds operational shadow prices. Thus the algorithm smoothly interpolates between an almost full-information regime and learning from scratch. Hard feasibility holds on every sample path through reservation envelopes.

Patrick Wong

LLM Serving Learning-Augmented Algorithms Dynamic Pricing Online Resource Allocation

Aug 10, 2026cs.LG

MARA: Flow-Matching-Guided Multi-Agent Resource Allocation for Computational Resource Efficient Learning

Allocating limited computation among concurrent learning tasks is difficult when each task must reach a target loss before a deadline but its required training effort is unknown. Existing approaches combine online loss prediction with adaptive resource allocation, yet commonly treat computation as continuously divisible throughput. We instead study a practical setting in which tasks arrive over time and computation is provided by discrete nodes. This setting introduces both uncertain demand and constrained sequential decisions. We propose MARA, which predicts future loss trajectories with conditional flow matching and coordinates compute nodes through a cooperative multi-agent autoregressive policy. A potential-based progress reward supplies intermediate training feedback while preserving the undiscounted task-completion objective. Across in-distribution, reinforcement-learning, and vision workloads, flow matching reduces remaining-resource prediction error relative to weighted least squares. At the scheduler's training load, MARA completes 63.46% of tasks on average, 8.54 percentage points above strong baseline Learning with Adaptive Resource Allocation (LARA), and remains ahead under unseen heavier workloads.

Hanye Zhao, Muning Wen, Yong Yu +1

Shanghai Jiao Tong University

Learning-Augmented Algorithms Online Resource Allocation

Jul 30, 2026hep-th

Learning to Trace Seiberg Dualities

Dualities play an important role in establishing both microscopic and emergent phenomena in a wide range of physical systems. In practice, though, it can often be computationally challenging to establish when two systems are dual, even when all of the "rules of the game" are well-known. Said differently, when confronted with two systems, how can one efficiently establish that they are in fact dual? In this paper we use machine learning methods to address this question for Seiberg dualities of supersymmetric quiver gauge theories. Mathematically, this involves establishing mutations of quivers, which is in turn a variation on the theme of "learning to unknot". On the one hand, this leads us to a practical tool for establishing the computational complexity of different dualities. On the other hand, it also allows us to study how different network architectures learn how to trace Seiberg dualities. We find that for quivers with a modest number of quiver nodes (of order

10

), different network architectures consisting of transformers and multi-layer perceptrons tend to outperform deterministic algorithms. Supplementing the network by well-established pathfinder algorithms (essentially "Google Maps for quivers") leads to an additional improvement in the efficiency and accuracy of the search strategy. We anticipate that this class of questions can serve as a useful benchmark for frontier AI models applied to theoretical physics.

Jonathan J. Heckman, Shani Meynet, Alessandro Mininno +1

Department of Physics and Astronomy, University of Pennsylvania, 209 South 33rd Street, Philadelphia, PA 19104, USA · Department of Physics, University of Wisconsin–Madison, 1150 University Avenue, Madison, WI 53706, USA

Transformer Scientific ML Learning-Augmented Algorithms

Jul 30, 2026cs.LG

Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the algorithms in terms of robustness and consistency. For each

λ\in (0,1]

, we first propose a deterministic learning-augmented \textsc{Balance} algorithm that is

(4/λ+1/λ^2)

-robust and

(4+λ)

-consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is

(e+1)

-competitive against an oblivious adversary, improving over the deterministic

5

-competitive \textsc{Balance} benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of

4

for deterministic online algorithms. Moreover, we establish a lower bound of

e

on the competitive ratio of randomized online algorithms, improving the previous lower bound of

e/(e-1)

. Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is

(e/λ+1/λ^2)

-robust and

(e+λ)

-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.

Tianhang Lu, Runtian Ren, Shengcai Liu +1

Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China

Competitive Analysis Learning-Augmented Algorithms

Jul 25, 2026cs.GT

Online Fair Division with Budget Constraints

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.

Saar Cohen, Nicholas Teh, Paul W. Goldberg +1

Department of Computer Science, University of Oxford, UK

Fair Resource Allocation Learning-Augmented Algorithms Approximation Algorithms Online Resource Allocation

Jul 22, 2026cs.LG

Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization

Learning-enabled decision systems often use offline data or computation to reduce online compute cost. Despite the empirical success of such approaches, there is limited general understanding of how much offline information is needed to achieve a desired accuracy under a fixed online computation budget. We study this question through the lens of amortized parametric optimization: an offline phase stores a finite memory of solved problem instances, and an online phase produces a solution to a new instance by retrieving a warm start and applying

K

steps of projected gradient descent. We analyze this setup for smooth convex parametric optimization over a compact domain, using a nonparametric predictor built from the stored offline solutions. For

μ

-strongly convex objectives, we establish matching upper and lower bounds on the memory required to guarantee

\varepsilon

-accuracy under a fixed online iteration budget

K

. For convex objectives satisfying a

β

-growth condition (

β>2

), we obtain near-matching bounds and identify a phase transition in

K

beyond which additional memory provides no benefit. We further provide a general proof framework that (i) explicitly quantifies the memory cost of acceleration---how much offline memory is required to achieve a prescribed speedup over the unaided online optimizer---and (ii) identifies two key quantities driving this cost: the convergence rate of the online optimizer and the Lipschitz sensitivity of the solution map to the problem parameter. Experiments on parameterized ridge regression confirm the predicted memory--computation--accuracy tradeoffs.

Shijie Pan, Agustin Castellano, Zeyu Shen +1

Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Applied Mathematics and Statistics, Johns Hopkins University Baltimore, MD 21218, USA

Learning to Optimize Learning-Augmented Algorithms

Jul 16, 2026cs.LG

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from

\tilde O(\varepsilon^{-2}\log K)

samples (

K

the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread

R

, none below

Ω(R/\varepsilon^2)

. Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to

26%

of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.

Haifeng Li, Mo Hai

School of Information, Central University of Finance and Economics Beijing 102206, China

Combinatorial Optimization Learning-Augmented Algorithms PAC Learning Approximation Algorithms Statistical Learning Theory

Jul 6, 2026cs.LG

Sensitivity Sampling with Predictions for k-Means Clustering

We study the problem of k-means clustering on large datasets. The state-of-the-art for the problem is given by coresets-based approaches, which build small weighted summaries of the input and derive approximate solutions with rigorous quality guarantees from them. One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling. However, sensitivity sampling requires to compute the importance of each input point with respect to the whole dataset over all possible choices of centers. Since the exact computation of such quantities is unfeasible, current approaches work by approximating the sensitivity values. Nevertheless, the runtime of such approaches is still impractical for large datasets. In this work, we propose to reduce the runtime of sensitivity-based approaches for k-means by leveraging predictions to approximate the importance of input points. We first formally prove that current theoretical results on coresets construction via sensitivity sampling hold for coarser approximations of sensitivities compared to the one required by existing approaches. This implies that even fairly noisy predictors can be leveraged for sensitivity-sampling approaches. We then propose a natural predictor, which applies to the common scenario where clustering is performed (over time) on a sequence of datasets from the same problem. We prove that when the datasets in the sequence come from the same (unknown) distribution, centers resulting in a low error on one dataset can be used as predictions for sensitivity sampling in subsequent datasets, with guarantees on their quality. We perform an extensive experimental evaluation showing that our approach significantly improves, in terms of clustering cost vs runtime, over uniform sampling and state-of-the-art sensitivity sampling approaches when applied to sequences of datasets.

Cristian Boldrin, Fabio Vandin

University of Padova, Padova, Italy

Clustering Importance Sampling Coreset Selection Learning-Augmented Algorithms

Jul 4, 2026cs.DS

TSP with Predictions: Heatmap to Tour with Provable Guarantees

The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent efforts to apply ML to algorithmic problems, TSP has also become a natural testbed for the development of ML-based techniques. A common approach is to train a neural network to output a heatmap estimating the likelihood of each edge to be part of the optimal tour; however, converting such a heatmap into an actual tour remains a non-trivial and often computationally intensive step. In this work, we propose algorithms for transforming heatmaps into tours with theoretical guarantees linking the achieved approximation ratio to the quality of the provided heatmap. In the spirit of algorithms with predictions, our results can be described as

(1+2\fracη{\mathrm{OPT}})

-approximation algorithms, where

η

denotes the L1 distance between the prediction (heatmap) and an optimal solution (tour). Since the previous works lack such explicit guarantees, we compare our approach against them experimentally.

Marek Eliáš, Fabrizio Grandoni, Adam Polak +1

Traveling Salesperson Problem Combinatorial Optimization Learning-Augmented Algorithms Approximation Algorithms Neural Combinatorial Optimization

Jul 1, 2026cs.DB

When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers

LLM agents increasingly rely on retrieval buffers to store and reuse past experience, yet the cache management policies governing these buffers remain largely ad-hoc. We formalize this as an online semantic cache replacement problem with switching costs, where items are matched by embedding similarity and hit quality is continuous rather than binary. Through experiments on two datasets from MemoryBench-Full (LoCoMo, DialSim) with 8 replacement policies, we reveal a surprising finding: classic heuristics (LRU, LFU) \emph{consistently underperform} the naive FIFO baseline on semantic workloads, due to the absence of temporal locality and frequency concentration. We propose SOLAR, a learning-augmented framework that derives modification timing from regret accumulation (achieving

\sim

17% modification rate) and content selection from Bayesian online learning over implicit retrieval feedback. We prove SOLAR achieves a constant competitive ratio

\leq 3

, independent of cache size and horizon (vs.\

Ω(K)

for FIFO), and eviction regret

O(\sqrt{KT\log T})

, matching the

Ω(\sqrt{KT})

lower bound up to logarithmic factors. Experiments demonstrate 5--75% relative improvement over FIFO at tight cache sizes, with a clearly characterized phase transition at the working set boundary. Synthetic experiments with 5000-item pools further reveal an inverted-U relationship between pool size and retrieval quality, justifying capacity constraints as a retrieval noise phenomenon rather than a storage limitation.

Yushi Sun, Bowen Cao, Wai Lam

LIGHTSPEED, Tencent · Shenzhen, China · The Chinese University of Hong Kong +1

Learning-Augmented Algorithms Semantic Caching Agent Memory Management

Jun 25, 2026cs.LG

Asymptotically Optimal Learning for Parametric Prophet Inequalities

We study learning in prophet inequalities with i.i.d. rewards drawn from an exponential-type parametric family with an unknown parameter

θ

, a class that includes exponential, Pareto, and bounded-support power-family distributions. We first characterize the optimal full-information asymptotic competitive ratio for this family. In the unbounded-support case, the limit is

{\left(θ/({θ-c_+})\right)^{c_+/θ}}/ {Γ(1-c_+/θ)},

while in the bounded-support case, the limit is

1

. We then propose a confidence-based dynamic-programming policy for online learning. By exploiting the explicit parametric structure, the policy achieves the same optimal asymptotic competitive ratio using only online observations, without external offline samples. We further derive distribution-specific convergence rates for canonical examples. Finally, numerical experiments on synthetic instances illustrate the performance of our algorithm.

Jung-hun Kim, Anna Grebennikova, Vianney Perchet

FairPlay Team, CREST, ENSAE, Institut Polytechnique de Paris · UFR IM2AG, Université Grenoble Alpes · Criteo AI Lab

Sequential Decision Making Optimal Stopping Learning-Augmented Algorithms Online Learning

Jun 24, 2026cs.LG

Black-Box Assisted Regression: Phase Transitions and Minimax Optimality

Foundation models are often used as fixed black-box predictors for downstream tasks with limited labeled data, but their predictions may be biased and unsafe to trust blindly. We study this setting through black-box assisted nonparametric regression: a learner observes labeled samples and can query a fixed predictor

f_0

, while the target

f^*

is close to

f_0

in

L_2(P_X)

up to an unknown radius

δ

. We give a finite-sample minimax characterization showing a phase transition at

δ_c(n) \asymp n^{-β/(2β+d)}

, with leading risk

\min\{δ^2, n^{-2β/(2β+d)}\}

. We then analyze a Safe Residual Estimator: it learns a correction around

f_0

, initializes the residual head at zero so the initial predictor equals

f_0

, and uses holdout selection to revert to

f_0

when the learned correction is not supported by validation data. Here, "safe" means avoiding negative transfer, i.e., performing worse than the black-box predictor alone. The estimator matches the leading minimax term up to an additive validation-selection cost. Synthetic regression experiments verify the predicted phase transition, while CIFAR-100 with CLIP and AG News with Qwen3-8B provide practice-facing evidence that the same residual-correction tradeoff is useful beyond the formal squared-loss regression setting.

Yan Zhou

School of Mathematics and Statistics, Changsha University of Science and Technology.

Residual Learning Nonparametric Regression Minimax Estimation Learning-Augmented Algorithms

Jun 22, 2026cs.CC

Learning-Augmented Algorithms for Online Vertex Cover

This paper studies learning-augmented online weighted vertex cover with advice and a parameter

λ\in (0,1)

. We consider two graph cases: bipartite graphs and general graphs. In both settings, the online algorithm must maintain a feasible vertex cover under irrevocable decisions. We show that these problems admit the same robustness--consistency tradeoffs as learning-augmented ski rental. For the bipartite graph model, we give a randomized algorithm that is

\frac{1}{1-e^{-λ}}

-robust and

\fracλ{1-e^{-λ}}

-consistent. For the general graph model, we give a deterministic algorithm that is

(1+\frac{1}λ)

-robust and

(1+λ)

-consistent. We prove that the tradeoffs above are optimal in both settings. We also validate the proposed algorithms through experiments on synthetic and real-world datasets.

Tianhang Lu, Runtian Ren, Shengcai Liu

Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China

Competitive Analysis Combinatorial Optimization Learning-Augmented Algorithms

Jun 17, 2026cs.DS

Learning Augmented Exact Exponential Algorithms

The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.

Tatiana Belova, Yuriy Dementiev, Danil Sagunov

ITMO University

Learning-Augmented Algorithms

Jun 11, 2026cs.DS

Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by

R\|C_{\max}

. By using predictions of heavy job assignments, we achieve a polynomial-time

(1+\varepsilon)

-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.

Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos

The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Combinatorial Optimization Learning-Augmented Algorithms Approximation Algorithms

Jun 3, 2026cs.DS

Learning-Augmented Online Minimization with Dual Predictions

We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the

k

-server problem and the parking permit problem.

Christian Coester, Alexa Tudose, Alexander Turoczy

University of Oxford, United Kingdom

Combinatorial Optimization Learning-Augmented Algorithms

Jun 2, 2026cs.NI

AUGUSTE: Online-Learning dApp for Predictive URLLC Scheduling

Ultra Reliable and Low Latency Communications (URLLC) was one of the main motivations behind 5G, with 3GPP advertising 1-10 ms latency targets for applications such as industrial automation, Vehicle-To-Everything (V2X), tactical edge networking, and unmanned-system control. Years on, real 5G Time Division Duplexing (TDD) networks still show median Uplink (UL) round-trip times in the 50-70 ms range, largely because of the Scheduling Request (SR) procedure that a User Equipment (UE) must complete before transmitting UL data. Existing remedies, primarily Configured Grant (CG) scheduling, only eliminate this overhead for strictly periodic traffic and require cross-layer synchronization, which has limited their adoption. We propose AUGUSTE (Anticipatory Uplink Grants for URLLC via Self-Adapting Temporal Estimation), a learning-based Medium Access Control (MAC) scheduling framework that embeds online Machine Learning (ML) models in the UL scheduler to predict packet arrivals and proactively allocate resources before an SR is issued. An adaptive state machine alternates between a learning phase that collects unbiased arrival statistics and a confident phase that exploits the learned predictions to schedule only when traffic is expected. We evaluate AUGUSTE on a real 5G testbed running OpenAirInterface across three URLLC traffic patterns (request-response, ML edge inference, and periodic autonomous reporting), and show that it operates at the best achievable point on the latency-overhead trade-off: it matches always-on scheduling's median Round Trip Time (RTT) (around 10 ms, halving the 20 ms SR-based baseline) at roughly one-tenth its resource cost (7-10 percent overhead).

Maxime Elkael, Michele Polese, Yunseong Lee +2

Institute for Intelligent Networked Systems, Northeastern University (NU), Boston, MA, USA. · SoftBank Corp. (SB), Japan.

Wireless Communications Wireless Resource Allocation Learning-Augmented Algorithms Online Learning

May 31, 2026cs.DS

Towards Optimal Robustness in Learning-Augmented Paging

Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is \emph{bounded robustness}, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bounds of

2H_k + O(1)

in the randomized setting, leaving a gap to the optimal competitive ratio

H_k

. In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest

H_k

-competitive algorithm, which facilitates our analysis in the learning-augmented setting. Then, we review existing learning-augmented paging algorithms and introduce a unifying primitive, the \emph{relative prediction budget}, which captures the essence of establishing robustness and reveals that prior algorithms either overuse or underutilize predictions. Guided by the above analysis, we develop a new framework that achieves the best-possible robustness up to an additive constant for learning-augmented paging:

H_k + O(1)

. Experiments further demonstrate strong practical performance.

Peng Chen, Hailiang Zhao, Xueyan Tang +2

Zhejiang University, Hangzhou, China · Nanyang Technological University, Singapore · Nanjing University of Aeronautics and Astronautics, Nanjing, China

Competitive Analysis Learning-Augmented Algorithms

May 26, 2026cs.DS

Parsimonious Learning-Augmented Online Metric Matching

Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.

Yongho Shin, Phanu Vajanopath

Institute of Computer Science, University of Wrocław, Wrocław, Poland.

Learning-Augmented Algorithms

May 22, 2026cs.LG

Learning-Augmented Online Scheduling with Parsimonious Preemption

Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include

O(1)

-competitive algorithms for single and unrelated parallel machines with only

O(1)

preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.

Mugen Blue, Sungjin Im, Alexander Lindermayr

University of California, Santa Cruz, US. · Institut für Mathematik, Technische Universität Berlin, Germany.

Combinatorial Optimization Learning-Augmented Algorithms

May 21, 2026cs.DS

The Secretary Problem with a Stochastic Precursor

In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least

\frac12

, improving on the classic

\frac1e

benchmark. With increasingly late precursors, the success probability approaches

1

. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.

Franziska Eberle, Alexander Lindermayr

Institut für Mathematik, Technische Universität Berlin, Germany.

Sequential Decision Making Optimal Stopping Learning-Augmented Algorithms

May 19, 2026cs.RO

Learning-Accelerated Optimization-based Trajectory Planning for Cooperative Aerial-Ground Handover Missions

This paper presents a learning-augmented trajectory planning framework for cooperative unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV) handover missions. While centralized trajectory optimization ensures dynamic feasibility and task optimality, its high computational cost limits real-time applicability. We propose a neural surrogate planner utilizing decoupled encoder-decoder long short-term memory (LSTM) networks to generate coordinated handover trajectory predictions from the task specifications. These predictions serve as informed warm starts for the downstream centralized optimizer, thereby accelerating convergence to dynamically feasible solutions. Benchmark evaluations demonstrate that the learning-augmented planning framework achieves more than a threefold speedup and 100% optimization success rate compared to cold start optimization. The results indicate that combining data-driven inference with model-based refinement enables fast and reliable trajectory generation for heterogeneous multi-robot systems.

Jingshan Chen, Bochen Yu, Henrik Ebel +1

Institute of Engineering and Computational Mechanics, University of Stuttgart, 70569 Stuttgart, Germany · Mechanical Engineering, LUT University, 53850 Lappeenranta, Finland

Multi-Robot Motion Planning Trajectory Optimization Trajectory Generation Multi-Robot Coordination UAV Trajectory Optimization Learning-Augmented Algorithms

May 18, 2026stat.ML

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), particularly those with decomposable structures, such as vehicle routing or unit commitment problems. By relaxing the coupling constraints, LR enables parallel subproblem solving and often yields tighter dual bounds than standard linear programming relaxations, which is crucial for efficient branch-and-bound pruning. While recent empirical work has shown promising results using machine learning to predict these multipliers, a theoretical understanding of such methods remains an open question. In this work, we bridge this gap by analyzing the problem of learning LR through the lens of Data-driven Algorithm Design, i.e., a statistical learning problem over a distribution of problem instances. Our contributions are as follows: first, we derive a generalization bound of

\mathcal{O}(s^{1.5}/\sqrt{N})

for the learned multipliers, where

s

is the number of coupling constraints and

N

is the sample size. Second, we provide a minimax lower-bound of

Ω(s/\sqrt{N})

, proving that a linear dependency is unavoidable. Third, we constructively close this theoretical gap by proving that Stochastic Gradient Ascent (SGA) with averaging achieves the minimax optimal rate

Θ(s/\sqrt{N})

. Finally, we extend our framework to the learning-to-warm-start setting, proving that it achieves a fast, minimax-optimal rate of

Θ(s/N)

and establishing a theoretical advantage over direct multiplier prediction.

Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen

Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.

Mixed-Integer Linear Programming Learning to Optimize Constrained Optimization Linear Programming Learning-Augmented Algorithms

May 11, 2026cs.AI

Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

Learning-assisted hyper-heuristics can select among dispatching rules while preserving the feasibility and interpretability of constructive Job Shop Scheduling Problem (JSSP) heuristics. Their main computational cost lies in label generation rather than model fitting, since each supervised label usually requires rolling out candidate rules from a partial schedule. We study this label-cost problem together with a reliability problem: a learned selector should not switch away from a strong default rule unless the predicted gain is credible. The proposed selector uses regret-normalized rollout labels, a contextual KNN uncertainty estimate, and a gate that acts only when the predicted improvement exceeds an uncertainty-adjusted margin. We also vary rollout depth and breadth to measure the cost-quality trade-off. On synthetic JSSP instances, the gated selector achieves the lowest mean RPD among learned selectors, remains close to the best fixed dispatching rule, and reduces Random-HH mean RPD by more than an order of magnitude.

Junhao Wei, Yanxiao Li, Yifu Zhao +8

Faculty of Applied Sciences, Macao Polytechnic University, Macao, 999078, China · College of Animal Science and Technology, Zhongkai University of Agriculture and Engineering, Guangzhou, 510225, China · 4Macao Polytechnic University, Macao, 999078, China

Selective Prediction Metaheuristic Optimization Learning to Optimize Learning-Augmented Algorithms Job Shop Scheduling

May 10, 2026cs.LG

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

The Linear Assignment Problem is a fundamental combinatorial optimization task where classical exact solvers ensure optimality but suffer from an

\mathcal{O}(N^{3})

bottleneck, while recent neural approximations struggle with scalability and exactness. We propose a learning-augmented framework that accelerates exact solvers by predicting dual variables to warm-start the search, backed by a fallback mechanism to preserve worst-case guarantees. Central to our approach is RowDualNet, a lightweight, row-independent architecture that avoids the

\mathcal{O}(N^{2})

memory bottleneck of graph models, enabling scalable neural warm-starting up to

N=16{,}384

. Feasibility is guaranteed by construction via the Min-Trick mechanism, completely eliminating the need for costly iterative projections. Empirically, our method drastically reduces the search effort of the Jonker-Volgenant (LAPJV) algorithm, yielding robust zero-shot generalization with strict optimality and end-to-end speedups of over 2x on complex synthetic data, 1.25x on real-world tracking, and 1.5x on transportation networks.

Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2

Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.

Neural Network Optimization Combinatorial Optimization Learning-Augmented Algorithms