NeurIPS 2026 论文列表

This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two-player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an *optimistic skew-gradient descent* with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on *uniform* convergence rates for OMWU. On the one hand, we prove *constant lower bounds* on the uniform *best-iterate* convergence rate in KL divergence and Total Variation distance from Nash. On the other hand, we establish for the $2\times 2$ setting a new $\widetilde O(T^{-1/2})$ best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.

Template tasks have emerged as a clean testbed for asking whether transformers reason with abstract symbols rather than concrete token names. We study the fixed-label classification version of this problem, where train and test examples share latent templates but may use disjoint vocabularies. Unlike next-token prediction, the model need not emit unseen symbols; it must learn a decision rule invariant to symbol renaming. We analyze regularized kernel logistic classification in the transformer-kernel regime. Our main result decomposes the learned predictor into an ideal template-level classifier and a finite-sample perturbation caused by accidental token overlaps in the training data. We encode these overlaps by a colored collision graph and prove high-probability margin-transfer guarantees for fresh-symbol classification. This perspective extends template-based analyses to logistic classification and refines scalar diversity conditions: vocabulary size controls the average rate of collisions, but collision geometry controls whether the ideal classification margin is preserved. More broadly, the same perturbation framework applies to abstraction-augmented inputs, yielding a general margin-versus-collision criterion for identifying when prompting strategies improve fresh-symbol generalization. Synthetic template experiments illustrate the predicted roles of regularization, sample size, and transformer-kernel structure.

In this work, we introduce a novel training-free encoding framework, dubbed **XShapeEnc**, that encodes an arbitrary spatially grounded 2D geometric shape into a compact representation exhibiting five favorable properties, including invertibility, adaptivity, generality and controllability. Specifically, a 2D spatially grounded geometric shape is decomposed into its normalized geometry within the unit disk and its pose vector, where the pose is further transformed into a harmonic pose field that also lies within the unit disk. A set of orthogonal Zernike basis is constructed to encode shape geometry and pose either independently or jointly, with controllable relative emphasis on shape geometry or shape pose. We demonstrate the theoretical validity, efficiency, discriminability, and wide applicability of **XShapeEnc** via extensive analysis and experiments across a wide range of shape-aware tasks and our self-curated XShapeCorpus dataset. We envision **XShapeEnc** as a foundational tool for research beyond one-dimensional sequential data and data-driven, learning-based encoding paradigms, paving the way for a unified spatial encoding framework for frontier 2D spatial intelligence.

Machine learning models, particularly large foundation models, are increasingly evaluated along multiple axes that are relevant for their usage. In addition to accuracy measures appropriate for the specific task of interest, measures capturing safety, calibration and fairness properties are often of interest. The classical approach to these problems assumes that the test set has been held out from the training process, an assumption that is increasingly harder to justify for large foundation models. In this work, we formalize a notion of evaluability without this assumption, and ask if it is feasible to evaluate black-box models in settings where our test samples may have been used during training. We study this problem under different settings, capturing different levels of access to the model. We first study the natural setting, where the evaluator only looks at the output of the model on the test set. We fully characterize the class of distributions where accurate evaluation is possible, and show tight upper and lower bounds on the sample complexity of evaluation. Our results show that black-box evaluation in this set up is feasible if and only if the distribution is close to being small support. We then consider evaluation algorithms that can query the model on additional inputs and demonstrate connections to self-correctors studied in program testing. Using these, we show that a small amount of query access can increase the power of the evaluator for natural distributions and concept classes.

We design the first regret guarantees for robust dynamic pricing which decouples the dependence on the corruption $C$ and the time horizon $T$. In dynamic pricing, a seller with unlimited supply of a good interacts with a stream of buyers over $T$ rounds, with the goal of maximizing revenue. At each round $t$, the seller posts a price $p_t$, and the buyer purchases the good only if their unknown valuation $v^\star$ exceeds this price. The seller observes only the binary feedback $\mathbb{I}[p_t \leq v^\star]$, indicating whether a sale occurred. In the robust pricing setting, a malicious adversary is allowed to corrupt this feedback in at most $C$ rounds. Even if the learner knows the corruption $C$, the best known regret bound is $\mathcal{O}(C\log\log T)$ by Gupta et al. [2025]. They left as an open problem to "decouple'' the dependence on $C$ and $T$. In this work, we resolve this open problem. In particular, we develop a robust variant of binary search that achieves regret $\mathcal{O}(C+\log T)$ when the corruption $C$ is known and $\mathcal{O}(C+\log^2 T)$ when the corruption is unknown.

We develop a framework for analyzing parameter symmetries in deep ReLU networks and obtain a complete characterization of the generic parameter fibers for three-layer bottleneck architectures. Our approach provides explicit semi-algebraic descriptions of these fibers and yields a polynomial time algorithm for deciding functional equivalence of two parameters. The symmetries include discrete and continuous transformations arising from layer composition, and depend on whether deeper layers hide or preserve geometric structure from preceding layers. Finally, we show that some of these symmetries induce local conservation laws along gradient flow, while others do not.

We study dynamic pricing where a seller repeatedly interacts with a strategic, non-myopic buyer who has a fixed private valuation and discounts future utility. Prior work focused exclusively on posted-price mechanisms, where the seller gives a take-it-or-leave-it offer. For our first result, we show that menu mechanisms consisting of allocation-payment achieve $O(T_\gamma \log T_\gamma)$ regret, where $T_\gamma$ is the buyer's effective discounted time horizon. We also establish a $\Omega(T_\gamma)$ lower bound, demonstrating the bound is tight up to $\log$ factors. Considering the geometric discounting buyer with a constant discount factor, our bound is $O(1)$, while prior bounds using posted-price mechanisms incur an unavoidable $\Omega(\log\log T)$ factor in regret. Our second contribution is more conceptual in nature. The problem of dynamic pricing sits at the intersection of two paradigms: learning with strategic agents in computer science / machine learning and revelation-principle-based mechanism design in economics, yet their relationship has remained unclear. We establish a fundamental equivalence: indirect learning-based mechanisms and direct revelation mechanisms achieve identical optimal regret. The adaptive, data-driven algorithms of online learning and explicit type elicitation are two languages towards solving the same problem.

Sortition is the practice of delegating public decision-making to randomly selected panels. Recently, it has gained momentum worldwide through its use in citizens' assemblies, sparking growing interest within the computer science community. One key appeal of sortition is that random panels tend to be more _representative_ of the population than elected committees or parliaments. Our main conceptual contribution is a novel definition of representative panels, based on the Wasserstein distance from statistical learning theory. Using this definition, we develop a framework for analyzing the _panel complexity_ problem—determining the required panel size to ensure desirable properties. We focus on three key desiderata: (1) that efficiency at the panel level extends to the whole population, measured by social welfare; (2) that fairness guarantees for the panel translate to fairness for the population, captured by the core; and (3) that the probability of an outlier panel, for which the decision significantly deviates from the optimal one, remains low. We establish near-tight panel complexity guarantees for these desiderata across two fundamental social choice settings: facility location and participatory budgeting.

In this paper, we investigate the long-run behavior of discounted regularized learning with stochastic gradient feedback in general, non-concave games. Specifically, we focus on a family of implicitly regularized exponential / multiplicative weight update schemes, and we seek to determine which actions\textemdash or, more generally, which recurrent patterns of play\textemdash are more likely to arise in the long run. We approach this question through the lens of large deviations theory and randomly perturbed dynamical systems, and we obtain a precise characterization of the distribution of the process: in the long run, it follows a Boltzmann-Gibbs law with temperature equal to the method's step-size, and energy levels determined by the game and the statistics of the noise. Concretely, we show that the distribution of play concentrates exponentially around the dynamics' *internally chain transitive* (ICT) sets - i.e., irreducible invariant sets containing no smaller attractors - and the probability of visiting such a set depends exponentially on its energy. As a result, unstable ICT sets are exponentially less likely to be visited than stable ones, and the sequence of play is exponentially concentrated around the problem's ``ground state'', where energy is minimized. In this manner, learning acts as a selection mechanism: with exponentially high probability, the ground state is the only outcome observed in the long run, even in the presence of multiple equilibria and other attractors.

AI alignment and participatory design motivate a new democratic design problem: how to collectively choose a _decision rule to use repeatedly_. We study this problem for _linear ranking rules_, which repeatedly rank items $x_j$ within batches $X=(x_1,\dots,x_m)\in(\mathbb{R}^d)^m$, where each item's ranking is dictated by its score $\langle \theta^{\ast},x_j\rangle$ according to a fixed scoring vector $\theta^{\ast}$. Given voters' preferred scoring vectors $\theta^{(1)},\dots,\theta^{(n)}$ and their population fractions $\alpha^{(1)},\dots,\alpha^{(n)}$, we ask how to choose a collective vector $\theta^{\ast}$ satisfying _individual proportionality (IP)_: every voter type $i$ should agree with the resulting rankings to an $\alpha^{(i)}$-proportional degree, either on average over time (_long-run IP_) or even within each batch (_per-batch IP_). The default rule, the arithmetic mean of the $\theta^{(i)}$, has been shown to be severely majoritarian; more generally, it is not clear that _any_ fixed linear rule can balance many voters' disparate opinions. Our main result is that, surprisingly, there _is_ a simple rule that does satisfy long-run IP: the _angular mean_, the spherical analog of the arithmetic mean. We then show that exact per-batch IP is impossible for fixed linear rules, but that the gap between per-batch and long-run IP shrinks quickly with batch size. Experiments on three real-world preference datasets show that all rules perform similarly when voters' preferences are homogeneous, while the angular mean substantially improves proportionality in high-disagreement regimes.

We study equilibrium learning in discretized Bayesian games, focusing on first-price auctions as a testbed for gradient-based learning dynamics under private information. While the symmetric independent private values model admits a unique Bayesian correlated equilibrium (BCE) in the continuous limit, standard convergence guarantees for gradient-based learners do not apply: classical no-regret theory predicts convergence only to Bayesian coarse correlated equilibria (BCCE), which can remain large and far from the competitive equilibrium even under fine discretizations. To bridge this gap, we introduce the notion of Bayesian semicoarse correlated equilibrium (BSCCE), an equilibrium concept that refines BCCE by restricting deviations to probability-preserving transformations consistent with projected gradient dynamics. We provide a linear programming characterization of BSCCE with polynomially many variables and constraints and establish the inclusion hierarchy $BCE \subseteq BSCCE \subseteq BCCE$. Our main finding is that the BSCCE set contracts in many cases as the discretization of the Bayesian game is refined. Even with priors for which BCCE fails to concentrate, the diameter of the BSCCE polytope shrinks toward zero, indicating convergence to the unique continuous-game Bayes-Nash equilibrium. These results provide a principled explanation for the observed robustness of gradient-based learning in discretized Bayesian games, showing that these dynamics select a smaller equilibrium set than standard no-regret theory predicts.

We study the algorithmic problem faced by an information holder (seller) who wants to optimally sell information to a budged-constrained decision maker (buyer). The utilities of both agents depend on a random state of nature that is revealed to the seller, but unknown to the buyer. Differently from previous works, we consider the case in which the seller is an interested party, as the decision taken by the buyer also influences seller's utility. The seller's goal is to (partially) sell their information about the state of nature to the buyer, so as to concurrently maximize revenue and induce the buyer to take a desirable decision. We study settings in which buyer's budget and utilities are determined by a random buyer's type unknown to the seller. First, we propose a polynomial-time algorithm for computing an optimal seller's protocol, which proposes a menu of information-revelation policies to the buyer, who acquires one of them by paying its corresponding price. Then, we switch the attention to the case in which the seller can only employ a single information-revelation policy, rather than proposing a menu. In such a setting, we completely characterize the computational complexity of the seller's algorithmic problem.

Machine learning relies on gradient-based training procedures whose empirical efficiency is usually analyzed through finite-dimensional arithmetic counts rather than formal complexity over continuous real-valued data. This paper studies neural-network training primitives as represented-real operators in the second-order complexity framework of Kawamura and Cook. Here, second-order polynomial time means computing a real-valued operator to accuracy $2^{-n}$ in time polynomial in the requested precision, architecture size, primitive evaluation costs, and supplied analytic certificates. We prove that dense backpropagation, convolutional backpropagation, soft attention, fixed finite SGD/Adam-style updates, and related smooth local primitives are second-order polynomial-time computable over the relevant represented real spaces. More precisely, dense one-sample backpropagation has tight arithmetic complexity $\Theta(s)$ for $s$ weights and polynomial bit complexity; convolutional backpropagation is polynomial in the number of active convolution incidences; dense soft-attention backpropagation has arithmetic cost $\Theta(\ell d^2+\ell^2d)$; and fixed finite smooth optimizer updates remain second-order polynomial-time computable under explicit smoothness and lower-bound certificates. Higher complexity enters through three distinct mechanisms: discontinuous selection, global optimization, and continuous-time flow solving. Hard routing, top-$k$ sparsification, argmax decisions, ReLU kink conventions, exact line search, and idealized gradient flow therefore change the second-order complexity status of the training operator. Overall, this work provides a rigorous mathematical language for precision, conditioning, and certificate dependence, which are often implicit in floating-point analyses, thus enabling a unifying complexity account for dense networks, CNNs, attention, Transformers, and standard optimizers.

Game balancing is a longstanding challenge requiring repeated playtesting, expert intuition, and extensive manual tuning. We introduce RuleSmith, a framework for automated game balancing that couples multi-agent LLM self-play with Bayesian optimization over a parameterized rule space. As a proof of concept, we build CivMini, a simplified civilization-style game with two asymmetric factions governed by 12 tunable parameters. LLM agents read textual rulebooks and game states to generate legal actions, enabling fast evaluation of balance metrics such as win-rate disparity. To search the rule space efficiently, we use Bayesian optimization with acquisition-based adaptive sampling: candidates with high Expected Improvement receive more evaluation games, while exploratory candidates receive fewer. RuleSmith consistently finds near-balanced configurations and produces interpretable parameter adjustments. It provides a scalable alternative to manual playtesting. Code will be available upon acceptance.

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 consider the problem of *regularized* best-response max-regret minimization in online RLHF under general preferences and bandit feedback. While various regularizers are utilized to robustify alignment, known polylogarithmic regret guarantees remain heavily specific to KL. To investigate whether such fast rates extend beyond KL, we adopt the *Generalized Bilinear Preference Model (GBPM)*—capturing intransitive preferences over $d$-dimensional item-wise features via a rank-$2r$ skew-symmetric matrix—to isolate the impact of generic regularization. Crucially, under GBPM, we prove that the dual gap of any greedy policy is bounded by the *squared* estimation error, derived using *only* strong convexity and skew-symmetry. Under a feature coverage assumption, we establish polylogarithmic $\tilde{\mathcal{O}}(\eta d^4 (\log T)^2 \wedge d^2 \sqrt{T})$ regret with Greedy Sampling and $\mathrm{poly}(d)$-free $\tilde{\mathcal{O}}(\sqrt{\eta r T} \wedge r^{1/3} T^{2/3})$ regret with Explore-Then-Commit, where $\eta^{-1}$ is the regularization coefficient and $T$ is the time horizon. This demonstrates that ``fast'' regrets are *not* KL-specific, but rather a fundamental consequence of generic strongly convex geometry.

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.

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.

We study online learning in linear dynamical games where multiple strategic agents act on a shared state evolving according to a linear dynamical system subject to adversarial disturbances. This setting lies beyond both single-agent nonstochastic online control and classical linear-quadratic games, which typically focus on quadratic objectives and noiseless or stochastic dynamics. Each agent seeks to minimize its own sequence of convex losses under full-state observability. Following the stabilizing-baseline paradigm in nonstochastic online control, we assume access to linear controllers that stabilize the noiseless system and focus on online adaptation by learning disturbance-action corrections. This extends adversarial online control to strategic multi-agent shared-state systems, where each agent's actions shape the state trajectory and hence the realized losses of all learners. Under state-only and aggregate-input feedback models, we analyze agents running online gradient descent with memory to update their own disturbance-action policies. We prove per-agent regret bounds that are sublinear and near-optimal in the time horizon, and show how their dependence on the number of agents varies with the feedback available to each learner. In the common-interest case, where all agents have identical cost functions, we show that the induced online problem forms a time-varying potential game and derive equilibrium-tracking guarantees. Together, these results provide a theoretical framework for adversarial online learning in stabilized linear dynamical games, connecting online control with learning in games.