NeurIPS 2026 Papers

Transformers have become a central architecture for \emph{in-context learning}, particularly through their strong empirical performance in large language models. This success suggests that transformers can extract task-relevant structure directly from prompts, even when the underlying data have complex geometric structure. However, existing theoretical analyses of transformer-based in-context learning are largely confined to simplified settings, such as Euclidean domains or single-manifold models. In this paper, we study in-context nonparametric regression under growing geometric complexity, modeled by a sample-size-dependent mixture of manifolds with heterogeneous local geometry. For this model class, we establish a minimax lower bound that captures the aggregate difficulty of its local components. We then construct an oracle tangent local-polynomial estimator and prove a matching upper bound by exploiting local geometric structure. The main technical step is to connect this estimator to a transformer architecture. We construct a two-stage linear-attention transformer consisting of a geometric preconditioner and all-chart reduced local-polynomial solvers, and show that its approximation error is negligible relative to the minimax regression rate. We also prove an in-context generalization bound for $\varepsilon$-near empirical risk minimizers within this transformer class. Together, the lower bound, oracle construction, transformer approximation, and generalization analysis identify the conditions under which the resulting in-context predictor adapts to local geometry and attains the aggregate minimax rate.

A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates `Poll`, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, `Poll` uses significantly fewer operations than exact computation and other distributed methods; statistically, its query complexity scales with topology and preference heterogeneity rather than with population size; and economically, it converges to welfare-maximizing prices while inducing truthful reports and detecting adversarial deviations.

We study the decoupled multi-armed bandit problem, where the player selects one arm to exploit (incurring its loss) and one arm to explore (observing its loss) at each round. We propose two algorithms: D-Exp3-Ada, based on Exp3 with an AdaGrad learning rate, and D-TINF-SPM, based on FTRL with Tsallis entropy and the stability-penalty matching learning rate. Here, $K$ denotes the number of arms, $T$ the time horizon, and $\Delta_i$ the suboptimality gap of arm $i$. D-Exp3-Ada achieves $\mathcal{O}(\sqrt{KT\log K})$ regret in adversarial regimes and $\mathcal{O}(\sum_{i \neq i^{\star}} \frac{\log K}{\Delta_i})$ in stochastic regimes, combining simplicity of algorithm design with strong guarantees. D-TINF-SPM achieves the minimax optimal $\mathcal{O}(\sqrt{KT})$ in adversarial regimes and $\mathcal{O}(\min\{\sqrt{K\sum_{i \neq i^{\star}} \frac{1}{\Delta_{i}^2}}, \sum_{i \neq i^{\star}} \frac{\log K}{\Delta_i}\})$ in stochastic regimes. We also provide a refined analysis of the prior best algorithm. Finally, we derive instance-dependent lower bounds under natural monotonicity and permutation-invariance assumptions on regret upper bounds, proving that our algorithms are optimal up to $\mathcal{O}((\log K)^2)$ within this class.

It is known that optimally regularized ridge regression can exhibit non-monotone dependence of the generalization risk on the sample size. We show that this behavior can be arbitrarily intricate in finite dimensions: for every $d \ge 2$, there exists a random design linear model in $\mathbb{R}^d$ whose generalization risk, viewed as a function of the sample size, exhibits at least $d - 1$ local maxima.

We study multi-armed bandits (MABs) augmented with best-action queries, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the full-feedback model, where the learner observes the rewards of all arms after each round. They show that, in both stochastic and adversarial environments, $k$ best-action queries reduce the optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret to $\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T}\})$. Whether this improvement extends to the more realistic bandit-feedback model---where the learner observes only the reward of the played arm---was left as an open problem. We fully resolve this question. When rewards are stochastic but correlated among arms, we show that the full-feedback result does not carry over: any algorithm must incur regret at least $\Omega(\sqrt{T-k})$. This lower bound directly extends to adversarial environments. On the positive side, we show that $\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T-k}\})$ regret is still achievable when rewards are stochastic and i.i.d., and establish a matching lower bound, up to logarithmic factors. Together, these results provide a complete characterization of the benefits of best-action queries in the bandit-feedback model.

Recursive training on synthetic data can drive generative models toward collapse, yet most explanations treat collapse as a statistical phenomenon: tail loss, variance shrinkage, or distributional drift. We develop a singular-geometric view of collapse. In a labeled Gaussian mixture abstraction of recursive self-training, we show that mode extinction induces a monotone trajectory in the real log-canonical threshold: as recursive resampling eliminates active modes, the overcomplete mixture moves through increasingly singular strata, with strictly decreasing singular complexity and growing Fisher-information nullity. We further show that this loss of identifiability begins before exact extinction: as a component's weight becomes small, Fisher curvature in its associated parameter directions shrinks proportionally, so exact singularity is the endpoint of a continuous near-nullity trajectory. Thus collapse corresponds not only to reduced distributional diversity, but also to a progressive loss of locally identifiable parameter directions. This theory separates the singular geometry of collapse from the multinomial/Wright--Fisher absorption dynamics. We also prove that, in the mixture abstraction, injecting enough real data prevents component extinction and keeps the singular-complexity trajectory from descending over a fixed horizon with high probability. We then use the theory to motivate loss-landscape diagnostics for neural recursive training, including Hessian spectra, Gauss--Newton effective rank, decoder-block curvature, feature-rank concentration, and local learning coefficient estimates. Across Gaussian mixtures, VaDE, standard VAEs, and a compact DDPM, we find that synthetic-only recursion exhibits the predicted geometric degeneration, that VaDE geometry diagnostics predict future component loss, and that real-data injection stabilizes both distributional and geometric collapse metrics.

In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this work, we show that early stopping can overcome this suboptimality: in a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimax-optimal excess zero-one risk for covariance spectra with fast and continuous decay, including polynomial and exponential spectral decays. Our analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are validated by experiments. A central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk; it handles the model misspecification induced by the label-flipping noise, and removes the square-root rate in standard bounds. We also establish a lower bound for linear interpolators, showing that interpolation can require exponentially more samples than early stopping to achieve the same excess risk.

We show that the MinMax algebra provides a form of recurrence that is expressively powerful, efficiently implementable, and most importantly it is not affected by vanishing or exploding gradient. We call MinMax Recurrent Neural Cascades (RNCs) the models obtained by cascading several layers of neurons that employ such recurrence. We show that MinMax RNCs enjoy many favourable theoretical properties. First, their formal expressivity includes all regular languages, arguably the maximal expressivity for a finite-memory system. Second, they can be evaluated in parallel with a runtime that is logarithmic in the input length given enough processors—and they can also be evaluated sequentially. Third, their state and activations are bounded uniformly for all input lengths. Fourth, at almost all points, their loss gradient exists and it is bounded. Fifth, they do not exhibit a vanishing state gradient: the gradient of a state w.r.t. a past state can have constant value one regardless of the time distance between the two states. Finally, we find empirical evidence that the favourable theoretical properties of MinMax RNCs are matched by their practical capabilities: they are able to perfectly solve a number of synthetic tasks, showing superior performance compared to the considered state-of-the-art recurrent neural networks; also, we train a MinMax RNC of 127M parameters on next-token prediction, and the obtained model shows competitive performance for its size, providing evidence of the potential of MinMax RNCs on real-world tasks.

State space models have shown strong potential to outperform Transformers, but their learning mechanisms remain poorly understood, particularly the conditions for successful parameter updates that preserve teacher information. Prior work attributes the difficulty of such updates to the vanishing gradient during backpropagation through time, in which error signals decay exponentially through repeated gradient multiplication. In this work, by expressing error signals explicitly as functions of inputs, we show that the conventional vanishing gradient framework is insufficient to explain the loss of information. Using this representation of error, we reveal that the memory of the input encoded in teacher information does not decay exponentially, and we analytically demonstrate that the loss of supervisory information cannot be alleviated through training. This result theoretically confirms the importance of the initial weights of SSMs and suggests that the recurrent layer does not require training. By performing experiments on both linear SSMs and a representative nonlinear SSM, including language modeling tasks, we confirm that appropriate initialization enables us to fix the recurrence, leading to more stable training of the entire network and higher performance than the conventional training scheme. Our results partially elucidate the learning mechanisms of SSMs and are expected to contribute to the development of improved RNN-based models.

Transformers have achieved remarkable success across a wide range of applications, and a growing body of work suggests that part of their strength comes from their ability to learn and execute algorithmic procedures. However, our understanding of how transformers learn such algorithms remains limited, especially in the presence of layer normalization (LN). In this work, we study principal component prediction as a concrete testbed for understanding the training dynamics of transformers with LN. We prove that a looped linear transformer with LN, trained by gradient descent, converges to a solution that implements the power method, with each self-attention layer performing one power iteration. Notably, the model is trained only for principal component prediction, rather than being explicitly supervised to implement the power method. Our finding thus reveals an ``algorithmic implicit bias'' of looped transformers with LN: principal-component prediction can in principle be achieved by many mechanisms, yet gradient descent selects one that realizes the power method. We further provide a concrete comparison between transformers with and without LN: even with layerwise guidance from power iterations, a transformer without LN cannot exactly learn the power method, whereas the corresponding transformer with LN can, leading to a provable performance gap in principal component prediction. Our results provide, to our knowledge, the first theoretical analysis of the training dynamics of looped and single-layer transformers with LN, and shed light on the role of LN in transformer models.

Ensemble sampling is a practically attractive approach to randomized exploration, but existing theoretical guarantees for linear bandits require ensembles much larger than what its practical motivation would suggest. In particular, the sharpest existing analysis achieves the ensemble complexity of $\Theta(d\log T)$, leaving a $\log T$ gap from the intrinsic $\Omega(d)$ ensemble-size barrier. We aim to narrow this gap by proposing an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially. This mechanism localizes the perturbation analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to $\Theta(d\log d+d\log\log T)$, while preserving the state-of-the-art $\tilde{\mathcal O}(d^{3/2}\sqrt T)$ regret for ensemble sampling with arbitrary bounded arm sets. We further show that, when the arm set is finite of cardinality $K$, the proposed algorithm achieves the sharper regret bound $\tilde{\mathcal{O}}(d\sqrt{T\log K})$. To the best of our knowledge, this is the first ensemble-sampling guarantee that simultaneously recovers both canonical regret scalings known for randomized linear bandit algorithms: the $\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ rate for arbitrary bounded arm sets and the $\tilde{\mathcal{O}}(d\sqrt{T\log K})$ rate for finite arm sets. The algorithm also admits an anytime implementation without resetting past data, and experiments show that it remains competitive with baselines while using substantially smaller ensembles.

Linear contextual bandit algorithms are typically built around pointwise optimism: the exploration bonus is chosen large enough to upper-bound the value of every action with high probability. We study an alternative principle of quasi-optimism, in which the index is deliberately allowed to be smaller than a valid confidence bound. We analyze the algorithmic framework, EQOL, that replaces the usual confidence-radius bonus with the capped quadratic bonus min(c₁,t ‖x‖²_{V_t⁻¹}, c₂,t ‖x‖_{V_t⁻¹}). This index is generally not optimistic, since its quadratic branch can be pointwise smaller than the OFUL bonus. We prove a general regret bound for arbitrary schedules (c₁,t, c₂,t), separating the exploration cost from the quasi-optimistic residual. With a single gap-agnostic tuning, EQOL recovers the high-probability minimax O(d√T) regret bound and, under a positive contextual margin, a uniform gap-dependent O(d²/Δ_min,T) bound. We also provide a geometric interpretation of EQOL through action-dependent ellipsoids, clarifying how quasi-optimism differs from simply shrinking a UCB bonus. Experiments on synthetic and real-data contextual bandit benchmarks show that EQOL substantially outperforms existing algorithms.

Many real-world applications require highly interpretable machine learning systems, particularly in high-stakes domains such as healthcare. A promising recent direction is the paradigm of Maximal Coding Rate Reduction (MCR$^2$), which seeks to characterize and preserve the low-dimensional structure underlying each class. However, we find that exhaustively preserving structural information is often unnecessary and can even be detrimental in supervised learning, especially under noisy and uncertain real-world conditions, as it may overly constrain the fitting flexibility of the model. In contrast, we propose a simple yet effective framework, termed SimCoding, which captures only minimal structural information for each class. Despite relying on substantially less structural information, SimCoding significantly improves the generalization ability and robustness of deep models. Extensive experiments across diverse benchmark datasets demonstrate the effectiveness of SimCoding. We further validate SimCoding on a challenging real-world application, Parkinson’s disease severity assessment from free-living human activity signals, where it consistently achieves strong robustness and outperforms competing methods. Moreover, SimCoding can be naturally extended to incremental learning scenarios, where it substantially alleviates catastrophic forgetting and consistently surpasses strong baselines.

When auditing machine learning models, human experts sequentially inspect model predictions and explanations, gradually building a mental model of the model’s behavior to uncover errors. This manual process is critical for safe deployment in high-stakes domains but fundamentally limited in scalability. In this work, we propose a novel method to simulate this human auditing behavior for automating the auditing process. We formalize auditing as a sequential decision-making problem, modeled as a Markov decision process. Our state representation summarizes the auditor’s accumulated knowledge of model predictions and feature usage. Building on this formalization, we solve the MDP using reinforcement learning, yielding RLAuditor, which learns to select informative test samples to efficiently uncover model errors. We further connect our formalization to Theory of Mind, showing that our state mirrors how human auditors build mental models: its update rule is equivalent to Bayesian belief revision and it converges to the model’s behavioral pattern at an interpretable rate. We validate our approach on multiple ML models and datasets across different data modalities. In a human subject study, we demonstrate that RLAuditor helps human auditors produce more accurate audit reports in less time.

We study how to choose a probability distribution, or lottery, over $m$ alternatives for $n$ agents when each agent's acceptable lotteries form an unknown linear halfspace of the simplex. The learner observes only binary accept/reject membership queries. Prior work asks whether there exists a lottery accepted by every agent; we study the relaxation that minimizes the number of agents who reject the lottery. We first show that this problem is APX-hard even when all halfspaces are explicitly known and scores are binary. We then give exact algorithms under additional structure: fixed $m$, and a margin condition under which an optimal lottery can be replaced by one supported on $\mathcal{O}(\log n/\gamma^2)$ alternatives. With limited queries, uniform sampling of agents gives additive population guarantees after recovering the sampled agents' normalized halfspaces. For arbitrary $m$, we give a polynomial-time LP based on a one-sided margin penalty and prove a population guarantee depending on the number of true violations and the number of agents near their thresholds. Finally, we prove a tight deterministic lower bound: without a stochastic link between queried and unqueried agents, querying only $K$ distinct agents cannot guarantee additive gap below $n-K$, and this gap is achievable.

Safe reinforcement learning (RL) commonly enforces expected-cost constraints, but such expectation safety may fail to control the probability of rare high-cost trajectories. Chance-constrained MDPs (CCMDPs) impose a stronger probability-level requirement, but are widely viewed as harder because the chance constraint is nonconvex and depends on the full trajectory rather than a Bellman-linear expectation. In this paper, we reveal that this computational difficulty does not imply a higher statistical price. In tabular discounted CCMDPs, we give a Bellman-certified model-based algorithm whose sample complexity matches the \emph{minimax optimal} primary dependence of classical CMDP learning, and prove a matching lower bound. Technically, our key idea is the \emph{Bellman distributional certificate}, which constructs a Bellman recursion for constraint violation probabilities before policy selection. The certificate can be reused across candidate policies, shifting concentration analysis from the number of possible policies to a finite Bellman certificate table. Building on this certificate, we establish high-probability safety and near-optimality guarantees for deterministic policy learning in discounted CCMDPs. To our knowledge, we also provide the first model-free sample complexity guarantee for stochastic policy learning in CCMDPs via variance-reduced policy gradient. Numerical experiments on synthetic CCMDPs and IEEE 14-bus energy-storage control benchmark illustrate the safety and behavior of the proposed algorithms.

Randomization is often used to compromise among fixed policies, classifiers, or interventions, but affected stakeholders may be unable or unwilling to report utilities over all alternatives. We study a weaker feedback model in which, for each proposed lottery, each stakeholder reports only whether it is acceptable. Unlike prior work focused on finding a unanimously acceptable lottery when one exists, we allow unanimity to be impossible and seek lotteries that minimize aggregate acceptability violations. We model each stakeholder's acceptable lotteries by an unknown linear threshold rule over the lottery simplex, and the learner may only ask accept/reject queries. Since binary labels do not reveal utility shortfalls, and such shortfalls are not comparable across stakeholders, we measure violation geometrically: the Euclidean distance, within the affine hull of the simplex, to the stakeholder's normalized acceptance hyperplane. These distances are aggregated using the power mean. Our results characterize exactly which boundary information can be learned from these queries. A deterministic algorithm uses $\mathcal{O}(nm\log(m/\varepsilon))$ queries to recover the normalized boundary whenever violation distances are identifiable from query answers. Otherwise, queries determine the acceptable face but not the rate at which violation grows away from it; this ambiguity is unavoidable. When no ambiguity arises, the aggregate violation objective can be optimized exactly. When it does, we optimize a convex worst-case upper bound objective based on distance to the learned acceptable set and prove an additive loss bound of $\sqrt{2}(|B|/n)^{1/p}$. We also prove structural properties of optimal lotteries, including a support-size bound of $n+1$, and give a limited-budget algorithm with additive-$\alpha$ guarantees. Synthetic experiments illustrate the resulting breadth-depth tradeoff and the effect of the power-mean parameter $p$ on violation distribution.

An extensive line of work studies fairness interventions for network embeddings, but less is known about their baseline behavior. In this work, we ask: how do baseline embeddings (without fairness interventions) produce disparate effects at the representation level? We analyze the asymptotic behavior of low-dimensional embeddings on stochastic block model (SBM) graphs, which encode both homophily and group structure. We characterize exact conditions under which embeddings cause information loss, showing that the amount of information loss depends directly on the graph’s density and assortativity. Notably, very different graphs can produce identical embeddings in the limit, and this non-invertibility disproportionately affects smaller and sparser communities. As a result, simple downstream tasks, such as link prediction, introduce higher error rates for these communities, helping explain disparities widely observed in practice.

While the approximation properties of single-layer Transformer architectures have been studied in recent works, a rigorous theoretical understanding of the multi-layer setting remains limited. In this work, we establish that multi-layer Transformers possess fundamentally different approximation capabilities from single-layer ones: for certain retrieval tasks, any single-layer Transformer requires least $\Omega (\varepsilon^{-k})$ parameters to achieve precision $\varepsilon$, where $k$ grows linearly with sequence length $T$, whereas a two-layer Transformer with a single head per layer achieves the same approximation precision with at most $O (\varepsilon^{-1})$ parameters. To understand this separation, we identify two structural mechanisms underlying multi-layer approximation. Specifically, softmax attention can only efficiently retrieve the token attaining the maximum attention score, incurring exponential-in-length parameter cost for $k$-th largest retrieval with $k \geq 2$. Moreover, the parameter cost of decoding coupled information scales with the size of the retrieved token set. Motivated by these findings, we propose **InfoFlow**, a framework for multi-layer Transformers. The framework tracks an information set of accessible input positions at each token and layer, assigning an explicit approximation rate to each mode of information propagation. This abstraction recovers known approximation bounds, remains consistent with experimental observations on trained networks, and yields concrete predictions in settings where direct theoretical analysis is currently intractable. Our results provide a principled framework for reasoning about the approximation efficiency of multi-layer Transformers.