NeurIPS 2026 论文列表

Deep learning systems are known to exhibit *implicit regularization* (alt. *implicit bias*), favoring simple solutions instead of merely minimizing the loss function. In some cases, we can analytically derive the implicit regularization -- connecting it to an equivalent penalty that augments the learning objective. However, modern deep learning systems are complex, carrying modifications to the training procedure and architecture (e.g. early stopping, minibatching, dropout) whose effects are not always directly interpretable. Although estimating the resulting implicit regularization could aid theorists in algorithm design and practitioners in interpreting their hyperparameter choices, this problem has received little direct attention. It is also tractable: regularization makes weight updates deviate from loss gradients, promising a signal for identifying implicit bias. Here we provide gradient matching methods that can be used to empirically estimate the implicit regularization. Our method works on networks with known regularization, recovering popular explicit penalties like $\ell_1$ and $\ell_2$. It also replicates known implicit effects, like the quadratic weight penalty induced by early stopping in gradient descent, demonstrating that it can be used to test theories of implicit regularization. Crucially, because our method is empirical, it can handle implicit regularization in arbitrary networks. We demonstrate this use by characterizing the effects of dropout in deep networks, showing implicit $\ell_2$ effects in this popular method. Our work shows that practitioners can use gradient matching to understand regularization in networks with implicit biases that are too complicated to derive analytically.

Online Convex Optimization with memory and time-varying constraints (COCO-M) is a recently-introduced framework that captures the dynamics of stateful online learning and non-stochastic control with budget constraints. Despite its expressive power, COCO-M remains largely understudied. In this work, we tackle this problem in its full scale, providing an optimistic algorithm that incorporates untrusted predictions to tame universal dynamic regret and cumulative constraint violation. Our analysis leverages a potent reduction from memory to delay and treats state-dependent gradients as delayed feedback. We establish the first bounds that adapt to both environment non-stationarity (path length $P_T$) and prediction accuracy, while lifting previous restrictive assumptions such as functional separability. En route to these results, we derive findings of independent interest for the memory-to-delay reduction, and for delayed OCO with time-varying constraints. The proposed framework ensures sublinear worst-case guarantees that improve with prediction accuracy, reaching \(\mathcal O(1)\) regret under perfect predictions, with cumulative constraint violation (CCV) $\mathcal O(\sqrt{T})$ for unknown $P_T$ and $\mathcal O(\log T)$ for known $P_T$, while recovering the optimal COCO rates when memory disappears.

Many bandit systems are deployed with offline historical data, such as past logs from earlier policies. By using these data, one can reduce the amount of online exploration needed early in learning. When the offline and online environments differ, such data can be biased for the online problem. For linear (contextual) bandits, this bias is directional: offline data may be informative in some feature directions and misleading in others. However, prior work typically controls this gap through a known Euclidean bound on the model parameters, which we prove is too coarse to separate easy and hard offline-to-online instances from offline data alone. To address this challenge, we introduce a directional bias certificate $(M_{\mathrm{bias}},\rho)$ that measures the offline-to-online gap through an $M_{\mathrm{bias}}$-induced norm and assigns different bias budgets to different directions. Building on this certificate, we propose \emph{Ellipsoidal-MINUCB}, which augments the online learning with an offline-pooled branch that safely exploits historical data. When the certificate is known, we show that the algorithm matches the standard SupLinUCB rate in the worst case and improves when offline coverage aligns with low-bias directions. When the certificate is unknown, we estimate it adaptively from offline and accumulated online data and establish a corresponding regret guarantee. Numerical experiments support the theory and show gains in aligned regimes.

Score-based diffusion models are typically trained by minimizing the $L^2$ score matching error, and standard theoretical analyses rely on this quantity to bound the sampling discrepancy between the learned and target distributions. We show the $L^2$ score error is not the right intrinsic measure of marginal distributional quality: a learned diffusion model can incur arbitrarily large $L^2$ score error while perfectly matching the target distribution. By decomposing score errors into a gradient and a solenoidal component (a Helmholtz-Hodge decomposition), we identify the geometric reason behind this: only the gradient component enters the marginal Fokker-Planck dynamics, while the solenoidal component is structurally invisible. We make this precise in three results. First, building on the corrected geometry, we prove an impossibility result: no monotone function of the $L^2$ score error can uniformly lower bound any divergence between the learned and target distributions. Second, we derive an upper bound on the Kullback-Leibler divergence that depends only on the observable gradient component of the error, tightening the standard Girsanov bound and identifying its looseness as the cost of operating on path-space rather than marginal-space dynamics. Third, we give a tractable estimator of the gradient component via a dual Sobolev identity, which is shown to empirically correlate substantially better with sample quality than the full $L^2$ error.

Cross-entropy (CE) loss is central to deep learning, but existing theory often relies on simplifications—such as squared loss or convex models—that miss key aspects of CE optimization. In this work, we study multi-class CE dynamics using a two-layer linear network with orthogonal inputs, the simplest non-convex setting where the CE implicit bias remains unresolved. This coincides with the unconstrained features model used to study neural collapse (NC). Our analysis is based on a key observation: Hadamard initialization diagonalizes the softmax operator. This allows us to extend the spectral initialization framework that Saxe et al. (2013, 2019) developed for squared loss. We prove convergence to NC under spectral CE training and give the first finite-time analysis in this setting via an explicit Lyapunov function that decreases monotonically to NC despite spurious critical points. We further identify CE-specific phenomena absent under squared loss—coupling, non-monotonic convergence, qualitative dependence on the number of classes, and exponential slowdowns. We also characterize the role of network width and show empirically that spectral dynamics qualitatively model small random initialization.

The learning dynamics of decentralized coupled representation learning can be formulated as a non-autonomous stochastic dynamical system, yet the macroscopic behavior of the resulting system on continuous manifolds remains poorly understood. We establish three theoretical results for such coupled slow-fast dynamics. First, under a standard random geometric graph scaling regime, we prove that the infinitesimal generator of the discrete Markov process converges to the generator of an overdamped Langevin diffusion for every $f \in C^3(\mathcal{M})$. Second, under timescale separation, the stochastic parameter dynamics converge to a deterministic averaged flow that admits a row-orthogonality Lyapunov function, controlling row-space degeneracy and ruling out parameter divergence. Third, under a spectral gap condition, the row space of the averaged parameter trajectory converges to the principal eigenspace of the induced covariance matrix. Together, these results give a stochastic-approximation limit theory for the coupled regime in which Markovian sampling and local subspace learning co-evolve, showing that memoryless local interactions can induce a stable and structured macroscopic limit.

Data-free methods for analysing and understanding the layers of neural networks offer many metrics for quantifying notions of `strong' versus `weak' layers, with the promise of increased interpretability. In particular, random matrix theory (RMT) offers data-free metrics that claim predictive power over the quality of pre-trained models at a layerwise precision and the ability to identify model pathologies, indicating a unique relationship with generalisation. As a result, metrics from RMT are championed for pre-training optimisation strategies and post-training compression. We establish that RMT-based metrics are unrelated to performance or training by showing that functionally indistinguishable reparametrisations of a pre-trained model can have arbitrary metrics. We show this across a range of architectures and scales. To create functionally indistinguishable reparametrisations, we exploit the well-established phenomenon of criticality: some layers can be re-initialised or re-randomised without affecting the functional behaviour of the model -- they are called robust -- while others cannot -- they are called critical. Re-initialising or re-randomising robust layers provides functionally indistinguishable reparametrisations for which RMT-based metrics are arbitrary. Moreover, we show that relationships between metrics offered by RMT are spuriously related to generalisation. We conclude by showing that if many pre-trained models have data-free metrics in a `good' range, it is, in part, dependent on model initialisation.

In Euclidean online convex optimization, first-order and full-information feedback share the minimax regret \(\Theta(DL\sqrt{T})\) over \(T\) rounds, as convex losses can be replaced by their linearizations. On Riemannian manifolds this reduction fails, because the corresponding first-order surrogate of a geodesically convex loss is generally not geodesically convex; we show that this failure has provable consequences. For online convex optimization on Hadamard manifolds with sectional curvature bounded below by \(\kappa<0\) and feasible diameter \(D\), we construct hard hyperbolic-space instances yielding first-order regret lower bounds at the scale \( DL\sqrt{\zeta\, T}, \) where \( \zeta=\sqrt{|\kappa|}D/\tanh(\sqrt{|\kappa|}D) \) is the curvature--diameter factor. Our first lower bound applies to all (possibly randomized) first-order algorithms satisfying a natural geometric-span condition, holding almost surely over the algorithm's internal randomness. Our second lower bound removes the geometric-span restriction for deterministic first-order algorithms, provided the feasible diameter satisfies \(D=\Omega(\log T)\); the proof rests on a new construction that confines the hidden comparator to a single horosphere in hyperbolic space. Combined with existing curvature-free full-information upper bounds, these results yield a feedback-model separation on Hadamard manifolds: full-information algorithms attain \(O(DL\sqrt{T})\) regret, yet the additional \(\sqrt{\zeta}\) factor is unavoidable for first-order feedback whenever either the geometric-span condition holds or the algorithm is deterministic.

We introduce a framework that models constrained MDPs subject to trajectory-wise safety constraints. These constraints require that expected future costs remain below zero conditioned to any possible trajectory---not merely in expectation from the initial state. This captures stronger and more realistic safety guarantees, which are crucial in high-stakes applications. We characterize the structure of optimal policies, and show that Markovian policies are in general suboptimal. Moreover, we show that computing approximately-safe optimal policies is NP-hard when the number of constraints can be arbitrarily large. Despite all these challenges, we provide an exact algorithmic characterization of optimal history-dependent (non-Markovian) policies, by exploiting a suitable recursive formulation of the sets of reachable reward-cost values. Then, we employ it to design a polynomial-time approximation algorithm that computes approximately-safe optimal policies by dynamic programming, when assuming a constant number of constraints.

Instantaneous Quantum Polynomial Quantum Circuit Born Machines (IQP-QCBMs) have been proposed as quantum generative models that combine a classically tractable training objective—based on the maximum mean discrepancy (MMD)—with a potential quantum advantage motivated by sampling-complexity arguments. While recent works have explored this model across various application domains, fundamental questions remain: does the model suffer from exponentially vanishing loss gradients, known as the barren plateau problem—a pervasive obstacle in quantum machine learning—and how do regimes of trainability relate to regimes of possible quantum advantage? Here, we address both questions analytically. To study trainability, we derive closed-form expressions for the variances of the partial derivatives of the MMD loss function and establish general upper and lower bounds. We explicitly characterize how trainability depends on the generator set and the spectrum of the chosen kernel, identifying regimes in which low-weight kernels avoid exponential gradient suppression under structured topologies. Regarding potential quantum advantage, we reformulate the anti-concentration property in terms of the same generator-set quantities that govern trainability, enabling a unified analysis. We show that sparse IQP architectures can produce classically intractable output distributions while simultaneously remaining trainable, at least at lower-weight frequencies. Our analytical results corroborate the numerical observations of prior work and provides principled guidelines for designing scalable IQP-QCBM architectures.

Algorithmic complexity measures the intrinsic structure (or randomness) of strings. Kolmogorov-Chaitin-Solomonoff (KCS) complexity is the length of the shortest program that can output a string and halt over all possible programs; due to this reason it is uncomputable. Estimating the algorithmic probability of strings using simulations of finite Turing machines is one way of obtaining tight estimations of KCS complexity of strings. For two dimensional objects, this is currently doable only for binary strings using the block decomposition method (BDM). In this work, we present the quantized block decomposition (QuBD) method to extend the estimation of algorithmic complexity to any $k$-ary objects such as the weights of deep neural networks. We show theoretically that the proposed QuBD method yields better KCS complexity estimations than BDM that relies on binarization. We further study how algorithmic complexity interacts with learning in deep neural networks by tracking the evolution of weights during training. Using a variety of experiments we show that algorithmic complexity decreases as models learn, it correlates with generalization performance and can be used as a diagnostic measure to perform model compression.

The attention mechanism in Transformers links queries, keys, and values through a sequence of computations, while the principles that constrain its form remain unclear. This paper examines attention under natural requirements that formalize basic properties of attention computation as transformations between representation spaces, and asks which forms of attention computation are admissible. We show that similarity computation, score-to-weight mapping, and value aggregation are unified by dual structures induced by convex potential functions and their Legendre transforms. In particular, the standard inner-product score is recovered as a limiting case of a potential-based score, the score-to-weight map must take a gradient-map form under structural requirements on attention normalization, and the value-aggregation rule must take a dual-coordinate barycentric form under structural requirements on representative-point aggregation. These results show that the standard components of attention are structurally constrained by the underlying dual structure, while the choice of potentials provides explicit degrees of freedom for understanding and modifying attention mechanisms.

Many prediction problems involve a hidden predictive state: a latent task, environment, rule, or data-generating mechanism that changes the query-optimal act. For a fixed query, recovering the full hidden predictive state is often stronger than necessary. The relevant target is the Bayes-act distinction among hidden predictive states that preserves oracle-gain adaptation. This question is central for in-context learning (ICL): a prompt may reveal part of an unseen task or rule, but an ICL system needs only to recover the prediction-relevant quotient state label for the query. We formalize this target through the canonical predictive quotient (CPQ), a problem-relative Bayes-act quotient of hidden predictive states. The theory characterizes the value of adaptation, the quotient that preserves full oracle gain, the sharp zero/positive-gain boundary, and a Bayes barrier showing why context-only prediction cannot recover a positive oracle gain at the risk level. We give two exact examples. A finite-state example makes the quotient structure, sharp positivity boundary, and a strict-loss mechanism explicit. A linear-Gaussian prior-family witness gives closed forms for a collapsed Gaussian baseline and a state-aware oracle, a restricted zero-gain boundary, and an exact prediction-level disagreement identity for the restricted gain. Together, the results give a decision-theoretic target for ICL: not full latent complexity, but the prediction-relevant quotient state label. We support the theory with exact checks, realized bridge experiments over prediction-relevant quotient state labels, and external validity tests on released pretrained in-context predictors.

The increasing prevalence of preference-based learning, particularly for machine learning models interacting with human users, gives rise to scenarios where the model's decision should cater to the preferences of a number of users. Due to the inherent misalignments in such preferences, it is natural to seek a fair decision-making paradigm. Motivated by that, we pose the problem of fair multi-user dueling bandit, where each user's preferences over pairs of actions are encoded by a preference matrix unknown to the agent. We design a Nash social welfare objective based on the Borda scores of the individual user preferences. The notion of the Borda score measures the average likelihood of an action being preferred over the other actions, and importantly, it does not require the existence of a completely dominant action. Considering online learning in this general setting, we construct hard instances and establish a minimax lower bound on the achievable regret. We also design an explore-then-commit algorithm and derive an upper bound on its worst-case regret. Furthermore, we formulate a fair multi-user generalized linear dueling bandit to enable modeling large action spaces, which typically necessitate a structured representation. In this setting, too, we establish a lower bound on regret and an upper bound on regret for a proposed explore-then-commit algorithm.

We study an endogenous nonstationary stochastic bandit problem with latent linear dynamics, where actions affect both immediate rewards and the future evolution of an unobserved latent state. Rewards are bilinear in the current action and latent state, inducing history-dependent rewards and a nontrivial long-horizon planning problem. The existing explore-then-commit approach (Choi et al., 2026) achieves $\tilde{\mathcal{O}}(T^{2/3})$ regret by uniformly exploring to estimate the latent dynamics and then committing to an optimized open-loop action sequence. We show that this rate can be improved via adaptive block-level optimism. Our key step is a cyclic approximation: under stable dynamics, the infinite-memory reward process can be truncated, and the open-loop benchmark can be approximated by optimizing a finite-memory block-level proxy. Building on this reduction, we propose a UCB-based block algorithm that maintains confidence sets for the truncated dynamics parameters and selects blocks optimistically. We prove a regret bound of order $\tilde{\mathcal{O}}(\sqrt T)$, significantly improving over the previous $\tilde{\mathcal{O}}(T^{2/3})$ guarantee for the same model. To the best of our knowledge, this is the first $\tilde{\mathcal{O}}(\sqrt T)$ regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.

We study \emph{bilinear matching bandits}, an online sequential decision problem in which at each round a learner assigns $M$ users to $N$ items via an injective matching $\pi:[M]\hookrightarrow[N]$ and observes semi-bandit feedback with bilinear mean reward $\mathbf{x}_i^\top \mathbf{\Theta}^\star \mathbf{y}_{\pi(i)}$, where the parameter $\mathbf{\Theta}^\star \in \mathbb{R}^{d_1 \times d_2}$ is unknown. We propose \textsc{HybridRRD}, a hybrid algorithm that combines high-width elimination with a row-wise regularized design sampler over the fractional matching polytope. Without assuming $\mathbf{\Theta}^\star$ is low-rank, \textsc{HybridRRD} achieves a high-probability regret bound of $\widetilde{O} (d_2 \sqrt{d_1MT} + Md_1 d_2)$, suppressing problem-scale constants. This improves the leading dimension dependence from $d_1d_2$ to $d_2\sqrt{d_1}$ over the standard Kronecker-linearized contextual combinatorial semi-bandit baseline. We further prove a minimax lower bound of $\Omega(d_2 \sqrt{d_1 M T})$ in a large-item regime, matching the leading regret term up to logarithmic factors. Numerical experiments show that \textsc{HybridRRD} performs favorably against Kronecker-linearized baselines.

We study the best arm identification problem in a novel non-stationary environment that we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbol{\Delta}$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ($\mathsf{ISM}$). Assuming means bounded by $U$ and $\sigma^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $\delta$-correct and to enjoy a sample complexity bound of $K (\sigma^2 + U^2) \Delta_{\min}^{-2} \ln \frac{1}{\delta}$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

Training powerful AI systems to exhibit desired behaviors hinges on the ability to provide accurate human supervision on increasingly complex tasks. A promising approach to this problem is to amplify human judgement by leveraging the power of two competing AIs in a debate about the correct solution to a given problem. Prior theoretical work has provided a complexity-theoretic formalization of AI debate, and posed the problem of designing protocols for AI debate that guarantee the correctness of human judgements for as complex a class of problems as possible. Recursive debates, in which debaters decompose a complex problem into simpler subproblems, hold promise for growing the class of problems that can be accurately judged in a debate. However, existing protocols for recursive debate run into the *obfuscated arguments problem*: a dishonest debater can use a computationally efficient strategy that forces an honest opponent to solve a computationally intractable problem to win. We mitigate this problem with a new recursive debate protocol that, under certain stability assumptions, ensures that an honest debater can win with a strategy requiring computational efficiency comparable to their opponent.

We study the fundamental and timely problem of learning long sequences in autoregressive modeling and next-token prediction under model misspecification, measured by the joint Kullback--Leibler (KL) divergence. Our goal is to characterize how the sequence horizon \(H\) affects both approximation and estimation errors in this joint-distribution, sequence-level regime. By establishing matching upper and lower bounds, we provide, to our knowledge, the first complete characterization of long-horizon error behavior under the natural joint KL objective, with improved rates and optimality justification relative to existing work. On the approximation side, we show that joint KL admits a horizon-free approximation factor, in sharp contrast to Hellinger-based analyses that exhibit an \(\Omega(H)\) dependence for computationally efficient methods; this isolates the choice of divergence as the source of approximation amplification. On the estimation side, we prove a fundamental information-theoretic lower bound of order \(\Omega(H)\) that holds for both decomposable policy classes and fully shared policies, matching the \(\widetilde O(H)\) upper bounds achieved by computationally efficient algorithms. Our analysis clarifies the landscape of recent autoregressive learning results by aligning the log-loss training objective, the sequence-level evaluation metric, and the approximation metric through a sharp joint-KL oracle theory. We further show that these joint-KL guarantees imply policy learning regret bounds at rates matching prior imitation learning literature.