NeurIPS 2026 论文列表

Symmetry-aware learning is typically framed as equivariance to a single group action, but many real-world distribution shifts are typed, partial/non-invertible, and compositional (e.g., modality changes, occlusion, subsampling, intervention chains). These shifts are better modeled by a category of transformations whose objects represent data contexts and whose morphisms represent admissible transformations between contexts. We thus extend symmetry-aware machine learning from groups to such transformation categories; enforcing categorical equivariance on neural architectures gives stronger robustness than group equivariance. We ground this in both theory and experiments. We formulate a universal approximation theorem for category-equivariant architectures and show density in the space of equivariant continuous transformations. We present experiments on compositional OOD shifts, demonstrating that enforcing categorical equivariance yields measurable robustness gains over group-equivariant and non-equivariant baselines.

Follow the regularized leader (FTRL) is a foundational algorithm in online learning whose regret properties have been extensively studied for decades. However, in stark contrast to mirror descent---and gradient descent in particular---the convergence of FTRL to first-order stationary points in constrained nonconvex optimization was hitherto unresolved. In this paper, we show that continuous-time FTRL can fail to converge even asymptotically in constrained optimization problems; that is, the Karush-Kuhn-Tucker (KKT) gap of FTRL can remain bounded away from zero indefinitely. This is especially surprising in light of the fact that continuous-time FTRL guarantees a monotonic improvement of the objective value. As a result, we establish that non-convergent behavior of no-regret dynamics---which besets general variational inequality problems---can occur even in potential systems. From a technical standpoint, our construction relies on an infinitely differentiable function where the gradient flow dynamics exhibit decelerating oscillations without ever converging pointwise, which we in turn embed into higher-dimensional FTRL dynamics that sustain a perpetually large KKT gap.

We introduce \emph{universal transformers}: fixed-parameter architectures that can simulate any transformer in a given class via a suitable input embedding. Analogous to a universal Turing machine, the input embedding encodes a description of the target model while all internal parameters remain fixed. We provide explicit sparse constructions achieving universality when the embedding dimension is sufficiently large, and further show that universality is generic: randomly initialized transformers are universal almost surely, which aligns with recent empirical results of Zhong and Andreas (2024). We empirically validate our theory on the algorithmic tasks of parenthesis balancing and multi-hop reasoning. Our results suggest that much of a transformer’s expressive power may reside in its input representation rather than its learned weights.

The framework of Online Convex Optimization with Memory captures sequential decision-making settings where the learner's instantaneous loss is affected by their past choices, in addition to the most recent decision. We first give a new first-order regret bound in this framework for potentially non-smooth loss functions, with regret scaling as the square root of the loss of the best decision in hindsight, which can be much better than known regret bounds that explicitly scale with the horizon. In fact, our result holds in a generalized non-differentiable setting, which also captures other decision making problems of interest. We then give a faster gradient-based algorithm that yields an improved first-order regret bound for smooth loss functions. As an application, we consider the recently introduced problem of online nonstochastic control, which involves controlling a linear dynamical system subject to adversarial disturbances to minimize convex cost functions, where our results can be adapted to produce novel first-order regret bounds. This means whenever there is a benchmark controller with small loss in hindsight, our regret bounds are significantly smaller than those present in the literature.

Progress in mathematics often depends not only on proving that a result is true, but on finding a proof that is simple enough to understand, verify, and adapt. Automated systems can now independently discover proofs, but the certificates they produce tend to be dense and difficult to interpret, even when simpler arguments exist. Recent work on performance estimation problems has shown that proofs of convergence for first-order optimization methods can be discovered by searching over a structured space of Lagrangian dual certificates. This paper studies the simplification of such proofs as an optimization problem. Starting from dual certificates, we develop post-processing procedures using tools from sparse optimization and statistical learning. We measure complexity through features such as active hypotheses and residual structure, and introduce methods based on exhaustive sparsification, (weighted) $\ell_1$ heuristics, and semidefinite programming (SDP) formulations for discovering simple proofs and intermediate lemmas. Examples on gradient descent, proximal methods, and fast-gradient methods show that these procedures can autonomously prune redundant inequalities, reveal structured proof patterns, and, in the proximal setting, recover standard intermediate lemmas that lead to streamlined proofs. By distilling dense machine-generated certificates into compact proof structures, this workflow acts as a pre-processing step for the final proof, reducing the complexity that must be managed during human interpretation, reuse, and formalization.

Neural combinatorial optimization (NCO) solvers generalize poorly under distribution shift, yet robustness across heterogeneous problem distributions is essential for real-world deployment where no single client should be left behind. Group distributionally robust optimization (Group DRO) offers a principled remedy, but requires pooling data that often cannot be shared due to confidentiality or regulatory constraints. Federated learning removes data-sharing requirements; however, existing federated DRO methods cannot accommodate the policy-gradient estimators used in modern NCO. Specifically, prior analyses rely on Lipschitz losses with bounded variance. In contrast, the REINFORCE policy-gradient estimator multiplies stochastic costs by score functions, causing variance to scale with cost magnitude and violating these standard assumptions. We close this gap by replacing Lipschitz-loss conditions with a bounded-cost assumption. This allows us to control cost-dependent variance and establish the first federated Group DRO framework with $O(1/\sqrt{T})$ convergence guarantees. Our analysis applies to any REINFORCE-trained model under bounded costs, including NCO solvers as a special case. Experiments on capacitated vehicle routing---one of many applicable domains including scheduling and packing---demonstrate the necessity of federated training for minority-distribution clients. We show that while na\"ive Group DRO suffers from catastrophic weight collapse, our KL-regularized formulation avoids this collapse. Furthermore, it provides a formal worst-group robustness certificate with no empirical performance penalty compared to standard federated averaging.

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.

Zeroth-order (ZO) optimization enables memory-efficient large language model (LLM) fine-tuning, with recent methods employing curvature-aware strategies. However, in the massive LLM parameter space, these methods inherently suffer from exploding gradient variance and prohibitive costs. Conversely, confining updates to a low-dimensional subspace reduces variance but discards critical high-dimensional information, degrading performance. This creates a fundamental dilemma: full-space optimization is informative but high-variance, while subspace optimization is low-variance but blind. To break this trade-off, we propose \textbf{\Engine} (\textbf{En}do\textbf{g}enous Var\textbf{i}atio\textbf{n}al MultiScal\textbf{e}). Inspired by computational mechanics, we adapt static Variational MultiScale theory to dynamic optimization, treating low- and high-dimensional spaces as resolved coarse and unresolved fine scales. Through a multigrid-style V-cycle, \Engine\ alternates between spaces, dynamically probing fine-grained information in the high-dimensional space and injecting it to correct the efficient low-dimensional sampling process. Evaluations on standard LLM benchmarks show that \Engine\ achieves higher accuracy and faster convergence than existing ZO methods, achieving up to a $\mathbf{2.61\times}$ \textbf{speed-up in forward passes} with zero additional peak memory overhead. Code is available at \url{https://anonymous.4open.science/r/ENGINE-D0A4}.

Deep neural networks suffer from catastrophic forgetting when learning on sequence tasks because standard adaptation mechanisms update a monolithic set of Cartesian weights, inherently entangling feature intensity with spatial displacement and destructively overwriting ancestral representations. Inspired by the brain’s multi-timescale consolidation and frequency-aware memory dynamics, we propose HiPo(Hierarchical Polar Adapters), a novel continual learning framework that fundamentally redefines how neural knowledge is parameterized, stored, and consolidated. First, HiPo projects token representations into a complex orthogonal Fourier basis and explicitly parametrizes the adapter weights in polar coordinates, decoupling feature intensity from geometric correlation to probabilistically isolate task updates. Second, we embed these polar weights within a multi-tiered hierarchical memory stack, functionally separating a highly plastic working memory from a deep, stabilizing long-term memory. Finally, an adaptively thresholded snapshot Fisher mechanism evaluates parameter criticality in the decoupled polar space. By executing mathematically safe, Cartesian-invariant knowledge transfers into the deep memory tiers, HiPo safely hollows out the working memory, paralyzing obsolete gradients and preserving plasticity without inducing structural distortion. Extensive experiments across standard CIL benchmarks demonstrate that HiPo establishes a highly resilient optimization manifold, achieving state-of-the-art performance and exceptional geometric stability, particularly under severe out-of-distribution shifts.

Sequential Model-Based Optimization (SMBO) traditionally relies on Bayesian or ensembling surrogates for uncertainty quantification. While historically treated as fully data-driven, SMBO increasingly integrates external domain expertise to accelerate discovery. To overcome the opaque guidance and diminished integration fidelity of standard acquisition re-weighting, Probabilistic Circuits (PCs) have emerged as a generative surrogate alternative, enabling direct knowledge injection via conditional sampling. However, these generative routines lack the formal exploration-exploitation semantics required for rigorous optimization. We introduce the Distributional Conformance Score (DisCo), a principled metric that unifies the flexibility of PCs with a rigorous uncertainty framework. DisCo provides a bounded, $[0, 1]$-normalized measure of model "surprise" that (1) recovers properties comparable to kernel-based uncertainty known from, e.g., Gaussian Processes while maintaining linear-time inference, and (2) enables principled and accurate assessment of conformance of external knowledge w.r.t. model evidence. We then present DisCoMBO, a framework leveraging these properties for robust, knowledge-aware optimization. We prove that DisCoMBO is a zero-regret algorithm and demonstrate its effectiveness across diverse benchmarks from AutoML, material optimization, and wind park optimization.

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.

Hyperparameter transfer has become an important component of modern large-scale training recipes. Existing methods, such as muP, primarily focus on transfer between model sizes, with transfer across batch sizes and training horizons often relying on empirical scaling rules informed by insights from timescale preservation, quadratic proxies, and continuous-time approximations. We study hyperparameter scaling laws for modern first-order optimizers through the lens of recent convergence bounds for methods based on the Linear Minimization Oracle (LMO), a framework that includes normalized SGD, signSGD (approximating Adam), and Muon. Treating bounds in recent literature as a proxy and minimizing them across different tuning regimes yields closed-form power-law schedules for learning rate, momentum, and batch size as functions of the iteration or token budget. Our analysis, holding model size fixed, recovers most insights and observations from the literature under a unified and principled perspective, with clear directions open for future research. Our results draw particular attention to the interaction between momentum and batch-size scaling, suggesting that optimal performance may be achieved with several scaling strategies.

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.

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 present the first method for intrinsic, continuous gradient-based optimization for models with $p$-adic parameters. To overcome the vanishing gradients caused by the discrete valuation of the $p$-adics, we lift parameters to the Berkovich affine line, a canonical analytification of the $p$-adic numbers that provides a path-connected space. This enables gradient descent that respects the non-Archimedean metric with a local transition cost that is linear. By extending losses to the Berkovich line, we get piecewise linear functions, corresponding to the cell decomposition of a tropical complex; gradients are efficiently computed via max-plus operations. We prove local convergence within tropical cells for linear models on the $\mathbb{Q}_p$ subtree, and demonstrate the success of our method on synthetic tasks and on the $p$-adic Quillian semantic benchmark [Martins, 2025], where we achieve performance equal or better than $\mathbb{R}$-valued counterparts while training in comparable time.

Diffusion bridges have emerged as versatile diffusion-based frameworks for facilitating transformations between arbitrary data distributions. However, these approaches are hindered by the immensity of the optimization space without consideration of underlying high-order structures. This paper explores a complex-valued variant of diffusion bridges for solving physical problems using conformal field theory and mean field games. To this end, we propose a new class of dynamical diffusion bridges, called complex Schr\"odinger Bridges (CSB), whose derived algorithms are able to handle diffusion-based tasks using Hamiltonian-based geometric prior. Additionally, we propose image-to-image CSB (I$^2$CSB), tractable diffusion bridge techniques with a spiral analytic posterior. We verify our theoretical claims and practicality of our Hamiltonian based approach with a wide range of experiments.

Neural networks are typically optimized with variants of stochastic gradient descent. Under a squared loss, however, the optimal solution to the linear last layer weights is known in closed-form. We propose to leverage this during optimization, treating the last layer as a function of the backbone parameters, and optimizing solely for these parameters. We show this is equivalent to alternating between gradient descent steps on the backbone and closed-form updates on the last layer. We adapt the method for the setting of stochastic gradient descent, by trading off the loss on the current batch against the accumulated information from previous batches. We provide theoretical analyses showing convergence of the method to an optimal solution in the neural tangent kernel regime, as well as quantifying the gains compared to standard SGD in a one-step analysis. Finally, we demonstrate the effectiveness of our approach compared with SGD and Adam on a squared loss in several regression tasks, including neural operators and causal inference.

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.

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.