Learning-Augmented Algorithms

Follow this topic Ask about this topic

Recent momentum

-28%

13 papers in the last 28 days · 0.2% of indexed attention

Twelve weeks of publication activity for this topic as it is defined today.

Weekly history

Recent digests

What was published in this topic, kept on the site without email delivery.

Period ending 2026-09-21

5 new papers

A weekly snapshot of new work published in Learning-Augmented Algorithms.

Period ending 2026-09-14

3 new papers

A weekly snapshot of new work published in Learning-Augmented Algorithms.

Period ending 2026-09-07

2 new papers

A weekly snapshot of new work published in Learning-Augmented Algorithms.

143 papers

Latest in Learning-Augmented Algorithms

Open your feed →

Learning Augmented Exact Exponential Algorithms
Jun 17, 2026Tatiana Belova, Yuriy Dementiev, Danil SagunovLearning-Augmented Algorithms Machine Learning
When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?
Jun 16, 2026Xuanfei Ren, Tengyang XieOffline Reinforcement Learning Learning-Augmented Algorithms
QueryMarket: Cost-Aware Online Active Learning in Data Markets
Jun 16, 2026Xiwen Huang, Pierre PinsonLearning-Augmented Algorithms Active Learning
SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums
Jun 14, 2026Igor Sokolov, Laurent Condat, Peter RichtárikVariance Reduction Convergence Analysis
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
Jun 11, 2026Kaito Baba, Evripidis Bampis, Giorgos MitropoulosApproximation Algorithms Approximation
Efficiently Learning Drifting Halfspaces with Massart Noise
Jun 9, 2026Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1Optimal Sample Complexity Learning-Augmented Algorithms
Scaling Decision-Focused Learning to Large Problems with Lagrangian Decomposition
Jun 7, 2026Stéphane Eilles-Chan Way, Hugo Percot, Quentin Cappart +2Learning-Augmented Algorithms Lagrangian Methods
Theoretical Foundations of Continual Learning via Drift-Plus-Penalty
Jun 7, 2026Nazreen Shah, Govinda Arya, Bharath B. N. +1Efficient Continual Learning Continual Learning Methods
Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making
Jun 5, 2026Kang Liu, Jianchen Hu, Ziyu Qu +3Feedback Linearization Mini-Batch Stochastic Gradient Descent
CLaaS: Continual learning as a service for sample efficient online learning
Jun 4, 2026Kion Fallah, Silen Naihin, Barak Widawsky +1Efficient Continual Learning Continual Learning Methods
Learning-Augmented Online Minimization with Dual Predictions
Jun 3, 2026Christian Coester, Alexa Tudose, Alexander TuroczyLearning-Augmented Algorithms Primal-Dual Methods
Online Learning with Gradient-Variation Interval Regret
Jun 2, 2026Yan-Feng Xie, Shuche Wang, Peng Zhao +1Learning-Augmented Algorithms Linear Regret
Towards Optimal Robustness in Learning-Augmented Paging
May 31, 2026Peng Chen, Hailiang Zhao, Xueyan Tang +2Learning-Augmented Algorithms Optimality
Linear Strategic Classification with Endogenous Improvements
May 31, 2026Siddharth Shrivastava, Mahvith Akshintala, B Vamsha Vardhan Reddy +3Object Classification Learning-Augmented Algorithms
Parameter-Free and Group Conditional Online Conformal Prediction
May 29, 2026Beepul Bharti, Ambar Pal, Jacopo Teneggi +1Finite-Sample Coverage Guarantees Conformal Prediction
When Softmax Fails at the Top: Extreme Value Corrections for InfoNCE
May 29, 2026Melihcan Erol, Suat Evren, Oktay Ozel +3Contrastive Learning Learning-Augmented Algorithms
Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference
May 29, 2026Salim I. Amoukou, Saumitra Mishra, Manuela VelosoDecision Trees Random Forest
Active Timepoint Selection for Learning Measure-Valued Trajectories
May 28, 2026Nicolas Huynh, Mihaela van der SchaarActive Learning Uncertainty-Aware Inference
Universal Multiclass Transductive Online Learning
May 28, 2026Steve Hanneke, Hongao WangTransductive Active Labeling Learning-Augmented Algorithms
Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning
May 27, 2026Tommaso Cesari, Roberto ColomboniDifferential Privacy Learning-Augmented Algorithms
Online Irregular Multivariate Time Series Forecasting via Uncertainty-Driven Dual-Expert Calibration
May 27, 2026Haonan Wen, Hanyang Chen, Songhe FengMultivariate Time Series Forecasting Time Series
Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization
May 27, 2026Sara Gjorgjieva, Eva Tuba, Tome EftimovStochastic Optimization Learning-Augmented Algorithms
Decentralized Parameter-Free Online Learning with Compressed Gossip
May 27, 2026Tomas Ortega, Hamid JafarkhaniLearning-Augmented Algorithms Near-Optimal Regret Guarantees
Agile Online Model Selection: Resolving Adaptation Lag via Safeguarded Large Learning Rates
May 26, 2026Kei Takemura, Ryuta Matsuno, Keita SakumaLearning-Augmented Algorithms Learning Rates
Parsimonious Learning-Augmented Online Metric Matching
May 26, 2026Yongho Shin, Phanu VajanopathLearning-Augmented Algorithms Meta-Learning
Joint Optimization of Training and Inference in Federated Edge Learning via Constrained Multi-Objective Deep Reinforcement Learning
May 25, 2026Zhen Li, Jun Cai, Chao Yang +1Heterogeneous Edge Devices Resource-Constrained Edge Devices
How to Mitigate the Distribution Shift Problem in Robotics Control: A Robust and Adaptive Approach Based on Offline to Online Imitation Learning
May 25, 2026Hyung-Suk Yoon, Seung-Woo SeoImitation Learning Distribution Shifts
T2S-MPC: Time-Embedded Online Adaptive Model Predictive Control for Time-Varying Dynamics
May 24, 2026Zeyu Shen, Zhuoyuan Wang, Laixi ShiModel Predictive Control Time-Varying Systems
Streaming Reinforcement Learning under Partial Observability with Real-Time Recurrent Learning
May 23, 2026Noah Farr, Aryaman Reddi, Carlo D'Eramo +1Deep Reinforcement Learning Learning-Augmented Algorithms
Learning-Augmented Online Scheduling with Parsimonious Preemption
May 22, 2026Mugen Blue, Sungjin Im, Alexander LindermayrOptimal Scheduling Learning-Augmented Algorithms
Truthful Online Preference Aggregation for LLM Fine-Tuning in Mobile Crowdsourcing
May 22, 2026Shugang Hao, Lingjie DuanCrowdsourced Framework Large Language Model Fine-Tuning
The Secretary Problem with a Stochastic Precursor
May 21, 2026Franziska Eberle, Alexander LindermayrOptimal Stopping Learning-Augmented Algorithms
Nonparametric Learning and Earning with One-Point Feedback under Nonstationarity
May 20, 2026Xiangyu Yang, Feng Xu, Jian-Qiang Hu +1Non-Stationarity Learning-Augmented Algorithms
A Geometric Approach to Constrained Online Learning
May 20, 2026Dhruv Sarkar, Abhishek SinhaConvex Optimization O(T^Β)$ Simultaneous Regret
Online Conformal Prediction with Corrupted Feedback
May 19, 2026Bowen Wang, Matteo Zecchin, Osvaldo SimeoneConformal Prediction Finite-Sample Coverage Guarantees
MANGO: Meta-Adaptive Network Gradient Optimization for Online Continual Learning
May 18, 2026Ankita Awasthi, Marco Apolinario, Kaushik RoyEfficient Continual Learning Learning-Augmented Algorithms
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
May 18, 2026Tung Quoc Le, Anh Tuan Nguyen, Viet Anh NguyenMixed-Integer Programming Semidefinite Programming
COOPO: Cyclic Offline-Online Policy Optimization Algorithm
May 18, 2026Qisai Liu, Zhanhong Jiang, Joshua Russell Waite +3Offline Reinforcement Learning Learning-Augmented Algorithms
RL4RLA: Teaching ML to Discover Randomized Linear Algebra Algorithms Through Curriculum Design and Graph-Based Search
May 18, 2026Jinglong Xiong, Xiaotian Liu, Ruoxin Wang +4Deep Reinforcement Learning Learning-Augmented Algorithms
Towards Sustainable Growth: A Multi-Value-Aware Retrieval Framework for E-Commerce Search
May 18, 2026Yifan Wang, Yixuan Wang, YiDan Liang +2Products Learning-Augmented Algorithms
Form and Function: Machine Unlearning as a Problem of Misaligned States
May 17, 2026Kennon StewartMachine Unlearning Learning-Augmented Algorithms
Efficient Online Conformal Selection with Limited Feedback
May 14, 2026Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala +1Conformal Inference Learning-Augmented Algorithms
ROAD: Adaptive Data Mixing for Offline-to-Online Reinforcement Learning via Bi-Level Optimization
May 14, 2026Letian Yang, Xu Liu, Yiqiang Lu +3Offline Reinforcement Learning Learning-Augmented Algorithms
Online Learning-to-Defer with Varying Experts
May 12, 2026Dang Hoang Duy, Yannis Montreuil, Maxime Meyer +3Learning-Augmented Algorithms Experts
MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound
May 12, 2026Phu-Hoa Pham, Chi-Nguyen Tran, Nguyen Lam Phu Quy +3Efficient Continual Learning Decision Trees
Online Sharp-Calibrated Bayesian Optimization
May 11, 2026Marshal Arijona Sinaga, Julien Martinelli, Teemu Turpeinen +1Bayesian Optimization Gaussian Process
Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift
May 11, 2026Bochao Li, Yao Fu, Wei Chen +1Thompson Sampling Learning-Augmented Algorithms
Online Set Learning from Precision and Recall Feedback
May 10, 2026Lee Cohen, Yishay Mansour, Shay Moran +1Learning-Augmented Algorithms Optimal Sample Complexity
Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates
May 10, 2026Anik Kumar Paul, Nibedita Roy, Nagesh Talagani +3Learning-Augmented Algorithms Zeroth-Order Optimization
Instance-Adaptive Online Multicalibration
May 10, 2026Zhiming Huang, Jamie Morgenstern, Aaron Roth +1Learning-Augmented Algorithms Multicalibration and Calibration
Non-Parametric Rehearsal Learning via Conditional Mean Embeddings
May 9, 2026Wen-Bo Du, Tian-Zuo Wang, Han-Jia Ye +1Learning-Augmented Algorithms Uncertainty-Aware Inference
Characterizing and Correcting Effective Target Shift in Online Learning
May 8, 2026Ziyan Li, Naoki HirataniLearning-Augmented Algorithms Online Learning
\mathsf{VISTA}: Decentralized Machine Learning in Adversary Dominated Environments
May 8, 2026Hanzaleh Akbari Nodehi, Parsa Moradi, Soheil Mohajer +1Learning-Augmented Algorithms Adversarial Training
Flexible Routing via Uncertainty Decomposition
May 8, 2026Charlotte Peale, Siddartha Devic, Parikshit Gopalan +2One-Shot Routing Uncertainty-Aware Inference
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
May 8, 2026Idan Attias, Steve Hanneke, Arvind RamaswamiLearning-Augmented Algorithms Regret
Hedging Memory Horizons for Non-Stationary Prediction via Online Aggregation
May 7, 2026Yutong Wang, Yannig Goude, Qiwei YaoLlm-Based Forecasting Methods Electricity Price Forecasting
SOPE: Stabilizing Off-Policy Evaluation for Online RL with Prior Data
May 7, 2026Carlo Romeo, Girolamo Macaluso, Alessandro Sestini +1Off-Policy Evaluation Learning-Augmented Algorithms
Online Localized Conformal Prediction
May 6, 2026Yuheng Lai, Garvesh RaskuttiConformal Prediction Conformal Inference
When Life Gives You BC, Make Q-functions: Extracting Q-values from Behavior Cloning for On-Robot Reinforcement Learning
May 6, 2026Lakshita Dodeja, Ondrej Biza, Shivam Vats +5Behavior Cloning Scalable Robot Learning
On-line Learning in Tree MDPs by Treating Policies as Bandit Arms
May 6, 2026Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir +1Markov Decision Processes Bandits

Jun 17, 2026 · cs.DSJ/K move · Enter open · S save

Learning Augmented Exact Exponential Algorithms

Tatiana Belova, Yuriy Dementiev, Danil Sagunov

ITMO University

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.

Learning-Augmented Algorithms Machine Learning

Open paper Ask about it PDF