Machine Learning and Algorithms

Derniers papiers

• Separating Oblivious and Adaptive Models of Variable Selection

  Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu · 19 février 2026

  Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with $\ell_\infty$ error guarantees. This variant of the problem is motivated by \emph{variable sel…

• Beyond Labels: Information-Efficient Human-in-the-Loop Learning using Ranking and Selection Queries

  Bel\'en Mart\'in-Urcelay, Yoonsang Lee, Matthieu R. Bloch, Christopher J. Rozell · 18 février 2026

  Integrating human expertise into machine learning systems often reduces the role of experts to labeling oracles, a paradigm that limits the amount of information exchanged and fails to capture the nuances of human judgment. We address this challenge by developing a human-in-the-loop framework to lea…

• Calibrated Predictive Lower Bounds on Time-to-Unsafe-Sampling in LLMs

  Hen Davidov, Shai Feldman, Gilad Freidkin, Yaniv Romano · 17 février 2026

  We introduce time-to-unsafe-sampling, a novel safety measure for generative models, defined as the number of generations required by a large language model (LLM) to trigger an unsafe (e.g., toxic) response. While providing a new dimension for prompt-adaptive safety evaluation, quantifying time-to-un…

• Why Code, Why Now: Learnability, Computability, and the Real Limits of Machine Learning

  Zhimin Zhao · 17 février 2026

  Code generation has progressed more reliably than reinforcement learning, largely because code has an information structure that makes it learnable. Code provides dense, local, verifiable feedback at every token, whereas most reinforcement learning problems do not. This difference in feedback qualit…

• Learning State-Tracking from Code Using Linear RNNs

  Julien Siems, Riccardo Grazzi, Kirill Kalinin, Hitesh Ballani, Babak Rahmani · 17 février 2026

  Over the last years, state-tracking tasks, particularly permutation composition, have become a testbed to understand the limits of sequence models architectures like Transformers and RNNs (linear and non-linear). However, these are often sequence-to-sequence tasks: learning to map actions (permutati…

• The Speed-up Factor: A Quantitative Multi-Iteration Active Learning Performance Metric

  Hannes Kath, Thiago S. Gouv\^ea, Daniel Sonntag · 17 février 2026

  Machine learning models excel with abundant annotated data, but annotation is often costly and time-intensive. Active learning (AL) aims to improve the performance-to-annotation ratio by using query methods (QMs) to iteratively select the most informative samples. While AL research focuses mainly on…

• High-dimensional Level Set Estimation with Trust Regions and Double Acquisition Functions

  Giang Ngo, Dat Phan Trong, Dang Nguyen, Sunil Gupta · 16 février 2026

  Level set estimation (LSE) classifies whether an unknown function's value exceeds a specified threshold for given inputs, a fundamental problem in many real-world applications. In active learning settings with limited initial data, we aim to iteratively acquire informative points to construct an acc…

• How Many Features Can a Language Model Store Under the Linear Representation Hypothesis?

  Nikhil Garg, Jon Kleinberg, Kenny Peng · 13 février 2026

  We introduce a mathematical framework for the linear representation hypothesis (LRH), which asserts that intermediate layers of language models store features linearly. We separate the hypothesis into two claims: linear representation (features are linearly embedded in neuron activations) and linear…

• Learning Conditional Averages

  Marco Bressan, Nataly Brukhim, Nicolo Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen · 13 février 2026

  We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in standard PAC learning. However, instead of learning the target concept itself, the goal is to predict, for each instanc…

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

  Alireza F. Pour, Farnam Mansouri, Shai Ben-David · 11 février 2026

  We study an online learning problem with multiple correct answers, where each instance admits a set of valid labels, and in each round the learner must output a valid label for the queried example. This setting is motivated by language generation tasks, in which a prompt may admit many acceptable co…

• Epistemic Throughput: Fundamental Limits of Attention-Constrained Inference

  Lei You · 11 février 2026

  Recent generative and tool-using AI systems can surface a large volume of candidates at low marginal cost, yet only a small fraction can be checked carefully. This creates a decoder-side bottleneck: downstream decision-makers must form reliable posteriors from many public records under scarce attent…

• Rational Transductors

  Mehryar Mohri · 10 février 2026

  Standard Transformers excel at semantic modeling but struggle with rigid sequential logic and state tracking. Theoretical work establishes that self-attention is limited to $\AC^0$ (under hard attention) or $\TC^0$ (under soft attention), complexity classes that often fail to support robust …

• Discrete Bridges for Mutual Information Estimation

  Iryna Zabarianska, Sergei Kholkin, Grigoriy Ksenofontov, Ivan Butakov, Alexander Korotin · 10 février 2026

  Diffusion bridge models in both continuous and discrete state spaces have recently become powerful tools in the field of generative modeling. In this work, we leverage the discrete state space formulation of bridge matching models to address another important problem in machine learning and informat…

• Active Learning Using Aggregated Acquisition Functions: Accuracy and Sustainability Analysis

  C\'edric Jung, Shirin Salehi, Anke Schmeink · 10 février 2026

  Active learning (AL) is a machine learning (ML) approach that strategically selects the most informative samples for annotation during training, aiming to minimize annotation costs. This strategy not only reduces labeling expenses but also results in energy savings during neural network training, th…

• Privately Learning Decision Lists and a Differentially Private Winnow

  Mark Bun, William Fang · 10 février 2026

  We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces in the PAC and online models. In the PAC model, we give a computationally efficient algorithm for learning decision lists with minimal sample overhead over the best non-priva…

• Positive Distribution Shift as a Framework for Understanding Tractable Learning

  Marko Medvedev, Idan Attias, Elisabetta Cornacchia, Theodor Misiakiewicz, Gal Vardi, Nathan Srebro · 10 février 2026

  We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training distribution D'(x), labeled by the true target f(x). Such a distribution shift (here in the form of covariate shift) is us…

• Wild Guesses and Mild Guesses in Active Concept Learning

  Anirudh Chari, Neil Pattanaik · 9 février 2026

  Human concept learning is typically active: learners choose which instances to query or test in order to reduce uncertainty about an underlying rule or category. Active concept learning must balance informativeness of queries against the stability of the learner that generates and scores hypotheses.…

• Robust Online Learning

  Sajad Ashkezari · 9 février 2026

  We study the problem of learning robust classifiers where the classifier will receive a perturbed input. Unlike robust PAC learning studied in prior work, here the clean data and its label are also adversarially chosen. We formulate this setting as an online learning problem and consider both the re…

• Semantically Labelled Automata for Multi-Task Reinforcement Learning with LTL Instructions

  Alessandro Abate, Giuseppe De Giacomo, Mathias Jackermeier, Jan Kret\'insk\'y, Maximilian Prokop, Christoph Weinhuber · 9 février 2026

  We study multi-task reinforcement learning (RL), a setting in which an agent learns a single, universal policy capable of generalising to arbitrary, possibly unseen tasks. We consider tasks specified as linear temporal logic (LTL) formulae, which are commonly used in formal methods to specify proper…

• Displacement-Resistant Extensions of DPO with Nonconvex $f$-Divergences

  Idan Pipano, Shoham Sabach, Kavosh Asadi, Mohammad Ghavamzadeh · 9 février 2026

  DPO and related algorithms align language models by directly optimizing the RLHF objective: find a policy that maximizes the Bradley-Terry reward while staying close to a reference policy through a KL divergence penalty. Previous work showed that this approach could be further generalized: the origi…

• Adaptive Sparse M\"obius Transforms for Learning Polynomials

  Yigit Efe Erginbas, Justin Singh Kang, Elizabeth Polito, Kannan Ramchandran · 9 février 2026

  We consider the problem of exactly learning an $s$-sparse real-valued Boolean polynomial of degree $d$ of the form $f:\{ 0,1\}^n \rightarrow \mathbb{R}$. This problem corresponds to decomposing functions in the AND basis and is known as taking a M\"obius transform. While the analogous problem for th…

• Private Prediction via Shrinkage

  Chao Yan · 6 février 2026

  We study differentially private prediction introduced by Dwork and Feldman (COLT 2018): an algorithm receives one labeled sample set $S$ and then answers a stream of unlabeled queries while the output transcript remains $(\varepsilon,\delta)$-differentially private with respect to $S$. Standard comp…

• Optimal Robust Recourse with $L^p$-Bounded Model Change

  Phone Kyaw, Kshitij Kayastha, Shahin Jabbari · 6 février 2026

  Recourse provides individuals who received undesirable labels (e.g., denied a loan) from algorithmic decision-making systems with a minimum-cost improvement suggestion to achieve the desired outcome. However, in practice, models often get updated to reflect changes in the data distribution or enviro…

• Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysis

  Kosuke Sugiyama, Masato Uchida · 6 février 2026

  This paper proposes an information-theoretic framework for analyzing the theoretical limits of pool-based active learning (AL), in which a subset of instances is selectively labeled. The proposed framework reformulates pool-based AL as a noisy lossy compression problem by mapping pool observations t…

• It's all In the (Exponential) Family: An Equivalence between Maximum Likelihood Estimation and Control Variates for Sketching Algorithms

  Keegan Kang, Kerong Wang, Ding Zhang, Rameshwar Pratap, Bhisham Dev Verma, Benedict H. W. Wong · 5 février 2026

  Maximum likelihood estimators (MLE) and control variate estimators (CVE) have been used in conjunction with known information across sketching algorithms and applications in machine learning. We prove that under certain conditions in an exponential family, an optimal CVE will achieve the same asympt…