Machine Learning and Algorithms

Latest papers

• Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

  Maryam Aliakbarpour, Alireza Azizi, Ria Stevens · 6 March 2026

  Independence testing is a fundamental problem in statistical inference: given samples from a joint distribution $p$ over multiple random variables, the goal is to determine whether $p$ is a product distribution or is $\epsilon$-far from all product distributions in total variation distance. In the n…

• Online Learnability of Chain-of-Thought Verifiers: Soundness and Completeness Trade-offs

  Maria-Florina Balcan, Avrim Blum, Kiriaki Fragkia, Zhiyuan Li, Dravyansh Sharma · 5 March 2026

  Large language models with chain-of-thought generation have demonstrated great potential for producing complex mathematical proofs. However, their reasoning can often go astray, leading to increasing interest in formal and learned verifiers. A major challenge in learning verifiers, especially when t…

• Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions

  Jacob Trauger, Tyson Trauger, Ambuj Tewari · 4 March 2026

  In this paper we will give a characterization of the learnability of forgiving 0-1 loss functions in the multiclass setting with effectively finite cardinality of the output and label space. To do this, we create a new combinatorial dimension that is based off of the Natarajan Dimension and we show …

• Neural Paging: Learning Context Management Policies for Turing-Complete Agents

  Liang Chen, Qi Liu · 4 March 2026

  The proof that Large Language Models (LLMs) augmented with external read-write memory constitute a computationally universal system has established the theoretical foundation for general-purpose agents. However, existing implementations face a critical bottleneck: the finite and costly Context Windo…

• Length Generalization Bounds for Transformers

  Andy Yang, Pascal Bergstr\"a{\ss}er, Georg Zetzsche, David Chiang, Anthony W. Lin · 4 March 2026

  Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a guarantee, one needs to be able to compute a length generalization bound, beyond which the model is guaranteed to general…

• Relatively Smart: A New Approach for Instance-Optimal Learning

  Shaddin Dughmi, Alireza F. Pour · 3 March 2026

  We revisit the framework of Smart PAC learning, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the marginal distribution on unlabeled data. Prior work has shown that such marginal-by-marginal guarantees are possible for "most" marginal…

• Monotone Classification with Relative Approximations

  Yufei Tao · 3 March 2026

  In monotone classification, the input is a multi-set $P$ of points in $\mathbb{R}^d$, each associated with a hidden label from $\{-1, 1\}$. The goal is to identify a monotone function $h$, which acts as a classifier, mapping from $\mathbb{R}^d$ to $\{-1, 1\}$ with a small {\em error}, measured as th…

• SimpleToM: Exposing the Gap between Explicit ToM Inference and Implicit ToM Application in LLMs

  Yuling Gu, Oyvind Tafjord, Hyunwoo Kim, Jared Moore, Ronan Le Bras, Peter Clark, Yejin Choi · 3 March 2026

  Large language models (LLMs) are increasingly tested for a "Theory of Mind" (ToM) - the ability to attribute mental states to oneself and others. Yet most evaluations stop at explicit belief attribution in classical toy stories or stylized tasks, leaving open the questions of whether LLMs can implic…

• Approximate SMT Counting Beyond Discrete Domains

  Arijit Shaw, Kuldeep S. Meel · 2 March 2026

  Satisfiability Modulo Theory (SMT) solvers have advanced automated reasoning, solving complex formulas across discrete and continuous domains. Recent progress in propositional model counting motivates extending SMT capabilities toward model counting, especially for hybrid SMT formulas. Existing appr…

• Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

  Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan · 2 March 2026

  Recent work has shown the surprising power of low-degree sandwiching polynomial approximators in the context of challenging learning settings such as learning with distribution shift, testable learning, and learning with contamination. A pair of sandwiching polynomials approximate a target function …

• Testable Learning of General Halfspaces under Massart Noise

  Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu · 27 February 2026

  We study the algorithmic task of testably learning general Massart halfspaces under the Gaussian distribution. In the testable learning setting, the aim is the design of a tester-learner pair satisfying the following properties: (1) if the tester accepts, the learner outputs a hypothesis and a certi…

• Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms

  Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis, Felix Zhou, Ziyu Zhu · 27 February 2026

  Coarse data arise when learners observe only partial information about samples; namely, a set containing the sample rather than its exact value. This occurs naturally through measurement rounding, sensor limitations, and lag in economic systems. We study Gaussian mean estimation from coarse data, wh…

• Evaluating the relationship between regularity and learnability in recursive numeral systems using Reinforcement Learning

  Andrea Silvi, Ponrawee Prasertsom, Jennifer Culbertson, Devdatt Dubhashi, Moa Johansson, Kenny Smith · 26 February 2026

  Human recursive numeral systems (i.e., counting systems such as English base-10 numerals), like many other grammatical systems, are highly regular. Following prior work that relates cross-linguistic tendencies to biases in learning, we ask whether regular systems are common because regularity facili…

• Error-awareness Accelerates Active Automata Learning

  Loes Kruger, Sebastian Junges, Jurriaan Rot · 26 February 2026

  Active automata learning (AAL) algorithms can learn a behavioral model of a system from interacting with it. The primary challenge remains scaling to larger models, in particular in the presence of many possible inputs to the system. Modern AAL algorithms fail to scale even if, in every state, most …

• Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination

  Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu · 26 February 2026

  We study the basic task of mean estimation in the presence of mean-shift contamination. In the mean-shift contamination model, an adversary is allowed to replace a small constant fraction of the clean samples by samples drawn from arbitrarily shifted versions of the base distribution. Prior work cha…

• Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise

  Rafael Hanashiro, Abhishek Shetty, Patrick Jaillet · 25 February 2026

  Towards understanding the statistical complexity of learning from heterogeneous sources, we study the problem of multi-distribution learning. Given $k$ data sources, the goal is to output a classifier for each source by exploiting shared structure to reduce sample complexity. We focus on the bounded…

• A Statistical Learning Perspective on Semi-dual Adversarial Neural Optimal Transport Solvers

  Roman Tarasov, Petr Mokrov, Milena Gazdieva, Evgeny Burnaev, Alexander Korotin · 25 February 2026

  Neural network-based optimal transport (OT) is a recent and fruitful direction in the generative modeling community. It finds its applications in various fields such as domain translation, image super-resolution, computational biology and others. Among the existing OT approaches, of considerable int…

• Statistical Query Lower Bounds for Smoothed Agnostic Learning

  Ilias Diakonikolas, Daniel M. Kane · 25 February 2026

  We study the complexity of smoothed agnostic learning, recently introduced by~\cite{CKKMS24}, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspace…

• Oracle-Robust Online Alignment for Large Language Models

  Zimeng Li, Mudit Gaur, Vaneet Aggarwal · 25 February 2026

  We study online alignment of large language models under misspecified preference feedback, where the observed preference oracle deviates from an ideal but unknown ground-truth oracle. The online LLM alignment problem is a bi-level reinforcement problem due to the coupling between data collection and…

• High-Dimensional Robust Mean Estimation with Untrusted Batches

  Maryam Aliakbarpour, Vladimir Braverman, Yuhan Liu, Junze Yin · 25 February 2026

  We study high-dimensional mean estimation in a collaborative setting where data is contributed by $N$ users in batches of size $n$. In this environment, a learner seeks to recover the mean $\mu$ of a true distribution $P$ from a collection of sources that are both statistically heterogeneous and pot…

• On the Limits of Self-Improving in Large Language Models: The Singularity Is Not Near Without Symbolic Model Synthesis

  Hector Zenil · 24 February 2026

  We formalise recursive self-training in Large Language Models (LLMs) and Generative AI as a discrete-time dynamical system. We prove that if the proportion of exogenous, externally grounded signal $\alpha_t$ vanishes asymptotically ($\alpha_t \to 0$), the system undergoes degenerative dynamics. We d…

• The Sample Complexity of Replicable Realizable PAC Learning

  Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen · 24 February 2026

  In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and w…

• Distribution-Free Sequential Prediction with Abstentions

  Jialin Yu, Mo\"ise Blanchard · 23 February 2026

  We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d.\ instances, but at each round, the learner may also \emph{abstain} from making a prediction without incurring any penalty if the instance was indeed corrup…

• Learning Without Training

  Ryan O'Dowd · 23 February 2026

  Machine learning is at the heart of managing the real-world problems associated with massive data. With the success of neural networks on such large-scale problems, more research in machine learning is being conducted now than ever before. This dissertation focuses on three different projects rooted…

• Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

  Lunjia Hu, Kevin Tian, Chutong Yang · 20 February 2026

  Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses $\mathcal{L}$ against a family of comparator predictors $\mathcal{C}$. We initiate the study of omniprediction in a multiclass setting, where the comparator family $\mathcal{C}$ may be infinite. Ou…