NeurIPS 2026 Papers

The alignment of Large Language Models (LLMs) via reinforcement learning from human feedback (RLHF) typically relies on Proximal Policy Optimization (PPO), which uses a uniform clipping hyperparameter $\epsilon$ to maintain a stable trust region. However, we demonstrate that this uniform constraint is ill-suited for the non-uniform semantic topology of natural language. In ``semantically dense'' regions, where candidate tokens act as semantic synonyms within the current context, noisy advantage estimates can destabilize the fixed trust region, leading to *policy collapse*, a severe loss of generative diversity and policy entropy. To resolve this, we propose *Structure-Aware Mirror Proximal Policy Optimization (SAMPPO)*, which introduces an adaptive trust region governed by local semantic density. SAMPPO generalizes the trust-region framework to non-uniform semantic spaces by adapting the mirror-descent geometry to the local action topology. SAMPPO uses a per-timestep *Semantic Isolation Score* to dynamically tighten the clipping range in dense regions and relax it in sparse ones. We provide theoretical foundations for this approach, deriving a *Structure-Aware Monotonic Improvement* bound and establishing a formal link to structure-aware margin-shifted $H$-consistency theory. Empirically, SAMPPO prevents the entropy collapse observed in standard PPO baselines and significantly improves alignment. Evaluated on the Anthropic HH-RLHF and NVIDIA HelpSteer benchmarks across multiple model architectures (Llama-3-8B and Gemma-2-2B), SAMPPO achieves robust, zero-shot generalizable alignment gains. Crucially, it strictly outperforms standard PPO and recent empirical adaptive heuristics (BAPO), demonstrating competitive performance against direct preference baselines including DPO and SimPO on the alignment-diversity Pareto frontier.

We introduce a new measure of robustness for statistical estimators, which we call empirical sensitivity. An estimator $\hat \mu$ has bounded empirical sensitivity if, with high probability over a dataset $X = (X_1, \dots, X_n) \sim \mathcal{D}^{\otimes n}$, for any dataset $Y$ obtained by modifying at most $\eta n$ points in $X$, we have that $\hat \mu(Y)$ is close to $\hat \mu(X)$. We study bounds on this quantity for the prototypical problem of Gaussian mean estimation. We prove new lower bounds, showing that for any estimator $\hat \mu$ which achieves an optimal $\ell_2$-error bound of $O(\sqrt{d/n})$, the empirical sensitivity is at least $\Omega(\eta + \sqrt{\eta d/n})$. The two terms arise due to obstructions on the mean and variance (via an Efron-Stein argument) of such an estimator. We show that this bound is tight up to logarithmic factors, by employing recent results for robust empirical mean estimation.

We give a computer-assisted counterexample to the open question posed by Rudin, Schapire, and Daubechies in COLT 2012, of whether exhaustive AdaBoost always converges to a finite cycle. The construction is based on a block-product gadget whose two factors share an exact period-2 orbit for their 5-step branch maps, but whose linearized return maps have dominant eigenvalues with an irrational logarithmic ratio. This irrationality forces the burst-winner sequence to have an irrational asymptotic frequency, precluding eventual periodicity. All assertions are certified by exact rational arithmetic in two independent computer algebra systems. We also document the collaborative workflow that led to the construction, in which one model produced the key technical arguments; another model summarized and critiqued different versions of that work, proposing new directions to pursue; and the authors orchestrated the process by selecting directions to prioritize, resolving ambiguities, heavily refining each argument, and verifying the final solution. We present this as one of the first in-depth case studies of LLM-assisted mathematical research in which a long-standing open problem from theoretical machine learning is resolved, and detail the advantages and challenges of such research.

Algorithmic *replicability* has recently been introduced to address the need for reproducible experiments in machine learning. A *replicable online learning* algorithm is one that takes the same sequence of decisions across different executions in the same environment, with high probability. We initiate the study of algorithmic replicability in *constrained* MAB problems, where a learner interacts with an unknown stochastic environment for $T$ rounds, seeking to maximize reward while satisfying multiple constraints. Our main result is that replicability can be achieved in constrained MABs. Specifically, we design replicable algorithms whose regret and constraint violation match those of non-replicable ones in terms of $T$. As a key step, we develop the first replicable UCB-like algorithm for *unconstrained* MABs, showing that algorithms that employ the optimism in-the-face-of-uncertainty principle can be replicable, a result that we believe is of independent interest.

We study principal-agent problems in which a principal commits to an outcome-dependent payment scheme (i.e., a contract) in order to induce an agent to take a costly action leading to a favorable outcome. We consider the online extension of the classical (one-shot) principal-agent problem, in which the principal repeatedly interacts with agents by proposing contracts over multiple rounds. The principal has no information about the agents and, crucially, does not observe their actions. As a result, the principal must learn an optimal contract using only the realized outcomes observed at each round. We focus on the setting with binary-actions and single-dimensional agent types, where the agent's private type represents their cost per unit-of-effort. For adversarial-type sequences, we provide tight $\widetilde\Theta(T^{2/3})$ regret guarantees. Remarkably, this rate is completely independent of the number of outcomes $m$. The upper bound is based on two key components: 1) a reduction to one-dimensional threshold optimization problem and 2) a non-uniform discretization to handle the non-Lipschitz nature of the problem. Moreover, in the case of a single (fixed) hidden type, we show that it is possible to improve the rates and provide a tight $\widetilde\Theta(\sqrt{T})$ regret bound. Our algorithm is based on an explore-then-commit strategy where we first approximately learn the hidden type via a stochastic binary search, and then we commit to a ``robustified'' near-optimal contract.

Empirical studies of trained models often report a transient regime in which signal is detectable in a finite gradient descent time window before overfitting dominates. We provide an analytically tractable random-matrix model that reproduces this phenomenon for gradient flow in a linear teacher--student setting. In this framework, learning occurs when an isolated eigenvalue separates from a noisy bulk, before eventually disappearing in the overfitting regime. The key ingredient is anisotropy in the input covariance, which induces fast and slow directions in the learning dynamics. In a two-block covariance model, we derive the full time-dependent bulk spectrum of the symmetrized weight matrix through a $2\times 2$ Dyson equation, and we obtain an explicit outlier condition for a rank-one teacher via a rank-two determinant formula. This yields a transient Baik--Ben Arous--P\'ech\'e (BBP) transition: depending on signal strength and covariance anisotropy, the teacher spike may never emerge, emerge and persist, or emerge only during an intermediate time interval before being reabsorbed into the bulk. We map the corresponding phase diagrams and validate the theory against finite-size simulations. Our results provide a minimal solvable mechanism for early stopping as a transient spectral effect driven by anisotropy and noise.

We develop a quantitative statistical theory of transformers in the large-context regime by adopting the abstraction of contextual flow maps: dynamical systems that evolve a distinguished token in the presence of a contextual measure across a stack of attention blocks. Within this framework, the finite-context model approximates an idealized infinite-context system in which the contextual measure is replaced by its underlying population, so that the context length $n$ becomes a statistical resource. Exploiting the McKean--Vlasov structure of the dynamics and the classical machinery of propagation of chaos, we establish a forward bound controlling the deviation between the finite- and infinite-context flow maps uniformly along depth, and a backward bound controlling the deviation between the corresponding training trajectories uniformly across iterations of online gradient descent. Both bounds achieve the optimal Wasserstein rate $n^{-1/d}$. The analysis rests on a new Eulerian adjoint formulation of the loss gradient and stability estimates for the resulting forward--adjoint system, both of which may be of independent interest. We further verify that the standard transformer architecture satisfies these estimates with Lipschitz constants independent of embedding and parameter dimensions, suggesting a structural reason why transformers train stably across model scales.

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 for the next step prediction. Classical MDL prediction theory shows that exact optimization of the MDL objective indeed provides a strong compression guarantee that supports reliable prediction. However, practical machine learning usually can only find models by approximately optimizing the objective function. To bridge this gap, this paper addresses the following fundamental question: \emph{Under what forms of approximation and regularization does approximate MDL still guarantee reliable sequential prediction?} This work offers a principled characterization. We prove that for any approximation with \emph{additive} slack \(C\) of the more general form of the \emph{balanced} MDL objective: $\lambda\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$, the cumulative expected squared prediction error is finite for all $\lambda\ge1$. The case $\lambda>1$ is proved by an affinity-telescoping argument, while the boundary case $\lambda=1$ is proved by a likelihood-ratio stopping argument based on exact static MDL bounds. Our results establish that classical MDL regularization remains robust to any fixed additive optimization error. Furthermore, we establish that our characterization of the approximate MDL framework is sharp: When $0<\lambda<1$, overfits can happen to incur infinite cumulative expected error in the universal class of estimable measures, and hence a strong form of model-complexity regularization is necessary. In addition, model selection may fail in every regularized regime $\lambda >0$, under multiplicative approximation, and thus, additive approximation is both sufficient and essential.

This paper studies binary classification under generalized performance metrics, going beyond standard misclassification error. We focus on linear-fractional measures—including the $F$-score and Jaccard index—which are widely used in class-imbalanced settings. We first provide a unified characterization of the optimal classifier, showing that it admits a thresholding structure on the regression function. This reduces the original infinite-dimensional, non-decomposable optimization problem to the estimation of a single scalar parameter. Building on this result, we analyze plug-in classifiers that combine a regression estimator with a data-driven estimate of the optimal threshold. We show that this threshold is characterized as the solution of a fixed-point equation depending only on the marginal distribution, enabling its estimation using unlabeled data and avoiding standard validation-based procedures. Our main contribution is a finite-sample analysis of this approach. We derive excess risk bounds that decompose the error into contributions from regression estimation, threshold estimation, and sampling effects, providing a modular understanding of learning under non-decomposable metrics. Under standard margin assumptions, we further establish fast convergence rates. Our results yield a unified theoretical framework for plug-in classification under linear-fractional metrics, extending prior analyses beyond specific measures such as the $F$-score. Empirical results on synthetic and real datasets support our theoretical findings.

We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees and multiple data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with data-dependent bounds, including first-order, second-order, and path-length bounds, but only under known transitions. We resolve the open problem raised by Dann et al. (2023) by developing optimistic follow-the-regularized-leader algorithms that extend such guarantees to unknown transitions. The key ingredient is a new design of optimistic $Q$-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with this transition-dependent complexity term while simultaneously achieving gap-dependent $\mathrm{polylog}(T)$ regret in the stochastic regime.

Attention is the key mechanism underlying in-context learning in transformers, and attention patterns have been observed empirically to emerge abruptly during training. We present a Bayesian theory of feature learning in attention; we then focus on how the copy subcircuit in the first layer of an induction head is learned by analyzing a single-layer softmax attention network trained on a copy task. We derive a closed-form posterior over the attention matrix and reduce it to a low-dimensional order parameter space. This reduction reveals a phase transition in the amount of training data, which we verify using both Bayesian sampling and standard training with Adam. We contrast our results with linear attention and find that softmax attention exhibits a *first-order phase transition* while in linear attention an initial *second-order phase transition* is followed by a smooth, continuous evolution toward the structured attention pattern (*crossover*). Our work provides a first-principles theoretical account of the abrupt emergence of the copy subcircuit, reminiscent of the one observed in training large language models.

Representations are routinely used in machine learning, psychology, and neuroscience to probe the computations of biological and artificial systems. Yet it remains unclear to what extent computation constrains representation in artificial neural networks. Neural networks admit *parameter symmetries*: transformations of the parameters that preserve function exactly but reshape representational geometry. We show that known parameter symmetries act on representations through just three primitives: *addition*, *duplication*, and *scaling*, giving a closed-form descriptor of representational geometry as task-linked features plus symmetry-induced noise. This decomposition yields analytic bounds on representational similarity between networks related by parameter symmetry, which reveal when functionally equivalent networks become arbitrarily *dis*similar. Finally, we identify *privileged* representational geometries, which weight features by their computational importance and recover a stable link between representation and computation. Overall, our results delineate when representation can support inferences about computation, and when it cannot.

In this paper we derive a Probably Approximately Correct (PAC)-Bayesian error bound for partially observed linear time-invariant (LTI) stochastic dynamical systems in state-space form with inputs. Such bounds are widespread in machine learning, and they are useful for characterizing the predictive power of models learned from finitely many data points. The bound derived in this paper relates the expectation of prediction errors with the prediction error generated by the model on the data used for learning. In addition, we show that it can also be used to derive bounds for the parameter estimation error. In turn, this allows us to provide finite-sample error bounds for the prediction error and parameter estimation error for a wide class of system identification algorithms. Furthermore, as LTI systems are a sub-class of recurrent neural networks (RNNs), these error bounds could be a first step towards PAC-Bayesian bounds for RNNs.

We prove optimal sampling bounds achieving $(1\pm\varepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove $k^2/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_2/k$ regularization, and $k/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_1/k$ regularization. For $\|\cdot\|_2^2/k$ regularization, the sampling complexity depends mainly on a bounded derivative property: if $|g'(x)|\leq g(x)$, and $g(0)>0$, and $g$ is monotonic or convex, then it admits linear in $k$ sampling complexity; otherwise the general bound is $k^2/\varepsilon^2$. However, if $g(0)=0$, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic $k^3/\varepsilon^2$ sensitivity sampling bounds of (Alishahi and Phillips, ICML'24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.

We consider the problem of learning an unknown subset $N^{target}$ of a domain in an online setting. % In each round $t$, the learner predicts a set of items ${N}_t$ and receives one of two types of feedback, each with equal probability: {\it precision feedback}, in which a randomly chosen item from the predicted set $N_t$ is revealed and the learner is told whether it belongs to $N^{target}$ (incurring a reward if it does), or {\it recall feedback}, in which a randomly chosen item from the target set $N^{target}$ is revealed and the learner is told whether it belongs to $N_t$ (incurring a reward if it does). The goal is to maximize the cumulative reward over time. This simple online set learning problem abstracts a variety of learning scenarios with precision and recall--type feedback. We show that a hypothesis class (a family of subsets of the domain) is learnable in this setting if and only if it has finite Vapnik-Chervonenkis (VC) dimension, mirroring the classical PAC characterization. However, the resulting algorithmic structure is markedly more intricate: in contrast to standard Probably Approximately Correct (PAC) learning---where the algorithmic landscape is governed by the simple principle of Empirical Risk Minimization (ERM)---our partial feedback model can invalidate ERM and even all proper learning rules. We develop algorithms to address the dependencies induced by the feedback, obtaining regret guarantees in both the realizable and agnostic settings. Our results provide a qualitative characterization of learnability in this model, addressing its most basic question, while pointing to a range of natural and intriguing open questions, including the determination of optimal regret rates.

Online resource allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints, with applications ranging from online advertising to revenue management. In this work, we study a broader setting that includes both budget constraints and general constraints, extending the classical budget-only model. This extension is essential for modelling critical economic requirements, such as Return-on-Investment (ROI) constraints. We develop an algorithm that achieves best-of-both-world guarantees within this generalized framework. In particular, against a dynamic benchmark, our algorithm achieves $\widetilde{\mathcal O}(\sqrt{T})$ regret in the stochastic regime and $\alpha$-regret of order $\widetilde{\mathcal O}(\sqrt{T})$ in the adversarial regime, where $\alpha$ depends on the feasibility margin of the corresponding offline problem. At the same time, our algorithm guarantees strict satisfaction of the budget constraints and $\widetilde{\mathcal O}(\sqrt{T})$ cumulative violation for the general ones. From a technical perspective, introducing general constraints alongside budgets precludes the use of standard budget-focus methods. While budget methods rely on a zero-consumption "safe'' action to ensure feasibility, general constraints are much less "aligned'' towards feasibility. We overcome these difficulties with a new analysis that exploits weak adaptivity to get boundedness of the Lagrangian multipliers and best-of-both-world guarantees.

We develop an online directional regression for sufficient dimension reduction with streaming data. Unlike first-moment methods, directional regression exploits both inverse conditional means and inverse conditional variances, and can therefore recover central subspace directions generated by linear structures, symmetric dependencies, and interaction driven relationships. Extending directional regression to the online setting is nontrivial because its kernel depends on slice-wise inverse moments and on standardization by an unknown covariance matrix. We address these challenges by utilizing a stable slice probability free kernel, a ridge-stabilized recursive least-squares estimator of the standardization operator, metric-aware subspace tracking under a vanishing-ridge covariance metric, and a weighted-bootstrap ladle criterion for online structural dimension selection. Under standard regularity conditions, the online kernel estimator is root-$t$ consistent, the estimated generalized eigenspace consistently recovers the central subspace, and the proposed dimension selector consistently estimates the structural dimension. Simulation studies and real-data analyses demonstrate that the proposed method serves as a robust online alternative when the dominant data structure is unknown, adapting to both first-moment and second-moment-driven dependencies while yielding substantial computational savings relative to repeated batch directional regression.

Chain-of-Thought (CoT) enables transformers to solve complex reasoning tasks by generating intermediate reasoning steps. Despite strong empirical success, the mechanisms by which such reasoning abilities emerge during training remain poorly understood, particularly from a theoretical perspective. In this work, we study this question in a stylized yet fully analyzable setting: in-context $\mathrm{K}$-nearest-neighbor ($\mathrm{K}$-NN) prediction with a one-layer transformer. Earlier work has demonstrated that one-layer transformers can be trained to perform $1$-NN without CoT \citep{Li2024One} by having the softmax attention attend to the nearest neighbor in context. However, this result on $1$-NN cannot be extended to $\mathrm{K}$-NN for $K>1$, as softmax attention is much less naturally suited to attending to the 2nd through $K$-th nearest neighbors. We first give a rigorous negative result showing that this limitation already appears on a well-separated class of binary classification tasks for odd $K>1$. We then give an explicit construction of a one-layer transformer, and show that it can solve $\mathrm{K}$-NN via CoT reasoning. We further prove that, under a stylized training setup, gradient descent can recover this construction, thereby showing that transformers can acquire the capability to solve $\mathrm{K}$-NN through training. In addition, we show that the resulting trained model applies to a broader test class than that assumed in the training analysis. Our results shed light on how CoT expands the ability of transformers to learn and solve tasks that are otherwise hard to solve.

We study preference-based bandits with general reward function classes, where a learner sequentially selects pairs of arms and observes binary preference feedback governed by the Bradley-Terry model. This setting naturally arises in applications such as recommender systems, tournament ranking, and learning from human feedback, where relative preferences are easier to elicit than absolute rewards. The observation model inherits the logistic bandit challenge of handling the problem-dependent constant $\kappa$, which accounts for the non-linearity of the link function and can grow arbitrarily large. Moreover, prior work has predominantly focused on linear or kernelized reward models, precluding the use of richer function classes. To address these limitations, we consider general reward function classes and introduce the *locally sensitive eluder dimension*, a novel complexity measure tailored to the logistic structure of preference feedback that yields fine-grained regret guarantees without unfavorable dependence on $\kappa$. Building on this notion, we propose **GINOP** (**G**eneric **IN**formative **OP**timism), an algorithm that constructs log-loss confidence sets and jointly selects arm pairs to balance optimism and informative exploration. We establish a first-order regret bound that, in contrast with what previous results suggest, demonstrates that learning with preference feedback is as statistically efficient as learning from direct reward observation. Finally, we corroborate our theoretical findings with empirical evaluations against competitive baselines.