UAI 2026 Papers

The Self-Improving Alignment (SAIL) algorithm addresses distribution shift by reducing a bilevel formulation of the problem to an efficient, single-level method. Empirically, SAIL has demonstrated strong performance on this task. However, a formal analysis of its convergence properties has been lacking. We identify a key theoretical challenge: the standard SAIL objective function is not guaranteed to be strongly concave due to unfavorable properties of its Hessian. To address this limitation, we propose a regularized objective, SAIL-RevKL, which incorporates a reverse Kullback-Leibler (KL) divergence penalty to improve the optimization landscape. Our central theoretical contribution is to prove that this regularized objective satisfies the Polyak-Lojasiewicz (PL) condition within a bounded parameter space. We establish global convergence guarantees, achieving a near-linear sample complexity. We further validate the effectiveness and stability of SAIL-RevKL through empirical evaluations, demonstrating that it outperforms the vanilla SAIL on both MuJoCo benchmarks and LLM alignment tasks.

Numerous attribute weighting methods have recently been proposed to alleviate the attribute conditional independence assumption in naive Bayes. Among them, multi-view attribute weighting framework has achieved state-of-the-art performance by constructing additional latent views beyond the raw attribute view, thereby capturing more comprehensive data characteristics. However, these latent views are usually derived from base classifiers trained on a fixed input distribution, which greatly limits the diversity of generated attributes. Additionally, in most cases, the latent views consist solely of hard labels, disregarding the predicted posterior probability of the base classifiers, resulting in incomplete utilization of discriminative evidence. To address these issues, we propose a novel framework called Perturbation-driven Matrix-view Weighted Naive Bayes (PMWNB). In PMWNB, diverse input perturbations are first applied to the raw attribute view to generate multiple base views. Subsequently, each base view independently trains multiple heterogeneous base classifiers, whose hard label and soft probability outputs are jointly leveraged to construct four latent views. Finally, class-specific attribute value weights in each view are respectively optimized by minimizing the negative conditional log-likelihood. Extensive experiments conducted on a collection of 59 benchmark datasets demonstrate the superiority of PMWNB. The source code and datasets are available at https://github.com/zhanghuan1994/PMWNB.

Efficient exploration is a central challenge in reinforcement learning (RL), especially under sparse rewards, large state-action spaces, or adversarial environment dynamics. A principled approach to exploration is to choose actions that maximize the upper bound return. Under certain conditions, this can be formulated in the Bayesian framework as exploration based on the posterior variance. In practice, the predictive variance of a neural network is often used as a surrogate for the posterior variance by techniques such as ensembles, randomized priors, and random network distillation. However, for wide neural networks, neural tangent kernel (NTK) theory proves there is a discrepancy between the predictive variance of a wide neural network trained by gradient descent and its posterior variance. This is a known issue in supervised learning and there exist methods to reconcile this discrepancy. In this work, we show that, in contrast to the supervised setting, reconciliation is not possible for semi-gradient temporal difference (TD) learning, which is a commonly used algorithm in deep RL. Instead, we derive the upper confidence bound (UCB) of the value function in semi-gradient TD learning directly and show that this UCB can be estimated by a neural network. To aid our analysis, we extend NTK theory to regularized semi-gradient TD learning.

Since the introduction of SHAP, many methods adapted the idea of using the Shapley value formula as a way to measure the importance of a feature in the decision of a model. However, computing this value theoretically imply to relearn the model with and without the feature for all subsets of features. To avoid this, the methods rely on sampling to compute an expectation to measure a mean impact of a feature. In this paper we investigate theoretically if we could, and under which conditions, build and use a textbook cooperative game with the help of other explanation techniques, Prime Implicants and Counterfactual explanations, for computing Shapley values for interpretability. We propose detailed and iterative analysis of the number of remaining explanations during the enumeration of the explanations, alongside the computation of the Shapley value and its upper and lower bounds.

We propose a conjugate and calibrated Gaussian process (GP) model for multi-class classification by exploiting the geometry of the probability simplex. Our approach uses Aitchison geometry to map simplex-valued class probabilities to an unconstrained Euclidean representation, turning classification into a GP regression problem with fewer latent dimensions than standard multi-class GP classifiers. This yields conjugate inference and reliable predictive probabilities without relying on distributional approximations in the model construction. The method is compatible with standard sparse GP regression techniques, enabling scalable inference on larger datasets. Empirical results show well-calibrated and competitive performance across synthetic and real-world datasets.

Randomized experiments are a staple in academic research, policy, and industry. Interference, when the outcome of one unit depends on the treatment status of other units, can cause bias in estimates of the treatment effect. Statistical corrections rely on knowing the underlying network of transmission pathways. Often, though, it is only possible to partially observe the network (e.g., through node subsamples, egocentric designs, respondent-driven sampling, or aggregated relational data). We develop a single-network asymptotic framework for inference about treatment effects in this regime. Starting from a structural causal model and exposure mapping, we assume a flexible class of generative network models consistent with the partial measurements and construct feasible proxy exposures by averaging over plausible completions of the network. We then study moment-based estimators for response parameters and treatment effects under dependence, and give conditions for consistency and asymptotic normality together with an explicit rate requirement ensuring that network-estimation error is first-order negligible. Simulations and an empirical replication illustrate how the theory maps to finite-sample workflows for interference with partial network data.

In non-stationary linear contextual bandits, existing efficient algorithms typically rely on the Weighted Regularized Least-Squares (WRLS) estimator. Because WRLS only provides point estimates, previous methods typically construct surrogate distributions when aiming to perform Bayesian-like randomized exploration. To more properly establish the Bayesian principles, we introduce *Weighted Sequential Bayesian* (WSB) inference, which forms a sequence of posteriors over a sequence of non-stationary reward parameters. This Bayesian take allows us to isolate the influence of initial beliefs into a dynamic prior penalty evaluated through the posterior covariance, which typically decreases over time. Building on this framework, we instantiate three WSB-based algorithms for exploration: *WSB-LinUCB*, *WSB-RandLinUCB*, and *WSB-LinTS*. By extending a refined drift analysis to randomized exploration without requiring local norms, we establish frequentist regret guarantees that match state-of-the-art WRLS-based baselines. Empirically, WSB’s dynamic prior penalty reduces over-conservatism, allowing our algorithms to consistently match or exceed their WRLS-based counterparts. Lastly, we also provide a simplified proof for the time-uniform concentration of vector-valued martingales, a critical subroutine used throughout the literature, that might be of independent interest.

Deploying trustworthy AI systems requires principled uncertainty quantification. Conformal prediction (CP) is a widely used framework for constructing prediction sets with distribution-free coverage guarantees. In many practical settings, including healthcare, finance, and mobile sensing, the calibration data required for CP are distributed across multiple clients, each with its own local data distribution. In this federated setting, data can often be partitioned into, potentially overlapping, groups, which may reflect client-specific strata or cross-cutting attributes such as demographic or semantic categories. We propose group-conditional federated conformal prediction (GC-FCP), a federated extension of conditional conformal calibration for a target mixture over prespecified groups. GC-FCP constructs mergeable, atom-stratified coresets from local calibration scores, enabling compact aggregation at the server when the number of active atoms is moderate. Experiments on synthetic and real-world datasets validate the performance of GC-FCP compared to centralized calibration baselines. The code of our work can be found at https://github.com/HaifengWen/GC-FCP.

Numerical integration is a cornerstone of various scientific computing applications, such as engineering simulations and model evidence computations in probabilistic machine learning. Bayesian Quadrature uses Gaussian process surrogates that explicitly encode structural assumptions about the integrand to obtain integral estimates with quantified uncertainty. These surrogates are predominantly based on stationary covariance functions, which results in model misspecification for integrands exhibiting nonstationary behavior. We tackle this issue through an adaptively growing, tree-based partition of the integration domain into local stationary models. Our method recombines the local integral estimates through a hierarchy of GP conditioning that reintroduces cross-subdomain correlations, while model selection criteria control the tree growth to avoid unnecessary partitioning. The resulting algorithm is simple, requires no MCMC, and adapts its evaluation budget to local integrand complexity. On benchmark integration problems and a model evidence computation for an epidemiological model, Hierarchical Bayesian Quadrature achieves substantial gains over standard Bayesian Quadrature on nonstationary integrands while matching its performance on stationary ones.

Deploying multi-agent reinforcement learning (MARL) in the real world is often limited by model mismatches between the training simulators and the true environment, which could be further amplified through strategic interactions and result in severe performance degradation upon deployment. Distributional robustness offers a principled response by optimizing policies against worst-case transition models drawn from an uncertainty set, but standard robust MARL frameworks become increasingly intractable as the number of agents grows. This paper develops an infinite-horizon, stationary mean-field game framework that incorporates distributional model uncertainty directly into the population-coupled dynamics. We establish a robust dynamic programming principle with a contractive Bellman operator and prove the existence of a stationary robust mean-field equilibrium via a fixed-point argument. We further develop the first concrete algorithm with convergence guarantees. We then connect the mean-field solution to a finite-population robust game whose ambiguity sets depend on the empirical distribution, showing that the mean-field equilibrium policy induces approximate equilibrium behavior as the population size increases. Under a contractive robust-dynamics regime, we further obtain explicit non-asymptotic error bounds. Numerical experiments further illustrate the qualitative and quantitative impact of robustness under multiple uncertainty models, validating our theoretical findings.

Graph Neural Networks (GNNs) have shown strong performance in learning node representations and node classification, but their effectiveness can be substantially degraded by noise in real-world graph data. To address this challenge, we introduce a robust and innovative node representation learning method named Graph Contrastive Learning with Low-Rank Regularization, or GCL-LRR, which follows a two-stage transductive learning framework for node classification. In the first stage, the GCL-LRR encoder is trained via prototypical contrastive learning with a low-rank regularization objective, and in the second stage, the learned representations are used by a linear transductive classifier to predict labels for unlabeled nodes. Our GCL-LRR is inspired by the Low Frequency Property (LFP) of the graph data and its labels, and it is also theoretically motivated by our sharp generalization bound for transductive learning. Our theoretical result is among the first to theoretically demonstrate the advantage of low-rank regularization in transductive learning, which is also supported by strong empirical results. To further enhance the performance of GCL-LRR, we present an improved model named GCL-LR-Attention, which incorporates a novel LR-Attention layer into GCL-LRR. GCL-LR-Attention reduces the kernel complexity of GCL-LRR and contributes to a tighter generalization bound, leading to improved performance. Extensive evaluations on standard benchmark datasets evidence the effectiveness and robustness of both GCL-LRR and GCL-LR-Attention. The code of GCL-LRR and GCL-LR-Attention is available at https://github.com/Statistical-Deep-Learning/GCL-LR-Attention.

Motivated by latency-critical streaming domains such as IoT data processing and cloud resource allocation, we investigate the problem of Online Scheduling with Immediate Decision, where a scheduler must instantly decide whether to accept an incoming task without buffering. We consider a system with M identical machines handling tasks with fixed processing lengths and stochastic, initially unknown rewards. A distinct feature of our model is preemption with abandonment: while a machine can interrupt a running task to accept a more valuable new arrival, the preempted task is permanently discarded, yielding no reward and no feedback, which is crucial for learning. We first analyze the setting with known rewards, deriving a worst-case competitive ratio lower bound and proposing the near-optimal Maximum Remaining Density First (MRDF) algorithm. For the challenging case of unknown rewards with censored feedback, we design an efficient bandit algorithm, Scheduling Upper Confidence Bound (S-UCB), which balances exploration and exploitation to achieve an O(log T) regret over time horizon T. Experimental results demonstrate the efficacy of the proposed algorithms against standard baselines.

Large language model (LLM) scaling inference is key to unlocking greater performance, and leveraging diversity has proven an effective way to enhance it. Motivated by the observed relationship between solution accuracy and meaningful response diversity, we systematically study the effect of prompt diversity in scaling inference. We theoretically explain why diversified sampling improves Best-of-N scaling, showing that responses generated from diverse prompts after Best-of-N selection exhibit significantly lower error rates than those produced from stationary prompts. Building on this analysis, we derive a diversity-fidelity trade-off principle, that guides the design of sampling strategies introducing diversity. From this guidance, we instantiate a family of effective perturbation styles. We theoretically and empirically characterize when diversified exploration remains effective, demonstrating that it works under a variety of conditions, and we further show that under majority voting, diversity may vanish. We systematically evaluate the effectiveness of sampling diversity and show that, when applied appropriately in different contexts, meaningful perturbations yield stronger, task-dependent gains as diversity increases. Overall, this work provides a systematic analysis that offers a theoretical and empirical foundation for understanding the effect of diversity in LLM inference-time scaling.

Trajectory representation learning (TRL) seeks to convert trajectory data into low-dimensional embeddings for various downstream tasks. Existing methods are limited to a single perspective: GPS-based approaches capture dynamic details but lack semantic context, while route-based methods preserve structure but lose fine-grained motion patterns. To address these limitations, we propose a trajectory representation model with multi-perspective fusion, MPH, where M denotes the Motion modality (GPS), P denotes the planned path modality (Route), andH signifies the Hierarchical encoding and fusion strategy. MPH first map-matches raw GPS trajectories to route sequences and designs dedicated encoders to extract dynamic behavioral patterns and static semantic features respectively. Based on this, MPH leverages a cross-attention mechanism for modality interaction and fusion, producing fused route representations that are hierarchically aggregated into trajectory-level embeddings. Furthermore, we introduce two self-supervised tasks to train the model. Contrastive learning is employed to align road segment representations across the two perspectives, while the dual-mask prediction task strengthens contextual modeling by jointly reconstructing masked road segment identities and their corresponding temporal information. Experiments on two real-world datasets show that MPH outperforms all baselines across different tasks.

Estimating the mean of manifold-valued data is a central problem in modern statistics, yet it remains challenging due to the lack of a closed-form expression for the Fréchet mean. The gradient descent algorithm is widely used to approximate this quantity across various applications. Although generally effective, it can be computationally intensive for large datasets, as each iteration requires evaluating gradients with respect to the entire dataset. To address these limitations, we propose a tree-based, Recursive Fréchet Mean Estimator (RFME), tailored to data on manifolds. The proposed method leverages a hierarchical aggregation strategy to reduce computational complexity while preserving statistical accuracy. We establish the weak consistency of RFME with respect to the population Fréchet mean and discuss its computational properties. Through simulation studies and real-world applications, we demonstrate that RFME achieves competitive estimation accuracy with substantially improved efficiency. Moreover, as a generalization of the incremental Fréchet mean estimator, RFME also offers enhanced flexibility while maintaining practical advantages.

Epistemic uncertainty in neural networks is commonly modeled using two second-order paradigms: distribution-based representations, which rely on posterior parameter distributions, and set-based representations based on credal sets (convex sets of probability distributions). These frameworks are often regarded as fundamentally non-comparable due to differing semantics, assumptions, and evaluation practices, leaving their relative merits unclear. Empirical comparisons are further confounded by variations in the underlying predictive models. To clarify this issue, we present a controlled comparative study enabling principled, like-for-like evaluation of the two paradigms. Both representations are constructed from the same finite collection of predictive distributions generated by a shared neural network, isolating representational effects from predictive accuracy. Our study evaluates each representation through the lens of 3 uncertainty measures across 8 benchmarks, including selective prediction and out-of-distribution detection, spanning 6 underlying predictive models and 10 independent runs per configuration. Our results show that meaningful comparison between these seemingly non-comparable frameworks is both feasible and informative, providing insights into how second-order representation choices impact practical uncertainty-aware performance.

Attention mechanisms are widely used in deep learning and have been incorporated into DNNs for person Re-Identification (Re-ID) to enhance discriminative feature learning. Existing attention modules, including self-attention and channel attention, learn attention weights that quantify the importance of feature tokens or feature channels. However, existing attention methods do not explicitly ensure that the attention weights are informative for predicting the identity of the person in the input image, and may consequently introduce noisy information from the input image. To address this issue, we propose a novel method termed Reduction of Information Bottleneck loss (RIB), motivated by the principle of the Information Bottleneck (IB). A novel distribution-free and efficient variational upper bound for the IB loss (IBB), which can be optimized by standard SGD, is derived and incorporated into the training loss of the RIB models. RIB is applied to DNNs with self-attention through a novel Differentiable Channel Selection Attention module (DCS-Attention), which selects informative channels to compute attention weights, leading to RIB-DCS. It is also integrated with existing channel attention modules to learn informative channel weights, leading to RIB-CA. Both RIB-DCS and RIB-CA are applied to fixed backbones and learnable backbones with Differentiable Neural Architecture Search (DNAS). Extensive experiments on multiple person Re-ID benchmarks show that RIB significantly improves prediction accuracy, including in occluded person Re-ID, by learning more discriminative and identity-informative features. The code of our work is available at https://github.com/Statistical-Deep-Learning/RIB-ReID.

Uncertainty quantification is a key aspect in many tasks such as model selection/regularization, or quantifying prediction uncertainties to perform active learning or OOD detection. Within credal approaches that consider modeling uncertainty as probability sets, upper entropy plays a central role as an uncertainty measure. This paper is devoted to the computational aspect of upper entropies, providing an exhaustive algorithmic and complexity analysis of the problem. In particular, we show that the problem has a strongly polynomial solution, and propose many significant improvements over past algorithms proposed for 2-monotone lower probabilities and their specific cases.

Reliable reasoning requires models to generalize under distribution shifts, yet in-distribution validation loss often fails to identify checkpoints that remain reliable out of distribution. We study representation collapse in Transformer hidden states as an internal degeneration that may reduce the effective capacity needed for multi-step inference. We characterize two complementary collapse signals: spectral capacity collapse, measured by the effective rank of layerwise representation covariance, and geometric alignment collapse, measured by average cosine alignment. We then propose the Collapse Risk Criterion (CRC), an ID-computable diagnostic score estimated from in-distribution validation representations. CRC is not a formal OOD guarantee, but a practical surrogate for OOD-free checkpoint selection. Across four reasoning benchmarks and three Transformer backbones, CRC correlates more strongly with OOD reasoning error than ID validation loss and standard confidence-based reliability scores. CRC-aware checkpoint selection improves OOD performance under depth/difficulty and template/rule shifts with minimal ID degradation. As an extension, collapse-aware training with a CRC-based regularizer improves average OOD performance in all evaluated dataset–backbone settings. Our results suggest that monitoring representation collapse is a simple and useful tool for improving reasoning reliability without OOD validation data.