Theory

Learning theory, optimisation theory, generalisation, mathematical analysis of models

91 articles · page 1 of 2

Theory

Reward-focused training can silently amplify unwanted model traits

The authors apply the Price equation from evolutionary biology to model how non-targeted traits change during RL post-training of language models. They show that this equation accurately predicts the observed dynamics of traits such as sycophancy and internal SAE features during GRPO training. This identifies trait hitchhiking as a mechanism by which RL can amplify undesirable traits without explicit reward shaping.

Theory

Theory explains why low-rank adapters resist forgetting and merge well

The authors propose a unified theoretical explanation for two surprising properties of low-rank adaptation (LoRA): its robustness to catastrophic forgetting and the ability to merge independently trained adapters. Analyzing LoRA in multiclass linear classification under a near-orthogonal task regime, they characterize the optimal adapter and derive closed-form expressions for margins, proving that a regularization parameter controls the balance between retention and adaptation, and that merged adapters maintain positive margins on each task.

Theory

AI models cannot be reliably evaluated without fresh test sets

Kunal Talwar formalizes when it is possible to evaluate a black-box model without a held-out test set, a setting increasingly relevant as foundation models are trained on nearly all publicly available data. The paper provides tight bounds showing that, with only output access on a given test set, accurate evaluation is feasible if and only if the distribution is close to supported on a small number of points. Introducing limited query access to the model connects to self-correction in program testing and can expand the evaluable class for certain distributions.

Theory

Noise injection reveals when machine learning cannot identify patterns

The authors develop a general framework that reinterprets the classic hardcore lemma in terms of masking channels, input-dependent noise that corrupts labels. They show that the difficulty of learning a function with a given class of models is tightly characterized by the maximum 'fidelity' of such a channel, i.e., the least noise required to make the function look random to that class. This unifies and extends previous results to multiclass problems and arbitrary convex losses.

Theory

A small positional signal replaces costly relaxation layers when training symmetry-aware models

The authors propose a constraint-relaxation method that injects a positional encoding with learnable scale into an equivariant network, then anneals it to zero during training, recovering the original symmetric model at test time. Across five architectures for point-cloud classification, image classification, smoke-plume forecasting, and N-body dynamics, this approach matches or improves strict equivariant baselines and outperforms a previous dense-layer relaxation method, while adding almost no compute or memory overhead.

Theory

Averaging several models beats one bigger model when training data is fixed

Retraining a language model on the same text for many epochs usually makes validation loss bottom out and then climb. Yang, Miao and Bordelon report that averaging the predictions of several independently trained models reduces this late rise, pushes the best stopping point later, and can beat a wider or deeper single model at the same parameter-token budget. Their theory attributes the effect to a variance term that shrinks in proportion to the number of models averaged.

Theory

Hybrid estimator predicts error of AI models that memorize exceptions

The authors study the problem of estimating the probability of an event that depends on a sample, such as the test error of a classifier. They unify classical missing mass estimation and test error estimation within a single framework. For predictors that combine a base classifier with memorized exceptions, they show the test error equals the missing mass restricted to the error region of the base classifier, and they propose a hybrid estimator that works even when the base classifier is unstable.

Theory

Under data shift, prediction intervals can be provably shortest on average

The paper studies building prediction intervals for regression when test inputs follow a different distribution than calibration data, a setting known as covariate shift, while the response mechanism stays the same. The author proves that one rule, using the inverse conditional density as a score with randomized weighted conformal calibration, has minimum expected interval length under the target distribution among all valid rules, for any fixed calibration size. Simulations and four regression benchmarks show it often yields shorter intervals than existing weighted methods.

Theory

AI models’ performance forecasts can diverge despite similarly good data fits

Neural scaling laws forecast how model performance changes with training resources, but finding a good fit does not necessarily identify a reliable forecast. Bruno Mlodozeniec and Spencer Frei show that substantially different curves can fit the observed measurements nearly equally well while diverging at larger scales. Their proposed method identifies this ambiguity rather than hiding it behind one selected curve.

Theory

Top-k data scores under-cover latent modes; class balancing or coverage fixes selection

The authors analyze the common practice of selecting training data by top-k per-point value scores such as Data Shapley, influence, and leverage. They prove in a latent-mode model that fixed top-k selection incurs a closed-form excess risk versus adaptive coverage, and they derive a practical rule: balance by labels when labels name the modes, otherwise use explicit coverage based on learner geometry.

Theory

Language models can transfer specialized skills across sizes without retraining

The authors propose Ariadne, a training-free approach that transfers task-specific behavior across Transformer architectures by focusing on the activation changes induced by fine-tuning rather than moving parameters directly. They show that aligning these activation displacements via local Procrustes maps and then synthesizing a target update through closed-form ridge regression improves target-model performance while requiring less time and memory than prior cross-architecture rebasin methods.

Theory

Reverse-KL distillation's sample needs hinge on who generates trajectories

Liu, Wei, and Zimmert establish minimax sample-complexity bounds for reverse-KL policy distillation under four settings, varying whether trajectories come from the student (online) or teacher (offline) and whether the teacher reveals its full action distribution or only the sampled action's probability. They find that online action-feedback distillation can require substantially more data than full feedback, whereas offline distillation achieves the same optimal rate regardless of feedback type.

Theory

Muon's orthogonalized updates win when gradients are far from low rank

The authors analyze PolarGD, the orthogonalized update at the core of the Muon optimizer, on matrix quadratics with exact line search. They show it reaches the minimizer in one step under much weaker conditions than gradient descent, and that its long-run speed depends on the conditioning of the iterate, not the Hessian. They also find that approximate Newton-Schulz steps can converge faster than exact orthogonalization when the iterate has tiny singular values.

Theory

Differentially private online prediction achieves regret proportional to square root of best expert's loss

Bo Li and Peng Ye present the first differentially private algorithm for online prediction from experts that attains regret Õ(√L*), where L* is the cumulative loss of the best expert. This improves over the standard Õ(√T) regret when L* is much smaller than T, showing that privacy incurs only a small additional cost in the low-loss regime. The algorithm works under an oblivious adversary and its regret matches the non-private lower bound up to poly-logarithmic factors for constant privacy parameters.

Theory

Computing approximate correlated equilibria is as hard as computing Nash equilibria.

The authors show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, making it polynomial-time equivalent to finding a Nash equilibrium. They introduce fixed sets, a relaxation of fixed points, and prove that computing such a set is PPAD-hard at inverse polynomial precision. This result overturns the classical view that correlated equilibria are computationally easier than Nash equilibria.

Theory

Transformers learn to detect invalid planning steps and abort to retry

This paper studies how Transformer language models can learn to recognise invalid steps during planning. The authors propose training with trajectory prefixes that end with an invalid transition, supervised only by an abort token. They provide a theoretical construction and capacity lower bound, and demonstrate empirically that the learned detection signal improves planning reliability on graph path-finding, Countdown, and maze tasks.

Theory

Binary sign patterns of neurons, not their magnitudes, drive classification in deep networks

Göring et al. introduce the 'sign code'—the collection of binary signs of all neuron outputs in a trained network—and demonstrate that this discrete pattern alone carries almost all classification-relevant information. Across architectures, activations, and datasets, a k-nearest-neighbor classifier operating only on the sign code matches the accuracy of the full model, while randomizing magnitudes (keeping signs intact) barely degrades performance and flipping 20% of signs reduces accuracy to chance. The authors provide a theoretical margin decomposition showing that the sign contribution to each logit grows as the square root of network width, dominating the magnitude residual.

Theory

Hosted decision model Jev violates independence of irrelevant alternatives

Rajput et al. pre-registered and ran 299,463 API calls on Jev-1.13.0, a hosted decision model, to test whether its probabilities respect independence of irrelevant alternatives (IIA). They found systematic, directional shifts in log-odds between the correct label and its strongest rival whenever any option was added, even when that option carried less than 0.1% of the probability mass. The violations are substantial and structured, invalidating the assumption that probabilities are fixed properties of options.

Theory

First-price auctions can be near-efficient for prompt allocation in agentic markets

Trivedi and colleagues analyze first-price auctions as a serving-time market where AI agents bid for the right to respond to a user prompt, paying their bid when they win. They prove that two structural features of agentic markets, a competitive floor among bidders and near-independence of values after conditioning on the prompt, substantially improve the price of anarchy, raising the welfare guarantee from about 63% to up to 86.5% of optimal welfare or better. Simulations on the EmbedLLM prompt routing dataset confirm that realized welfare losses are much smaller than the worst-case bound.

Theory

Recursive synthetic data can cause screening to discard relevant variables before model fitting

The authors introduce and analyze screening collapse, a phenomenon where recursive synthetic data (labels generated by previous models) degrades variable screening, causing relevant features to be discarded. In a Gaussian linear model with minimum-norm recursive generators, they establish finite-sample screening bounds, characterize an information-loss limit in late generations, and prove a minimax impossibility result. They also show that data accumulation can avoid collapse if the pooled target preserves a positive margin and the sample grows sufficiently.