Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications

• URL: http://arxiv.org/abs/2609.04787v2
• Date: Mon, 07 Sep 2026 02:49:22 GMT
• Title: Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications
• Abstract summary: Learning-augmented algorithms use fallible predictions while retaining formal performance guarantees.<n>This survey synthesizes prediction error measures, consistency--robustness trade-offs, and five representative construction mechanisms.
• Score: 36.362057717354524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning-augmented algorithms use fallible predictions while retaining formal performance guarantees. This survey synthesizes prediction interfaces, error measures, consistency--robustness trade-offs, and five representative construction mechanisms across online optimization, caching, learned data structures, graph problems, and mechanism design. An orthogonal theorem-level axis distinguishes achieved upper bounds from matched asymptotic dependence. Formal guarantees are separated from empirical systems evidence, with explicit treatment of prediction cost, feedback, and composition. The resulting synthesis states sufficient conditions for limited end-to-end reasoning and delineates open problems in cost-aware prediction, endogenous error, semantic predictors, and benchmarking.

Related papers

• Causal-INSIGHT: Probing Temporal Models to Extract Causal Structure [4.718641165826564]
  Causal-INSIGHT is a model-agnostic, post-hoc interpretation framework for extracting model-implied (predictor-dependent) directed, time-lagged influence structure from trained temporal predictors.<n>We introduce Qbic, a sparsity-aware graph selection criterion that balances predictive fidelity and structural complexity without requiring ground-truth graph labels.
  arXiv  Detail & Related papers  (2026-03-26T14:16:37Z)
• Mechanisms vs. Outcomes: Probing for Syntax Fails to Explain Performance on Targeted Syntactic Evaluations [31.54093034816165]
  Large Language Models (LLMs) exhibit a robust mastery of syntax when processing and generating text.<n>No comprehensive study has yet established whether a model's probing accuracy reliably predicts its downstream syntactic performance.
  arXiv  Detail & Related papers  (2025-06-20T01:46:50Z)
• Partial Transportability for Domain Generalization [56.37032680901525]
  Building on the theory of partial identification and transportability, this paper introduces new results for bounding the value of a functional of the target distribution.<n>Our contribution is to provide the first general estimation technique for transportability problems.<n>We propose a gradient-based optimization scheme for making scalable inferences in practice.
  arXiv  Detail & Related papers  (2025-03-30T22:06:37Z)
• Topology-Aware Conformal Prediction for Stream Networks [68.02503121089633]
  We propose Spatio-Temporal Adaptive Conformal Inference (textttCISTA), a novel framework that integrates network topology and temporal dynamics into the conformal prediction framework.<n>Our results show that textttCISTA effectively balances prediction efficiency and coverage, outperforming existing conformal prediction methods for stream networks.
  arXiv  Detail & Related papers  (2025-03-06T21:21:15Z)
• Prediction-Powered Inference [68.97619568620709]
  Prediction-powered inference is a framework for performing valid statistical inference when an experimental dataset is supplemented with predictions from a machine-learning system. The framework yields simple algorithms for computing provably valid confidence intervals for quantities such as means, quantiles, and linear and logistic regression coefficients. Prediction-powered inference could enable researchers to draw valid and more data-efficient conclusions using machine learning.
  arXiv  Detail & Related papers  (2023-01-23T18:59:28Z)
• RIGID: Robust Linear Regression with Missing Data [7.638042073679073]
  We present a robust framework to perform linear regression with missing entries in the features. We show that the proposed formulation, which naturally takes into account the dependency between different variables, reduces to a convex program. In addition to a detailed analysis, we also analyze the behavior of the proposed framework, and present technical discussions.
  arXiv  Detail & Related papers  (2022-05-26T21:10:17Z)
• Parsimonious Inference [0.0]
  Parsimonious inference is an information-theoretic formulation of inference over arbitrary architectures. Our approaches combine efficient encodings with prudent sampling strategies to construct predictive ensembles without cross-validation.
  arXiv  Detail & Related papers  (2021-03-03T04:13:14Z)
• Learning Output Embeddings in Structured Prediction [73.99064151691597]
  A powerful and flexible approach to structured prediction consists in embedding the structured objects to be predicted into a feature space of possibly infinite dimension. A prediction in the original space is computed by solving a pre-image problem. In this work, we propose to jointly learn a finite approximation of the output embedding and the regression function into the new feature space.
  arXiv  Detail & Related papers  (2020-07-29T09:32:53Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  We propose and analyze a novel theoretical and algorithmic framework for structured prediction. We study a large class of loss functions that implicitly defines a suitable geometry on the problem. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.
  arXiv  Detail & Related papers  (2020-02-13T10:30:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.