Learning-Augmented Algorithms

Follow this topic Ask about this topic

Recent momentum

-77%

6 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-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.

140 papers

Latest in Learning-Augmented Algorithms

Open your feed →

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
Sep 17, 2026David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1Convex Optimization Lipschitz Constant
Online Adaptive Kernel Mixing for Gaussian Process Decision Making
Sep 17, 2026Kavin Aravindan, Mani Tej Sriram, Gautam Dasarathy +1Gaussian Process Kernel Method
Efficient Robust Learning at the Information-Theoretic Limit
Sep 15, 2026Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1Empirical Risk Minimization Optimal Sample Complexity
Fast-Convergent Meta-RL via Gradient-Clustered BS Sampling for Edge Caching
Sep 14, 2026Farnaz Niknia, Ping WangMeta-Learning Heterogeneous Edge Devices
Learning-Augmented Optimization for Strategic Two-Echelon Spare Parts Network Design
Sep 14, 2026Donato Maragno, Marco Caserta, Alberto Sinigaglia +3Monotonic Inventory Estimation Supply Chain Optimization
Algorithmic stability via ensembling
Sep 9, 2026Rina Foygel Barber, Richard J. SamworthPerturbations Federated Averaging
An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
Sep 9, 2026Xuan LiSharp Joint-Kl Oracle Theory Learning-Augmented Algorithms
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
Sep 8, 2026Ashkan Soleymani, Gabriele Farina, Patrick JailletMirror Descent Linear Regret
Constrained Online Learning with Noisy Constraint Values
Sep 7, 2026Vaneet AggarwalConvex Optimization Learning-Augmented Algorithms
OR-Transformer: Scaling Real-Time Decision-Making to 1,000 Items
Sep 1, 2026Shuze Daniel Liu, David Simchi-Levi, Claire Chen +2Monotonic Inventory Estimation Supply Chain Optimization
Rethinking Learnability in Offline Data-driven Optimization
Sep 1, 2026Chao Qian, Chen-Guang Wang, Rong-Xi Tan +1Black-Box Optimization Learning-Augmented Algorithms
Defensive Boosting for Online Probabilistic Forecasting
Aug 13, 2026Georgy Noarov, Aaron RothLearning-Augmented Algorithms Gradient Boosted Tree
Beyond Binary: Continuous State Optimization with Graph-Structured Objectives
Aug 10, 2026Corinna Cortes, Yishay Mansour, Mehryar MohriLearning-Augmented Algorithms State Space
MARA: Flow-Matching-Guided Multi-Agent Resource Allocation for Computational Resource Efficient Learning
Aug 10, 2026Hanye Zhao, Muning Wen, Yong Yu +1Optimal Scheduling Multi-Agent Reinforcement Learning
Decision-Focused Learning in Network Interdiction Games
Aug 10, 2026Luca M. Hartmann, Parinaz NaghizadehLearning-Augmented Algorithms Shortest Paths
Optimal Learning Under Tsybakov Noise
Aug 9, 2026Steve Hanneke, Hongao Wang, Mingyue XuOptimal Sample Complexity Learning-Augmented Algorithms
Shaping Wind-Tunnel Airflow for Unmanned Aerial Vehicles using Online Learning
Aug 4, 2026Ghadeer Elmkaiel, Michael MuehlebachAerodynamics Flight Performance
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Aug 3, 2026Deeparnab Chakrabarty, Aditi Dudeja, David SaulpicPartitioning Optimal Sample Complexity
Relative Parameter Importance in Task-Agnostic Replay-Free Continual Learning
Aug 1, 2026Malavika Suresh, Ikechukwu Nkisi-Orji, Nirmalie WiratungaEfficient Continual Learning Continual Learning Methods
ALIVE: Warnings Before Exclusion in Budgeted Multi-Source Learning
Jul 31, 2026Xiyang Zhang, Hongzhi Wang, Yuanhe TianAlgorithm Auditing Token Budgets
Fast Rates for Swap-Agnostic Learning of Proper Losses
Jul 30, 2026Princewill OkoroaforLearning-Augmented Algorithms Optimal Sample Complexity
Operationally Guided Placement-Aware Learning for Industrial Online 3D Bin Packing
Jul 30, 2026Dheeraj Poolavaram, Aanchal Rajesh Chugh, Sebastian DornKnapsack Constraint 3D Layout Generation
Multi-channel Uplift Policy Learning
Jul 30, 2026Changjian Liu, Tianyu Wang, Xiaoxuan Deng +7Funnel Efficiency Learning-Augmented Algorithms
LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning
Jul 30, 2026Mohand Mezmaz, Grégoire DanoyMetaheuristics Llm-Based Optimization Modeling
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
Jul 30, 2026Tianhang Lu, Runtian Ren, Shengcai Liu +1Learning-Augmented Algorithms Stochastic Delays
Kairos: Numerically Robust News Recommendation under Item Cold-Start via Cholesky-based LinUCB
Jul 29, 2026Finn HertschLarge-Scale Recommendation Systems Cold-Start
Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction
Jul 29, 2026Rahul VazeFinite-Sample Coverage Guarantees Conformal Inference
Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling
Jul 28, 2026Itai Zilberstein, Pranav Rajbhandari, Steve Chien +1Learning-Augmented Algorithms Prices
Adaptive Data Admission and Retention for Streaming Federated Learning
Jul 27, 2026Zhuoyi Zhao, Ben LiangFederated Learning Learning-Augmented Algorithms
Kutti AI: A Voice-First, Offline-Capable Learning Companion with Real-Time Struggle Detection for Visually-Impaired Children
Jul 24, 2026Kadharmoideen FadurudeenVoice Agents Automatic Speech Recognition Systems
Smart predict-then-robustly-optimize
Jul 23, 2026Aakil Caunhye, Xuefei Lu, Belen Martin-BarraganRobust Optimization Predictive Uncertainty
Probabilistic Residual Learning for Online Recommendations
Jul 23, 2026Wenyuan Wang, Yusong Zhao, Zihao Xu +11Residual Learning Learning-Augmented Algorithms
Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization
Jul 22, 2026Shijie Pan, Agustin Castellano, Zeyu Shen +1Learning-Augmented Algorithms Optimizer Design
Adaptive Bayesian Online Learning via Expert Aggregation
Jul 22, 2026Jungbin Jun, Ilsang OhnLearning-Augmented Algorithms Bayesian
Optimal Recalibration of an Online Predictor
Jul 22, 2026Lunjia Hu, Kevin Tian, Chutong YangRecalibration Multicalibration and Calibration
Adaptive Two-Stage Online Learning for Service-Affecting Failure Detection in Mobile Core Networks
Jul 20, 2026J. du Toit, G. Fita, J. Salzwedel +2Early Failure Prediction Mobile Networks
Weak-to-Strong Learning in Decision Making
Jul 20, 2026Jingwei Ji, Renyuan XuWeak Supervision Learning-Augmented Algorithms
A Predict-then-Correct Loop Based on Few-Shot Continuous Contextual Bandit for Demand Forecasting
Jul 17, 2026Zhiwei Lei, Benedict Jun Ma, Ilya JacksonDemand Forecasting Linear Contextual Bandits
CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
Jul 16, 2026Haifeng Li, Mo HaiCertificates Learning-Augmented Algorithms
Efficient Online Proportional Sampling with Applications to Smoothed Online Learning
Jul 13, 2026Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh BeyhaghiLearning-Augmented Algorithms Optimal Sample Complexity
Kernel-based Operator Learning: Error Analysis, Budget Allocation, and a Physics-Informed Extension
Jul 7, 2026Rüdiger KempfProbabilistic Operator Learning Physics-Informed Machine Learning
Online Linear Programming for Multi-Objective Routing in LLM Serving
Jul 4, 2026Zixi Chen, Yinyu Ye, Zijie ZhouLarge Language Model Routing Large Language Model Serving
Selectivity Estimation for Linear Queries via Online Learning
Jul 3, 2026Fangzhu Shen, Debmalya Panigrahi, Sudeepa RoyLearning-Augmented Algorithms Selectivity
When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
Jul 1, 2026Yushi Sun, Bowen Cao, Wai LamCache Learning-Augmented Algorithms
Hybrid Active-Online Learning Framework for Label-Efficient Concept Drift Adaptation in Optical Network Failure Detection
Jun 29, 2026Yousuf Moiz Ali, Jaroslaw E. Prilepsky, João Pedro +4Learning-Augmented Algorithms Active Learning
A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming
Jun 28, 2026Yaohui Guo, X. Jessie Yang, Cong ShiBipartite Perfect Matchings Multi-Robot Systems
Adaptive Iterative Hard Thresholding for Online High-dimensional Quantile Regression
Jun 26, 2026Zitian Zhou, Nan LinQuantile Regression Learning-Augmented Algorithms
Non-Linear Strategic Classification Made Practical
Jun 26, 2026Jack Geary, Boyan Gao, Henry GoukLearning-Augmented Algorithms Zeroth-Order Optimization
Learning Optimization Proxies for Sequential Contextual Stochastic Programs: An Order Fulfillment Application
Jun 24, 2026Tinghan Ye, Shuaicheng Tong, Changkun Guan +2Dynamic Order Fulfillment Operations Stochastic Optimization
Topological Online Learning for Displacement-based Formation Control
Jun 22, 2026Saksham Sharma, Shubhankar Gupta, Sumant A Gunagi +1Robust Formation Control Adaptive Controller
DT-GOL: Dual-Track Geometric Online Learning in Nonstationary Environment with Label Delay
Jun 22, 2026Yulin Wang, Yi He, Dianlong You +1Learning-Augmented Algorithms Non-Stationarity
Learning-Augmented Algorithms for Online Vertex Cover
Jun 22, 2026Tianhang Lu, Runtian Ren, Shengcai LiuLearning-Augmented Algorithms Maximum Independent Set
Sequential Minimal Optimization Algorithm for One-Class Support Vector Machines With Privileged Information
Jun 20, 2026Andrey Lange, Dmitry Smolyakov, Evgeny BurnaevSupport Vector Machines Learning-Augmented Algorithms
Decision-Focused Learning: When and Why Traditional Prediction Models Fail
Jun 19, 2026Mo LiuPredictive Uncertainty Sequential Decision Making
Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation
Jun 19, 2026Jianwei LouLearning-Augmented Algorithms Cold-Start
Provably Sub-Linear Two-Timescale NeuroEvolution with Online Plasticity
Jun 18, 2026Shishen Lin, Yixin ChenNeural Control Learning-Augmented Algorithms
OnDeFog: Online Decision Transformer under Frame Dropping
Jun 18, 2026Daiki Yotsufuji, Kenta Nishihara, Shoma Shimizu +2Offline Reinforcement Learning Learning-Augmented Algorithms
A Solver-Free Training Method for Predict-then-Optimize
Jun 17, 2026Beichen Wan, Mo LiuLearning-Augmented Algorithms Llm-Based Optimization Modeling
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

Sep 17, 2026 · math.OCJ/K move · Enter open · S save

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina

We study first-order black-box convex optimization over an

\ell_p

-ball for objectives Lipschitz in the

\ell_q

-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set (

p < q

) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors. Our rates include

\widetilde O(1/T)

for convex Euclidean-Lipschitz optimization over the

\ell_1

-ball, improving on the

O(1/\sqrt{T})

classical rate under general assumptions. The key technical device is a new online learning game, where the comparator is evaluated using the maximum of affine losses observed so far. We bound the value of this game above and below in terms of a combinatorial online learning quantity: the sequential fat-shattering dimension, which we characterize for the

\ell_p / \ell_q

case. Our results generally apply when the feasible set

X

and the set of possible subgradients

H

are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.

Convex Optimization Lipschitz Constant Spectral Norm Learning-Augmented Algorithms

Open paper Ask about it PDF