New Algorithm Achieves Optimal Robustness in Learning-Augmented Paging
A new algorithmic framework achieves a robustness bound of H_k + O(1) for learning-augmented paging, closing a longstanding gap from the prior best of 2H_k + O(1) down to the optimal competitive ratio H_k. The work, accepted at ICML 2026, introduces a unifying concept called the 'relative prediction budget' to analyze how existing algorithms over- or under-utilize machine learning predictions. This matters because robust learning-augmented algorithms provide worst-case performance guarantees even when predictions are wrong, making them more trustworthy for deployment in real-world systems.
Learning-augmented paging algorithms combine classical online algorithms with machine learning predictions to improve cache management performance, while maintaining provable worst-case guarantees when predictions fail. Prior work in the randomized setting had achieved robustness bounds of 2H_k + O(1), leaving a significant gap relative to the theoretically optimal competitive ratio of H_k. The authors first establish a new property of the current best H_k-competitive online paging algorithm, which serves as a foundation for their learning-augmented analysis. They then introduce the 'relative prediction budget,' a unifying primitive that characterizes how predictions should be consumed, revealing that prior algorithms either overuse or underutilize available prediction information. Building on this analysis, the paper presents a new algorithmic framework that achieves H_k + O(1) robustness — optimal up to an additive constant — in the learning-augmented setting. Experimental results are reported to confirm strong practical performance beyond the theoretical guarantees. The work has been accepted at ICML 2026.
What's missing
The paper does not detail the specific datasets or workloads used in experiments, nor does it discuss computational overhead introduced by the new framework relative to prior algorithms. It is also unclear how performance scales with prediction accuracy in intermediate regimes between perfect and adversarial predictions.
What different sources said
- arXiv cs.LGCenter
Towards Optimal Robustness in Learning-Augmented Paging
Related
Gut Bacteria Enzyme Found to Break Down Heat-Processed Food Compounds, Producing Novel Biogenic Amines
Researchers have discovered that an enzyme in common gut bacteria can degrade N-epsilon-carboxymethyllysine (CML), a compound formed during thermal food processing, producing previously unknown biogenic amines. The enzyme, ornithine decarboxylase SpeC from enterobacteria, acts on CML and related modified lysine derivatives through a low-level 'underground' catalytic activity. This finding suggests a previously unrecognized communication axis between thermally processed dietary compounds and gut microbial physiology, with potential implications for host health.
Full-Length Gene Sequencing Reveals Two Distinct Bacterial Communities in Black-Legged Ticks Expanding Into Canada
Researchers used Oxford Nanopore full-length 16S rRNA gene sequencing to characterize the microbiome of Ixodes scapularis black-legged ticks collected in Nova Scotia, Canada, distinguishing between tick-adapted bacteria and environmentally acquired bacteria. The study comes as I. scapularis — the primary vector of Lyme disease — is rapidly expanding northward into Canada due to climate change. The findings suggest that environmentally derived bacteria in tick microbiomes are not mere contamination, which has implications for how tick microbiome data is collected and interpreted across surveillance studies.
Study Identifies Metabolic Link Between Cell Envelope Stress and Biofilm Formation in Bacteria
Researchers have discovered that the metabolite acetyl-CoA directly inhibits enzymes that degrade the bacterial signaling molecule c-di-GMP, connecting cell envelope biosynthesis stress to biofilm formation in Pseudomonas aeruginosa. The study found that sub-inhibitory concentrations of antibiotics targeting early peptidoglycan biosynthesis — but not other antibiotic classes — elevate c-di-GMP levels by reducing phosphodiesterase activity, with acetyl-CoA competing for the enzyme active site. Because the relevant enzyme domain is broadly conserved across bacterial species, this checkpoint mechanism may be widespread and could have implications for understanding antibiotic-induced biofilm responses.