NeurIPS 2026 Papers

Safe exploration remains a fundamental challenge in reinforcement learning (RL), limiting the deployment of RL agents in the real world. We propose _Sampling-Based Safe Reinforcement Learning_ (SBSRL), a model-based RL algorithm that maintains safety throughout the learning process by enforcing constraints jointly across a _finite_ set of dynamics samples. This formulation approximates an intractable worst-case optimization over uncertain dynamics and enables practical safety guarantees in continuous domains. We further introduce an exploration strategy based on constraining epistemic uncertainty, eliminating the need for explicit exploration bonuses. Under regularity conditions, we derive high-probability guarantees of safety throughout learning and a finite-time sample complexity bound for recovering a near-optimal policy. Empirically, SBSRL achieves safe and efficient exploration both in simulation and in real-world experiments, and readily extends to practical deep-ensemble implementations that scale to high-dimensional continuous control problems.

We study estimating rare-event probabilities $I = \mathbb{P}(g(\mathbf{X}) > \gamma)$ with $\mathbf{X} \sim \mathcal{N}(\mu, \Sigma)$ and general $g : \mathbb{R}^d \to \mathbb{R}$. We address this problem through importance sampling, and propose a framework that substantially improves efficiency and robustness over baselines such as crude Monte Carlo, adaptive cross-entropy, variational-inference-based methods (including forward- and reverse-KL approaches), as well as Safe-ICE, Subset Simulation, and Sequential Monte Carlo, *drawing* on ideas from both cross-entropy methods for rare-event estimation and cross-entropy methods for optimization. The key contribution has two parts: first, we separate the problem into *coverage*, to overcome the cold-start barrier, and *fitting*, to refine proposals once a meaningful signal is available; second, we constrain the proposal family in a way that provably guarantees finite-variance importance sampling, supported by a theoretical result (since coverage alone is not sufficient --- without safeguards, importance sampling may still suffer from infinite variance). Together, these ingredients yield proposals that are both expressive and stable. Extensive experiments demonstrate significant variance reduction, strong robustness across diverse benchmarks, and favorable cost--efficiency trade-offs, with the proposed approach often outperforming these baselines, particularly in high-dimensional and multimodal settings where competing methods frequently become unstable or fail.

We study the sample complexity of noisy one-bit compressed sensing for signals drawn from a prior distribution. By characterizing the effective distributional complexity of the prior via its approximate covering number, we prove that posterior sampling achieves accurate recovery with high probability when the number of measurements scales with the logarithm of the approximate covering number, up to a one-bit separation gap factor. This upper bound is robust to learned prior mismatch. Specifically, we show that posterior sampling with an approximate prior remains reliable, provided that the learned prior distribution is sufficiently close to the true signal distribution in Wasserstein distance. In addition, we establish a sample complexity lower bound for any reliable method of noisy one-bit compressed sensing, showing that our upper bound is nearly matched in its main prior dependent term. To approximate the ideal posterior sampling process for real world scenarios, we instantiate posterior sampling through a plug-and-play algorithm with diffusion priors. Experiments on the FFHQ and ImageNet datasets demonstrate the effectiveness of our proposed approach.

Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for $d$-dimensional distributions, given access to score estimates with polynomial accuracy $\varepsilon=d^{-O(1)}$ (in any $L^p$ sense), any sampling algorithm requires $\widetilde{\Omega}(\sqrt{d})$ adaptive score queries. In particular, our proof shows that any sampler must search over $\widetilde{\Omega}(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Computing Shapley values exactly requires exponentially many evaluations of a cooperative value function, making approximation essential in high-dimensional applications. Recent leverage-score-based methods yield provably accurate estimators with sample complexity scaling linearly in the number of players, but this can still be too costly when only a small subset of players is truly influential. We study Shapley value estimation under a sparse influence model, where the Shapley vector is supported on an unknown set of size $s \ll n$. Using the regression characterization of Shapley values, we propose a sparse leverage sampling scheme and analyze it via sparse matrix concentration. Our main result shows that the resulting estimator achieves relative-error approximation with $\widetilde{O}(s^2)$ value function evaluations, up to logarithmic and accuracy factors, thereby replacing the ambient-dimension dependence of prior guarantees with dependence on the intrinsic support size. Empirically, our method matches or improves over dense Leverage SHAP on sparse synthetic and real-data benchmarks, while exhibiting better numerical stability at small sample sizes.

Diffusion models cannot enforce hard constraints, yet applications in the physical sciences demand exact satisfaction of conservation laws, boundary conditions, and observational consistency. In this work, we identify a corrector kernel whose unique stationary distribution is the constrained marginal at each noise level, and approximate it by iteratively projecting through the denoiser and renoising via the forward kernel. The resulting Predict-Project-Renoise (PPR) algorithm enables sampling from pretrained diffusion models under hard constraints. Its three components are each necessary: projecting through the denoiser keeps samples close to the data manifold, while renoising and iterating drive samples toward the constrained marginal. On 2D distributions, the Kuramoto-Sivashinsky equation, and global weather forecasting with a $10^8$-dimensional atmospheric model, PPR simultaneously achieves low constraint violations and high distributional fidelity, a combination that existing methods fail to deliver.

We introduce P-IMLA, a preconditioned implicit-midpoint Langevin sampler for high-dimensional log-concave targets with non-smooth regularization. The obstruction is that the large steps enabled by matrix preconditioning are precisely where preconditioned Euler--Maruyama inflates stationary variance. Implicit midpoint removes this surplus via a Cayley-transform identity, making P-IMLA Gaussian-exact at any step size. Beyond Gaussians, a Möbius-monotonicity argument gives an $M$-Wasserstein rate governed by $\kappa_{\rm eff}$ rather than the $\kappa_f$ of unpreconditioned IMLA, while backward-error analysis shows drift-only rather than Euler-type diffusion bias. An $M$-norm Moreau envelope yields a proximal non-smooth variant with a three-term error budget. Controlled Gaussian and TV-regularized imaging experiments confirm the predicted separation: the unpreconditioned IMLA degenerates as $\kappa_f$ grows, whereas P-IMLA remains $\kappa_{\rm eff}$-governed and near variance-exact.

Recent analyses question whether reinforcement learning (RL) is responsible for strong reasoning in large language models (LLMs). At the same time, distillation and inference-time sampling, including power sampling, have emerged as effective ways to improve LLM performance. However, the relationship among RL, distillation, and sampling remains unclear. In this study, we focus on the power distribution, the target distribution of power sampling, and show that the power distribution bridges sampling, self-reward KL-regularized RL, and self-distillation. From the sampling perspective, we show that inexpensive local approximations cannot reproduce sequence-level power without information about possible suffixes. From the RL perspective, the power distribution is the closed-form optimizer of KL-regularized RL when the model's sequence-level log-probabilities are used as the reward. This identification leads to \emph{power self-distillation}, an offline distillation surrogate that shares the same target distribution and amortizes the cost of power sampling into supervised training on teacher samples. We further show that power self-distillation can achieve self-reward sharpening, while improvement in a downstream true reward is governed by the covariance between true reward and self-reward under the power distribution. Experiments on reasoning tasks support our analysis: power sampling raises self-reward, true-reward gains depend on alignment with self-reward, and power self-distillation can match or exceed the performance of power sampling at much lower inference cost.

Reinforcement learning (RL) is well known to be data-intensive, and recent works have proposed leveraging data from similar systems to improve sample efficiency. In this work, we focus on the collaborative Linear Quadratic Regulator (LQR) setting and study the problem of learning under heterogeneous system dynamics. Due to the presence of a heterogeneity-induced additive bias, most existing collaborative methods are suitable only for low heterogeneity regimes and exhibit suboptimal performance under large heterogeneity. Based on the principle of Thompson sampling (TS), we propose an algorithm that, by leveraging data from other agents, yields a \emph{personalized} controller for every agent without incurring any additive heterogeneity-induced bias, i.e., with sublinear Bayes regret even under large heterogeneity. Under high heterogeneity regimes, we establish that our algorithm incurs $\tilde{\mathcal{O}}( T^{1-0.5\epsilon}\sqrt{\Delta})$ cumulative regret, where $T$ denotes the time horizon, $\epsilon\in[0,1]$ is a user-defined personalization parameter, and $\Delta$ denotes an upper bound on the maximum dissimilarity among the agents' dynamics. Our algorithm and analysis also generalize the special case of no heterogeneity. In particular, under no heterogeneity, we establish that our algorithm incurs $\mathcal{O}(\sqrt{T/M})$ cumulative regret. From a distributed implementation perspective, our method incurs only logarithmic communication overhead. Additionally, our algorithm outperforms methods that do not personalize data from other agents and, in certain regimes, also outperforms methods that do not utilize any data from other agents.

Entropy-regularized optimization problems arise in various areas of machine learning, including mean-field neural networks, variational inference, and reinforcement learning. Mean-field Langevin dynamics (MFLD) is a dynamics capable of sampling from the optimal solution of such problems under appropriate conditions, and has been the subject of extensive recent research. As machine learning models grow in scale and parameter dimension, computational efficiency becomes increasingly important, especially in reducing the adaptive complexity of computation of MFLD, that is, the number of sequential rounds they require. In this work, we initiate the study of the adaptive complexity of MFLD and provide the first theoretical evidence that MFLD can indeed be accelerated through parallelism. In particular, we provide polylogarithmic convergence guarantees for both the infinite-particle and finite-particle setting under the log-Sobolev inequality.

Flow matching and diffusion models achieve high-quality generation by solving continuous-time generative dynamics, but their sampling remains inherently sequential and costly. Parallel sampling reduces wall-clock latency, yet often requires many function evaluations (NFEs) due to inaccurate future-state initialization and repeated correction. We propose ParaPC-FM, a fixed-point predictor--corrector framework that unifies high-order solver correction and future-state initialization, enabling both components to be incorporated into different parallel samplers. In particular, our UniP-based truncated initialization reuses past velocity predictions to estimate future states more accurately, reducing correction iterations and NFEs with almost no additional overhead. On a ParaDiGMS-style framework, ParaPC-FM achieves up to $1.25\times$ and $1.49\times$ speedups on FLUX.1-dev at $50$ and $100$ steps, and up to $1.22\times$ and $1.16\times$ speedups on Stable Diffusion 3 and Stable Diffusion 3.5 at $50$ steps. When integrated into ParaTAA, the proposed initialization further achieves up to $1.17\times$ speedup at $50$ steps. Importantly, these acceleration gains are obtained while keeping image quality nearly unchanged.

Reinforcement learning (RL) has become an effective way to improve prompt alignment and perceptual quality in diffusion and flow-matching generators. A critical step for applying online RL to flow matching is turning the deterministic sampling trajectory into a stochastic policy, typically by replacing the reverse-time Ordinary Differential Equation (ODE) with a Stochastic Differential Equation (SDE). The stochastic sampler, controlling the exploration behavior and denoising dynamics, is thus part of the policy, and its design can significantly affect the reward optimization performance. We break down the sampler design into two interdependent components: choosing the right amount of stochastic exploration, and discretizing the resulting SDE faithfully at the small step counts used in RL. To address the first component, we analyze the inherent tension between exploration and stability in denoising and derive an SDE schedule that balances the two. Turning to the discretization challenge, we use a toy example to show that existing samplers can deviate from the flow-matching process, either by introducing excessive discretization noise or by relying on heuristic rules that do not guarantee convergence to the data distribution. To address these issues, we propose \textsc{Precise}, a new stochastic sampler that balances effective exploration with stability. Crucially, \textsc{Precise} keeps the denoising trajectory SDE-consistent through a novel approximation that freezes the clean-latent posterior mean, resolving the excess noise issue in standard samplers. Extensive experiments demonstrate that this formulation leads to significantly faster and more stable reward optimization via reinforcement learning, achieving state-of-the-art alignment scores (e.g., PickScore, HPSv2.1) while requiring 13.1--53.2\% less wall-clock training time to match the best in-domain performance of prior samplers.

Diffusion image generators owe much of their practical success to accurate denoising networks and strong numerical samplers. Yet the two components are not fully matched. During sampling, the denoiser is asked to make predictions based on imperfect noisy states formed by model predictions that differ from the training noisy states formed by real data. This train-test gap, known otherwise as exposure bias in literature, caps image generation quality (i.e., blurry, lacking in details or unnaturally-shaped). To mitigate the problem, we propose PEEK, a training-free deterministic sampler plugin. At each eligible denoising step, PEEK first performs a provisional one-step update, evaluates the denoiser once at the look-ahead state, and either keeps the current clean prediction or replaces it with this one-step-later prediction to form the actual noisy state. By taking the additional step, we generally obtain a higher-signal, more-image-like prediction for the noisy state, mitigating the exposure bias. To optimize the replacement positions, PEEK searches for a binary replacement schedule with a greedy metric-driven search made efficient by the PEEK prefix and baseline noise-schedule-rebasing caches; for a 9-step search, the caches reduce the one-candidate worst-case vanilla denoiser-evaluation count by 69.3\%. Across pixel-space and latent-space diffusion models with unconditional, label-guided, and text-guided settings on CIFAR-10, CelebA-HQ, LSUN Bedroom, ImageNet, and MS-COCO datasets, PEEK improves over NFE-matched DPM-Solver++ and DEIS baselines, with five-run mean FID reductions up to 39.3\% under the same deployment cost. Code will be released.

Diffusion models have emerged as powerful learned priors for Bayesian inverse problems (BIPs). Diffusion-based solvers rely on a presumed likelihood for the observations in BIPs to guide the generation process. Likelihood misspecification is common in practical BIPs and is known to degrade recovery performance, particularly under outlier contamination. We investigate this problem by first characterizing the induced posterior deviation and proving the stability of diffusion-based solvers for linear BIPs. Our stability analysis further reveals potential robustness deficiencies of existing diffusion-based solvers under outlier-contaminated measurements. To address this issue, we propose a simple yet effective solution: robust diffusion posterior sampling, which is provably outlier-robust for linear BIPs and compatible with existing gradient-based posterior samplers. Empirical results from scientific inverse problems and natural image tasks demonstrate the effectiveness and robustness of our method, with consistent performance gains in challenging scenarios involving outlier contamination for both linear and nonlinear tasks.

We prove optimal sampling bounds achieving $(1\pm\varepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove $k^2/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_2/k$ regularization, and $k/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_1/k$ regularization. For $\|\cdot\|_2^2/k$ regularization, the sampling complexity depends mainly on a bounded derivative property: if $|g'(x)|\leq g(x)$, and $g(0)>0$, and $g$ is monotonic or convex, then it admits linear in $k$ sampling complexity; otherwise the general bound is $k^2/\varepsilon^2$. However, if $g(0)=0$, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic $k^3/\varepsilon^2$ sensitivity sampling bounds of (Alishahi and Phillips, ICML'24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.

We address the problem of evaluating machine learning models under a limited labelling budget in streaming environments, where data arrive sequentially. This setting is particularly critical for embedded and continuously deployed systems, such as autonomous driving or computer-aided diagnosis, where models must reliably assess their own performance online. We focus on a constrained online setting, where labelling decisions must be made immediately, and data cannot be stored. We introduce an \emph{online active testing} (OAT) framework based on an adaptive importance sampling estimator that provides unbiased risk estimation for both regression and classification tasks. While importance sampling has been extensively studied in pool-based settings, we establish novel theoretical ground for the fully online setting, including deviation bounds and consistency guarantees. We derive an optimal sampling strategy in order to minimise the estimator's variance, which is driven by the expected second moment of the loss. This strategy is expressed for common loss functions, including mean squared error, mean absolute error, 0–1 loss, and log-loss, and analysed from a statistical perspective. We empirically demonstrate the effectiveness of OAT on synthetic benchmarks, deep learning tasks, and a real-world application involving the evaluation of machine learning models for molecular simulations, where data are generated sequentially, and labels require expensive quantum chemistry computations, showing improved efficiency and reliable performance estimation under limited labelling budgets. In particular, on the real-world task, OAT requires only $\sim$30\% of labels to match the accuracy of a naïve uniform baseline, compared to $\sim$23\% for an oracle method that has access to the labels.

Differential Privacy (DP) provides a rigorous framework for quantifying privacy guarantees. While most methods achieve DP by injecting calibrated random noise, the intrinsic randomness of certain procedures such as sampling can yield DP guarantees ``for free''. In this work, we develop a unified R\'enyi divergence framework to characterize the inherent DP guarantees of sampling from a Bayesian posterior distribution. We show that the privacy loss incurred by One-Posterior-Sampling (OPS) is governed by posterior exponential moments of the single-record log-likelihood ratio, and establish explicit DP guarantees under uniformly bounded, sub-Gaussian, or sub-exponential tail regimes. We apply the framework to representative Bayesian models, including categorical likelihoods with arbitrary priors, Gaussian-Gaussian conjugate pair, generalized linear models from the exponential family and linear regression with Gaussian likelihood, both with Gaussian priors on the regression coefficients. Our results elucidate sample size, model structure, neighboring relations in DP (bounded or unbounded), and how prior if applicable, jointly determine the inherent DP guarantees of OPS. Furthermore, our results recover the existing DP guarantees for OPS as special cases -- often with tighter privacy loss bounds -- and substantially broaden the class of Bayesian models for which the inherent DP guarantees of OPS can be rigorously characterized.

This paper studies concentration inequalities for sampling without replacement. We introduce a general inequality that provides simple guidelines for proving concentration inequalities, offers a degree of unification of existing results, and is strong enough to yield sharper bounds. As applications, we revisit several standard statistics and either recover classical inequalities through streamlined proofs or strengthen them to tighter bounds, with rates optimal up to constants.

Protein structure prediction has progressed rapidly, with a flourishing ecosystem of open-source AlphaFold (AF)-style systems delivering real progress. But isolating which architectural and training choices actually drive that progress is difficult. Production-scale training is both computationally prohibitive and not accessibly reproducible; moreover, the public corpora are complex, with structural biases that compound in parameter- and compute-constrained regimes. To address these gaps, we introduce NanoFold, a compact, fixed-data benchmark for AF-style training studies. Its sealed-hidden tracks address three fundamental questions, with a $\textit{limited}$ track for sample efficiency, a $\textit{research large}$ track for whether early gains persist under more optimization, and an $\textit{unlimited}$ track for best fixed-data final performance. NanoFold's split is designed rather than naively sampled, with chains grouped into biological units under MMseqs2 cluster and PDB-entry disjointness, stratified across structural metadata, and allocated to $10{,}000$ training, $1{,}000$ public-validation, and $1{,}000$ sealed hidden chains. We verify the construction through statistically principled diagnostics, including a randomization study over $1{,}000$ alternative valid splits, confirming the dataset is diverse, well-distributed, and statistically typical of its constraint class. We use NanoFold to run comprehensive experiments on model behavior across scales and training regimes, demonstrating that the benchmark is learnable but unsaturated, scales predictably with budget, cleanly separates training primitives, and that the underlying codebase flexibly supports head-to-head comparison. NanoFold makes architectural and training progress in protein structure prediction more transparent, comparable, and reproducible at a compute-accessible scale.