NeurIPS 2026 Papers

Multinomial logistic regression (MLR) is the default last-layer classifier in fully supervised recognition, while prototype classifiers are central to few-shot recognition. Although they are usually presented as different principles, we show that both can be organized by a geometric notion of class boundaries. A Euclidean MLR logit is a signed distance to a class hyperplane, so ordinary MLR is already the hyperplane decision-boundary case of Umbilic Multinomial Logistic Regression (UMLR). Classical submanifold geometry supplies the matching spherical decision boundary: in Euclidean space, the complete connected totally umbilic hypersurfaces are hyperplanes and spheres. The spherical UMLR form keeps a prototype-like center but adds a learnable radius; its signed squared-distance form contains squared prototype scoring as the radius-zero case. Thus UMLR is not a separate replacement for MLR or prototypes, but a boundary-aware family that places hyperplane logits, spherical logits, mixed heads, and prototype scoring in one framework. Experiments on low-shot vision head swaps, prototype comparisons, and mixed hyperplane--sphere heads support this organization and show how the different decision boundaries behave across data regimes. UMLR provides a compact geometric language for studying when class evidence is better modeled by flat boundaries, spherical boundaries, or their mixture.

We study transfer learning for a linear regression task using several least-squares pretrained models that can be overparameterized. We formulate the target learning task as optimization that minimizes squared errors on the target dataset with penalty on the distance of the learned model from the pretrained models. We analytically formulate the test error of the learned target model and provide the corresponding empirical evaluations. Our results elucidate when using more pretrained models can improve transfer learning. Specifically, if the pretrained models are overparameterized, using sufficiently many of them is important for beneficial transfer learning. However, the learning may be compromised by overparameterization bias of pretrained models, i.e., the minimum L2-norm solution's restriction to a small subspace spanned by the training examples in the high-dimensional parameter space. We propose a simple debiasing via multiplicative correction factor that can reduce the overparameterization bias and leverage more pretrained models to learn a target predictor.

Kotłowski et al. (NeurIPS 2017) posed as a central open problem the design of efficient online isotonic regression algorithms beyond totally ordered domains. We resolve this for the product order $[m]\times[m]$, the canonical two-dimensional case, by determining the minimax regret up to constant factors: $$ R_T^* = \Theta\left(\min\left\\{T,\ \inf_{K \in \mathbb{N}_+}\left[\log\Omega([m]^2, K+1) + \frac{T}{K^2}\right]\right\\}\right), $$ where $\Omega(\mathcal{P}, K+1)$ is the order polynomial counting monotone maps from $\mathcal{P}$ to $[K+1]$. This unified formula reveals a three-phase scaling law: $\Theta(T)$ for $T \lesssim m$, $\Theta(m^{2/3} T^{1/3})$ for $m \lesssim T \lesssim m^4$, and $\Theta(m^2 \log(T/m^4))$ for $T \gg m^4$. We further construct polynomial-time algorithms achieving this rate in every regime, including a horizon-free variant requiring no advance knowledge of $T$.

Explanations of multiple instance learning (MIL) models are widely used for validation and discovery in digital histopathology. Existing methods primarily rely on heatmaps that highlight influential regions but do not explain how evidence from different tissue regions is combined to produce a prediction. This limits interpretability, especially when decisions depend on interactions between tissue features. We introduce Symbolic explainable MIL (Symb-xMIL), a post-hoc explanation framework that quantifies how a MIL model’s behavior aligns with human-readable decision rules, expressed as logical relationships (e.g., AND, OR, NOT) between input features. These alignment scores reveal semantic patterns underlying the model’s predictions. We evaluate Symb-xMIL on synthetic and real-world histopathology datasets. On synthetic MIL data, Symb-xMIL reliably recovers ground-truth logical rules. In a clinical tumor detection task, the best-aligned rules uncover heterogeneous decision patterns and expose hidden model errors. On an HPV-prediction task on TCGA-HNSCC, a cohort of head and neck cancer, our framework refines patient survival stratification beyond HPV status with potential clinical relevance. Overall, Symb-xMIL extends MIL explainability beyond visual attribution toward structured, rule-based reasoning, enabling more transparent and semantically grounded interpretation of model predictions.

This paper characterizes the sharp asymptotics of the $\ell_{\infty}$-norm estimation error for estimating the coefficient vector in linear regression under proportional asymptotics. While $\ell_2$-error is well-documented, we demonstrate that the $\ell_{\infty}$-error exhibits a distinct phase transition governed by the structure of the underlying signal. We explore this through the lens of a class of estimators that include ridge-regularized estimators, a method-of-moments estimator, and the ordinary least squares estimator for the under-parametrized regime. Our results provide a comparative study of these estimators and characterize regimes (as identified by the maximal signal component, number of large signals, total signal strength, and noise variance) where one estimator is preferable to the others. As a by-product, we obtain new double descent curves in $\ell_{\infty}$-error metric for the ridgeless regression, as well as ingredients for uniform confidence intervals for the signal coordinates. Our theoretical results are supported by extensive numerical simulations that confirm the predicted phase transitions and error limits.

Recent work has revealed a link between self-attention mechanisms in transformers and test-time kernel regression via the Nadaraya-Watson estimator, with standard softmax attention corresponding to a Gaussian kernel. However, a kernel-theoretic understanding of sparse attention mechanisms is currently missing. In this paper, we establish a formal correspondence between sparse attention and compact (bounded support) kernels. We show that normalized ReLU and sparsemax attention arise from Epanechnikov kernel regression under fixed and adaptive normalizations, respectively. More generally, we demonstrate that widely used kernels in nonparametric density estimation---including Epanechnikov, biweight, and triweight---correspond to $\alpha$-entmax attention with $\alpha = 1 + \frac{1}{n}$ for $n \in \mathbb{N}$, while the softmax/Gaussian relationship emerges in the limit $n \to \infty$. This unified perspective explains how sparsity naturally emerges from kernel design and provides principled alternatives to heuristic top-$k$ attention and other associative memory mechanisms. Experiments with a kernel-regression-based variant of transformers---Memory Mosaics---show that kernel-based sparse attention achieves competitive performance on language modeling, in-context learning, and length generalization tasks, offering a principled framework for designing attention mechanisms.

Wasserstein distributionally robust optimization (DRO) is a prominent paradigm for robust decision-making in the face of distributional uncertainty. Given a nominal data distribution, DRO selects a decision which minimizes the risk for a worst-case data distribution within a prescribed Wasserstein radius $\varepsilon$ of the nominal distribution. In this paper, we investigate the quality of DRO decisions when evaluated on a worst-case distribution within a 2-Wasserstein $\varepsilon$-neighborhood of the nominal distribution, as measured by excess risk or ex-ante regret. Beginning with multivariate linear regression and extending to ridge regression, we first identify the asymptotic complexity of robust decision-making in the $\varepsilon \to 0$ limit, characterized by a problem-specific condition number $\kappa$. In this regime, a wide spectrum of simple algorithms, including DRO, achieve the instance-optimal rate of $O(\kappa \varepsilon^2)$. For fixed $\varepsilon > 0$, we prove that DRO still achieves the minimax rate if the problem is of an appropriate ``low rank''. On the other hand, we identify significant failure modes where DRO is provably suboptimal by dimension-dependent factors. To resolve this, we introduce a new condition number reduction (CNR) procedure which achieves the optimal rate and admits tractable approximation algorithms. We support these theoretical results with numerical experiments comparing the performance of various estimators including DRO and CNR.

Verifying that two quantum circuits are equivalent is a critical challenge in compiler validation. A common approach is to transform the circuits into a tensor network and then iteratively contract tensors in the network. The order in which contractions are applied has a crucial influence on the complexity, as tensor size may grow exponentially in the number of qubits. This motivated research into heuristic policies to find good contraction orders, including recent work based on reinforcement learning (RL). Orthogonally, to mitigate the complexity of an explicit tensor representation, tensor decision diagrams (TDDs) have been proposed as a compact symbolic representation. However, also the TDD performance is sensitive to the contraction order, and policies designed for tensor networks do not perform well in case of a TDD representation. In this paper, we propose an RL framework to obtain a graph-neural-network policy that navigates the trade-off between arithmetic complexity and TDD size. Experimental results demonstrate that a policy learned with our framework is effective at taming the symbolic representation size.

Neuro-symbolic learning was proposed to address challenges with training neural networks for complex reasoning tasks with the added benefits of interpretability, reliability, and efficiency. Neuro-symbolic learning methods traditionally train neural models in conjunction with symbolic programs, but they face significant challenges that limit them to simplistic problems. On the other hand, purely-neural foundation models now reach state-of-the-art performance through prompting rather than training, but they are often unreliable and lack interpretability. Supplementing foundation models with symbolic programs, which we call neuro-symbolic prompting, provides a way to use these models for complex reasoning tasks. Doing so raises the question: What role does specialized model training as part of neuro-symbolic learning have in the age of foundation models? To explore this question, we highlight three pitfalls of traditional neuro-symbolic learning with respect to the compute, data, and programs leading to generalization problems. This position paper argues that foundation models enable generalizable neuro-symbolic solutions, offering a path towards achieving the original goals of neuro-symbolic learning without the downsides of training from scratch.

Datasets in many settings naturally partition into clusters arising from sub-populations, batch effects, or aggregation across multiple sources. A common response to such heterogeneity is to ensemble learners trained on each cluster rather than fit a single model to the pooled data. Prior work motivating such approaches has typically considered settings in which both the covariate distribution and the conditional outcome model differ across clusters; the role of cluster-aware partitioning and ensembling based solely on the covariate distribution remains to be explored. We address this case for ridge-regularized least-squares regression under a linear outcome model and consider all ridge penalty values $\lambda \geq 0$, including the special case of the ridgeless predictor at $\lambda = 0$. By considering both fixed-effects and random-effects models, we argue that under random effects, an optimally tuned pooled ridge predictor always outperforms ensembles of individually optimally tuned predictors. For fixed effects, we derive a general formula for the pooled and ensembled predictors to characterize the role of both regression coefficients as well as the predictor distribution shifts. Together, these results generalize prior risk analyses of bagging and random-partition estimation using ridge and ridgeless regression predictors from the i.i.d. setting to encompass covariate shift and heterogeneity-aware partition structure.

We study high-probability linear regression in the infinite variance regime, where the regression noise has only a finite conditional $\alpha$-moment $\nu$ for an unknown $\alpha\in(1,2)$, and the covariates may also be heavy-tailed. We give a black-box reduction that converts finite-variance regression procedures into weak-moment procedures. The reduction is based on empirical residual pruning and is agnostic to the moment exponent, the noise scale, the covariance, and the design moment constant. Under a finite fourth-moment condition on the covariates, any finite-variance subroutine with the sub-Gaussian rate yields the following for all $n$ above a suitably defined threshold: $ \lVert \widehat\theta-\theta^* \rVert_\Sigma \lesssim_\alpha \nu^{1/\alpha} \left(\frac{d+\log(1/\delta)}{n}\right)^{\frac{\alpha-1}{\alpha}} $ with probability at least $1-\delta$, without knowing $\alpha$ or $\nu$. We further prove a matching minimax lower bound that holds under the same conditions. The reduction is computationally efficient whenever the finite-variance subroutine is. We also obtain a distribution-free prediction guarantee under a bounded raw $\alpha$-moment assumption on the response, and give an analogous $\alpha$-agnostic reduction for mean estimation.

Web-based language agents operate under severe partial observability, where the semantic divergence between internal state assumptions and the ground-truth environment is often unobservable. Consequently, agents frequently maintain high-level reasoning coherence over misgrounded states, causing errors to compound as subsequent decisions are conditioned on silently invalidated premises. We present **NesyProAct**, a proactive neural-symbolic agentic decision framework that transforms conventional ReAct-style web agents from reactive prompting pipelines into execution-aware decision processes. NesyProAct exposes a typed symbolic decision interface over states, actions, transitions, and subgoals, enabling LLM-based agents to automatically compose and reason over execution semantics across decision hierarchies. From this interface, programmatic verification logic is synthesized online to evaluate step-level executability and progress, with verification outcomes directly regulating decision evolution through targeted grounding interventions. As a result, execution feedback is integrated into planning itself, allowing agents to maintain semantic alignment under partial observability rather than propagating unverified assumptions. On WebArena, NesyProAct achieves a **12\%** overall improvement over strong skill-induction agentic web framework ASI across six domains. NesyProAct also achieves noticeable performance when reasoning with small models GPT-4o-mini, with **5.1\%** gain over ASI with Claude-3.5.

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

Synthetic data has become a promising way to scale model training beyond limited human-generated data but it may also induce strong model collapse (Dohmatob et al., 2024), where any fixed fraction of synthetic data prevents model performance from improving under data scaling, leaving a non-vanishing excess risk floor. In this paper, we studied how synthetic data affects the generalization of one-pass SGD in high-dimensional linear regression with model shift. We show that mixed training induces strong model collapse while two-stage training avoids this by using synthetic data only in the first stage, followed by real-data training in the second stage, showing that strong model collapse is not inevitable through a simple data curriculum. We further establish scaling-law upper bounds for both protocols under a random sketch model, showing that larger models amplify synthetic-induced degradation in mixed training and giving an explicit characterization of how high-quality synthetic training may reduce bias in two-stage training. Overall, our results highlight that synthetic data is neither inherently harmful nor beneficial; its effect depends critically on both its quality and the training protocol used to incorporate it.

Optimal Transport (OT) provides a principled framework for comparing probability distributions. Classical solvers remain the gold standard for this task, providing exact solutions. At the same time, OT is an ideal testbed for studying whether learning-based amortized models can internalize the structure of OT type problems. Here, ground-truth solutions are available, constraints are explicit, and exact discrete solutions have well-characterized sparsity. We describe ToR-OT, a transformer-based model that learns to predict discrete OT plans through autoregressive token regression. We reframe OT into a structured sequence generation task. ToR-OT decodes sparse transport plans as sequences rather than solving an optimization task at test time. We focus on three properties: (a) Zero-shot generalization: pretraining on a large synthetic corpus of OT instances allows a single model to generalize to unseen distribution pairs and heterogeneous cost metrics without retraining. (b) Sparse primal decoding: by exploiting the inherent sparsity in exact discrete OT solutions, the decoder predicts only nonzero entries (avoids dense coupling outputs). (c) Amortized inference: on low-dimensional discrete problems, ToR-OT gives accurate approximate plans and compares favorably with per-instance neural OT baselines. Overall, ToR-OT is not yet a replacement for classical solvers, but best viewed as a step toward understanding how autoregressive transformers can learn structure of constrained optimization problems like OT.

Value overestimation is a central challenge in offline reinforcement learning (RL), arising when Bellman backups propagate out-of-distribution (OOD) errors that lead to catastrophic inflation of $Q$-values. Prior approaches address this issue by encouraging the learned policy to stay close to the behavior policy, but they often result in suboptimal policies or require significant training complexity. More recent work attempts to tackle this issue through minimal modifications to the critic network, yet it remains limited in either theoretical grounding or practical implementation. In this work, we present Kernel Value Regression (KVR), a simple critic regularization method based on kernel regression. KVR builds on the vanishing extrapolation property of kernel ridge regression, which encourages value estimates to decay toward zero away from the data support. This inductive bias naturally suppresses $Q$-values for OOD actions without auxiliary regularizers, providing a structural mechanism for addressing value overestimation. Using random Fourier features, KVR can be incorporated into standard actor-critic algorithms with only minimal modifications. We empirically demonstrate that these properties persist in complex offline RL environments, leading to strong performance across diverse tasks in the D4RL and OGBench benchmarks.

Network interference complicates A/B testing on online platforms, such as social networks and marketplaces, where causal methods based on single experiments often suffer from significant bias due to complex interference patterns. This paper demonstrates the statistical benefits of merging data from multiple experiments with varying treatment proportions. Sequential experimentation with increasing traffic, or ramp-up, is widely used in tech companies for risk management and cost control. Beyond operational benefits, we show that regression-based estimators trained on merged data achieve substantial bias reduction, even under simple randomization schemes and regression models. We focus on the global average treatment effect (GATE), a key estimand in the tech industry, and consider a general interference pattern that extends beyond the 1-hop setting. We present an exact bias–variance analysis of the linear regression estimator and show that, in practical settings, the bias term typically dominates. In addition, we characterize the substantial bias reduction achieved by our proposed approach, which merges experimental data collected at different ramp-up stages to improve the training of the regression function. We also offer an intuitive explanation for this reduction and highlight the synergy between cluster-level randomization and our approach. Furthermore, we consider a refined estimator based on graph neural networks (GNN). Extensive simulations across novel and challenging scenarios confirm that our methodology significantly improves the accuracy of regression-based estimators.

Inferring latent interaction structures from observed dynamics is a fundamental inverse problem in many-body interacting systems. Most neural approaches rely on black-box surrogates over trainable graphs, achieving accuracy at the expense of mechanistic interpretability. Symbolic regression offers explicit dynamical equations and stronger inductive biases, but typically assumes known topology and a fixed function library. We propose $\textbf{COSINE}$ ($\textbf{C}$o-$\textbf{O}$ptimization of $\textbf{S}$ymbolic $\textbf{I}$nteractions and $\textbf{N}$etwork $\textbf{E}$dges), a differentiable framework that jointly discovers interaction graphs and sparse symbolic dynamics. To overcome the limitations of fixed symbolic libraries, COSINE further incorporates an outer-loop large language model that adaptively prunes and expands the hypothesis space using feedback from the inner optimization loop. Experiments on synthetic systems and large-scale real-world epidemic data demonstrate robust structural recovery and compact, mechanism-aligned dynamical expressions. Code: https://anonymous.4open.science/r/COSINE-6D43.

In in-context learning (ICL), a frozen pre-trained model solves tasks by conditioning on a prompt of a few input–output examples, without gradient updates. If the task was present in pretraining but the particular prompt sequence was not, the resulting in-distribution generalization is retrieval-based ICL. Learning-based ICL instead reflects out-of-distribution generalization: the model succeeds on prompts generated by a novel task. Empirically, both forms improve with scale. By analogy to benign overfitting in supervised learning, we call this in-context benign overfitting: larger models more faithfully memorize the pretraining tasks (improving retrieval ICL) while also generalizing better to novel tasks (improving learning ICL). We prove that this phenomenon already arises in a minimal in-context linear-regression feature-selection model. In contrast, standard in-context linear-regression models exhibit a retrieval–learning tradeoff, where the emergence of learning-based ICL coincides with degraded retrieval-based performance.