UAI 2026 Papers

The Rashomon effect, the fact that many different models can achieve nearly identical predictive accuracy, has been extensively studied across various domains of machine learning. While modern conformal prediction provides valid intervals for a single model, it remains blind to the inherent arbitrariness of having to select from multiple candidates. This paper bridges this gap by investigating when model multiplicity, or the existence of many near-optimal models, materially widens prediction intervals. We prove a sharp phase transition for ridge regression under Gaussian design and introduce *Rashomon Prediction Intervals* (RPIs), which bound the range of predictions across the Rashomon set and establish a Rashomon-Conformal Bridge that provides distribution-free coverage guarantees. A critical tolerance ε^⋆ = Θ(σ^2/p) separates two distinct regimes: below it, Rashomon-conformal intervals match standard conformal width; above it, model multiplicity dominates, and this scaling is provably minimax optimal. Computationally, exact RPIs are polynomial for convex classes but NP-hard for tree ensembles, with a thin-cap volumetric barrier ruling out sampling-based approximation. Experiments on six UCI benchmarks confirm the phase transition, with all datasets falling in the sub-critical regime at standard tolerances, indicating that model multiplicity is invisible in prediction intervals for typical tabular regression.

We study how well the quantal response equilibrium (QRE) approximates the mixed Nash equilibrium (MNE) in two-player zero-sum games, as a function of the inverse temperature β. We introduce a reduction framework that decomposes the worst-case Nikaido–Isoda error of the QRE into a sum of two independent single-player Gibbs concentration problems, enabling tight matching bounds across a range of payoff classes. For finite games with M × N payoff matrices, we establish a tight rate of Θ(β^-1(log M + log N)). For games with α-Hölder-continuous payoffs on the torus, we prove a lower bound of Ω((d_x+d_y)/(αβ)) and an upper bound of O((d_x+d_y)log(Lβ)/(αβ)); whether the logarithmic gap is tight is left as an open problem. For smooth payoffs with sparse non-degenerate MNE, we prove that every individual game achieves a rate of (d_x + d_y)/(2β) + O(1/β^2) via Laplace concentration, and that this rate is tight.

Active learning reduces labeling costs by querying samples to maximize information gain. A dominant framework, Query-by-Committee, typically relies on *perturbation-based diversity* by inducing model disagreement through random feature subsetting or data blinding. While this approximates one notion of epistemic uncertainty, it sacrifices direct characterization of the plausible hypothesis space. We propose the complementary approach: *Rashomon Ensembled Active Learning (REAL)* which constructs a committee by exhaustively enumerating the Rashomon Set of all near-optimal models. To address functional redundancy within this set, we adopt a Probably Approximately Correct-Bayesian framework using a Gibbs posterior to weigh committee members by their empirical risk. Leveraging recent algorithmic advances, we exactly enumerate this set for the class of sparse decision trees. Across synthetic and established active learning baselines, REAL outperforms randomized ensembles, particularly in moderately noisy environments where it leverages expanded model multiplicity to achieve faster convergence.

In recent years, watermarking generative tabular data has become a prominent framework to protect against the misuse of synthetic data. However, while most prior work in watermarking methods for tabular data demonstrate a wide variety of desirable properties (e.g., high fidelity, detectability, robustness), the findings often emphasize empirical guarantees against common oblivious and adversarial attacks. In this paper, we study a flexible and robust watermarking algorithm for generative tabular data. Specifically, we demonstrate theoretical guarantees on the performance of the algorithm on metrics like fidelity, detectability, robustness, and hardness of decoding. The proof techniques introduced in this work may be of independent interest and may find applicability in other areas of machine learning. Finally, we validate our theoretical findings on synthetic and real-world tabular datasets.

As artificial agents become increasingly capable, what internal structure is *necessary* for an agent to act competently under uncertainty? Classical results show that optimal control can be *implemented* using belief states or world models, but not that such representations are required. We prove quantitative "selection theorems" showing that strong task performance (low *average-case regret*) forces world models, belief-like memory and—under task mixtures—persistent regime-tracking variables resembling functional primitives of emotion, along with informational modularity under block-structured tasks. Our results cover stochastic policies, partial observability, and evaluation under task distributions, without assuming optimality, determinism, or access to an explicit model. Technically, we reduce predictive modeling to binary "betting" decisions and show that regret bounds limit probability mass on suboptimal bets, enforcing the predictive distinctions needed to separate high-margin outcomes. In fully observed settings, this yields approximate recovery of the interventional transition kernel; under partial observability, it implies necessity of predictive state and belief-like memory, addressing an open question in prior world-model recovery work.

In many economically relevant contexts where machine learning is deployed, multiple platforms obtain data from the same pool of users, each of whom selects the platform that best serves them. Prior work in this setting focuses exclusively on the “local” losses of learners on the distribution of data that they observe. We find that there exist instances where learners who use existing algorithms almost surely converge to models with arbitrarily poor global performance, even when models with low full-population loss exist. This happens through a feedback-induced mechanism, which we call the overspecialization trap: as learners optimize for users who already prefer them, they become less attractive to users outside this base, which further restricts the data they observe. Inspired by the recent use of knowledge distillation in modern ML, we propose an algorithm that allows learners to "probe" the predictions of peer models, enabling them to learn about users who do not select them. Our analysis characterizes when probing succeeds: this procedure converges almost surely to a stationary point with bounded full-population risk when probing sources are sufficiently informative, e.g., a known market leader or a majority of peers with good global performance. We verify our findings with semi-synthetic experiments on the MovieLens, Census, and Amazon Sentiment datasets.

Retrieval-augmented prediction systems select documents by semantic similarity, ignoring their effect on downstream predictive uncertainty. In high-stakes domains such as clinical diagnosis, this can yield overconfident or needlessly imprecise predictions. We propose Information-Directed Conformal Retrieval, a framework that selects documents to minimize the volume of conformal prediction sets while preserving distribution-free coverage. Modeling each document as a Bayesian precision update, we show that minimizing conformal volume is exactly equivalent to maximizing a log-determinant objective, and prove this objective monotone submodular, so greedy selection inherits the constant-factor (1-1/e) guarantee. A Document Interaction Tensor characterizes corpus-level interaction structure, and a lightweight marginal-gain-separation gate routes uncertain retrieval steps to lookahead search. On MIMIC-IV clinical diagnosis (275 admissions from 100 patients, 9273 PubMed abstracts), greedy retrieval attains a mean greedy-to-optimal ratio of 0.9999, produces conformal ellipsoids 4.8 times smaller than random retrieval and 5.8 times smaller than cosine retrieval while retaining the distribution-free coverage guarantee, and two-step lookahead closes 77 percent of the remaining gap. Gains generalize to the SciQ and GoEmotions benchmarks, and on GoEmotions and LexGLUE the method yields tighter posterior uncertainty than learned and uncertainty-aware retrieval baselines. Complex multi-morbid patients benefit most, with twice the synergy-gap rate, precisely where prediction is hardest.

This article proposes an online bootstrap scheme for nonparametric level estimation in nonstationary time series. Our approach applies to a broad class of level estimators expressible as weighted sample averages over time windows, including exponential smoothing methods and moving averages. The bootstrap procedure is motivated by asymptotic arguments and provides well-calibrated uniform-in-time coverage, enabling scalable uncertainty quantification in streaming or large-scale time-series settings. This makes the method suitable for tasks such as adaptive anomaly detection, online monitoring, or streaming A/B testing. Simulation studies demonstrate good finite-sample performance of our method across a range of nonstationary scenarios. In summary, this offers a practical resampling framework that complements online trend estimation with reliable statistical inference.

Graph Neural Networks have emerged as a powerful tool for the fast and accurate prediction of various crystal properties. These models often encode domain-specific knowledge into their graph encoding modules, which increases their parameter size and makes their performance heavily dependent on domain expertise. Added to this, explicitly incorporating all chemical and structural features, that might influence a specific crystal property into the GNN encoder, is a challenging task. In this work, we propose a soft prompt learning framework that captures latent features essential for property prediction, which are not explicitly provided to the GNN. We introduce a novel multilevel graph prompt learning framework comprising both node-level and graph-level soft prompts. At the node level, we capture the local chemical semantics of different atom types, while at the graph level, we encode the global structural symmetry of the crystal graph. Our proposed prompt learning framework is lightweight and seamlessly integrates with any existing GNN encoder. Extensive experiments on popular benchmark datasets show that incorporating prompt learning significantly improves (3

Many scientific datasets contain sparse, irregular observations of dynamic processes. Fast inference techniques are required to infer the unseen evolution of physical systems underlying growing datasets, and estimate the parameters that govern them. We first accelerate the convergence of Gauss-Markov Variational Inference via efficient natural gradient computation and automatic step-size adaptation. We then propose two general-purpose schemes for initialization from sparse data, one using junction tree representations of Gauss-Markov distributions, and another attention-based neural network architecture that learns to predict correlated temporal posteriors. We show that these initializers dramatically improve performance for ecological models of soil decomposition and predator-prey dynamics. We further extend our methods to a semiparametric epidemiological model of SARS-CoV-2 RNA wastewater measurements, which uses Gaussian processes to model uncertainty in latent reproduction numbers. Our methods allow for quick inference of both local states and global dynamical parameters, and unlike prior work, can be applied even when measurements are sparse and the generative process is not fully known.

Causal Bayesian networks (CBNs) and structural causal models (SCMs) are the dominant frameworks for graphical causal reasoning, but they cannot adequately represent all real-world causal systems. In particular, systems at equilibrium—where feedback mechanisms create cyclic causal dependencies—can exhibit causal semantics that are fundamentally incompatible with these frameworks: different interventions that enforce the same variable value may have different effects, rendering the standard “perfect intervention” do(X=x) ambiguous. We propose _bipartite graphical causal models_ (BGCMs), in which the structure of a system of equations is encoded by a bipartite graph with variable and equation nodes. In this framework, a hard intervention do(f_j : X_v=ξ_v) specifies which equation is replaced, which variable is targeted, and at what value—resolving the ambiguity of the standard notion. We demonstrate, through a detailed case study of a physical system, that this representation naturally corresponds to distinct real-world interventions. We formulate a Markov property in terms of a new graphical separation criterion (B-separation) that exploits the functional determinism inherent in the equations, and we extend it to settings with non-random inputs. We show how this gives rise to a do-calculus for reasoning about domain invariances. BGCMs strictly generalize CBNs and SCMs while retaining the ability to perform graphical causal reasoning.

Wasserstein barycenters provide a principled approach for aggregating probability measures, while preserving the geometry of their ambient space. Existing discrete methods are not because as they assume access to the complete set of samples from the input measures. Meanwhile, neural network approaches do scale well, but rely on complex optimization problems and cannot easily incorporate label information. We address these limitations through gradient flows in the space of probability measures. Through time discretization, we achieve a scalable algorithm that i) relies on mini-batch optimal transport, ii) accepts modular regularization through task-aware functions, and iii) seamlessly integrates supervised information into the ground-cost. We empirically validate our approach on domain adaptation benchmarks that span computer vision, neuroscience, and chemical engineering. Our method establishes a new state-of-the-art Wasserstein barycenter solver, with labeled barycenters consistently outperforming unlabeled ones. Our code at https://github.com/SigmaNova/barycentric-gradient-flows

We propose StableSpIn, a continuous optimization framework for learning potentially cyclic causal directed graphs (digraphs) in linear structural equation models via a spectral-radius constraint on the absolute adjacency matrix. Our motivation is twofold: first, stability is a natural requirement for linear structural models; second, the contractive cycles that stability induces facilitate the identifiability of digraphs. We formulate causal discovery as a likelihood-based optimization problem under a sparse-input assumption, yielding a scalable algorithm applicable to both cross-sectional and time-series data. Unlike prior continuous acyclicity constraints, our stability regularizer is cheaper to evaluate while accommodating general digraphs, yielding faster optimization in practice. Experiments on synthetic benchmarks show improved graph recovery over state-of-the-art baselines, and empirical studies on U.S., European, and Swiss equity markets reveal interpretable cyclic dependencies that persist across time windows. Our implementation is available at https://github.com/pmisiakos/StableSpIn.

We study finite-horizon MDP planning under root-based (resolute) risk objectives that apply a rank-dependent functional to the distribution of total returns. Such objectives are non-linear in the return distribution and generally break Bellman optimality, so direct optimization by scenario-tree enumeration is intractable. We propose ERQDP, an enumeration-free and sampling-free method that solves a rank–quantile surrogate via exact DP (Dynamic Programming), evaluates candidate policies exactly by DP over return Probability Mass Functions (PMFs) on a discretized return grid (with an explicit rounding bound), and refines the surrogate in an anytime loop that reports an explicit upper–lower gap (certificate) for the target objective up to discretization budgets. Across tested benchmarks, ERQDP returns certified solutions or explicit residual gaps, enables fast risk-parameter sweeps with substantial runtime gains, and supports both risk-averse and risk-seeking behaviors.

This paper addresses the problem of learning Gaussian graphical models from data contaminated by additive measurement error. Applying traditional procedures to the noisy data may result in many false discoveries. On the other hand, existing procedures that explicitly account for measurement error assume that the measurement error covariance is known or can be estimated precisely. We provide two practical alternatives for the common setting where this side information is not available. The first proposed method follows a partial identification approach and estimates a graph with controlled false discovery rate when given an upper bound on the measurement error variances. In many settings, the precise variance of the errors is unknown, but the scientist may still confidently specify an upper bound. The second framework is a sensitivity analysis that assesses the minimum amount of measurement error required to explain away an estimated edge. This yields an interpretable measure for practitioners to assess which estimated edges are robust and which may be simply due to measurement error. We derive theoretical guarantees and show good empirical performance in simulations. We further illustrate the practical utility of our procedures on a single-cell mRNA sequencing dataset.

In multi-object tracking (MOT), the trajectories of moving objects – e.g., molecules, cells, or people – must be recovered from detected positions. MOT is often solved using network flow approaches to find globally optimal solutions. Here, we consider a version of MOT where objects can split or merge – such as cells that are moving but also dividing while being tracked. We show that this problem is NP-hard, phrase it as a Max-SAT problem, and ask: (1) To what extent can modern optimized satisfiability solvers be applied to realistic MOT problems? (2) Are the globally optimal solutions better than those generated by existing methods? Using both simulated data and real-world cell tracking data, we show that Max-SAT is a computationally costly but feasible approach that can lead to substantially improved solutions for problems of realistic size. We hope that the Max-SAT instances generated by the MOT problem can serve as practically relevant benchmarking cases for the future improvement of Max-SAT solvers.

Exact marginalization in deep Gaussian processes (DGPs) is analytically intractable, typically requiring computationally costly sampling-based approximations. We introduce the Gaussian process neuron, a computational unit built on a novel Wasserstein exponential kernel. By defining a composable map between factorized Gaussian measures, this unit enables analytical uncertainty propagation; concurrently, optimizing deterministic inducing variables via maximum a posteriori estimation ensures strict probabilistic rigor. By eliminating sampling variance and the depth-scaling computational bottlenecks of Monte Carlo methods, our approach enables exact probabilistic variants of diverse architectures, including DGPs, multilayer perceptrons, and Kolmogorov-Arnold Networks. Empirically, these networks demonstrate superior uncertainty calibration relative to state-of-the-art approximate DGP frameworks, alongside high-dimensional scalability and robust compositional expressiveness.

Supervised graph prediction addresses regression problems where the outputs are structured graphs. Although several approaches exist for graph-valued prediction, principled uncertainty quantification remains limited. We propose a conformal prediction framework for graph-valued outputs, providing distribution-free coverage guarantees in structured output spaces. Our method defines nonconformity via the Z-Gromov–Wasserstein distance, instantiated in practice through Fused Gromov–Wasserstein (FGW), enabling permutation-invariant comparison between predicted and candidate graphs. To obtain adaptive prediction sets, we introduce Score Conformalized Quantile Regression (SCQR), an extension of Conformalized Quantile Regression (CQR) to handle complex output spaces such as graph-valued outputs. We evaluate the proposed approach on a synthetic task and a real problem of molecule identification.

Causal discovery aims to learn causal structures up to certain symmetries. Diverse populations or changing environments give rise to heterogeneous data in the following sense: each population/environment is a “source” which idiosyncratically determines the forms of causal effects. From this perspective, the source is a latent common cause for every observed variable. While some methods for causal discovery can work around latent confounding in special cases, a global confounder poses a significant challenge. The only known ways to deal with latent global confounding involve making assumptions that limit structural equations and/or noise functions. We demonstrate that globally confounded causal structures can still be identified with arbitrary structural equations and noise functions, so long as the number of latent classes remains small relative to the size and sparsity of the underlying DAG. The approach relies on agglomerating variables into large-enough matrices of moments, whose ranks directly reveal graphical properties of the causal structure. We also provide a statistical test to test the rank of these matrices.