Machine Learning and Algorithms

Latest papers

• A Function-Space Stability Boundary for Generalization in Interpolating Learning Systems

  Ronald Katende · 4 February 2026

  Modern learning systems often interpolate training data while still generalizing well, yet it remains unclear when algorithmic stability explains this behavior. We model training as a function-space trajectory and measure sensitivity to single-sample perturbations along this trajectory. We propose…

• Active learning from positive and unlabeled examples

  Farnam Mansouri, Sandra Zilles, Shai Ben-David · 3 February 2026

  Learning from positive and unlabeled data (PU learning) is a weakly supervised variant of binary classification in which the learner receives labels only for (some) positively labeled instances, while all other examples remain unlabeled. Motivated by applications such as advertising and anomaly dete…

• Reassessing Active Learning Adoption in Contemporary NLP: A Community Survey

  Julia Romberg, Christopher Schr\"oder, Julius Gonsior, Katrin Tomanek, Fredrik Olsson · 3 February 2026

  Supervised learning relies on data annotation which usually is time-consuming and therefore expensive. A longstanding strategy to reduce annotation costs is active learning, an iterative process, in which a human annotates only data instances deemed informative by a model. Research in active learnin…

• Nearly Optimal Active Preference Learning and Its Application to LLM Alignment

  Yao Zhao, Kwang-Sung Jun · 3 February 2026

  Aligning large language models (LLMs) depends on high-quality datasets of human preference labels, which are costly to collect. Although active learning has been studied to improve sample efficiency relative to passive collection, many existing approaches adopt classical experimental design criteria…

• Learning Half-Spaces from Perturbed Contrastive Examples

  Aryan Alavi Razavi Ravari, Farnam Mansouri, Yuxin Chen, Valentio Iverson, Adish Singla, Sandra Zilles · 3 February 2026

  We study learning under a two-step contrastive example oracle, as introduced by Mansouri et. al. (2025), where each queried (or sampled) labeled example is paired with an additional contrastive example of opposite label. While Mansouri et al. assume an idealized setting, where the contrastive exampl…

• Stability of In-Context Learning: A Spectral Coverage Perspective

  Tongxi Wang, Zhuoyang Xia · 3 February 2026

  In-context learning (ICL) is a pivotal capability for the practical deployment of large-scale language models, yet its reliability can vary substantially with the number of demonstrations provided in the prompt. A central obstacle is that the target notion, \emph{distributional stability under demon…

• Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing

  Anxin Guo, Jingwei Li · 3 February 2026

  Large language models often hallucinate with high confidence on "random facts" that lack inferable patterns. We formalize the memorization of such facts as a membership testing problem, unifying the discrete error metrics of Bloom filters with the continuous log-loss of LLMs. By analyzing this probl…

• Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds

  Sujoy Bhore, Liana Khazaliya, Fionn Mc Inerney · 3 February 2026

  Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the collusion-avoidance benchmark established in the seminal work of Goldman and Mathias [COLT 1993]. Recently, (positive) non…

• Active Transfer Bagging: A New Approach for Accelerated Active Learning Acquisition of Data by Combined Transfer Learning and Bagging Based Models

  Vivienne Pelletier, Daniel J. Rivera, Obinna Nwokonkwo, Steven A. Wilson, Christopher L. Muhich · 3 February 2026

  Modern machine learning has achieved remarkable success on many problems, but this success often depends on the existence of large, labeled datasets. While active learning can dramatically reduce labeling cost when annotations are expensive, early performance is frequently dominated by the initial s…

• Myopic Bayesian Decision Theory for Batch Active Learning with Partial Batch Label Sampling

  Kangping Hu, Stephen Mussmann · 3 February 2026

  Over the past couple of decades, many active learning acquisition functions have been proposed, leaving practitioners with an unclear choice of which to use. Bayesian Decision Theory (BDT) offers a universal principle to guide decision-making. In this work, we derive BDT for (Bayesian) active learni…

• It's all 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 · 2 February 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…

• Asymptotic Theory of Iterated Empirical Risk Minimization, with Applications to Active Learning

  Hugo Cui, Yue M. Lu · 2 February 2026

  We study a class of iterated empirical risk minimization (ERM) procedures in which two successive ERMs are performed on the same dataset, and the predictions of the first estimator enter as an argument in the loss function of the second. This setting, which arises naturally in active learning and re…

• Elastic Spectral State Space Models for Budgeted Inference

  Dachuan Song, Xuan Wang · 2 February 2026

  Foundation models are typically trained at a fixed computational capacity, while real-world applications require deployment across platforms with different resource constraints. Current approaches usually rely on training families of model variants or model distillation, which requires additional tr…

• Causal Imitation Learning under Expert-Observable and Expert-Unobservable Confounding

  Daqian Shao, Thomas Kleine Buening, Marta Kwiatkowska · 2 February 2026

  We propose a general framework for causal Imitation Learning (IL) with hidden confounders, which subsumes several existing settings. Our framework accounts for two types of hidden confounders: (a) variables observed by the expert but not by the imitator, and (b) confounding noise hidden from both. B…

• Partial Feedback Online Learning

  Shihao Shao, Cong Fang, Zhouchen Lin, Dacheng Tao · 30 January 2026

  We study partial-feedback online learning, where each instance admits a set of correct labels, but the learner only observes one correct label per round; any prediction within the correct set is counted as correct. This model captures settings such as language generation, where multiple responses ma…

• Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles

  Lutz Oettershagen · 30 January 2026

  Identifying the top-$k$ items is fundamental but often prohibitive when exact valuations are expensive. We study a two-oracle setting with a fast, noisy weak oracle and a scarce, high-fidelity strong oracle (e.g., human expert verification or expensive simulation). We first analyze a simple screen-t…

• Machine Learning. The Science of Selection under Uncertainty

  Yevgeny Seldin · 30 January 2026

  Learning, whether natural or artificial, is a process of selection. It starts with a set of candidate options and selects the more successful ones. In the case of machine learning the selection is done based on empirical estimates of prediction accuracy of candidate prediction rules on some data. Du…

• Discovering Hidden Gems in Model Repositories

  Jonathan Kahana, Eliahu Horwitz, Yedid Hoshen · 30 January 2026

  Public repositories host millions of fine-tuned models, yet community usage remains disproportionately concentrated on a small number of foundation checkpoints. We investigate whether this concentration reflects efficient market selection or if superior models are systematically overlooked. Through …

• Quantifying Noise in Language Generation

  Aaron Li, Ian Zhang · 30 January 2026

  Kleinberg and Mullainathan recently proposed a formal framework for studying the phenomenon of language generation, called language generation in the limit. In this model, an adversary gives an enumeration of example strings from an unknown target language, and the algorithm is tasked with correctly…

• Plain Transformers Can be Powerful Graph Learners

  Liheng Ma, Soumyasundar Pal, Yingxue Zhang, Philip H. S. Torr, Mark Coates · 30 January 2026

  Transformers have attained outstanding performance across various modalities, owing to their simple but powerful scaled-dot-product (SDP) attention mechanisms. Researchers have attempted to migrate Transformers to graph learning, but most advanced Graph Transformers (GTs) have strayed far from plain…

• POLAR: A Pessimistic Model-based Policy Learning Algorithm for Dynamic Treatment Regimes

  Ruijia Zhang, Xiangyu Zhang, Zhengling Qi, Yue Wu, Yanxun Xu · 30 January 2026

  Dynamic treatment regimes (DTRs) provide a principled framework for optimizing sequential decision-making in domains where decisions must adapt over time in response to individual trajectories, such as healthcare, education, and digital interventions. However, existing statistical methods often rely…

• A Theory of Universal Agnostic Learning

  Steve Hanneke, Shay Moran · 30 January 2026

  We provide a complete theory of optimal universal rates for binary classification in the agnostic setting. This extends the realizable-case theory of Bousquet, Hanneke, Moran, van Handel, and Yehudayoff (2021) by removing the realizability assumption on the distribution. We identify a fundamental te…

• Active Learning for Decision Trees with Provable Guarantees

  Arshia Soltani Moakhar, Tanapoom Laoaron, Faraz Ghahremani, Kiarash Banihashem, MohammadTaghi Hajiaghayi · 29 January 2026

  This paper advances the theoretical understanding of active learning label complexity for decision trees as binary classifiers. We make two main contributions. First, we provide the first analysis of the disagreement coefficient for decision trees-a key parameter governing active learning label comp…

• Efficient Evaluation of LLM Performance with Statistical Guarantees

  Skyler Wu, Yash Nair, Emmanuel J. Cand\'es · 29 January 2026

  Exhaustively evaluating many large language models (LLMs) on a large suite of benchmarks is expensive. We cast benchmarking as finite-population inference and, under a fixed query budget, seek tight confidence intervals (CIs) for model accuracy with valid frequentist coverage. We propose Factorized …

• SERA: Soft-Verified Efficient Repository Agents

  Ethan Shen, Danny Tormoen, Saurabh Shah, Ali Farhadi, Tim Dettmers · 29 January 2026

  Open-weight coding agents should hold a fundamental advantage over closed-source systems: they can be specialized to private codebases, encoding repository-specific information directly in their weights. Yet the cost and complexity of training has kept this advantage theoretical. We show it is now p…