Machine Learning and Algorithms

Latest papers

• AgentBrew: Lifelong Knowledge Brewing from Strong Teachers to Weak LLM Agents

  Yangqin Jiang, Chao Huang · 21 July 2026

  Deploying LLM agents typically requires a compact test-time student, even if a stronger teacher is available during training. We study knowledge brewing: distilling a teacher's interactive experience into a persistent external memory for the student. Crucially, this requires no weight updates, exper…

• Testing Distributions Against Bounded Distinguishers

  Mark Bun, Rathin Desai, Renato Ferreira Pinto Jr · 20 July 2026

  Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution $P$ over a very large domain to decide between two ca…

• Publicly-Verifiable Certificates for Statistical Algorithms

  Michael Ngo, Michael P. Kim · 20 July 2026

  Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow …

• Mirror Horizon: Viable Path Entropy as a Measure of Bounded Reflection

  Tiantian Zhang (Crystal) · 15 July 2026

  Mirror Theory proposes that an intelligent system should be studied not only by what it represents, but by what coherent continuations it can sustain under repeated reflection. We make this claim operational through \emph{viable path entropy} (VPE), a finite-budget measure of verified continuation c…

• When Does Reward Teach State? A Hidden-Automaton Instrument and the Group-Language Boundary

  Jim Allchin · 15 July 2026

  Does a reinforcement-learning agent that earns high reward represent its task's latent state, or only a reward-correlated shortcut? The question is usually unanswerable: the "true state" is undefined. We make it exactly answerable with a white-box instrument: express the task as a hidden determinist…

• Language Identification with Succinct Machine-Independent Traces

  Moses Charikar, Jon Kleinberg, Chirag Pabbaraju · 15 July 2026

  Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation. Recent papers on this question have prop…

• High-Dimensional Gaussian Mean Estimation under Realizable Contamination

  Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas · 15 July 2026

  We study mean estimation for a Gaussian distribution with identity covariance in $\mathbb{R}^d$ under a missing data scheme termed realizable $\epsilon$-contamination model. In this model an adversary can choose a function $r(x)$ between 0 and $\epsilon$ and each sample $x$ goes missing with probabi…

• Globally Consistent Coloring Schemes for Language Identification

  Moses Charikar, Jon Kleinberg, Chirag Pabbaraju · 14 July 2026

  We study how little extra information is needed to make adversarial language learning possible. In Gold's model of language identification in the limit, a learner is given an enumeration of the strings from an unknown language chosen from a countable language collection. The learner guesses the iden…

• What Context Does a Coding Agent Actually Need to Act?

  Brian Sam-Bodden · 14 July 2026

  A modern coding agent can hold an entire repository in its context window. Most of its reading is wasted -- and the interesting question is not how much context an agent can use, but what it actually \emph{needs}. We study that question at the moment it matters most: when the agent must \emph{edit} …

• MawForge: Memory-Bounded Expert Materialization for Local Mixture-of-Experts Inference

  Craig Opie · 14 July 2026

  Sparse Mixture-of-Experts (MoE) language models separate total parameter count from per-token active computation, but local inference systems often still require the full model, key-value cache, runtime buffers, and operatingsystem headroom to fit in fast memory. MawForge tests a different systems h…

• The VC dimension of partial concept classes via Radon's theorem

  Grigory Ivanov, Attila Jung, M\'arton Nasz\'odi · 14 July 2026

  Following Alon, Hanneke, Holzman, and Moran (FOCS 2021), we define a partial concept class (PCC) as a family of partial functions \(f: V\to\{0,1,\ast\}\); equivalently, its concepts partition the ground set into black ($f^{-1}(1)$), grey ($f^{-1}(\ast)$), and white parts ($f^{-1}(0)$). Its VC dimens…

• Fundamental Limitations of Fixed-Budget Best-Arm Identification

  Motti Goldberger · 14 July 2026

  In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across $K$ arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the …

• Influence Diagnostics in High-dimensional M-estimation: Precise Asymptotics

  Hugo Cui · 13 July 2026

  The impact of a given training point on a statistical model is classically measured through its leave-one-out influence, which quantifies the effect of its removal from the training set on the model accuracy. While the statistics of leave-one-out influences are well understood in the low-dimensional…

• A Fourier analytique approach to Gaussian mixture learning

  Somnath Chakraborty, Hariharan Narayanan · 13 July 2026

  Suppose that we are given independent, identically distributed random samples $x_1,\cdots,x_n$ from a mixture at most $k$ many $d$-dimensional spherical Gaussian distributions $\mu_1,\cdots,\mu_{k_0}$ of identical and known variance $\sigma^2$ in each coordinate, such that the minimum $\ell^2$ dista…

• Protocol Models: Scaling Decentralized Training with Communication-Efficient Model Parallelism

  Sameera Ramasinghe, Thalaiyasingam Ajanthan, Gil Avraham, Yan Zuo, Alexander Long · 9 July 2026

  Scaling models has led to significant advancements in deep learning, but training these models in decentralized settings remains challenging due to communication bottlenecks. While existing compression techniques are effective in data-parallel, they do not extend to model parallelism. Unlike data-pa…

• The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

  Stephen Mussmann · 9 July 2026

  Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced wit…

• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

  Meihua Dang, Stefano Ermon · 9 July 2026

  Constrained decoding is essential for serving LLMs, ensuring that generated outputs follow specific structures such as JSON schema-formatted function calls. Existing systems are designed for autoregressive models and assume left-to-right generation, masking out invalid next tokens at each step. Diff…

• The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

  Zhiyuan Li · 9 July 2026

  We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exac…

• Boosting with List-Decodable Codes

  Addison Prairie, Li-Yang Tan · 8 July 2026

  Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}{\epsilon})/\gamma^2)$ calls to a $\gamma$-advantage weak learner, and this round complexity is known to be…

• It's all In 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 · 7 July 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…

• Self-Reference in Large Language Models: The Introspection Threshold for Recursive Self-Improvement

  Jiang Zhang, Bing Yuan, Qian Zhang · 7 July 2026

  The pursuit of self-evolving AI raises a critical question: when is autonomous self-improvement sustainable rather than degenerative? Drawing an analogy to von Neumann's complexity threshold for self-reproducing automata, we argue that sustainable recursive self-improvement in Large Language Models …

• Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

  Ivan Lau, Jonathan Scarlett · 7 July 2026

  We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.…

• The Bayesian Approach to Continual Learning: An Overview

  Tameem Adel · 7 July 2026

  Continual learning is an online paradigm where a learner continually accumulates knowledge from different tasks encountered over sequential time steps. Importantly, the learner is required to extend and update its knowledge without forgetting about the learning experience acquired from the past, and…

• A Mechanism-Driven Theory of Phase Transitions in Active Learning

  Julia Machnio, Mads Nielsen, Mostafa Mehdipour Ghazi · 2 July 2026

  Active learning (AL) performance is known to be budget-dependent, yet regimes are typically defined by heuristic label counts that fail to generalize across datasets or architectures. We characterize AL dynamics by reframing budget regimes as shifts in the dominant generalization mechanism. By reint…

• Behavior Cloning is Not All You Need: The Optimality of On-Policy Distillation for Noisy Expert Feedback

  Ved Sriraman, Peihan Liu, Daniel Hsu, Adam Block · 1 July 2026

  Imitation Learning is a natural framework for learning in sequential decision-making systems and has emerged as the dominant paradigm through which we understand language model training. A central puzzle is that, while in theory offline IL can be horizon-free and optimal, in practice online methods …