NeurIPS 2026 Papers

We consider the problem of learning an unknown subset $N^{target}$ of a domain in an online setting. % In each round $t$, the learner predicts a set of items ${N}_t$ and receives one of two types of feedback, each with equal probability: {\it precision feedback}, in which a randomly chosen item from the predicted set $N_t$ is revealed and the learner is told whether it belongs to $N^{target}$ (incurring a reward if it does), or {\it recall feedback}, in which a randomly chosen item from the target set $N^{target}$ is revealed and the learner is told whether it belongs to $N_t$ (incurring a reward if it does). The goal is to maximize the cumulative reward over time. This simple online set learning problem abstracts a variety of learning scenarios with precision and recall--type feedback. We show that a hypothesis class (a family of subsets of the domain) is learnable in this setting if and only if it has finite Vapnik-Chervonenkis (VC) dimension, mirroring the classical PAC characterization. However, the resulting algorithmic structure is markedly more intricate: in contrast to standard Probably Approximately Correct (PAC) learning---where the algorithmic landscape is governed by the simple principle of Empirical Risk Minimization (ERM)---our partial feedback model can invalidate ERM and even all proper learning rules. We develop algorithms to address the dependencies induced by the feedback, obtaining regret guarantees in both the realizable and agnostic settings. Our results provide a qualitative characterization of learnability in this model, addressing its most basic question, while pointing to a range of natural and intriguing open questions, including the determination of optimal regret rates.

Online resource allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints, with applications ranging from online advertising to revenue management. In this work, we study a broader setting that includes both budget constraints and general constraints, extending the classical budget-only model. This extension is essential for modelling critical economic requirements, such as Return-on-Investment (ROI) constraints. We develop an algorithm that achieves best-of-both-world guarantees within this generalized framework. In particular, against a dynamic benchmark, our algorithm achieves $\widetilde{\mathcal O}(\sqrt{T})$ regret in the stochastic regime and $\alpha$-regret of order $\widetilde{\mathcal O}(\sqrt{T})$ in the adversarial regime, where $\alpha$ depends on the feasibility margin of the corresponding offline problem. At the same time, our algorithm guarantees strict satisfaction of the budget constraints and $\widetilde{\mathcal O}(\sqrt{T})$ cumulative violation for the general ones. From a technical perspective, introducing general constraints alongside budgets precludes the use of standard budget-focus methods. While budget methods rely on a zero-consumption "safe'' action to ensure feasibility, general constraints are much less "aligned'' towards feasibility. We overcome these difficulties with a new analysis that exploits weak adaptivity to get boundedness of the Lagrangian multipliers and best-of-both-world guarantees.

The task of constructing a predictor that is simultaneously accurate under multiple evaluation metrics has been popularized recently under the name omniprediction. Prior work in this area has largely focused on binary prediction tasks, and existing results for multiclass and continuous outcomes typically suffer from slow error rates. In this paper, we consider forecasts expressed as a set of quantiles over a discrete but otherwise arbitrary set of probability levels. We develop sample-efficient algorithms for constructing forecasts that are simultaneously accurate across all proper losses that satisfy mild regularity conditions, where proper losses are those minimized by predicting the true quantiles. Our algorithms are online and can operate in a dynamic environment while simultaneously taking multiple losses into account, and their forecasts offer the potential to provide diverse end-users with rich information for evaluating risk and informing a range of practical decision-making tasks. As an example, we demonstrate how our procedure can be used to ensemble quantile forecasts of COVID-19 hospitalizations made by experts during the pandemic.

We present an algorithm for margin-based online learning using lossless compressors (like zip) via the Minimum Description Length Principle. The technique, we call \emph{MDL-PA}, can be viewed as an analogue of Passive-Aggressive algorithms for probability distributions (equivalently viewed as lossless compression schemes) where we consider a \emph{code length margin}. Separate models are maintained per class, and the update rule is an information projection correcting the true-class model's prediction on a margin-violating sample. To bridge theory and practice, we demonstrate a practical approximation to this online learning setup via adaptive Lempel-Ziv-style compression dictionaries to classify sequences in the text and malware domains.

We propose and study an online version of min-max optimization based on cumulative saddle points under a variety of performance measures beyond convex-concave settings. After first observing the incompatibility of (static) Nash equilibrium (SNE-Reg$_T$) with individual regrets even for strongly convex-strongly concave functions, we propose an alternate static duality gap (SDual-Gap$_T$) inspired by the online convex optimization (OCO) framework that is compatible with the individual regrets . We provide algorithms that achieve sub-linear regret bounds for (SDual-Gap$_T$) and the individual regrets and a novel dynamic saddle point regret (DSP-Reg$_T$), which we suggest naturally represents a min-max version of the dynamic regret in OCO. We derive our bounds for (SDual-Gap$_T$) and DSP-Reg$_T$ under strong convexity-strong concavity and a min-max notion of exponential concavity (min-max EC), and in addition we establish a class of functions satisfying min-max EC that captures a two-player variant of the classic portfolio selection problem. Finally, for a dynamic notion of regret compatible with individual regrets, we derive bounds under a two-sided Polyak-\L{}ojasiewicz (PL) condition.

We study sequential learning for classification metrics that are non-decomposable across instances and are general functions of the confusion matrix, such as the Jaccard index and the $F$-measure. The learner observes instances sequentially, makes irrevocable predictions, and is evaluated by the final empirical performance metric, leading to an online-regret objective. After observing the sequence, the learner also returns a classifier for future population use, leading to a population-regret objective. This single protocol connects two central frameworks for optimizing non-decomposable metrics: Expected Test Utility (ETU) and Population Utility (PU). For smooth concave utilities of the confusion matrix, we show that the ETU benchmark is controlled, in expectation, by the population PU comparator, and that an algorithm with small online regret also yields PU guarantees by an online-to-batch conversion. We then turn to non-concave linear-fractional metrics. We devise a general stochastic Dinkelbach-root method that tracks the relevant metric parameter online and gives online and population regret of order $n^{-1/2}$, up to logarithmic factors, with explicit dependence on conditional-probability estimation error. Our empirical studies evaluate these methods on benchmark datasets.

Conformal prediction is a framework that provides valid uncertainty quantification for general models with exchangeable data. However, in the online learning and time-series settings, exchangeability is not satisfied. Existing online conformal methods, such as adaptive conformal inference (ACI), can achieve long-run validity, yet they remain inefficient under covariate heterogeneity because they rely on global calibration. We propose *Online Localized Conformal Prediction (OLCP)*, which combines online adaptation with covariate-dependent localization to better reflect heterogeneity. To reduce sensitivity to the localization bandwidth, we further develop *OLCP-Hedge*, which performs bandwidth selection as an online expert aggregation problem using a constrained online convex optimization framework. Importantly, we provide coverage guarantees for both algorithms and demonstrate through simulations and real-data experiments that the proposed methods attain valid long-run coverage with narrower prediction intervals than existing baselines.

Online learning in non-stationary environments requires models to adapt rapidly from streaming data under strict computational constraints. A principled approach casts online learning as Bayesian state tracking, where model parameters are updated sequentially via Bayesian filtering. However, applying Bayesian filters directly to modern deep models is computationally prohibitive due to the high dimensionality of parameter space, forcing existing methods to rely on restrictive approximations or manually designed low-dimensional subspaces. In this work, we identify the absence of a suitable low-dimensional dynamical representation as the core bottleneck in Bayesian filtering-based online learning. Accordingly, we propose Adaptive Update through Representation Adaptation (AURA), a meta-learning framework that learns offline a low-dimensional latent state-space model governing the evolution of optimal model parameters under distribution shift. Online adaptation is then performed via extended Kalman filtering in this learned latent space followed by reconstruction of the full model parameters through a learned lifting map, enabling efficient single-step online adaptation while preserving model expressiveness. Evaluated on online adaptation of neural wireless receivers under time-varying channels and on non-stationary image classification, AURA shows substantial improvements in adaptation speed, accuracy, and computational efficiency over existing online learning and Bayesian filtering baselines, demonstrating that an adaptation-aware latent geometry is beneficial for effective Bayesian online learning in high-dimensional models.

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu, and Hazan (NeurIPS 2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding $\mathcal{O}(T^{2/3})$ regret. They left open whether the optimal $\Theta(\sqrt{T})$ regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves $\mathcal{O}(\sqrt{T})$ regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu, and Hazan by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers $\Omega(T)$ regret. Finally, we extend our analysis to one-point bandit feedback and prove a $\mathcal{O}(T^{3/4})$ expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.

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.

Online A/B tests are the dominant tool for evaluating new LLM variants in deployment: each user query arrives sequentially, must be routed to one variant before its outcome is observed, and is then scored against the alternative. In practice, these tests almost always use complete randomization. Yet for many queries, simple signals such as predicted difficulty, expected reward, or embedding-based scores are already available, and these are predictive of the outcome. Using them to guide assignment can substantially reduce the variance of the estimated treatment effect. We propose a new dyadic design that uses such covariates to balance treatment and control online across the full covariate distribution, with no hyperparameters to tune. Under stochastic arrivals, our design attains a covariate matching discrepancy of $O(\log^{3} T)$ in one dimension, which is a significant improvement over the $O(T^{1/4})$ rate of existing online stratified designs, and matches the offline minimax rate up to logarithmic factors in higher dimensions, closing a gap left open by prior work. Experiments on a sequential A/B test simulator built from AlpacaEval, in which 805 prompts are scored under two real LLM variants, confirm the theory: our design achieves a covariate matching discrepancy roughly $6\times$ smaller than complete randomization and consistently outperforms the best-tuned online stratified baseline. The method extends to multi-dimensional covariates and to general sequential evaluation pipelines.

We develop an online directional regression for sufficient dimension reduction with streaming data. Unlike first-moment methods, directional regression exploits both inverse conditional means and inverse conditional variances, and can therefore recover central subspace directions generated by linear structures, symmetric dependencies, and interaction driven relationships. Extending directional regression to the online setting is nontrivial because its kernel depends on slice-wise inverse moments and on standardization by an unknown covariance matrix. We address these challenges by utilizing a stable slice probability free kernel, a ridge-stabilized recursive least-squares estimator of the standardization operator, metric-aware subspace tracking under a vanishing-ridge covariance metric, and a weighted-bootstrap ladle criterion for online structural dimension selection. Under standard regularity conditions, the online kernel estimator is root-$t$ consistent, the estimated generalized eigenspace consistently recovers the central subspace, and the proposed dimension selector consistently estimates the structural dimension. Simulation studies and real-data analyses demonstrate that the proposed method serves as a robust online alternative when the dominant data structure is unknown, adapting to both first-moment and second-moment-driven dependencies while yielding substantial computational savings relative to repeated batch directional regression.

We study differentially private (DP) $k$-means and $k$-median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need to output a set of $k$ centers that optimizes the clustering objective for all points seen so far. We give a generic reduction that transforms the (sensitive) input stream into a private stream, which is a *semi-coreset* of the input stream. This implies that any (non-private) online clustering algorithm, run as a post-processing step, can achieve good utility for the original clustering objective. Our algorithm matches or improves upon the approximation ratio, space usage, and running time of existing algorithms (Dupr{\'{e}} la Tour, 2024; Epasto et al., 2026). A key aspect of our reduction is that it inherits desirable properties of the underlying non-private clustering algorithm, such as *consistency* (Lattanzi and Vassilvitskii, 2017)---a property not satisfied by previous DP algorithms.

Decision-focused learning (DFL) improves on the Predict-then-optimize (PtO) pipeline by training predictive models to minimize decision regret rather than prediction loss. Most DFL methods assume offline full-feedback data with complete action cost vectors. Many real-world decision systems instead operate in an online setting: in each round, the agent acts using past feedback and observes costs only for the selected components, yielding semi-bandit feedback. Bandit methods optimize regret in this regime, but train models with predictive updates rather than decision-focused updates. In this paper, we formalize online semi-bandit DFL: decision-focused learning for online optimization problems with semi-bandit feedback. The most straightforward extension would impute unobserved components with the model's own predictions and compute the decision-focused gradient. But this creates a self-confirming imputation degeneracy: imputation errors can flip counterfactual decisions that define the decision-focused gradient, biasing the representation update and reinforcing errors in later imputations. To address this degeneracy, we propose BayesianSPO, which combines an analytically updated Bayesian last-layer head with masked decision-focused learning. The Bayesian head supplies both (i) uncertainty to balance exploration and exploitation and (ii) stable imputations for unobserved components, while masking unobserved component gradients prevents those imputations from directly corrupting the representation update. Across knapsack, shortest-path, and portfolio benchmarks, BayesianSPO achieves the lowest mean cumulative regret on all five instances and the improvement is statistically significant on four of them.

With Large Language Model (LLM) pre-training and fine-tuning shifting its focus from data volume to data quality, quality data selection has emerged as a critical research topic. Existing online data selection methods for LLM training are typically ``batch-constrained'', limiting optimization to local utility within random batches. To overcome this, we propose GAIA (Global Adaptive Instruction tuning via GAussian processes), a framework that formulates data valuation as a global estimation process. GAIA employs Gaussian Process regression to model continuous utility manifolds across the semantic space, utilizing an adaptive strategy fusion mechanism to dynamically prioritize high-utility samples. By casting the strategy-posterior update as an instance of the classical fixed-share Hedge framework for tracking the best expert, we inherit a dynamic-regret guarantee that characterizes GAIA's robustness under non-stationary quality scores during training. Empirical evaluations on three datasets demonstrate that GAIA significantly outperforms state-of-the-art baselines like GREATS, establishing our method as a scalable and robust solution for efficient instruction tuning.

We consider a variant of the partially observed online control problem where there are _multiple sensors_ which provide noisy linear measurements of the system. In our setting, the system state evolves according to a discrete-time linear dynamical system. The objective is to design an algorithm which minimizes regret relative to the best _single-sensor_ policy (within a restricted class) in hindsight. When the system and process noise is stochastic and the costs are quadratic in the control and _unobserved state_, we design an algorithm that achieves $\mathcal{O}(\mathrm{poly}\log(S)\sqrt{n})$ regret over time horizon $n$ relative to our benchmark policy class if there are $S$ sensors. Notably, this regret guarantee is with respect to the _state costs_, which are never fully observed. When the system and process noise is chosen by an oblivious adversary, and the cost functions are convex-Lipschitz (or subquadratic) functions of the control and _observations_, then a similar $\mathcal{O}(\mathrm{poly}\log(S)\sqrt{n})$ regret is achievable. While our work is the first, to our knowledge, to study this generalization of the online control problem, we remark that a na\"ive application of known results in the partially observed online control literature have regret scaling $\mathcal{O}(\mathrm{poly}(S)\sqrt{n})$, exponentially worse than our regret scaling in terms of dependence on the number of sensors. Our algorithm is based on the Follow-The-Regularized-Leader framework, and our analysis carefully exploits the $\ell_1$ geometry of the policy class.

Online change-point detection is a fundamental problem in sequential monitoring, where the goal is to detect distributional changes in a time series as quickly as possible while controlling false alarms. We propose a general framework for online change-point detection that leverages foundation probabilistic forecasters, such as Chronos-2, which can capture complex temporal structure including trend, seasonality, heteroskedasticity, and nonlinear dependence. Our approach transforms each incoming observation relative to its predictive quantile forecast into an approximately standard Gaussian monitoring statistic, which can then be used in classical sequential detection procedures such as CUSUM and MOSUM. To reduce adaptation of the forecaster to post-change observations, we introduce a buffer between the forecasting context window and the forecast target. Because this design can induce serial dependence in the monitoring statistics, we develop a parametric bootstrap procedure to calibrate critical thresholds and control false alarms in practice. Extensive simulations across data-generating processes involving non-normality, trend, seasonality, heteroskedasticity, and autoregressive dependence show that the proposed method achieves competitive detection performance relative to benchmark procedures, while requiring no explicit specification of a parametric pre-change model.

Large-scale networked systems are increasingly controlled through a small number of global configuration variables while their local controllers remain black-box, adaptive, and mutually interfering. The operator observes only post-burn-in telemetry, so neither independent-unit causal estimators nor immediate-feedback bandits directly apply. We propose \emph{CAUSAL-UCB}, a causal-optimistic framework for online steady-state configuration. The framework turns raw network operation into a linked pipeline: an exposure interface maps neighborhood interference into an auditable context; measurement-level exploration creates overlap while the target remains the no-exploration steady-state value $\Winf(z;0)$; a clipped doubly robust evaluator converts exploratory logs into value certificates; and an OFU rule selects the next configuration. We prove a unified high-probability deviation bound that decomposes statistical fluctuation, nuisance product error, clipping bias, exposure approximation, cross-configuration mismatch, context shift, and residual dependence. We also give an identification--deployment frontier showing that reliable counterfactual identification and low deployment cost cannot be optimized independently. Controlled semi-realistic replay and real-data-driven semi-synthetic replay on METR-LA and FlockLab validate the resulting benefit--reliability trade-off across regret, optimality gap, ATE error, confidence width, deployment gap, sensitivity, ablation, and frontier visualizations.

Brain–computer interfaces (BCIs) must continually adapt as neural signals drift, yet labeled calibration data is expensive to collect at time of use. Recent systems address this challenge by updating neural decoders using language-model–pseudo-labels, but they treat the pseudo-label as ground truth. We reinterpret recalibration as approximate Bayesian filtering: the decoder parameters are the latent states, and language models provide observations in the form of unnormalized potentials. Guided by this analysis, we introduce \textbf{B-CORP} (Bayesian Continual Online Recalibration with Pseudo-labels). B-CORP replaces hard pseudo-labels with a soft top-$K$ marginalization, increases the number of iterations in the coordinate ascent on the joint likelihood, and models parameter drift with a prior on latent dynamics. Across synthetic drifting regression tasks and real BCI benchmarks, including handwriting and speech BCI datasets, B-CORP attains word error rates consistently under 3\% on a difficult handwriting BCI dataset. B-CORP improves almost 30\% versus the state-of-the-art, while retaining performance even with poor pseudo-labels where naive methods fail. More broadly, our approach connects pseudo-label recalibration with online Bayesian inference, providing a principled foundation for problems requiring long-term recalibration with access to black box predictive models, such as LLMs, for use as strong priors over the labels.