Machine Learning and Algorithms

Latest papers

• CAAL: Contextual Bandits based Online Hand-Craft Active Learning Strategy Selection

  Shao-An Yin, Jiacong Li, Tianpei Xie, Cecile Levasseur, Wojciech Kowalinski, Nicola Elia · 9 June 2026

  The challenge with active learning algorithms is the uncertainty of the statistical distribution of unlabeled data, making it difficult to choose the best hand-crafted strategy. To address this, we introduced Contextual Adaptive Active Learning (CAAL). In CAAL, each "arm" represents a hand-crafted s…

• Formalizing Learning from Language Feedback with Provable Guarantees

  Wanqiao Xu, Allen Nie, Ruijie Zheng, Aditya Modi, Adith Swaminathan, Ching-An Cheng · 9 June 2026

  Interactively learning from observation and language feedback is an increasingly studied area driven by the emergence of large language model (LLM) agents. Despite impressive empirical demonstrations, so far a principled framing of these decision problems remains lacking. We formalize the Learning f…

• Deep Active Re-Labeling: Toward Noise-Resilient Annotation Efficiency

  Md Abdullah Al Forhad, Weishi Shi · 9 June 2026

  While Deep Active Learning (DAL) effectively reduces human annotation costs, its efficacy is constrained by human annotation errors. This is because the data sampled for active learning is assumed to be highly informative for training. When human annotators introduce errors into this informative dat…

• Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

  Blanka K\"over, Alexandra Butoi, Anej Svete, Michael Hahn, Ryan Cotterell · 9 June 2026

  Transformers consistently fail to learn certain simple functions that are provably expressible with specific parameter settings. This gap between learnability and expressivity is particularly prominent for sensitive functions -- functions whose output is likely to change if a single bit of the input…

• Active Learning with Foundation Model Priors: Efficient Learning under Class Imbalance

  Jiancheng Zhang, Meiqing Li, Qi Zhang, Yinglun Zhu · 9 June 2026

  Real-world datasets across image and text domains are often characterized by skewed class distributions and noisy annotations, which jointly degrade model performance, particularly on minority classes. Among existing solutions, active learning offers an effective and efficient paradigm by selectivel…

• Modeling Stochastic Conditional Dynamics from Sparse Observations via Kernel-Stabilized Flow Matching

  Adam P. Generale, Andreas E. Robertson, Surya R. Kalidindi · 9 June 2026

  Learning to transform conditional probability densities over time is a fundamental challenge spanning probabilistic modeling and the natural sciences. This task is paramount when forecasting the evolution of stochastic nonlinear dynamical systems in biological and physical domains. While flow-based …

• Finite Certificates for In-Context Determinacy and a Threshold Theory of Emergence in Language Models

  Faruk Alpay, Hamdi Alakkad · 9 June 2026

  This paper develops a model-theoretic framework for verifying context-conditioned language-model behavior by replacing benchmark labels with finite semantic certificates. The first problem is finite determinacy: when do examples in a context force the answer to a query without changing model paramet…

• Finding Most Influential Sets

  Lucas D. Konrad, Nikolas Kuschnig · 8 June 2026

  Identifying most influential sets (MIS) - size-$k$ subsets whose removal maximally changes a target estimand - is typically infeasible because it requires searching over $\binom{n}{k}$ subsets. For estimands with linear-fractional leave-set-out effects, we show that MIS selection reduces to a one-pa…

• Activation-Based Active Learning for In-Context Learning: Challenges and Insights

  Yaseen M. Osman, Geoff V. Merrett, Stuart E. Middleton · 4 June 2026

  Deep active learning has previously been explored for LLM in-context sample selection, but not with methods that utilise recent advances in understanding of transformer activations. In this paper, we test the hypothesis that model activations could provide a fine-grained signal to optimise the selec…

• Why Muon Outperforms Adam: A Curvature Perspective

  Shuche Wang, Fengzhuo Zhang, Jiaxiang Li, Dirk Bergemann, Zhuoran Yang · 4 June 2026

  Muon improves training efficiency over Adam in large language-model training by about two times, but the local geometric source of this advantage remains unclear. Our work takes a first step toward demystifying Muon's superiority over Adam from a curvature perspective. First, we apply a second-order…

• The price of multi-group transductive learning

  Noah Bergam, Samuel Deng, Daniel Hsu · 4 June 2026

  We show every multi-group learner in the transductive setting may incur a multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting, and the penalty can increasing linearly with the number of groups, up to roughly the square-root of the …

• Prediction Under Imperfect Compression: A Theory of Approximate MDL

  Qian Li, Xinyu Mao, Shang-Hua Teng, Guangxu Yang · 4 June 2026

  Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: $L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$. For sequential prediction, the MDL method repeatedly selects a model with a minimum objective score of the observed prefix…

• Finding Needles in the Haystack: Transductive Active Labeling in Ecology

  Rupa Kurinchi-Vendhan, Sara Beery · 3 June 2026

  Active learning is now standard practice in labeling ecological data, enabling ecologists to quickly process large volumes of field data to understand and monitor natural environments. Current practices evaluate active learning inductively, estimating predictive performance on a held-out test set. W…

• Incentivized Collaboration in Active Learning

  Lee Cohen, Han Shao · 2 June 2026

  In collaborative active learning, where multiple agents try to learn labels from a common hypothesis, we introduce an innovative framework for incentivized collaboration. Here, rational agents aim to obtain labels for their data sets while keeping label complexity at a minimum. We focus on designing…

• Characterizing the Effect of Noise in Language Generation in the Limit

  Aaron Li, Ian Zhang · 2 June 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…

• From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learning

  Ali Azizpour, Reza Ramezanpour, Santiago Segarra · 2 June 2026

  Real-world graph datasets often arise from mixtures of populations, where graphs are generated by multiple distinct underlying distributions. In this work, we propose a unified framework that explicitly models graph data as a mixture of probabilistic graph generative models represented by graphons. …

• Everywhere Learning: Artificial Intelligence with Pointwise Constraints

  Ignacio Boero, Ignacio Hounie, Luiz Chamon, Alejandro Ribeiro · 2 June 2026

  Everywhere learning is a new paradigm whereby Artificial Intelligence (AI) systems are trained to satisfy loss constraints with probability one over the data distribution. This is in contrast to the standard paradigm of training AI systems to minimize average losses. We develop an approximate dualit…

• A Theoretical Framework for Self-Play Theorem Proving Algorithms

  Thomas Chen, Zhiyuan Li · 2 June 2026

  Self-play, a type of training algorithm that enables a model to self-improve, has recently shown promising empirical results in the context of formal theorem proving using Large Language Models (LLMs). (Dong & Ma, 2025) instantiate self-play with two cooperating agents: a prover, which proves theore…

• How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?

  Michael Benedikt, Alessio Mansutti · 2 June 2026

  We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the compu…

• Universal Multiclass Transductive Online Learning

  Steve Hanneke, Hongao Wang · 1 June 2026

  We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class $\mathcal{H}$ is learnable if there is a lear…

• Improving Selective Classification with Pairwise Queries for Binary Classification

  Harsh Vardhan, Sunav Choudhary, Natwar Modani, Arya Mazumdar · 1 June 2026

  In selective classification, a model predicts the labels of data samples where it is confident, and abstains from predicting labels for samples on which it is not confident. The rejected samples are often labeled by an expert, which is expensive. The budget for the expert is best utilized when the m…

• The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

  Wei Luo · 1 June 2026

  Pattern languages are a classical model in formal language theory and algorithmic learning theory. This note formulates the problem of computing the inclusion depth of a pattern language: the length of the longest strict inclusion chain from the universal pattern language to the language generated b…

• On Language Generation in the Limit with Bounded Memory

  Jon Kleinberg, Anay Mehrotra, Amin Saberi, Grigoris Velegkas · 29 May 2026

  We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples. Prior work assumes access to the entire history, a strong assumption since realistic algorithms …

• A Training-Time Diagnostic for Generalization via the Log-Alignment Ratio

  Ali Shehper, Ashish Vaswani · 29 May 2026

  We study the log-alignment ratio (LAR), a measure of parameter-activation alignment, introduced in parameterization theory. We reformulate it as the overlap between a weight spectrum $p$ of the normalized squared singular values of a matrix and an activation spectrum $q$ of the normalized squared pr…

• Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

  Sergei Tikhonov, Arsen Vasilyan · 28 May 2026

  We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over $\mathbb{R}^d \times \{\pm 1\}$ whose marginal on $\mathbb{R}^d$ is Gaussian…