UAI 2026 论文列表

Conditional independence testing is a critical component of feature screening, invariant statistical models, and causal discovery. Many of these algorithms rely on the sequential application of conditional independence tests, and their stability hinges on how their outcomes interact. We study this "meta-dependence" between conditional independence properties using the following geometric intuition: satisfying each conditional independence property constrains the space of possible joint distributions to a manifold. The "meta-dependence" of multiple conditional independences in a probability distribution is informed by its position relative to these manifolds. We provide a simple-to-compute measure of this meta-dependence using moment projections, with a closed-form expression for multivariate Gaussian distributions, and consolidate our findings empirically using both synthetic and real-world data. Our measure of meta-dependence does not rely on graphical properties of the distribution and can be computed directly from summary statistics such as a covariance matrix, allowing for various applications. We demonstrate one use case of meta-dependence, using a simple redundancy metric to tune significance thresholds and improve causal discovery.

We study feature selection (support recovery) in sparse linear models, including linear and logistic regression, under a strong adversarial contamination model where an adversary can arbitrarily corrupt a constant fraction of samples in the high-dimensional regime. Most of the existing methods target one or two aspects of this interesting problem: (1) achieving robustness against strong adversaries, (2) handling adversarial corruption in both features and labels, and (3) performing feature selection in high dimensions. Our approach tackles all three issues simultaneously. We propose a trimmed maximum likelihood estimator with ℓ_1-regularization, leading to a non-convex relaxation of an NP-hard combinatorial optimization problem. We prove that any locally optimal solution to this non-convex problem achieves near-minimax optimal statistical rates, up to logarithmic factors. Critically, our method recovers the true support in a computationally efficient manner despite the intractability of the exact formulation. The resulting sample complexity scales only logarithmically with the ambient dimension, making it well-suited for high-dimensional settings. Furthermore, our framework accommodates heavy-tailed noise distributions under mild moment assumptions, requiring only that the fourth moment be bounded. We also validate our theoretical findings empirically.

Ensuring fairness in AI is challenging, especially when privacy concerns prevent access to proprietary models and training data. We propose a cryptographic framework for auditing fairness without requiring model disclosure. Unlike existing solutions – which either fail to capture attack vectors enabling dishonest model providers to pass audits unfairly, or require continuous auditing during deployment involving real-world users – our framework is the first to simultaneously achieve the following: (1) Model Privacy: Proprietary model details remain hidden from verifiers; (2) A dishonest model provider cannot cause a non-compliant model to pass the fairness audit without detection by the verifier; (3) Pre-deployment Certification: The certification can be conducted entirely prior to deployment, without requiring interaction with or data from real-world users; (4) Test Data Transparency: Test data for auditing is generated in a transparent and accountable way, preventing dishonest parties from manipulating it. We achieve these goals by carefully combining cryptographic commitments, coin tossing, and zero-knowledge proofs. We evaluate our protocol on decision trees, XGBoost, and neural networks. Our results confirm the practicality of our approach: for a dataset with 10,000 samples and 10 features, and an XGBoost model with 100 trees of depth 3, proof generation takes 42 seconds and verification takes 2 seconds.

Explainable artificial intelligence promises to yield insights into relevant features, thereby enabling humans to examine and scrutinize machine learning models or even facilitating scientific discovery. Considering the widespread technique of Shapley values, we find that purely data-driven operationalization of multivariate feature importance is unsuitable for such purposes. Even for simple problems with two features, spurious associations due to collider bias and suppression arise from considering one feature only in the observational context of the other, which can lead to misinterpretations. Causal knowledge about the data-generating process is required to identify and correct such misleading feature attributions. We propose cc-Shapley (causal context Shapley), an interventional modification of conventional observational Shapley values leveraging knowledge of the data’s causal structure, thereby analyzing the relevance of a feature in the causal context of the remaining features. We show theoretically that this eradicates spurious association induced by collider bias. We compare the behavior of Shapley and cc-Shapley values on various, synthetic, and real-world datasets. We observe nullification or reversal of associations when moving from observational to cc-Shapley.

We develop interacting particle algorithms for learning latent variable models with energy-based priors. To do so, we leverage recent developments in particle-based methods for solving maximum marginal likelihood estimation (MMLE) problems. Specifically, we provide a continuous-time framework for learning latent energy-based models, by defining stochastic differential equations (SDEs) that provably solve the MMLE problem. We obtain a practical algorithm as a discretisation of these SDEs and provide theoretical guarantees for the convergence of the proposed algorithm. Finally, we demonstrate the empirical effectiveness of our method on synthetic and image datasets.

Surrogate endpoints are used in place of long-term outcomes in randomized experiments when observing the real outcome for a large enough cohort is prohibitively expensive or impractical. A short-term surrogate is good if the result of an experiment using the surrogate is predictive of the result of a hypothetical study using the real outcome. Much attention has been paid to formalizing this property in causal terms, but most criteria are unidentifiable and cannot be turned into practical algorithms for learning surrogate endpoints from data. To address this, we study plug-in composite surrogates, functions of post-treatment variables that may be substituted directly for the primary outcome in a randomized experiment. We propose two methods for learning plug-in surrogates that maximize effect predictiveness, and characterize the possibility of finding endpoints that yield unbiased effect estimates in representative scenarios. Finally, in both synthetic experiments with known effects and in data from a real-world experiment, we find that our method, based on directly modeling the surrogate effect, returns plug-in endpoints more predictive of the primary effect than established methods.

Causal effect estimation from observational data typically assumes a single fixed observational distribution. We study the setting in which the distribution is known only to belong to a credal set, a convex set of plausible observational laws. Our results characterize how this observational ambiguity is transformed by causal identification formulas. First, using standard two-point information-theoretic tools after composition with the interventional map, we derive lower bounds for causal effect estimation. The key message is a causal amplification phenomenon: observational discrepancies in low-propensity treatment strata can be hard to detect while producing separated interventional effects. Consequently, in the binary hard-pair constructions, sample complexity scales as Ω(1/(π_0ε^2)) or Ω(1/(β_0ε^2)), and the average treatment effect need not incur an additional dependence on the number of strata. Second, we prove Lipschitz bounds for the interventional mapping, with amplification factor (1+1/α_min), showing how positivity controls robust identification width. Third, we study minimax regret for causal decisions under credal uncertainty and show that randomization can halve worst-case regret in a symmetric action-separation construction. We also give matching upper bounds in special cases and an NP-hardness result for computing robust identification width. The experiments are diagnostic checks of the tight hard-instance scaling laws rather than broad empirical benchmarks.

Multi-Adversarial Team Games (MATGs) extend the canonical normal-form framework of von Stengel and Koller – where a team of players sharing a common objective but unable to coordinate faces a single adversary - to settings involving multiple independent adversaries. From an algorithmic perspective, MATGs are notable as one of the few game classes admitting polynomial-time algorithms for computing ε-Nash equilibria. However, no complexity or algorithmic guarantees are known for the finite-horizon Markovian generalisation of MATGs. This paper establishes positive and negative results for approximating non-stationary Nash equilibria in finite-horizon Multi-Adversarial Team Markov Games. Specifically, we provide a polynomial-time algorithm for the single-adversary case, prove PPAD-hardness for the multiple-adversary case and present a polynomial-time algorithm for the multiple-adversary setting with additive transitions. We also provide an empirical evaluation of the proposed algorithms.

In coarsely sampled longitudinal data, feedback loops can appear as cyclic contemporaneous structure, yet most causal-discovery methods assume acyclicity. Bayesian directed cyclic graph models allow cycles by using non-Gaussian errors with lagged outcomes and exogenous covariates to identify contemporaneous structure. However, consecutive lags are often highly correlated. Existing methods place a binary indicator on each candidate lag, creating exponentially many lag patterns per edge; evidence for a true edge can split across correlated configurations and fall below selection thresholds (posterior fragmentation). We replace these indicators with one categorical variable recording edge absence or active lag, so lags compete within one state space. Under the Gaussian scale-mixture of Laplace errors, each candidate coefficient integrates out exactly, yielding closed-form Bayes factors from cached scalars with no matrix operations for lag comparison. We prove edge-and-lag selection consistency and show that the at-most-one-active-lag assumption is least costly where fragmentation is most severe; the method is a finite-sample regulariser for correlated-lag regimes, not a uniformly better alternative. Cached sufficient statistics and incremental Cholesky updates make the sampler 55–67 times faster without changing the target posterior. In the largest single-lag synthetic benchmark, the categorical encoding raises the true-positive rate from 0.83 to 0.99 and lowers structural Hamming distance from 6.0 to 0.3. On the Health and Retirement Study panel (17,883 individuals, 13 waves), both formulations share a four-edge contemporaneous core, but the categorical encoding yields larger autoregressive coefficients and a sparser contemporaneous graph than the independent encoding.

The random feature (RF) method is a powerful kernel approximation technique, but it typically uses fixed activation functions, limiting its adaptability across diverse tasks. To overcome this limitation, we introduce the Random Feature Model with Learnable Activation Functions (RFLAF), a novel statistical model that parameterizes activation functions as weighted sums of basis functions within the random feature framework. Examples of basis functions include radial basis functions (RBFs), spline functions, polynomials, and so forth. For theoretical results, we consider RBFs as representative basis functions. We start with a single RBF as the activation, and then extend the results to multiple RBFs, demonstrating that RF models with a learnable activation component substantially expand the represented function space. We provide estimates on the required number of samples and random features to achieve low excess risk. In our experiments, we test RFLAF with three types of bases: radial basis functions, spline functions and polynomials. Experimental results show that RFLAFs with RBFs and splines consistently outperform other RF models, where RBFs are three times more computationally efficient than splines. We then unfreeze the first-layer parameters and retrain the models, validating the expressivity advantage of learnable activation components on regular two-layer neural networks. Our work provides a deeper understanding of learnable activation components within modern neural network architectures.

This paper addresses the distributed stochastic minimax optimization problem subject to stochastic constraints. We propose a novel first-order Softmax-Weighted Switching Gradient method tailored for federated learning. Under full client participation, our algorithm achieves the standard 𝒪̃(ϵ^-4) oracle complexity to satisfy a unified bound ϵ for both the optimality gap and feasibility tolerance. We extend our theoretical analysis to the practical partial participation regime by quantifying client sampling noise through a stochastic superiority assumption. Furthermore, by relaxing standard boundedness assumptions on the objective functions, we establish a strictly tighter lower bound for the softmax hyperparameter. We provide a unified error decomposition and establish a sharp 𝒪(log1/δ) high-probability convergence guarantee. Ultimately, our framework demonstrates that a single-loop primal-only switching mechanism provides a stable alternative for optimizing worst-case client performance, effectively bypassing the hyperparameter sensitivity and convergence oscillations often encountered in traditional primal-dual or penalty-based approaches. We verify the efficacy of our algorithm via experiment on the Neyman-Pearson (NP) classification, fair classification, and federated safe reinforcement learning tasks.

We investigate the asymptotic properties of Bayesian bivariate causal discovery for Gaussian Linear Structural Equation Models (SEMs) with heteroscedastic noise. We demonstrate that with purely observational data, the posterior distribution over the models fails to consistently identify the true causal structure—a consequence of the fundamental non-identifiability within the Markov Equivalence Class. Specifically, if the true generating mechanism corresponds to a connected graph (A → B or B → A), the asymptotic behavior of the posterior is given by the ratio between the prior on the true model and the push-forward prior of the alternative. In contrast, for the independence model, we establish that the posterior concentrates at a stochastic polynomial rate of O_p(n^-1/2). To resolve this non-identifiability, we incorporate m interventional samples and characterize the concentration rates as a function of the observational-to-total sample ratio, η. We identify a sharp concentration dichotomy: while the independence graph maintains a polynomial O_p(N^-1/2) rate (where N = n+m), connected graphs undergo a phase transition to exponentially fast convergence. This highlights an exponential relative importance between the two data types, as altering the amount of one data type directly changes the exponent governing the concentration speed. We derive explicit formulae for the exponential decay rates and provide precise conditions under which mixing observational and interventional data optimizes concentration speed. Finally, our theoretical findings are validated through empirical simulations in Bayesian Gaussian equivalent (BGe)-style prior specifications offering a principled foundation for experimental design in Bayesian causal discovery.

Computing mixed-strategy Nash equilibria (MSNE) in graphical games being PPAD-complete, special types of graphical games have received a lot of attention over the years. We present a number of new results using a geometric approach to computing exact MSNE. We consider graphical games of several structures, such as paths, stars, and caterpillars. We also consider graphical polymatrix games on these structures. We provide a new tight upper bounding result for path-structured graphical games and a new quadratic-time algorithm for representing all MSNE and computing one for path-structured polymatrix games. For star graphical games, our algorithm is logarithmic time for non-degenerate cases (i.e., without symmetric players) and linear time for general cases with symmetric players. Interestingly, having more symmetric players makes the computation more expensive. For star polymatrix games, our algorithm is linear in the input size. For the open problems on caterpillar polymatrix and graphical games, our algorithms are polynomial time in the input size.

Current instance segmentation models achieve high performance on average predictions, but lack principled uncertainty quantification: their outputs are not calibrated, and there is no guarantee that a predicted mask is close to the ground truth. To address this limitation, we introduce a conformal prediction algorithm to generate adaptive confidence sets for instance segmentation. Given an image and a pixel coordinate query, our algorithm generates a confidence set of instance predictions for that pixel, with a provable guarantee for the probability that at least one of the predictions has high Intersection-Over-Union (IoU) with the true object instance mask. We apply our algorithm to instance segmentation examples in agricultural field delineation, cell segmentation, and vehicle detection. Empirically, we find that our prediction sets vary in size based on query difficulty and attain the target coverage, outperforming baselines (naive best parameter and morphological dilation-based methods). We provide versions of the algorithm with asymptotic and finite sample guarantees. Our work is the first to capture structural uncertainty in instance segmentation by constructing confidence sets of diverse segmentation predictions.

SAT-based bounded fitting—searching for a smallest logical concept that correctly classifies all given examples—yields sample-efficient PAC learning for structured hypothesis classes such as description logic (DL) concepts. Yet this paradigm is fundamentally brittle: it demands realizability, and a single mislabeled example can render the underlying SAT instance unsatisfiable. While agnostic learnability follows from finite VC-dimension of bounded-size concept classes, the real barrier is computational: minimizing misclassifications over all concepts of bounded size is NP-hard. We study this barrier through parameterized complexity. We introduce ApxFit(k,t)—the problem of deciding whether there exists a DL concept of size at most k that misclassifies at most t out of m examples—and establish a complexity landscape for fragments of 𝒜ℒ𝒞 whose operator sets contain {⊓,∃} or {⊔,∀}: the problem is W[2]-hard parameterized by concept size k (even for t=0), yet lies in XP parameterized by outlier count t for any fixed k. Algorithmically, we lift bounded fitting from SAT to partial weighted MAX-SAT and combine it with structural risk minimization, yielding the first noise-tolerant DL concept learner with formal agnostic generalization guarantees.

Flow matching models effectively represent complex distributions, yet estimating expectations of functions of their outputs remains challenging under limited sampling budgets. Independent sampling often yields high-variance estimates, especially when rare but high-impact outcomes dominate the expectation. We propose a non-IID sampling framework that jointly draws multiple samples to cover diverse, salient regions of a flow matching model’s generative distribution. To balance diversity and quality, we introduce a score-based regularization for the diversity mechanism (SR), which uses the score function, i.e., the gradient of the log probability, to ensure samples are pushed apart within high-density regions of the data manifold, mitigating off-manifold drift. To enable unbiased estimation when desired, we further develop an approach for importance weighting of non-IID flow samples by learning a residual velocity field that reproduces the marginal distribution of the non-IID samples and by evolving importance weights along trajectories. Empirically, our method produces diverse, high-quality samples and accurate importance-weight estimates and debiased expectation estimates, advancing the reliable characterization of flow matching model outputs.

Large language model (LLM) routing aims to select an appropriate model for each query under performance–cost trade-offs. A natural approach to improve adaptivity is to leverage interaction feedback to form behavioral signatures and continuously refine routing decisions as the environment changes. However, in realistic deployments, such feedback can have highly variable effective precision due to selective logging, imperfect evaluation signals, and temporal drift. As a result, behavioral signatures may be noisy or weakly informative, and treating them as uniformly precise can miscalibrate performance estimation and destabilize routing effectiveness. We propose the Latent prEcisioN inference System (LENS), a probabilistic routing framework that explicitly models the latent precision of interaction-derived signals. LENS formulates routing as posterior utility maximization under imprecise supervision, and marginalizes over latent precision to adaptively control how strongly behavioral signatures influence model selection. We instantiate LENS with an efficient variational inference procedure and evaluate it on multi-LLM routing benchmarks across diverse tasks and distribution shifts. Experimental results show that LENS consistently improves performance–cost trade-offs, with particularly strong gains under task and model shifts.

Small object detection underpins wide-area vision tasks such as UAV and remote-sensing imagery. However, standard convolutions often exhibit low-pass smoothing behavior, which suppresses the sparse edge cues of tiny targets and may cause them to be overwhelmed by background clutter, leading to semantic information loss at the early stages of feature extraction. Inspired by the dual-fovea physiology of the eagle eye, we propose EagleConv, a bio-inspired operator that superimposes three Gaussian components into a center-excitation, surround-inhibition, peripheral-context response profile to selectively amplify small-object signals while attenuating noise. Architecturally, EagleConv adopts a sparse dual-pathway design that integrates partial-channel depthwise dual-foveated filtering, pointwise channel mixing, and adaptive residual gating, followed by anti-aliasing downsampling for robust dimensionality reduction. Experiments on three public benchmarks show that augmenting YOLOv11s with EagleConv delivers consistent and significant gains over multiple convolution-augmentation baselines, achieving state-of-the-art performance and confirming its transferability and generality as a plug-and-play module for wide-area small-object detection.

Domain generalization is a critical challenge in machine learning, where models must generalize outside their training domain(s) to unseen test or deployment domains without retraining. Motivated by the principle of independent causal mechanisms, the notion of domain invariance provides a principled causality-inspired approach to domain generalization. In this context, we introduce a general domain-constrained supervised learning framework where the aim is to learn a representation of the input data that results in improved domain invariance and stability in the resulting prediction model. Adapting the framework to tree-based learning, we introduce the Constrained Random Forest that prioritizes stable predictive mechanisms, leading to improved generalization across diverse environments. Experiments on synthetic and real-world datasets show improved robustness over competing methods, even in settings where the underlying assumptions that enable domain-invariant learning in theory are violated.