NeurIPS 2026 Papers

We study nonconvex stochastic optimization under the Blum-Gladyshev ($\mathsf{BG}$-0) noise model, where the stochastic gradient variance grows quadratically with the distance from the initialization. We consider this problem under both standard smoothness and the symmetric generalized-smoothness framework, which captures objectives whose local curvature can scale with the gradient norm. We prove that normalized stochastic gradient descent with momentum, using only one stochastic gradient per iteration, converges under $\mathsf{BG}$-0 noise with oracle complexity $\mathcal{O}(\varepsilon^{-6})$. This rate holds both for standard smoothness and for $\alpha$-symmetric generalized smoothness, showing that generalized smoothness is rate-neutral for normalized momentum in this setting. We then study a variance-reduced normalized STORM method. Under mean-square smoothness and sharp initialization, the method achieves the minimax optimal $\mathcal{O}(\varepsilon^{-4})$ complexity, matching the lower bound. Under expected $\alpha$-symmetric generalized smoothness, the STORM recursion couples gradient-dependent smoothness with distance-dependent noise, leading to complexity $\mathcal{O}(\varepsilon^{-(4+\alpha)})$ for $\alpha \in (0,1)$ and $\mathcal{O}(\varepsilon^{-5})$ for $\alpha=1$. When the distance-growth parameter in the noise model vanishes, our guarantees recover the standard bounded-variance rates: $\mathcal{O}(\varepsilon^{-4})$ for momentum, $\mathcal{O}(\varepsilon^{-3})$ for variance reduction, and $\mathcal{O}(\varepsilon^{-2})$ in the deterministic case. To our knowledge, these are the first convergence guarantees for normalized methods in non-convex stochastic optimization under $\mathsf{BG}$-0 noise without bounded domains, increasing batch sizes, or explicit anchoring, covering both standard and generalized smoothness regimes.

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 problem of finding approximate envy-free allocations up to any $k$ goods ($\alpha$-EFkX), when agents have additive values over goods in a bundle. As our main result, we show that for any $k>2$, $\frac{k+1}{k+2}$-EFkX allocations exist for any number of agents, and can be computed in polynomial time, via an appropriate generalization of the 3PA algorithm of (Amanatidis et al., 2024). An immediate corollary of this result is that $3/4$-EF2X allocations exist for any number of agents; in contrast, $2/3$-EFX allocations are only known to exist for up to 7 agents. We improve this latter result by devising an algorithm that achieves $2/3$-EFX for 8 agents. We also consider EFkX graph orientations; we prove that such orientations do not always exist, and that deciding their existence is NP-complete, thereby generalizing the corresponding result of (Christodoulou et al., 2023) for $k=1$.

We study zeroth-order optimization of non-convex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order $O(1/T)$ rate and the zeroth-order $O(d/T)$ rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on nonconvex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.

This paper addresses the challenge of obtaining strong optimality guarantees in constrained nonsmooth nonconvex optimization under mild regularity conditions, namely local Lipschitz continuity and existence and continuity of directional derivatives. While standard methods typically ensure weak stationarity notions, achieving directional (d-)stationarity remains nontrivial. We show that a random direction exploration step is sufficient to attain d-stationarity. The proposed approach augments any base optimization method with a single exploration step that samples a direction and step size and accepts the candidate based on a function value comparison. The resulting scheme guarantees that all accumulation points are d-stationary almost surely, independently of the behavior of the underlying method. Moreover, it preserves convergence rates of the base method, as established for DCA and prox-linear-type schemes. The theoretical results are complemented by numerical experiments illustrating the effect and guarantees of the exploration step.

Neural network training can be viewed as a discrete-time dynamical system, suggesting that its optimisation trajectory can be learned and extrapolated to reduce the cost of repeated backpropagation. Motivated by Koopman operator theory, which represents nonlinear dynamics as linear evolution in a lifted space, we propose a training acceleration method based on augmented Koopman dynamics. Instead of approximating the evolution of parameters alone, our method lifts the training state to include both model parameters and optimiser-dependent internal states, enabling the learned operator to better capture the dynamics of modern optimisers with momentum or adaptive gradient statistics. We estimate a strided, multi-step Koopman operator from training snapshots and use matrix-vector multiplications to extrapolate future parameters and optimiser states, effectively bypassing an adaptive number of backpropagation steps. This formulation suppresses high-frequency stochastic fluctuations induced by mini-batch training and reduces the storage required for operator estimation. To improve robustness, we further introduce a safeguarding mechanism that prevents Koopman-extrapolated states from degrading performance relative to the most recent backpropagation iterate. The method can be integrated with standard optimisers, including Adam, AdamW, SGD with momentum, Adadelta, and other commonly used variants. Experiments across multiple optimisers show that the proposed approach significantly reduces both the number of backpropagation steps and the wall-clock training time required to reach a target accuracy, while maintaining, and in many cases improving, final model performance.

Modern vision--language models are trained with very different objectives: CLIP-style contrastive alignment, SigLIP-style match/no-match prediction, caption-style token generation (Flamingo, LLaVA), and latent-space prediction (VL-JEPA). Each has been claimed as best-in-class for its target task. Yet practitioners lack clear guidelines for choosing between them, and existing identifiability theory analyzes only the contrastive case. In this work, we unveil the core statistical mechanisms that distinguish each objective family using a unified spectral analysis. By leveraging closed-form solutions for the linearized losses under a latent structure in which modality-specific nuisances may spuriously carry shared semantic content, we characterize what each objective recovers from the data. We demonstrate that contrastive alignment, match/no-match prediction, and latent-space prediction collapse to the same cross-modal solution, while directed token-space generation recovers a different one. Our findings indicate that in scenarios where one modality is heavily contaminated by spurious nuisance, token-space generation is preferable because it imposes a strictly weaker, one-sided alignment condition. In scenarios where two modalities are both clean, retrieval is maximized by the latent-prediction objective whose target matches the query modality. These results clarify the trade-offs between the four objective families. We validate our theoretical predictions on numerical, controlled synthetic, and real (Flickr30k, COCO, CC3M) data.

In this work, we develop theoretical foundation for flow matching with neural-network–parameterized conditional velocity fields. We establish convergence guarantees for gradient descent in the over-parameterized 2-layered ReLU neural network regime. We derive generalization bounds for the conditional velocity-field matching objective. Building on these results, we provide Wasserstein-distance guarantees for the samples generated by the induced flow. Our analysis is based on generalization bound for multi-task representation learning with unbounded losses, which may be of independent interest beyond flow-based generative modeling. These theoretical results are validated through extensive experiments on both synthetic and real-world image benchmarks.

Scaling large language models (LLMs) requires tremendous computational resources, and recent advances in AI have gone hand in hand with massive amounts of capital expenditure. While it is established that scaling up LLMs reliably increases model quality (quantified in terms of loss or downstream evaluations), it is unclear how these quality improvements translate to potential revenue, and whether revenue increases would offset costs of larger-scale training and inference. In this work, we develop an economic model for characterizing the rational behavior of an LLM training firm by combining scaling laws with microeconomic theory. Under our model, LLM quality can be increased with more parameters and training tokens, leading to more potential adoption by consumers, who each have a quality threshold for using the LLM. On the other hand, additional parameters and training tokens both incur additional costs. We analyze the profit maximization problem for this model under compute-bound and data-bound regimes. In the compute-bound regime, optimal model size and token budget track hardware efficiency $E$ (FLOPs/dollar) at a near-linear rate; total training cost then scales sub-quadratically in $E$. Data efficiency improvements incentivize larger models and training expenditure. When we are limited to $D$ data, profit-optimal training expenditure scales as $D^2 / E$, i.e, increase with data and *decreases* with hardware efficiency (as well as data efficiency). Finally, we analyze practical trends in training expenditure: current trends in training expenditure are consistent with our most permissive model variants in the compute-bound regime, but are not profit-optimal in the data-bound regime or assuming hardware advances will stall. Overall, our results provide a theory of profit-optimal LLM training, providing a foundation for engaging critically with industry statements and supporting long-term economic decision making.

Spatial cognition requires stable neural manifolds of orientation and location that track self-motion and sensory cues. Continuous attractors provide a natural dynamical principle, but learning such mechanisms that form and control manifolds with theoretical guarantees remains difficult. We propose Spatial Energy Attractor Learning (SEAL), a theory of neurodynamics learning for spatial cognition, where continuous spatial representations arise as learned low-energy manifolds in Hopfield energy landscapes through population-level Fourier energy learning. For head-direction and grid-cell systems, Fourier energy landscapes yield ring and torus attractors with learned normal attraction and input-driven tangent transport. We prove that Fourier construction is a special case of a general Hopfield-compatible energy extension whose autonomous dynamics preserve energy descent and whose expressive energy families approximate target attractor energies and restoring fields. Experiments on HD and grid-cell populations show that the learned energies restore perturbed states to ring and torus manifolds, stabilize velocity-driven moving bumps across multiple input regimes, and induce continuous-attractor interactive structures with local excitation and surround inhibition. Together, these results provide a stable, learnable, and biologically interpretable energy-based account of continuous spatial representation.

We introduce the problem of *adversary-directed* online learning, in which the learner is aware of the set of instances in advance, and an adversary adaptively determines their ordering during the learning process. Surprisingly, this formulation has not been previously studied, perhaps due to its conceptual resemblance to the traditional adversarial online learning problem, despite related models, including the transductive, self-directed, and best-order, having been extensively explored. However, by utilizing novel techniques, we demonstrate that the landscape of adversary-directed online learning significantly diverges from that of traditional adversarial online learning. In the realizable setting, we establish a trichotomy of possible rates of the minimax number of mistakes. Specifically, for a learning horizon $\operatorname{T}$, the minimax number of mistakes can only be of the orders $\Theta(\operatorname{T})$, $\Theta(\log \operatorname{T})$, or $\Theta(1)$. To prove this, we introduce a new combinatorial complexity parameter, termed the perfect Littlestone dimension, whose finiteness distinguishes the $\Theta(\log \operatorname{T})$ rate from the $\Theta(\operatorname{T})$ rate. On the other hand, in the agnostic setting, we essentially show a dichotomy of possible rates of the minimax expected regret. In particular, if the learner plays for $\operatorname{T} \in \mathbb{N}$ rounds, its minimax expected regret can only be of the orders $\Theta(\operatorname{T})$, or $\widetilde{\Theta}(\sqrt{\operatorname{T}})$, which is also characterized by the finiteness of the perfect Littlestone dimension. Technically, a key ingredient in the proof of our $\mathcal{O}(\log \operatorname{T})$ and $\widetilde{\mathcal{O}}(\sqrt{\operatorname{T}})$ upper bounds is a novel online learning algorithm that leverages a new notion of shattering based on the perfect Littlestone dimension, which exploits the adaptive adversarial nature of the problem.

Self-attention has greatly contributed to the success of the widely used Transformer architecture by enabling learning from data with long-range dependencies. In an effort to improve performance, a gated attention model that leverages a gating mechanism within the multi-head self-attention has recently been proposed as a promising alternative. Gated attention has been empirically demonstrated to increase the expressiveness of low-rank mapping in standard attention and even to eliminate the attention sink phenomenon. Despite its efficacy, a clear theoretical understanding of gated attention's benefits remains lacking in the literature. To close this gap, we rigorously show that each entry in a gated attention matrix or a multi-head self-attention matrix can be written as a hierarchical mixture of experts. By recasting learning as an expert estimation problem, we demonstrate that gated attention is more sample-efficient than multi-head self-attention. In particular, while the former needs only a polynomial number of data points to estimate an expert, the latter requires exponentially many data points to achieve the same estimation error. Furthermore, our analysis also provides a theoretical justification for why gated attention yields higher performance when a gate is placed at the output of the scaled dot product attention or the value map rather than at other positions in the multi-head self-attention architecture.

We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1\}^n$ under uniform marginals in the model of \citet{KM25} where each input coordinate is independently flipped with probability $\sigma \in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\tilde{O}(n^{O(\log(1/\varepsilon)/\sigma)})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{\Omega(\log(1+\sigma/\varepsilon^2)/\sigma)}$. This complements the recent work of \citet{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.

Large language models successfully solve classic theory-of-mind tasks adapted from cognitive science, but the mechanisms underlying this ability remain unclear. Do they deploy circuitry specialized for reasoning about other minds, memorize common false-belief vignette structures and outputs, or rely on more domain-general computations? We investigate this question in Qwen2.5-14B-Instruct using causal mediation and representational similarity analyses across matched prompt sets that systematically vary an agent’s beliefs, the state of the physical world, and the correct answer. We identify a population of mid-layer attention heads that tracks divergence between an initial representation and the current state of the world. These heads are causally relevant regardless of whether the initial representation is an agent’s belief or a photograph, despite the photograph condition involving no agent or perspective-taking. A distinct population of later-layer heads retrieves the answer token. The two populations are functionally dissociable yet combine compositionally. Together, these findings argue against both mentalizing-specific and memorization accounts, suggesting instead that LLMs solve classic false-belief problems by reusing a domain-general mechanism for detecting divergence between representations and reality.

Inverse Reinforcement Learning (IRL) is classically solved using Lagrangian optimization, by jointly optimizing a primal-dual problem with gradient descent to obtain the optimal reward function parameters and corresponding optimal policy. While this algorithmic view of IRL has been highly influential, gradient-based reward updates only paint a partial picture, largely ignoring the geometry of the problem in occupancy space. In this paper, we present an occupancy-space view of reward updates in IRL. We leverage the insight that both the optimal solution and its geometry in occupancy space are known, and show that the geometry along the e-geodesic (straight line in occupancy space) toward the optimal occupancy directly affects the gradient of the IRL dual problem in reward parameter space. This perspective naturally suggests preconditioning the dual gradient with the average Fisher information along the occupancy trajectory. We show that this preconditioned gradient is just a convex interpolation of the old reward and a new target reward, yielding efficient natural-gradient-style updates with little additional computational overhead. We then analyse these occupancy-space reward updates from a Mirror Descent (MD) perspective, and show that policy search over the resulting rewards induces approximate entropic MD on the policy. Finally, we conclude with convergence results of such geometry-aware IRL algorithms.

Decentralized stochastic minimax optimization has recently attracted significant attention due to its applications in machine learning. However, existing state-of-the-art methods use learning rates of different scales for the primal and dual variables, making them difficult to tune in practice. To address this problem, this paper proposes a novel doubly smoothed decentralized stochastic minimax algorithm. Specifically, in terms of algorithm design, we update both the primal and dual variables using smoothed gradients and introduce novel approaches to handle the computation and communication of the auxiliary variables introduced by the smoothing technique. On the theoretical side, for nonconvex-PL problems, our convergence analysis reveals that the learning rates for the primal and dual variables are of the same scale. Moreover, the order of the condition number in our convergence rate is improved to $O(\kappa^{3/2})$. To the best of our knowledge, this is the first time it has been improved to such a favorable order. Finally, extensive experimental results validate the effectiveness of our algorithm.

\emph{Scaling} has been the central driver of progress in modern AI, yet data curation remains an exception: it still relies on manual heuristics rather than systematic, scalable methods. In practice, data recipes (e.g., filter thresholds, deduplication strength, domain mixing ratios) are determined through many small-scale ablation training runs. This work demonstrates that the performance of the best-discovered recipe improves \emph{predictably}--as a \emph{power law}--in the number of such ablation runs. Theoretically, the power-law form arises naturally from regret bounds in zero-order optimization theory. Empirically, we validate it across diverse training stages, including pretraining, supervised fine-tuning, preference optimization, and reinforcement learning. Building on this finding, we derive a principled approach to \emph{data quality--quantity tradeoff} under a fixed compute budget, yielding a Pareto frontier that dominates standard heuristic pipelines (e.g., DCLM). Together, this work provides a general framework for scaling data-curation compute, establishing it as a new axis alongside the well-studied pretraining and test-time scaling.