NeurIPS 2026 Papers

We study classification and regression tasks under label differential privacy (label-DP), a setting where only the labels are considered sensitive information. We quantify the "price of locality" by revealing fundamental statistical gaps between local and central privacy models. For classification, we establish a strict separation in accuracy. Specifically, we prove that the minimax excess risk in the local model is lower bounded by $\Omega(\frac{1}{\epsilon}\sqrt{\text{VC}(\mathcal{H})/n})$ for classification on size-$n$ dataset, a fundamental limitation that holds even under relaxed approximate $(\epsilon, \delta)$-local DP. Overcoming this barrier, we propose the first *efficient* central-model algorithm that operates under the stricter pure $\epsilon$-DP, yet achieves a significantly improved upper bound of $\tilde{O}(\sqrt{\text{VC}(\mathcal{H})/(\epsilon n)})$. For linear regression, we show that local randomizers or naive central-DP approach algorithms are statistically inefficient. Instead, we turn to the Matrix Mechanism and use an encoder-decoder framework built on ridge regression, which projects the data into a spherical latent space before injecting noise. This structural design effectively isolates and exponentially suppresses the severe noise inflation typically caused by ill-conditioned feature covariance matrices in full-DP (Cai et al., The Annals of Statistics, 49(5)), achieving an optimal privacy penalty of $\tilde{O}({d^2}/({n^2\epsilon^2}))$ where $d$ is the feature dimension.

We study optimal design of $\varepsilon$-locally differentially private mechanisms for binary hypothesis testing. Each observation is drawn from one of two known distributions $P_0,P_1$ on a finite alphabet of size $k$, privatized by a mechanism $Q$, and then used to infer which distribution generated the data. We measure testing utility using an $f$-divergence—including total variation, KL, and hockey-stick divergences—between the two induced output distributions. Previous work established structural properties of optimal mechanisms, but only yielded exponential-time algorithms. We prove a sharp structure: for every $\varepsilon$ and every $f$-divergence objective, after sorting the alphabet by likelihood ratio, there exists an optimal mechanism that partitions the sorted alphabet into contiguous blocks and applies randomized response to the block label. We call this class Sort–Partition–Randomize (SPR). This characterization yields an exact dynamic program that computes an optimal mechanism in $O(k^3)$ time, and more generally in $O(\ell k^2)$ time with an $\ell$-output budget. Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond asymptotic privacy regimes.

We present the first algorithms for generalized linear contextual bandits under shuffle differential privacy and joint differential privacy. While prior work on private contextual bandits has been restricted to linear reward models---which admit closed-form estimators---generalized linear models (GLMs) pose fundamental new challenges: no closed-form estimator exists, requiring private convex optimization; privacy must be tracked across multiple evolving design matrices; and optimization error must be explicitly incorporated into regret analysis. We address these challenges under two privacy models and context settings. For stochastic contexts, we design a shuffle-DP algorithm with regret $\tilde{O}\!\big(d^{3/2}\sqrt{T \log T} + d^{5/4} \sqrt{T/\varepsilon} (\log T)^{3/4}\big)$ in the dominant term, matching the non-private rate $\tilde{O}(d \sqrt{T \log T})$ in the leading-in-$T$ term up to a multiplicative factor of $\sqrt d$ and a privacy correction term of $\tilde{O}(d^{5/4}\sqrt{T \log T/\varepsilon})$. For adversarial contexts, we provide a joint-DP algorithm with regret $\tilde{O}\!\big(d\sqrt{T}\log T + d^{3/4}\sqrt{T/\varepsilon}\,(\log T)\,(d+\log T)^{1/4}\big)$ matching the non-private rate $\tilde{O}(d\sqrt{T}\log T)$ in the leading term. Unlike prior work on locally private GLM bandits, our methods require no spectral assumptions on the context distribution beyond $\ell_2$ boundedness.

Neural networks with randomly generated hidden weights (RaNNs) have been extensively studied, both as a standalone learning method and as an initialization for fully trainable deep learning methods. In this work, we study RaNN expressivity for learning solutions to non-linear partial differential equations (PDEs). Despite their widespread use in practical applications, a rigorous theoretical understanding of the approximation properties of RaNNs in this context remains limited. Here, we derive error bounds for RaNN approximations to time-dependent Sobolev functions and obtain a dimension-free approximation rate $\frac{1}{2}$ for sufficiently regular functions. We apply our results to two important classes of non-linear PDEs: Porous Medium Equations and Compressible Navier-Stokes Equations, showing that RaNNs are capable of efficiently approximating solutions to these complex, non-linear PDEs. Our theoretical analysis is supported by numerical experiments, validating the obtained convergence rates.

Randomized smoothing provides a powerful framework for certifying robustness against adversarial perturbations by injecting randomized noise either into the training process (against poisoning attacks) or model inputs (against evasion attacks). Yet, extending these guarantees to hold against backdoor attacks, where adversaries jointly perturb both training and test data, remains challenging. In particular, certifying general mechanisms requires tight, compositional guarantees over heterogeneous randomized components, which are not jointly supported by existing approaches. We address this gap by proposing a general framework that numerically composes robustness guarantees for arbitrary mechanisms while remaining tightly connected to black-box randomized smoothing guarantees. To achieve this, we establish a connection between randomized smoothing and the dual perspective of differential privacy, enabling us to leverage advances in the analysis of differentially private mechanisms together with tight numerical composition. This yields a modular framework in which robustness guarantees are derived by reasoning about the privacy of individual components and composing them end-to-end. We instantiate our framework for DP-SGD and Deep Partition Aggregation with inference-time smoothing, deriving joint robustness guarantees against both training-time and inference-time attacks. Empirically, we demonstrate the effectiveness of our framework on MNIST and CIFAR-10. Overall, we provide a principled and general framework for certifying robustness under complex joint threat models and mechanisms, laying the groundwork for future research on unified certification methods towards guarantees under more complex real-world adversaries.

We introduce **PD-RAG**, a technique for retrieval-augmented generation (RAG) that leverages a language model's own randomness to safeguard privacy. The algorithm partitions documents into groups, generates a candidate answer from a randomly chosen group, and then uses a privacy test to enforce that the released answer could have been produced by multiple disjoint document groups, thereby ensuring a controllable degree of *plausible deniability*. Compared to existing methods that operate at the token level and therefore incur both substantial utility loss and growing privacy budget per generated token, PD-RAG operates at the answer level, so the privacy it offers does not loosen with output length. We prove that PD-RAG satisfies $(\varepsilon,\delta)$-differential privacy. We experimentally evaluate PD-RAG on three QA benchmarks using three language models and find that it reduces membership inference attack advantage to near random while consistently outperforming alternative methods on all four utility metrics we used and running between $17$ and $33{\times}$ faster.

Traditional differential privacy assumes each training example affects only one user's privacy, but many real-world datasets contain examples attributed to multiple users. We study \emph{fixed-graph differential privacy}, a framework for learning from such multi-attribution data where the attribution structure is public but example contents are private. We establish fundamental limits and optimal algorithms for this setting. First, we develop approximation algorithms for the NP-hard contribution bounding problem: a sampling-based LP-rounding algorithm achieving $O(|V|^{1/(k+1)})$-approximation and a greedy algorithm achieving $O(r)$-approximation, where $r$ is the maximum number of users per example. We prove matching hardness results showing the greedy bound is tight up to $O(\log r)$ factors. Second, we introduce a \emph{network density parameter} $c$ that measures how concentrated the attribution network is, and establish information-theoretic error lower bounds scaling as $\tilde\Omega(c^2d/\varepsilon^2)$ for learning $d$-dimensional models from $n$ examples. We provide matching upper bounds using contribution bounding combined with DP-SGD, demonstrating our algorithms are optimal. We further characterize when contribution bounding introduces selection bias and provide conditions under which bias vanishes. Finally, we extend our analysis to the i.i.d. setting where examples are sampled from a distribution, obtaining improved bounds scaling as $\tilde{O}(\sqrt{c/n})$ for hypothesis testing and providing matching algorithm for clustered networks.

We propose a simple framework for constructing differentially private confidence regions _in one shot_, i.e., by adding noise only to the final resampling quantile instead of privatizing the estimator computed on each resample. The cost of privacy of our procedure is $O(\log B)$ under with-replacement ($m$-out-of-$n$) sampling and independent of $B$ under without replacement sampling (subsampling), avoiding the $\sqrt{B}$ factor that arises in previous works. We provide _nonasymptotic_ Gaussian Differential Privacy (GDP) and utility guarantees for both subsampling and $m$-out-of-$n$ resampling, covering mean-like estimators with small global sensitivity as well as estimators admitting efficiently computable _smooth sensitivity_ bounds, including quantiles and degenerate U-statistics. This allows us to also obtain private confidence regions for degenerate U-statistics where the private error is much smaller than the non-private error. In all, we provide a toolbox for widely applicable DP uncertainty quantification procedures under popular resampling strategies while avoiding the computational and privacy costs of privatizing many intermediate resample statistics.

We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE) with $\ell_1$, $\ell_2$ and $\ell_p^p$ kernels. This new DP data structure offers not only improved privacy-utility tradeoff but also better query efficiency over prior results. Specifically, we study the mathematical problem: given a similarity function $f$ (or DP KDE) and a private dataset $X \subset \mathbb{R}^d$, our goal is to preprocess $X$ so that for any query $y \in \mathbb{R}^d$, we approximate $\sum_{x \in X} f(x, y)$ in a differentially private fashion. The best previous algorithm for $f(x, y) = |x - y|_1$ is the node-contaminated balanced binary tree by [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. Their algorithm requires $O(nd)$ space and time for preprocessing with $n = |X|$. For any query point, the query time is $\alpha^{-1} d \log^2 n$, with an error guarantee of $(1+\alpha)$-approximation and $\varepsilon^{-1} \alpha^{-0.5} d^{1.5} R \log^{1.5} n$. In this paper, we use the same space and pre-processing time, improve the best previous result [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] in three aspects - We reduce query time by $\alpha^{-1} \log n$ factor - We improve the approximation ratio from $\alpha$ to $1$ - We reduce the error dependence by a factor of $\alpha^{-0.5}$ From a technical perspective, our method of constructing the search tree differs from previous work [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. In prior work, for each query, the answer is split into $\alpha^{-1} \log n$ numbers, each derived from the summation of $\log n$ values in interval tree countings. In contrast, we construct the tree differently, splitting the answer into $\log n$ numbers, where each is a smart combination of two distance values, two counting values, and $y$ itself. We believe our tree structure may be of independent interest.

Partial differential equations (PDEs) are central to modeling physical and engineering systems, but repeatedly solving parametric PDEs remains computationally expensive. Operator learning enables fast surrogate inference, yet typically requires large input–output paired datasets generated by costly high-fidelity PDE solvers. Unsupervised operator learning frameworks alleviate data dependency but remain hindered by computational bottlenecks. To address this, we propose Neural Variational Quantum Linear Solver (NVQLS), the first hybrid quantum–classical operator learning framework leveraging the Legendre-Galerkin weak formulation. We critically resolve the sign ambiguity in VQLS energy minimization, preventing erroneous solution representations. Additionally, we introduce a neural embedding, a novel encoding scheme to map varying forcings and PDE coefficients into parameterized quantum circuit representations. These structural innovations provide theoretical computational complexity advantages under efficient state preparation schemes, while achieving superior accuracy compared to a representative classical baseline. Validations on 1D and 2D parametric PDEs under diverse boundary conditions demonstrate NVQLS's capability to simultaneously process varying inputs, offering a scalable unsupervised approach to quantum-enhanced operator learning.

Fractional differential equations (FDEs) excel at modelling systems with long-range memory, while stochastic differential equations (SDEs) capture inherent randomness. Existing neural differential equation models address either memory (Neural FDEs) or stochasticity (Neural SDEs), but a unified framework combining both with a learnable scalar memory exponent and an efficient adjoint remains absent. We introduce the Neural Fractional Stochastic Differential Equation (Neural FSDE), which learns continuous-time dynamics with both memory and randomness from data via a Caputo FSDE with neural drift, neural diffusion, and a learnable fractional order. To enable scalable training, we derive a discrete adjoint method that computes gradients with respect to the initial state, the drift and diffusion network parameters, and the fractional order, with memory cost independent of the autograd graph depth. We validate the framework on two real-world domains. On the stochastic-fractional COVID-19 model of Bonyah et al., the NeuralFSDE provides the first end-to-end real-data calibration under a rolling-origin forecasting protocol, recovering a fractional order less than 1. On S&P~500 index option pricing, we recast rough Bergomi, rough Heston, Neural SDE, and NeuralFSDE as Caputo-FSDE special cases under a single calibration pipeline; the NeuralFSDE achieves the lowest implied-volatility error across schedules and instruments, with a matched-architecture comparison against the memoryless Neural SDE, isolating the contribution of fractional memory. Code is available at https://anonymous.4open.science/r/NeuralFSDE.

Most physical systems are governed by nonlinear partial differential equations, yet the analytical tools that make linear systems transparent, such as eigenspectra, dispersion relations and modal decomposition, remain unavailable in nonlinear settings. We introduce Lie Generator Network-Koopman (LGN-KM), a neural operator that lifts nonlinear dynamics into a linear latent space and learns the continuous-time Koopman generator through the decomposition $L_k = S - D_k$, where $S$ is skew-symmetric (conservative coupling) and $D_k$ is positive-definite diagonal (mode-selective dissipation). The decomposition guarantees stability by construction and exposes the eigenstructure directly, making linear-systems analysis available on a nonlinear PDE. On 2D Navier-Stokes turbulence, the generator recovers a complete multi-branch dispersion relation and the viscous dissipation scaling $\mathrm{Re}(\lambda) \propto -|k|^2$ from trajectory data alone, with no physics supervision. The same architecture recovers the analogous diffusive scaling on FitzHugh-Nagumo reaction-diffusion without modification. Independently trained models at different regimes show matched gauge-invariant spectral structure. The architecture additionally enables long-horizon stability, $O(1)$ continuous-time evaluation, and physics--informed cross-regime model transfer.

We study regret minimization for time-homogeneous episodic tabular reinforcement learning with $S$ states and $A$ actions under non-interactive $\epsilon$-local differential privacy (LDP). In each episode $k \in [K]$, the decision-maker sends a policy to a user, the user executes the policy for $H$ steps, and sends an $\epsilon$-locally differentially private message back to the decision-maker. When $H=1$, the problem reduces to an LDP contextual bandit with $S$ contexts, $A$ arms and horizon $K$. We prove that the minimax regret is $\min\bigg(K, \frac{ \sqrt{\max( S, \exp(\epsilon) + 1) S A K (\exp(\epsilon) + 1)}}{\exp(\epsilon) - 1}\bigg)$, up to constants and a $\sqrt{\log(A)}$ factor. The upper bound is achieved by an adaptation of EXP3 and a unary encoding mechanism. When $H > 1$, and for small $\epsilon$, we show a lower bound in $\Omega(HS\frac{\sqrt{A K}}{\epsilon})$ and an upper bound in $\tilde{O}(H^2 S^2 \frac{\sqrt{ AK}}{\epsilon})$. The upper bound is achieved by an algorithm based on UCBVI and a unary encoding mechanism. For small $\epsilon$, these bounds improve the previously known lower bound by a factor $\sqrt{S}$ and the previously known upper bound by a factor of $H \sqrt{A}$.

Text-to-image diffusion models have demonstrated remarkable capabilities in generating high-quality images, yet their tendency to reproduce undesirable concepts poses growing concerns for safe and controllable deployment, particularly regarding NSFW content, specific objects and styles. While existing concept erasure approaches primarily focus on DDPM-based diffusion models and rely on costly fine-tuning, the recent emergence of flow matching models introduces a fundamentally different generative paradigm for which prior methods are not directly applicable. In this paper, we propose **Differential Vector Erasure (DVE)**, a training-free concept erasure method specifically designed for flow matching models. Our key insight is that semantic concepts are implicitly encoded in the directional structure of the velocity field governing the generative flow. Leveraging this observation, we construct a differential vector field that characterizes the directional discrepancy between a target concept and an anchor concept. During inference, DVE selectively removes concept-specific components by projecting the velocity field onto the differential direction, enabling precise concept suppression without affecting unrelated semantics. Extensive experiments on FLUX demonstrate that DVE consistently outperforms existing baselines on a wide range of concept erasure tasks, including NSFW suppression, artistic style removal, and object erasure, while preserving image quality and diversity.

Comparative claims about large language model (LLM) performance are typically based on aggregate benchmark scores. This treats models with similar scores as comparable on the items the benchmark contains, an assumption that can fail if models from different populations succeed on systematically different items. We test this assumption using Differential Item Functioning (DIF), a psychometric diagnostic that flags items whose relative difficulty differs across groups after conditioning on overall performance. Applying Mantel--Haenszel DIF analyses to six widely-used LLM benchmarks across two widely-used open-source model families (Llama and Qwen), we find that many items behave differently across families even among models with the same total benchmark score, with some items favoring Llama-family models and others favoring Qwen-family models. The flagged items concentrate in benchmark-provided categorical content (subjects, subtasks, problem types), and choosing items based on which family they favor can substantially amplify, attenuate, or reverse aggregate family-level comparisons. Our results show that aggregate benchmark scores can summarize different item-level performance patterns across model populations, and that DIF offers a useful diagnostic for surfacing this variation.

Differential privacy (DP) has a wide range of applications for protecting data privacy, but designing and verifying DP algorithms requires expert-level reasoning, creating a high barrier for non-expert practitioners. Prior works either rely on specialized verification languages that demand substantial domain expertise or remain semi-automated and require human-in-the-loop guidance. In this work, we investigate whether large language models (LLMs) can automate DP reasoning. We introduce DPrivBench, a benchmark in which each instance asks whether a function or algorithm satisfies a stated DP guarantee under specified assumptions. The benchmark is carefully designed to cover a broad range of DP topics, span diverse difficulty levels, and resist shortcut reasoning through trivial pattern matching. Experiments show that while the strongest models handle textbook mechanisms well, all models struggle with advanced algorithms, revealing substantial gaps in current DP reasoning capabilities. Through further analytic study and failure-mode analysis, we identify several promising directions for improving automated DP reasoning. Our benchmark provides a solid foundation for developing and evaluating such methods, and complements existing benchmarks for mathematical reasoning.

Neural surrogate solvers of partial differential equations (PDEs) promise dramatic speedups over numerical methods, especially in scenarios requires many solves. However, current accuracy-based evaluations do not fully consider two central issues: (i) neural solvers incur substantial up-front costs for data generation, training, and tuning; and (ii) classical solvers can also generate low-fidelity solutions at a sufficiently low simulation cost. To explicitly account for these realities and fully incorporate end-to-end costs, we propose an evaluation framework centered on **breakeven complexity**, a metric that counts the forward solves before a learned solver is cost-effective relative to an error-equivalent traditional solver. To evaluate this measure, we apply scaling laws to determine how much training budget to allocate to data generation and discuss how to achieve smooth error-matching in diverse settings. We evaluate the breakeven complexity of many modern neural PDE solvers on three PDEs on 2D periodic domains from APEBench and a novel benchmark of flows past multiple obstacles generated by the GPU-native PyFR code. Among other findings, our results suggest that neural PDE solvers will be *more effective* on problems as problems get harder in terms of cost, dimension, rollout, physics regime (e.g. higher Re), etc.

Modern language models are commonly adapted after pretraining to follow instructions, align with user preferences, and improve deployment behavior. Such post-training often relies on preference data from users, annotators, or model interactions, which may contain sensitive prompts, private responses, proprietary tasks, or confidential judgments. Understanding the privacy implications of this data is therefore essential. Membership inference attacks (MIAs), which test whether a record was used for training, are the de facto standard for empirical privacy auditing in machine learning. However, preference-based post-training changes the unit of membership: a training record contains a prompt, a preferred response, and a dispreferred response, rather than a single input-output sequence. Audits that ignore this structure can under-report leakage. We therefore introduce a benchmark protocol that adapts strong reference-model MIAs to complete preference records. Our protocol asks whether membership is exposed by either response alone, by the model’s preference between them, or by the two responses jointly. We find that auditing the response pair can reveal membership evidence missed when the record is reduced to a single score. Across three preference datasets, two model families, and seven post-training objectives spanning three post-training families, measured leakage depends strongly on both the audited record statistic and the training objective, with imbalanced risk between preferred and dispreferred responses. We further evaluate the impact of parameter-efficient fine-tuning (PEFT) and differential privacy (DP), finding widely varying privacy-utility trade-offs. Overall, preference-based post-training leaks in ways that standard single-response audits can miss, motivating formal privacy methods that protect complete preference records while preserving post-training utility.

Best arm identification under differential privacy is a pure-exploration problem in which both statistical efficiency and privacy protection must be achieved simultaneously. We study fixed-budget best arm identification for bandits under pure $\epsilon$-differential privacy, where the learner must recommend an arm after a prescribed sampling budget while protecting the full transcript. We prove that the optimal exponential decay rate of the error probability is upper bounded by an instance-dependent privacy-aware transportation exponent that differs from the analogous quantity used to characterize the stopping time of in fixed-confidence analysis by Jourdan and Azize [2025]. Guided by this exponent, we propose AO-Pri-BAI, an adaptive algorithm that maintains private running estimates through Laplace-tree mechanisms and learns a sampling design through a min-max interaction between hard alternatives and arm allocations. We prove that AO-Pri-BAI satisfies pure $\epsilon$-differential privacy. We also establish that the exponent of the failure probability of AO-Pri-BAI matches the privacy-aware benchmark. Numerical studies show that even in the non-asymptotic setting, AO-Pri-BAI outperforms benchmark algorithms on various instances, complementing the theoretical analyses.