Machine Learning and Algorithms

Derniers papiers

• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition

  Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan · 30 juin 2026

  We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to an abstention budget $\alpha$, we analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining. Our central…

• Actively Learning Halfspaces without Synthetic Data

  Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So · 30 juin 2026

  In the classic point location problem, one is given an arbitrary dataset $X \subset \mathbb{R}^d$ of $n$ points with query access to an unknown halfspace $f : \mathbb{R}^d \to \{0,1\}$, and the goal is to learn the label of every point in $X$. This problem is extremely well-studied and a nearly-opti…

• Generating in the Limit with Infinitely Many Hallucinations

  Irene Strauss, Alexandra Butoi, Ryan Cotterell · 30 juin 2026

  The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner tasked with identifying that language. The recently introduced framework of language generation in the limit shifted the obj…

• When Is a Draft Accepted? A Theory of Acceptance in Speculative Decoding

  Aaryam Sharma · 30 juin 2026

  Speculative decoding accelerates language model inference by using a fast drafter to propose candidate tokens that are then verified by a larger target model. Existing theory largely studies the stochastic, distribution-preserving setting, where the goal is to exactly sample from the target distribu…

• Machine-learnable Sets

  Veit Elser, Manish Krishan Lal · 30 juin 2026

  In this study we present a formal definition of large discrete sets having, informally, three properties: their elements are easily recognized, easily generated, and the latter tasks are easily learned from examples. The formalism is specialized to sets of binary strings and a definition of "machine…

• Learning to Reason with Curriculum II: Compositional Generalization

  Nived Rajaraman, Audrey Huang, Miroslav Dudik, Robert Schapire, Dylan Foster, Akshay Krishnamurthy · 29 juin 2026

  Compositional generalization, the ability to solve complex problems by combining solutions to simpler sub-problems, is a fundamental capability of both natural and artificial intelligence, and a key mechanism underlying chain-of-thought reasoning. However, the theoretical underpinnings of compositio…

• Surprises in Proper Positive-Only Learning

  Shai Ben-David, Farnam Mansouri, Anay Mehrotra, Manolis Zampetakis · 29 juin 2026

  Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, but is evaluated under the original distribution (which places mass on both positive and negative regions). This model dat…

• Learning from a Biased Sample

  Roshni Sahoo, Lihua Lei, Stefan Wager · 26 juin 2026

  The empirical risk minimization approach to data-driven decision making requires access to training data drawn under the same conditions as those that will be faced when the decision rule is deployed. However, in a number of settings, we may be concerned that our training sample is biased in the sen…

• Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis

  Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, Adam Wierman · 26 juin 2026

  We present a finite-sample analysis of decentralized learning in two-player zero-sum matrix games and stochastic games, with a focus on best-response-based learning algorithms. In matrix games, the learning algorithm is payoff-based and symmetric: each player updates its policy using only its own pa…

• Why Pool When You Can Flow? Active Learning with GFlowNets

  Renfei Zhang, Mohit Pandey, Artem Cherkasov, Martin Ester · 25 juin 2026

  The scalability of pool-based active learning is limited by the computational cost of evaluating large unlabeled datasets, a challenge that is particularly acute in virtual screening for drug discovery. While active learning strategies such as Bayesian Active Learning by Disagreement (BALD) prioriti…

• Space-Efficient Language Generation in the Limit

  Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, Ola Svensson · 25 juin 2026

  We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language $K$ and must eventually output a hallucination-free hypothesis language $L \su…

• Learning through Internalization

  Nikolaos Tsilivis, Nirmit Joshi, Marko Medvedev, Julia Kempe, Nati Srebro · 23 juin 2026

  We study internalization processes, by which neural-network-based systems absorb an explicit computational procedure into their own weights, and how they facilitate learning. We investigate how transformers internalize the simulation of semiautomata by internalizing chain-of-thought (CoT) tokens, wh…

• Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models

  Alireza F. Pour, Farnam Mansouri, Shai Ben-David · 23 juin 2026

  We study the problem of learning with multiple correct answers, where each instance admits a set of valid labels. We primarily focus on the online setup, where in each round the learner must output a valid label for the queried example. This setting is motivated by language generation, in which a pr…

• Channel Location Constrains the Auditability of Subliminal Learning

  Tamas Madl · 23 juin 2026

  Subliminal learning lets a student inherit a teacher's hidden trait from distillation data that never names it. We ask when such transfer can be audited before training. The answer is not model identity or scale alone, but channel location: the carrier through which the trait reaches the student. We…

• Optimal Deterministic Multicalibration and Omniprediction

  Georgy Noarov, Aaron Roth · 19 juin 2026

  A model is multicalibrated on a collection of group weights $G$ if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each $g \in G$. It is a useful property for many downstream applications and is a basic desideratum of t…

• Benign overfitting beyond prediction: The ordinary least squares interpolator

  Dennis Shen, Dogyoon Song, Peng Ding, Jasjeet S. Sekhon · 19 juin 2026

  Recent advances in deep learning have highlighted the phenomenon of benign overfitting in overparameterized statistical models, sparking significant interest in understanding its foundations. Owing to its simplicity and practical relevance, the ordinary least squares (OLS) interpolator has become a …

• Zero-Shot Active Feature Acquisition via LLM-Elicitation

  Binyamin Perets, Natalie Mendelson, Shiran Vainberg, Yehuda Chowers, Shai Shen-Orr, Shie Mannor · 18 juin 2026

  Active feature acquisition (AFA) sequentially selects which features to observe to reach a classification or ranking decision. Its central limitation is reliance on large amount of labeled data to fit probabilistic models guiding acquisition. Large language models (LLMs) supply unsupervised domain k…

• Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials

  Jasper van Doornmalen, Mathieu Molina, Victor Verdugo, Jos\'e Verschae · 17 juin 2026

  Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform $L_\infty$-error guarantees rather th…

• Bounded Difference Concentration for Infinitely Exchangeable Sequences with Applications to AI Benchmark Uncertainty

  Fangyuan Lin, Spencer Frei, Victor H. de la Pena · 17 juin 2026

  We consider the concentration properties of functions of infinitely exchangeable random variables. By conditioning on the de Finetti directing measure, we show that the deviation of any function with bounded-difference constants $c_1, \dots, c_n$ decomposes into a conditional sampling fluctuation an…

• Sign-Rank, Index, and List Replicability: Connections and Separations

  Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak · 17 juin 2026

  In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bound…

• On Rate-Optimal Partitioning Classification from Observable and from Privatised Data

  Bal\'azs Csan\'ad Cs\'aji, L\'aszl\'o Gy\"orfi, Ambrus Tam\'as, Harro Walk · 15 juin 2026

  In this paper we revisit the classical method of partitioning classification and prove novel convergence rates under relaxed conditions, both for observable (non-privatised) and for privatised data. We consider the problem of classification in a $d$ dimensional Euclidean space. Previous results on t…

• The Power of Test-Time Training for Approximate Sampling

  Noah Golowich, Ankur Moitra, Dhruv Rohatgi · 11 juin 2026

  Efficiently sampling from a complex probability distribution is a fundamental problem which has become increasingly pertinent in recent years with the rise of generative AI, as sophisticated sampling procedures from LLMs have been proposed to solve challenging reasoning problems. The efficacy of suc…

• Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more

  Spencer Compton, Jerry Li · 11 juin 2026

  We study the task of density estimation, where we hope to accurately estimate a probability density from $n$ samples. A textbook method for density estimation in total variation distance is the minimum-distance estimator approach, where we conclude both the algorithm and the analysis merely from bou…

• Counterexample Guided Learning in the Large using Reasoning Agents

  Hongyi Liu, Frederic Sala, Thomas Reps, Adithya Murali · 11 juin 2026

  LLMs and LLM agents should improve when given feedback, but identifying when they are able to do so is difficult: feedback is heterogeneous, domain-specific, and difficult to control. We approach this challenge by asking LLMs to perform regular-expression induction, a classical symbolic learning pro…

• Robust Active Learning for Few-Shot Example Selection in Text-to-SQL

  Arash Pourhabib · 10 juin 2026

  Few-shot example retrieval is the dominant paradigm for grounding large language models (LLMs) in domain-specific text-to-SQL systems. However, the quality of the annotated example bank directly governs system accuracy, and expert annotation is prohibitively expensive. We formalize the active select…