NeurIPS 2026 论文列表

Feed-forward transformer models have driven remarkable progress in 3D vision, yet their quadratic complexity renders them impractical for long video sequences. Streaming 3D reconstruction addresses this bottleneck by processing frames sequentially with constant memory. However, existing recurrent architectures inevitably suffer from progressive degradation over long sequences, as they fail to account for the intrinsic reliability of observations and the accumulated confidence of the historical state, leading to severe error accumulation. To address these issues, we introduce BAT3R, a training-free Bayesian adaptation framework comprising two synergistic modules: State Innovation Gating (SIG) and Bayesian-guided Adaptive State Updating (BASU). SIG acts as a distributional regularizer that anchors state evolution to its geometric initialization, effectively arresting representational drift during long-term inference. Building on this, BASU reformulates state update as a recursive Bayesian inference process within a Kalman filtering framework. By jointly modeling the temporal reliability of observations via information-theoretic gain and spatial relevance via cross-attention maps, BASU achieves an asymmetric spatio-temporal state fusion: well-consolidated historical regions are protected from redundant updates, while genuinely novel scene content is aggressively incorporated. Extensive experiments on standard benchmarks (7-Scenes, TUM, ScanNet, KITTI, etc.) demonstrate that BAT3R consistently outperforms state-of-the-art online 3D reconstruction methods, with the most significant gains observed on long sequences and complex scenes.

We study online learning in the adversarial injection model [GHMS23], where each instance is either drawn i.i.d. from an unknown distribution or is an arbitrary adversarial injection. The learner never knows which rounds are adversarial, but may abstain without penalty on adversarial injections. The learner's goal is to make few total misclassifications and few abstentions on i.i.d. instances. This model lies between classical statistical learning, governed by the VC dimension, and adversarial online learning, governed by the Littlestone dimension. Unlike prior work, which has largely focused on the realizable setting, we consider an agnostic formulation that allows arbitrary labels. We present an online algorithm that guarantees sublinear excess misclassification error and sublinear abstention error, against oblivious and adaptive adversaries, for function classes that admit bounded bracketing number witnessed by brackets of bounded VC dimension. Our algorithm is distribution-independent and does *not* require prior knowledge of the distribution. As corollaries, we obtain new learning guarantees for halfspaces (linear classifiers) and richer classes such as feed-forward neural networks with threshold activations.

Making calibrated online predictions is a central challenge in modern AI systems. Much of the existing literature focuses on fully adversarial environments where outcomes may be arbitrary, leading to conservative algorithms that can perform suboptimally in more benign settings, such as when outcomes are nearly stationary. This gap raises a natural question: can we design online prediction algorithms whose calibration error automatically adapts to the degree of non-stationarity in the environment, smoothly interpolating between i.i.d. and adversarial regimes? We answer this question in the affirmative and develop a suite of algorithms that achieve adaptive calibration guarantees under multiple calibration measures. Specifically, with $T$ being the number of rounds and $C\in[0,T]$ being an unknown non-stationary measure defined as the minimal $\ell_1$ deviation of the mean outcomes, our algorithms attain $\widetilde{O}(\sqrt{T}+(TC)^{\frac{1}{3}})$ for $\ell_1$ calibration error and $\widetilde{O}((1+C)^{\frac{1}{3}})$ for both $\ell_2$ and pseudo KL calibration error. These bounds match the optimal rates in the stationary case ($C=0$) and recover known guarantees in the fully adversarial regime ($C=T$). Our approach builds on and extends prior work [Hu et al., 2025, Luo et al., 2025], introducing an epoch-based scheduling together with a novel non-uniform partition of the prediction space that allocates finer resolution near the underlying ground truth.

Autoregressive generation lies in the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an input string (prompt), the generator is applied for $M$ steps, and the last generated token is taken as the final output. [Joshi et al., 2025] proposed a PAC model for studying the learnability of the input-output maps arising from this process. We develop an online analogue of this framework, focusing on the mistake bound of learning the final output induced by an unknown next-token generator. We distinguish between two forms of feedback. In the End-to-End model, after each round the learner observes only the final token produced after M autoregressive steps. In the Chain-of-Thought model, the learner is additionally shown the entire $M$-step trajectory. Our goal is to understand how the optimal mistake bound depends on the generation horizon $M$, and to what extent observing intermediate tokens can reduce this dependence. Our main results show that the online theory of autoregressive learning exhibits a qualitative picture analogous to the statistical one found by [Hanneke et al., 2026], but with a different scale of dependence on the generation horizon. In the End-to-End model, we prove a taxonomy of possible mistake-bound growth rates in the generation horizon $M$: subject to mild regularity conditions, every rate between constant and logarithmic can arise. We also show that this logarithmic ceiling is unavoidable for the online setting, in the sense that every class of finite Littlestone dimension exhibits at most logarithmic dependence on $M$. In the Chain-of-Thought model, the parallel is even sharper: as in the statistical setting, access to the full generated trajectory eliminates the dependence on $M$ altogether. We also analyze autoregressive linear threshold classes. For autoregressive linear thresholds in \(\mathbb{R}^d\), we prove that the optimal mistake bound is \(\Theta(d^2)\) under both End-to-End and Chain-of-Thought feedback, and for any generation length $M$. The methods developed for this analysis also yield new lower bounds in the statistical setting. Along the way, our results resolve several questions left open by [Joshi et al., 2025]. In particular, we show that even for classes of finite Littlestone dimension, the End-to-End statistical sample complexity can depend on the generation length M.

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.

We study nonstationary online linear programming (OLP), where orders arrive sequentially and follow independent but not-identical reward-resource distributions. The decision- maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to a resource endowment available at the beginning of the planning horizon. Such problems arise in resource-constrained ML and AI systems, including inference admission control, online advertising and recommendation, and data-acquisition pipelines, where the mix and value of requests may change over time. We focus on a minimal-information regime in which the decision-maker observes only one independent sample from each future distribution before the horizon begins. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of order, we prove that our algorithm achieves $O((\log n)^2)$ regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.

Online data selection is typically driven by per-sample scores such as loss, uncertainty, or gradient norm, which measure how strongly the model reacts to a candidate but not what parameter update the candidate would induce. What an online learner should select is therefore not the most striking example, but the one whose update is most worth taking. To make this concrete, we score a candidate by the movement induced by its update, using a Fisher-whitened information gain that evaluates the update in the loss geometry rather than by raw gradient size. Movement, however, is not yet progress, so we pass this score through a \emph{Descent Alignment Gate}, a soft factor that retains it only when the induced update agrees with the descent direction. This yields a sample-level score favoring updates that are both informative and descent-aligned. To make the criterion compatible with training, we extend it from samples to batches, where selected updates should not only score well individually but also complement one another. We capture this with the \emph{Gated Fisher Volume}, a log-determinant batch objective that reduces to the per-sample score on a singleton, grows with the volume spanned by the chosen updates in the Fisher geometry, and admits a greedy algorithm with a constant-factor approximation guarantee. Across supervised fine-tuning benchmarks, our selector consistently outperforms online selection baselines under matched training budgets. More broadly, the framework reframes data selection itself: rather than a spotlight on conspicuous examples, it acts as a compass toward updates worth taking.