UAI 2026 Papers

Principal component analysis (PCA) has recently been adopted for out-of-distribution (OOD) detection, yet most existing methods focus on dominant, high-variance directions of the feature space. This energy-retaining perspective overlooks a crucial fact: discriminative signals separating in distribution (ID) and OOD samples often lie in low variance residual components that are typically discarded. Furthermore, prior PCA-based scores rely solely on feature geometry, limiting robustness under distributional shift. In this work, we revisit PCA for OOD detection from an uncertainty aware perspective. Specifically, we propose a residual-aware OOD detection framework that explicitly models the discarded subspace of a shared within-class PCA basis. By constructing a residual variation score, we capture deviations that are ignored by the leading principal components. To further enhance reliability, we introduce a complementary classifier-weight alignment score that measures the consistency between the selected class-centered residual and the corresponding classifier weight vector. This dual-signal design enables reliable detection even when OOD samples exhibit high energy in the dominant subspaces. Extensive experiments across convolutional and transformer backbones show consistent improvements over strong baselines in AUROC and FPR at 95

Uncertainty quantification is central to the reliable deployment of large language models (LLMs), and eigenvalues of semantic embeddings have recently emerged as a key tool in state-of-the-art methods. However, conventional calibration results developed for classification probabilities cannot be directly transferred to eigenvalues. We address this gap by proposing a novel framework for calibrating the eigenvalues of semantic embeddings. We interpret LLMs combined with semantic embeddings of their generated answers as density matrix predictors, and we propose a novel approach to calibrate density matrix predictors by applying temperature scaling to their eigenvalues. We establish entropy–risk equivalence under calibration, derive a central calibration inequality specific to eigenvalues, and prove that temperature-scaled eigenvalues optimize calibration when minimizing proper score risks. Experiments on a variety of real-world settings show that current LLMs are systematically overconfident, and validate our theoretical findings. Together, these results advance the foundations and practice of uncertainty quantification for semantic embeddings.

Gaussian graphical models, estimated via precision matrices, are popular for uncovering underlying conditional dependencies among variables, yet the case of multimodal data with blockwise missing remains unaddressed. We propose a novel method, Direct Sparse Graphical Learning for Multimodal Data (DSGL), to handle this issue using only observed data. The DSGL consists of two stages: constructing a pilot estimator for the covariance matrix without imputation as an admissible input for GLASSO; and estimating the DSGL precision matrix via GLASSO with repeated cross-validation tuning. We further propose a thresholded variant to address false-positive edges, a common issue in high-dimensional data. We establish theoretical properties for DSGL with respect to element-wise deviation and its ability to recover the true graphical structure. In simulations and an Alzheimer’s Disease Neuroimaging Initiative (ADNI) application, DSGL outperforms imputation-based and other competing approaches, yielding more accurate graph estimation and lower Frobenius-norm error.

Credal sets, i.e., closed convex sets of probability measures, provide a natural framework to represent aleatoric and epistemic uncertainty in machine learning. Yet how to quantify these two types of uncertainty for a given credal set, particularly in multiclass classification, remains underexplored. In this paper, we propose a distance-based approach to quantify total, aleatoric, and epistemic uncertainty for credal sets. Concretely, we introduce a family of such measures within the framework of Integral Probability Metrics (IPMs). The resulting quantities admit clear semantic interpretations, satisfy natural theoretical desiderata, and remain computationally tractable for common choices of IPMs. We instantiate the framework with the total variation distance and obtain simple, efficient uncertainty measures for multiclass classification. In the binary case, this choice recovers established uncertainty measures, for which a principled multiclass generalization has so far been missing. Empirical results confirm practical usefulness, with favorable performance at low computational cost.

We study the problem of stochastic contextual bandits in the agnostic setting, where the goal is to compete with the best policy in a given class without assuming realizability or imposing model restrictions on losses or rewards. In this work, we propose Online Pessimistic Policy Learning and establish the first fast rate for regret relative to the best-in-class policy. Our proposed algorithm updates the policy at every round by minimizing a pessimistic objective, defined as a clipped inverse-propensity estimate of the policy value plus a variance penalty. By leveraging entropy assumptions on the policy class and a Hölderian error-bound condition (a generalization of the margin condition), we achieve fast best-in-class regret rates, including polylogarithmic rates in the parametric case. Our analysis is driven by a novel sequential self-normalized maximal inequality for bounded martingale empirical processes, which yields uniform variance-adaptive confidence bounds and guarantees pessimism under adaptive data collection.

Reasoning under uncertainty is a fundamental challenge, particularly when inference involves complex computations over large relational domains. Existing probabilistic inference methods typically answer probabilistic queries by leveraging symmetries to perform efficient, lifted inference assuming access to a complete model. However, the upstream task of learning such a model from partial and noisy observations is generally intractable. We propose the first polynomial-time framework for “implicit learning to reason" in a first-order relational probability logic, even over infinite domains. Our approach combines statistical signals from data with semidefinite relaxations of the moment problem, jointly informed by new observations and prior knowledge from the knowledge base. This enables verifying or refuting first-order queries without ever constructing an explicit model. We establish soundness and completeness guarantees for our algorithm, as well as a tractability result.

Conformal prediction equips machine learning models with a reasonable notion of uncertainty quantification under mild assumptions. However, conformal prediction only works if we fix the underlying model in advance. A relatively unaddressed issue in conformal prediction is that of model selection and/or aggregation: given a set of prediction models, which one should we conformalize? We suggest that instead of performing model selection, it can be prudent and practical to perform conformal set aggregation in an online, adaptive fashion. We propose a wrapper that takes in several conformal prediction sets, and outputs a single adaptively-combined prediction set. Our method, called conformal online model aggregation (COMA), is based on combining the prediction sets from several algorithms by weighted voting, and can be thought of as a sort of online stacking of the underlying conformal sets. As long as the input sets have (distribution-free) coverage guarantees, COMA retains coverage guarantees, under a negative correlation assumption between errors and weights. COMA is well suited to decentralized settings, where users are only willing to share their prediction sets for a new test point in a black-box fashion. As we demonstrate, it is also well suited to settings with distribution drift, where model selection is not advisable.

This paper presents three theoretical contributions that improve the usability of risk certificates for neural networks based on PAC-Bayes bounds. First, two bounds on the KL divergence between Bernoulli distributions enable the derivation of the tightest explicit bounds on the true risk of classifiers across different ranges of empirical risk. Then, a novel method to optimize bounds on non-differentiable objectives is introduced, allowing to optimize risk bounds directly on the 0-1 loss instead of resourcing to a surrogate differentiable loss, such as the bounded cross-entropy. These theoretical contributions are illustrated with an empirical evaluation on the MNIST and CIFAR-10 datasets. In fact, this paper presents the first non data-dependent generalization bounds on the 0-1 loss for neural networks fitted on CIFAR-10.

We study the problem of matching two sets of noisy feature vectors when underlying true features are related by an unknown scalar affine transformation. Our method comprises two primary steps. First, we standardize the feature vectors to estimate the unknown scalar affine transformation. Subsequently, we estimate the permutation by minimizing the Least Sum of Logarithms (LSL) between two sets of observations using the estimated transformation. Our main result shows that the unknown permutation can be perfectly recovered given that the minimal separation distance of true feature vectors scales as √(ρ_σ)∨ (dlog n)^1/4∨√(log n), where d is the ambient dimension, n is the sample size, and ρ_σ is the maximal ratio of noise magnitudes. Interestingly, the obtained rate, under mild heteroscedasticity, coincides with that of the non-affine setting. We additionally demonstrate that there exist configurations requiring a larger minimal separation distance for perfect recovery. The latter makes the matching problem more challenging from minimax perspective compared to the non-affine setting. Consequently, we show that in the problem of feature matching, standardizing the data implicitly estimates the scalar affine parameters. As part of our analysis, we prove non-asymptotic concentration bounds for the affine parameter estimators in the presence of heterogeneous noise magnitudes.

Learning unnormalized models is an ubiquitous problem in modern statistics and machine learning. Noise contrastive estimation (NCE) takes a popular approach based on solving a binary classification problem: Unnormalized models are learned by discriminating input data with artificially generated noise data. This paper follows this approach, but proposes a general framework based on the Bregman divergence. By selecting the convex function in the divergence, our framework includes existing methods as special cases, and novel variants of NCE can be also derived. Learning unnormalized models in the proposed framework is performed by estimating the posterior probability in the binary classification, i.e., the composition of the logistic function and the ratio of data and noise distributions. Due to the boundedness of the logistic function, our framework is advantageous in outlier-robustness. In fact, we theoretically prove that robust estimation is possible in our framework under a variety of convex functions in the Bregman divergence. Furthermore, the asymptotic efficiency is also investigated, implying a trade-off between efficiency and robustness in our framework. Inspired by these results, we derive the optimal noise distribution under some constraints for robustness. Finally, we numerically demonstrate the robustness of the novel variants of NCE and the derived optimal noise distribution.

The explainable clustering problem was first posed by Moshkovitz et al. (ICML 2020) and studies how well an axis-aligned decision tree with K leaves can approximate a given clustering. The performance of the tree is measured via the price of explainability, defined as the ratio between the clustering cost of the tree (where every leaf is a cluster) and the optimal cost. Several recent works have given worst-case characterizations of the price of explainability for different cost functions. However, these guarantees are data-agnostic and therefore notoriously pessimistic in practical clustering settings. In this paper, we study explainable clustering from the point of view of mixture models, which allows us to give the first data-dependent bounds on the price of explainability. First, we focus on K-medians clustering of mixture models with subexponential tails. We propose an algorithm that leverages information about the distribution of the data to find better cuts, and prove new upper and lower bounds. Second, we extend our algorithm and the theoretical guarantees it provides to kernel clustering, thereby refining the existing worst-case analysis.

In this paper, we investigate the identifiability of average controlled direct effects and average natural direct effects in causal systems represented by summary causal graphs, which are abstractions of full causal graphs, often used in dynamic systems where cycles and omitted temporal information complicate causal inference. Unlike in the traditional linear setting, where direct effects are typically easier to identify and estimate, non-parametric direct effects, which are crucial for handling real-world complexities, particularly in epidemiological contexts where relationships between variables (e.g., genetic, environmental, and behavioral factors) are often non-linear, are much harder to define and identify. In particular, we give sufficient conditions for identifying average controlled micro direct effect and average natural micro direct effect from summary causal graphs in the presence of hidden confounding. Furthermore, we show that the conditions given for the average controlled micro direct effect become also necessary in the setting where there is no hidden confounding and where we are only interested in identifiability by adjustment.

Real-world datasets often contain spurious correlations that are not causally related to the target label. When such correlations dominate the majority of training samples, models tend to rely on them, leading to misclassification of minority samples that do not exhibit the same spurious patterns. While a potential approach is to select judicious subsets of data to better represent of the minority samples, it may require group labels which are typically unknown. Furthermore, as we demonstrate, widely used sample scoring functions in the invariant subset or coreset selection literature largely depend on spurious features and therefore fail to accurately capture the importance or difficulty of core, causally relevant features. Accordingly, we propose to mitigate spurious correlations, by developing a two-stage sample scoring function that disentangles the learning dynamics of core and spurious features and evaluates their difficulty separately. Based on our proposed metric, we introduce a new algorithm to find and prioritize informative samples both with and without spurious correlations. Extensive experiments demonstrate that a standard ERM model trained on our selected samples achieves superior performance compared to state-of-the-art debiasing techniques, while requiring as little as 10

Dynamic knowledge graphs are ubiquitous in today’s AI applications, as we represent molecular structures, social relationships, and language information using these graph models. As knowledge graphs evolve over time and are often noisy and incomplete, modeling their temporal and relational dependencies becomes crucial for downstream tasks. To address these challenges, this paper proposes PGRE (Poisson–Gamma Relational Evolution), a probabilistic model for modeling inter-relational dependencies in dynamic knowledge graphs. PGRE represents multi-relational temporal links via a Poisson–Bernoulli formulation. It introduces Gamma-distributed latent variables to capture entity–factor associations and cross-relation dependencies mediated by shared latent communities. A Gamma Markov process further models the temporal evolution of these latent variables, enabling principled characterization of relational dynamics. Experiments on benchmark datasets show that PGRE achieves competitive performance in link prediction, particularly in sparse settings, while revealing meaningful relational evolution patterns in dynamic knowledge graphs.

Causal discovery methods based on the PC algorithm are proven to be sound if all structural assumptions are fulfilled and all conditional independence tests are correct. This idealized setting is rarely given in real data. In this work, we first showcase how local errors can lead to untrustworthy edge orientations far away from the error source, highlighting how consequential seemingly innocuous errors can become. Next, we introduce coherency scores to find assumption violations and small sample errors in the absence of a ground truth. These scores do not require statistical tests beyond those already executed by the causal discovery algorithm. Errors detected by our approach extend the set of errors that present themselves as orientation conflicts or ambiguities. We place our computationally cheap global error detection and quantification scores as a bridge between computationally expensive global answer-set-programming-based methods and less expensive local error detection methods. The scores are analyzed on simulated and real-world datasets.

Causal Bayesian Networks (CBNs) provide a framework for reasoning about interventions, but analyzing complex systems often requires working with multiple overlapping models or hierarchical levels of granularity. We study how to canonically merge separate causal models that share a common substructure or abstract representation. We formalize this problem using category theory. We construct two distinct categories of causal models where morphisms are defined by maps that commute with interventions. Depending on whether these maps are injective or surjective, they represent causal submodels or causal abstractions, respectively. We demonstrate that the canonical merging of models sharing a common subsystem corresponds to computing a pushout in the category of submodels, while merging models sharing a common abstraction corresponds to a pullback in the category of abstractions. We establish sufficient topological and domain-level conditions under which these universal constructions exist.

Cox processes model overdispersed point process data via a latent stochastic intensity, but both estimation of the nonparametric intensity model and posterior inference over intensity paths are generally intractable, relying on computationally-heavy MCMC methods. We introduce Neural Diffusion Intensity Models, a variational inference framework for Cox processes driven by neural stochastic differential equations (SDEs). Our key theoretical result, based on enlargement of filtrations, shows that conditioning on point process observations preserves the diffusion structure of the latent intensity with an explicit drift correction. This provides guidance on how to choose an appropriate variational family so that ELBO maximization coincides with maximum likelihood estimation under sufficient model capacity. We provide an amortized encoder architecture that maps variable-length event sequences to posterior intensity paths by simulating the drift-corrected SDE, replacing repeated MCMC runs with a single forward SDE simulation. Experiments on synthetic and real-world data demonstrate accurate recovery of latent intensity dynamics and posterior paths, with orders-of-magnitude speedups over MCMC-based methods.

Action-dependent policies, which condition decisions of each agent on both states and other agents’ actions, provide a powerful structured framework for cooperative multi-agent reinforcement learning (MARL). Most existing studies have focused on auto-regressive formulations, where each agent’s policy depends on the actions of all preceding agents. However, this structure suffers from severe scalability limitations as the number of agents grows. In contrast, the theoretical foundations of sparse dependency structures remain largely unexplored. To address this gap, we introduce the Action Dependency Graph (ADG) to model sparse inter-agent dependencies. We propose a refined equilibrium concept with respect to the ADG that is stronger than the Nash equilibrium which often traps independent policies. Furthermore, within Coordination Graphs (CG) structured problems, we show that such an equilibrium attains global optimality when the ADG satisfies specific CG-induced conditions. To substantiate our theory, we develop a tabular multi-agent policy iteration algorithm that converges to the refined equilibrium exactly as predicted. We further extend our approach to deep MARL, confirming that these structural conditions provide a reliable design principle for scalable and optimal coordination.

We study centralized distributed data parallel training of deep neural networks (DNNs), aiming to improve the trade-off between communication efficiency and model performance of local gradient methods. Motivated by the flat-minima hypothesis, we first introduce a simple sharpness measure, Inverse Mean Valley, and show it strongly correlates with the generalization gap of DNNs. We then incorporate an efficient relaxation of this measure into the distributed objective as a lightweight regularizer that encourages workers to seek wide minima collaboratively. The regularizer exerts a pushing force that counteracts the consensus step pulling the workers together, giving rise to the Distributed Pull-Push Force (DPPF) algorithm. Empirically, DPPF generalizes better than other local gradient methods and synchronous gradient averaging while maintaining communication efficiency. In addition, our loss landscape visualizations confirm the ability of DPPF to locate flatter minima. Theoretically, we show that DPPF drives workers to span flat valleys with valley width governed by push–pull strengths, it yields self-stabilizing dynamics, it obeys generalization guarantees that depend on valley width, and it converges in the non-convex setting.