Machine Learning and Algorithms

Latest papers

• Learning $\mathsf{AC}^0$ Under Graphical Models

  Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan · 8 April 2026

  In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the uniform distribution. Their work has had a deep and lasting legacy in computational learning theory, in particular introduci…

• Understanding Uncertainty Sampling via Equivalent Loss

  Shang Liu, Xiaocheng Li · 8 April 2026

  Uncertainty sampling is a prevalent active learning algorithm that queries sequentially the annotations of data samples which the current prediction model is uncertain about. However, the usage of uncertainty sampling has been largely heuristic: There is no consensus on the proper definition of ``un…

• Why Code, Why Now: An Information-Theoretic Perspective on the Limits of Machine Learning

  Zhimin Zhao · 8 April 2026

  This paper offers a new perspective on the limits of machine learning: the ceiling on progress is set not by model size or algorithm choice but by the information structure of the task itself. Code generation has progressed more reliably than reinforcement learning, largely because code provides den…

• The Role of Generator Access in Autoregressive Post-Training

  Amit Kiran Rege · 7 April 2026

  We study how generator access constrains autoregressive post-training. The central question is whether the learner is confined to fresh root-start rollouts or can return to previously built prefixes and query the next-token rule there. In the root-start regime, output sampling, generated-token log p…

• Online learning of smooth functions on $\mathbb{R}$

  Jesse Geneson, Kuldeep Singh, Alexander Wang · 7 April 2026

  We study adversarial online learning of real-valued functions on $\mathbb{R}$. In each round the learner is queried at $x_t\in\mathbb{R}$, predicts $\hat y_t$, and then observes the true value $f(x_t)$; performance is measured by cumulative $p$-loss $\sum_{t\ge 1}|\hat y_t-f(x_t)|^p$. For the class …

• Robust Learning with Optimal Error

  Guy Blanc · 6 April 2026

  We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of \textsl{randomized} hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. - For $\eta$-rate malicious noise, we s…

• Feature Weighting Improves Pool-Based Sequential Active Learning for Regression

  Dongrui Wu · 3 April 2026

  Pool-based sequential active learning for regression (ALR) optimally selects a small number of samples sequentially from a large pool of unlabeled samples to label, so that a more accurate regression model can be constructed under a given labeling budget. Representativeness and diversity, which invo…

• In-context Learning in Presence of Spurious Correlations

  Hrayr Harutyunyan, Rafayel Darbinyan, Samvel Karapetyan, Hrant Khachatrian · 3 April 2026

  Large language models exhibit a remarkable capacity for in-context learning, where they learn to solve tasks given a few examples. Recent work has shown that transformers can be trained to perform simple regression tasks in-context. This work explores the possibility of training an in-context learne…

• Learn by Surprise, Commit by Proof

  Kang-Sin Choi · 3 April 2026

  We propose LSCP, a self-gated post-training framework for autonomous knowledge acquisition: learning only what a model does not already know, verified against what it does know, at a strength proportional to conviction, with no external oracle. When a passage produces anomalously high per-token loss…

• The No-Clash Teaching Dimension is Bounded by VC Dimension

  Jiahua Liu, Benchong Li · 2 April 2026

  In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching. However, whether No-Clash Teaching Dimension is upper-bounded by Vapnik-Chervonenki…

• MSG: Multi-Stream Generative Policies for Sample-Efficient Robotic Manipulation

  Jan Ole von Hartz, Lukas Schweizer, Joschka Boedecker, Abhinav Valada · 1 April 2026

  Generative robot policies such as Flow Matching offer flexible, multi-modal policy learning but are sample-inefficient. Although object-centric policies improve sample efficiency, it does not resolve this limitation. In this work, we propose Multi-Stream Generative Policy (MSG), an inference-time co…

• Mind the Gap: A Framework for Assessing Pitfalls in Multimodal Active Learning

  Dustin Eisenhardt, Yunhee Jeong, Florian Buettner · 1 April 2026

  Multimodal learning enables neural networks to integrate information from heterogeneous sources, but active learning in this setting faces distinct challenges. These include missing modalities, differences in modality difficulty, and varying interaction structures. These are issues absent in the uni…

• Efficient Human-in-the-Loop Active Learning: A Novel Framework for Data Labeling in AI Systems

  Yiran Huang, Jian-Feng Yang, Haoda Fu · 31 March 2026

  Modern AI algorithms require labeled data. In real world, majority of data are unlabeled. Labeling the data are costly. this is particularly true for some areas requiring special skills, such as reading radiology images by physicians. To most efficiently use expert's time for the data labeling, one …

• Active In-Context Learning for Tabular Foundation Models

  Wilailuck Treerath, Fabrizio Pittorino · 31 March 2026

  Active learning (AL) reduces labeling cost by querying informative samples, but in tabular settings its cold-start gains are often limited because uncertainty estimates are unreliable when models are trained on very few labels. Tabular foundation models such as TabPFN provide calibrated probabilisti…

• Learning Expressive Priors for Generalization and Uncertainty Estimation in Neural Networks

  Dominik Schnaus, Jongseok Lee, Daniel Cremers, Rudolph Triebel · 31 March 2026

  In this work, we propose a novel prior learning method for advancing generalization and uncertainty estimation in deep neural networks. The key idea is to exploit scalable and structured posteriors of neural networks as informative priors with generalization guarantees. Our learned priors provide ex…

• Functional Natural Policy Gradients

  Aurelien Bibaut, Houssam Zenati, Thibaud Rahier, Nathan Kallus · 31 March 2026

  We propose a cross-fitted debiasing device for policy learning from offline data. A key consequence of the resulting learning principle is $\sqrt N$ regret even for policy classes with complexity greater than Donsker, provided a product-of-errors nuisance remainder is $O(N^{-1/2})$. The regret bound…

• The Order Is The Message

  Jordan LeDoux · 27 March 2026

  In a controlled experiment on modular arithmetic ($p = 9973$), varying only example ordering while holding all else constant, two fixed-ordering strategies achieve 99.5\% test accuracy by epochs 487 and 659 respectively from a training set comprising 0.3\% of the input space, well below established …

• Working Paper: Active Causal Structure Learning with Latent Variables: Towards Learning to Detour in Autonomous Robots

  Pablo de los Riscos, Fernando J. Corbacho · 27 March 2026

  Artificial General Intelligence (AGI) Agents and Robots must be able to cope with everchanging environments and tasks. They must be able to actively construct new internal causal models of their interactions with the environment when new structural changes take place in the environment. Thus, we cla…

• Upper Entropy for 2-Monotone Lower Probabilities

  Tuan-Anh Vu, S\'ebastien Destercke, Fr\'ed\'eric Pichon · 26 March 2026

  Uncertainty quantification is a key aspect in many tasks such as model selection/regularization, or quantifying prediction uncertainties to perform active learning or OOD detection. Within credal approaches that consider modeling uncertainty as probability sets, upper entropy plays a central role as…

• Labeled Compression Schemes for Concept Classes of Finite Functions

  Benchong Li · 26 March 2026

  The sample compression conjecture is: Each concept class of VC dimension d has a compression scheme of size d.In this paper, for any concept class of finite functions, we present a labeled sample compression scheme of size equals to its VC dimension d. That is, the long standing open sample compress…

• General Machine Learning: Theory for Learning Under Variable Regimes

  Aomar Osmani · 25 March 2026

  We study learning under regime variation, where the learner, its memory state, and the evaluative conditions may evolve over time. This paper is a foundational and structural contribution: its goal is to define the core learning-theoretic objects required for such settings and to establish their fir…

• Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classification

  Xiaohan Zhu, Mesrob I. Ohannessian, Nathan Srebro · 25 March 2026

  We consider a PAC-Bayes type learning rule for binary classification, balancing the training error of a randomized ''posterior'' predictor with its KL divergence to a pre-specified ''prior''. This can be seen as an extension of a modified two-part-code Minimum Description Length (MDL) learning rule,…

• REALITrees: Rashomon Ensemble Active Learning for Interpretable Trees

  Simon D. Nguyen, Hayden McTavish, Kentaro Hoffman, Cynthia Rudin, Tyler H. McCormick · 25 March 2026

  Active learning reduces labeling costs by selecting samples that maximize information gain. A dominant framework, Query-by-Committee (QBC), typically relies on perturbation-based diversity by inducing model disagreement through random feature subsetting or data blinding. While this approximates one …

• Conformal Cross-Modal Active Learning

  Huy Hoang Nguyen, C\'edric Jung, Shirin Salehi, Tobias Gl\"uck, Anke Schmeink, Andreas Kugi · 25 March 2026

  Foundation models for vision have transformed visual recognition with powerful pretrained representations and strong zero-shot capabilities, yet their potential for data-efficient learning remains largely untapped. Active Learning (AL) aims to minimize annotation costs by strategically selecting the…

• Sparse Learning and Class Probability Estimation with Weighted Support Vector Machines

  Liyun Zeng, Hao Helen Zhang · 25 March 2026

  Classification and probability estimation are fundamental tasks with broad applications across modern machine learning and data science, spanning fields such as biology, medicine, engineering, and computer science. Recent development of weighted Support Vector Machines (wSVMs) has demonstrated consi…