Machine Learning and Algorithms

Latest papers

• Active Learning Methods for Efficient Data Utilization and Model Performance Enhancement

  Chiung-Yi Tseng, Junhao Song, Ziqian Bi, Tianyang Wang, Chia Xin Liang, Xinyuan Song, Ming Liu · 27 November 2025

  In the era of data-driven intelligence, the paradox of data abundance and annotation scarcity has emerged as a critical bottleneck in the advancement of machine learning. This paper gives a detailed overview of Active Learning (AL), which is a strategy in machine learning that helps models achieve b…

• Scaling Up Active Testing to Large Language Models

  Gabrielle Berrada, Jannik Kossen, Freddie Bickford Smith, Muhammed Razzak, Yarin Gal, Tom Rainforth · 26 November 2025

  Active testing enables label-efficient evaluation of predictive models through careful data acquisition, but it can pose a significant computational cost. We identify cost-saving measures that enable active testing to be scaled up to large language models (LLMs). In particular we show that the surro…

• Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets

  Kasper Green Larsen, Natascha Schalburg · 26 November 2025

  We prove the first margin-based generalization bound for voting classifiers, that is asymptotically tight in the tradeoff between the size of the hypothesis set, the margin, the fraction of training points with the given margin, the number of training samples and the failure probability.…

• How to Purchase Labels? A Cost-Effective Approach Using Active Learning Markets

  Xiwen Huang, Pierre Pinson · 26 November 2025

  We introduce and analyse active learning markets as a way to purchase labels, in situations where analysts aim to acquire additional data to improve model fitting, or to better train models for predictive analytics applications. This comes in contrast to the many proposals that already exist to purc…

• PTF Testing Lower Bounds for Non-Gaussian Component Analysis

  Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas · 25 November 2025

  This work studies information-computation gaps for statistical problems. A common approach for providing evidence of such gaps is to show sample complexity lower bounds (that are stronger than the information-theoretic optimum) against natural models of computation. A popular such model in the liter…

• High-Accuracy List-Decodable Mean Estimation

  Ziyun Chen, Spencer Compton, Daniel Kane, Jerry Li · 25 November 2025

  In list-decodable learning, we are given a set of data points such that an $\alpha$-fraction of these points come from a nice distribution $D$, for some small $\alpha \ll 1$, and the goal is to output a short list of candidate solutions, such that at least one element of this list recovers some non-…

• Smoothed Agnostic Learning of Halfspaces over the Hypercube

  Yiwen Kou, Raghu Meka · 25 November 2025

  Agnostic learning of Boolean halfspaces is a fundamental problem in computational learning theory, but it is known to be computationally hard even for weak learning. Recent work [CKKMK24] proposed smoothed analysis as a way to bypass such hardness, but existing frameworks rely on additive Gaussian p…

• The Limits of Assumption-free Tests for Algorithm Performance

  Yuetian Luo, Rina Foygel Barber · 25 November 2025

  Algorithm evaluation and comparison are fundamental questions in machine learning and statistics -- how well does an algorithm perform at a given modeling task, and which algorithm performs best? Many methods have been developed to assess algorithm performance, often based around cross-validation ty…

• Extracting Robust Register Automata from Neural Networks over Data Sequences

  Chih-Duo Hong, Hongjian Jiang, Anthony W. Lin, Oliver Markgraf, Julian Parsert, Tony Tan · 25 November 2025

  Automata extraction is a method for synthesising interpretable surrogates for black-box neural models that can be analysed symbolically. Existing techniques assume a finite input alphabet, and thus are not directly applicable to data sequences drawn from continuous domains. We address this challenge…

• Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization

  Rahul Krishna Thomas, Arka Pal · 21 November 2025

  Speculative sampling reduces the latency of autoregressive decoding for target model LLMs without sacrificing inference quality, by using a cheap draft model to suggest a candidate token and a verification criterion to accept or resample this token. To improve acceptance and decoding efficiency, rec…

• Beyond Tsybakov: Model Margin Noise and $\mathcal{H}$-Consistency Bounds

  Mehryar Mohri, Yutao Zhong · 21 November 2025

  We introduce a new low-noise condition for classification, the Model Margin Noise (MM noise) assumption, and derive enhanced $\mathcal{H}$-consistency bounds under this condition. MM noise is weaker than Tsybakov noise condition: it is implied by Tsybakov noise condition but can hold even when Tsyba…

• Exact Learning of Weighted Graphs Using Composite Queries

  Michael T. Goodrich, Songyu Liu, Ioannis Panageas · 20 November 2025

  In this paper, we study the exact learning problem for weighted graphs, where we are given the vertex set, $V$, of a weighted graph, $G=(V,E,w)$, but we are not given $E$. The problem, which is also known as graph reconstruction, is to determine all the edges of $E$, including their weights, by aski…

• WaveFuse-AL: Cyclical and Performance-Adaptive Multi-Strategy Active Learning for Medical Images

  Nishchala Thakur, Swati Kochhar, Deepti R. Bathula, Sukrit Gupta · 20 November 2025

  Active learning reduces annotation costs in medical imaging by strategically selecting the most informative samples for labeling. However, individual acquisition strategies often exhibit inconsistent behavior across different stages of the active learning cycle. We propose Cyclical and Performance-A…

• Sample-Adaptivity Tradeoff in On-Demand Sampling

  Nika Haghtalab, Omar Montasser, Mingda Qiao · 20 November 2025

  We study the tradeoff between sample complexity and round complexity in on-demand sampling, where the learning algorithm adaptively samples from $k$ distributions over a limited number of rounds. In the realizable setting of Multi-Distribution Learning (MDL), we show that the optimal sample complexi…

• Statistical Deficiency for Task Inclusion Estimation

  Lo\"ic Fosse, Fr\'ed\'eric B\'echet, Beno\^it Favre, G\'eraldine Damnati, Gw\'enol\'e Lecorv\'e, Maxime Darrin, Philippe Formont, Pablo Piantanida · 18 November 2025

  Tasks are central in machine learning, as they are the most natural objects to assess the capabilities of current models. The trend is to build general models able to address any task. Even though transfer learning and multitask learning try to leverage the underlying task space, no well-founded too…

• Efficient Calibration for Decision Making

  Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, Pranay Tankala · 18 November 2025

  A decision-theoretic characterization of perfect calibration is that an agent seeking to minimize a proper loss in expectation cannot improve their outcome by post-processing a perfectly calibrated predictor. Hu and Wu (FOCS'24) use this to define an approximate calibration measure called calibratio…

• LLM on a Budget: Active Knowledge Distillation for Efficient Classification of Large Text Corpora

  Viviana Luccioli, Rithika Iyengar, Ryan Panley, Flora Haberkorn, Xiaoyu Ge, Leland Crane, Nitish Sinha, Seung Jung Lee · 18 November 2025

  Large Language Models (LLMs) are highly accurate in classification tasks, however, substantial computational and financial costs hinder their large-scale deployment in dynamic environments. Knowledge Distillation (KD) where a LLM "teacher" trains a smaller and more efficient "student" model, offers …

• Active Learning of Symbolic Automata Over Rational Numbers

  Sebastian Hagedorn, Mart\'in Mu\~noz, Cristian Riveros, Rodrigo Toro Icarte · 18 November 2025

  Automata learning has many applications in artificial intelligence and software engineering. Central to these applications is the $L^*$ algorithm, introduced by Angluin. The $L^*$ algorithm learns deterministic finite-state automata (DFAs) in polynomial time when provided with a minimally adequate t…

• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back

  Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, Qian Zhang · 18 November 2025

  The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both learnability and sample complexity. Extending this to multiclass classification has long been challenging, since Natara…

• Is nasty noise actually harder than malicious noise?

  Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio · 14 November 2025

  We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise, under two well-studied and challenging adversarial noise models for learning Boolean functions: malicious noise, in which an adversary can arbitrarily corrupt a random su…

• A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes

  Alireza F. Pour, Shai Ben-David · 14 November 2025

  We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses. While the common approach to such challenges is SRM (or regularization) based learning algorithms, we propose a novel learning paradigm that r…

• Product distribution learning with imperfect advice

  Arnab Bhattacharyya, Davin Choo, Philips George John, Themis Gouleakis · 14 November 2025

  Given i.i.d.~samples from an unknown distribution $P$, the goal of distribution learning is to recover the parameters of a distribution that is close to $P$. When $P$ belongs to the class of product distributions on the Boolean hypercube $\{0,1\}^d$, it is known that $\Omega(d/\varepsilon^2)$ sample…

• Robust Sampling for Active Statistical Inference

  Puheng Li, Tijana Zrnic, Emmanuel Cand\`es · 13 November 2025

  Active statistical inference is a new method for inference with AI-assisted data collection. Given a budget on the number of labeled data points that can be collected and assuming access to an AI predictive model, the basic idea is to improve estimation accuracy by prioritizing the collection of lab…

• Tight Bounds for Answering Adaptively Chosen Concentrated Queries

  Emma Rapoport, Edith Cohen, Uri Stemmer · 13 November 2025

  Most work on adaptive data analysis assumes that samples in the dataset are independent. When correlations are allowed, even the non-adaptive setting can become intractable, unless some structural constraints are imposed. To address this, Bassily and Freund [2016] introduced the elegant framework of…

• Pushdown Reward Machines for Reinforcement Learning

  Giovanni Varricchione, Toryn Q. Klassen, Natasha Alechina, Mehdi Dastani, Brian Logan, Sheila A. McIlraith · 13 November 2025

  Reward machines (RMs) are automata structures that encode (non-Markovian) reward functions for reinforcement learning (RL). RMs can reward any behaviour representable in regular languages and, when paired with RL algorithms that exploit RM structure, have been shown to significantly improve sample e…