| Total: 24
We study active elicitation of agent preferences for collectively choosing among $m$ alternatives using prominent voting rules. We focus on the next-best query model, in which an agent responds to a query by revealing their next most favorite alternative, and measure the competitive ratio, which is the worst case ratio between the number of queries made by the active elicitation algorithm and the minimum number of queries needed to reveal the winning alternative(s) in hindsight. We show that the best competitive ratio is sublinear in $m$ for many positional scoring rules but linear in $m$ for all Condorcet-consistent rules. Our analysis centers on a simple elicitation algorithm we propose, which not only achieves optimal theoretical bounds, but also impressive empirical performance on real data.
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.
Constraint-based causal discovery relies on conditional independence tests (CITs), which are highly unstable in high-dimensional settings. As the conditioning set grows, CITs suffer from low statistical power, leading to frequent false negatives. In the context of structure learning, this causes error propagation that degrades the accuracy of the estimated graph. We propose DF-PC (Deduce-First PC), a theoretically sound framework that integrates graphoid-based reasoning into the PC algorithm. Unlike prior approaches that primarily utilize deduction for conflict resolution or additive checks, DF-PC adopts a proactive ``Deduce-First'' strategy: it prioritizes logical deduction from strictly lower-order tests to preemptively replace high-order CITs. This "Deduce-First" strategy enables structure learning with potentially fewer CITs while improving performance. Empirical evaluations across various settings demonstrate that DF-PC achieves competitive learning performance and computational efficiency.
The pivotal challenge of handling uncertainty in artificial intelligence has prompted a growing focus on learning Bayesian network (BN) structures from data in recent years. Nevertheless, most of the existing methods such as hill-climbing, variational auto-encoder and graph neural network-based algorithms continue to encounter the issues like local optimum and exponential computational complexity, etc. In response to these challenges, we propose a Transformer-based approach for learning the BN structure (T-BNSL) from an information theory perspective. Specifically, we first establish the graph skeleton of a BN by employing conditional independence tests grounded in mutual information. Subsequently, we propose a hill-climbing method with decomposable BIC scoring function to generate potential directed acyclic graphs (DAGs) and evaluate the BIC scores of a subset of these DAGs. Lastly, we use the Transformer framework with a refined attention module to predict the BIC scores of the remaining DAGs, enabling the efficient identification of the DAG with the highest score. Experimental findings demonstrate that our approach significantly surpasses state-of-the-art competitors in terms of accuracy and efficiency by several orders of magnitude when learning the BN structure.
In this paper, we investigate tradeoffs among differential privacy (DP) and several representative axioms for approval-based committee voting, including justified representation, proportional justified representation, extended justified representation, Pareto efficiency, and Condorcet criterion. Without surprise, we demonstrate that all of these axioms are incompatible with DP, and thus establish both upper and lower bounds for their two-way tradeoffs with DP. Furthermore, we provide upper and lower bounds for three-way tradeoffs among DP and every pairwise combination of such axioms, revealing that although these axioms are compatible without DP, their optimal levels under DP cannot be simultaneously achieved. Our results quantify the effect of DP on the satisfaction and compatibility of the axioms in approval-based committee voting, which can provide insights for designing voting rules that possess both privacy and axiomatic properties.
Selective conformal prediction can yield substantially tighter uncertainty sets when we can identify calibration examples that are exchangeable with the test example. In interventional settings, such as perturbation experiments in genomics, exchangeability often holds only within subsets of interventions that leave a target variable "unaffected" (e.g., non-descendants of an intervened node in a causal graph). We study the practical regime where this invariance structure is unknown and must be estimated from data. Our main result quantifies how coverage degrades when the estimated safe calibration set accidentally includes interventions that affect the target, and gives a conservative correction when an upper bound on this error is available. Rather than learning a full causal graph, we learn only the intervention-target relationships needed to choose calibration interventions. We give algorithms for this partial learning task and evaluate them on synthetic structural equation models and Replogle K562 CRISPR-interference data, where the experiments illustrate synthetic gains from selective calibration and finite-sample tradeoffs on real perturbation screens.
Graph transformers are the state-of-the-art for learning from graph-structured data and are empirically known to avoid several pitfalls of message-passing architectures. However, there is limited theoretical analysis on why these models perform well in practice. In this work, we prove that attention-based architectures have structural benefits over graph convolutional networks in the context of node-level prediction tasks. Specifically, we study the neural network gaussian process limits of graph transformers (GAT, Graphormer, Specformer) with infinite width and infinite heads, and derive the node-level and edge-level kernels across the layers. Our results characterise how the node features and the graph structure propagate through the graph attention layers. As a specific example, we prove that graph transformers structurally preserve community information and maintain discriminative node representations even in deep layers, thereby preventing oversmoothing. We provide empirical evidence on synthetic and real-world graphs that validate our theoretical insights, such as integrating informative priors and positional encoding can improve performance of deep graph transformers.
Belief Propagation (BP) has operated in Euclidean space for four decades, yet the polynomial volume growth of $\mathbb{R}^d$ is fundamentally mismatched to hierarchical graphs: faithful embedding of exponentially branching structure demands $d = \Omega(\log n)$ dimensions and prohibitive $\mathcal{O}(d^3)$ covariance costs, while truncating $d$ corrupts marginal estimates. We introduce Continuous Hyperbolic Belief Propagation (CHBP), formulated natively on the Lorentz hyperboloid $\mathbb{H}^n_K$, whose exponential volume growth eliminates this bottleneck. CHBP parameterises beliefs as Jacobian-corrected Wrapped Normals, approximates message integrals via Gauss--Hermite quadrature, and transports covariance tensors between tangent spaces via closed-form Levi-Civita parallel transport, with a curvature annealing schedule ensuring stable convergence. On hierarchical graphs, CHBP at $d{=}5$ reduces marginal KL divergence by $25\times$ versus Euclidean BP at $d{=}50$ and achieves up to 91.45\% accuracy on real-world taxonomies, outperforming all baselines including Hyperbolic GCNs. On flat topologies, CHBP predictably underperforms Euclidean methods, confirming a topology-specific rather than universal advantage.
Causal effects estimated by covariate adjustment on a discovered graph have invalid confidence intervals, because the graph-selection step is ignored. We develop a unified selective-inference framework. For constraint-based discovery with latent confounders (FCI) under Gaussianity, we prove that the selection event, given the execution trace and signs, is a polyhedron in Fisher-z space; along the inference direction it becomes polynomial/rational constraints solving to a union of intervals. Inverting the truncated-Gaussian approximate pivot gives exact finite-sample $1-\alpha$ coverage, with known $\sigma^2$, of the adjustment functional $\gamma_1(S^\star)$ when $\{i\}\cup S^\star$ contains the outcome's Markov blanket, and approximate coverage otherwise, with a non-vanishing distortion governed by the variance-ratio excess $\rho^2=\sigma^2_{j|X}/\sigma^2_{j|-j}-1$ (small under sparsity); the $\hat\sigma^2$ plug-in does not remove it. This is the first truncation-set characterization handling latent confounders. Coverage of the structural effect $\beta_{i\to j}$ is asymptotically valid up to the same distortion when the adjustment set is valid (exact when $\rho^2=0$), via high-dimensional FCI consistency under $d=o(\sqrt n)$. For unmodified GES, heuristic Taylor linearization indicates approximate coverage $1-\alpha-O(d^2/\sqrt n)$ when $n\gg d^4(\log d)^2$. In the nonparametric setting, $\Theta(n^{3/4})$-split discovery incurs width ratio $1+\Theta(n^{-1/4})$ versus a known-graph oracle.
Bounding causal effects analytically, rather than numerically, is appealing for its interpretability and conceptual clarity. Existing sharp methods rely on optimization-based approaches such as the Balke–Pearl framework, whose computational complexity grows rapidly. An alternative line of work derives bounds heuristically using probability laws and generic inequalities, and some recent papers have claimed or conjectured that this approach can yield sharp analytical bounds with substantially lower complexity. In this paper, we show that this perceived advantage is illusory. In particular, in a discrete instrumental variable setting, we show that any sharp analytical bound for the average treatment effect must be expressible as a maximum (minimum) over a collection of linear terms whose cardinality grows exponentially in the number of values taken by the outcome. In parallel, we show that the number of instrumental variable inequalities itself also grows exponentially. Consequently, bounds and inequalities expressed using only polynomially many such terms cannot be sharp. As a constructive complement, the paper is accompanied by codes implemented in python and R to derive sharp analytical bounds and sharp inequalities with optimal computational complexity, matching the lower bounds proven in this paper. These codes are available \href{https://github.com/ArefeBoushehrian/Analytical-Causal-Bounds-in-Instrumental-Variable-Models}{online}.
The Shapley value is a widely used concept in attribution problems, as it uniquely satisfies the axioms of linearity, consistency, equal treatment, and efficiency. Often, the inclusion AUC metric is used to evaluate the quality of player rankings, in order to identify positively participating players. However, it can be established that the Shapley value is not always reliable for this purpose. The core issue lies in its linearity: the Shapley value acts as a linear operator with an excessively large null space, which is likely to contain non-negligible perturbations that remain indistinguishable to the operator. To address this limitation, we explore the design of nonlinear axiomatic attribution methods. Inspired by the least core, which is a popular nonlinear substitute for the Shapley value, we introduce a class of nonlinear attribution methods that retain the remaining necessary axioms. Each method yields a contribution vector that is the unique optimal solution to a minimization problem, which aims to approximate utility functions as faithfully as possible. In terms of the inclusion AUC metric, our experiments demonstrate the potential effectiveness of these methods compared to Shapley value variants that relax only the efficiency axiom.
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.
Large multi-modal language models are increasingly deployed in high-stakes domains, making well-calibrated uncertainty essential. Traditional Bayesian methods approximate posteriors over all model weights, which becomes intractable for modern large models. For this reason, recent work instead considers Bayesian low-rank adaptation to enable tractable posterior approximation. Due to a lack of a standardized benchmark to evaluate these approaches, it remains unclear where these methods provide meaningful benefits. To fill this gap, we introduce Bayesian Adaptation Gym (BAG), a benchmark for the Bayesian adaptation of multi-modal language models. BAG provides reference implementations of classic Bayesian baselines and state-of-the-art adaptation methods, along with a multi-modal dataset and task suite designed to probe calibration, robustness under distribution shift, and decision-making under uncertainty via active learning. Using BAG, we conduct and report extensive experiments across model sizes, datasets, and tasks to highlight the successes and failures of current Bayesian adaptation approaches. To enable further research, BAG is fully open source: https://github.com/SRI-CSL/BayesAdapt.
Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes. In this paper, we tackle these issues by providing new disagreement-based certificates for the gap between the true risk of any two predictors. We then bound the true risk of the predictor of interest via a surrogate model that enjoys tight generalization guarantees, and by evaluating our disagreement bound on an unlabeled dataset. We empirically demonstrate the tightness of the obtained certificates and showcase the versatility of the approach by training surrogate models leveraging three different frameworks: sample compression, model compression and PAC-Bayes theory. Importantly, such guarantees are achieved without modifying the target model, nor adapting the training procedure to the generalization framework.
Many distributional quantities in reinforcement learning are intrinsically joint across actions, including distributions of gaps and probabilities of superiority. However, the classical Markov decision process (MDP) formalism specifies only marginal laws and leaves the joint law of counterfactual one-step outcomes across multiple possible actions at a state unspecified. We study coupled-dynamics environments with a multi-action generative interface which can sample counterfactual one-step outcomes for multiple actions under shared exogenous randomness. We propose joint MDPs (JMDPs) as a formalism for such environments by augmenting an MDP with a multi-action sample transition model which specifies a coupling of one-step counterfactual outcomes, while preserving standard MDP interaction as marginal observations. We adopt and formalize a one-step coupling regime where dependence across actions is confined to immediate counterfactual outcomes at the queried state. In this regime, we derive Bellman operators for $n$th-order return moments, providing dynamic programming and incremental algorithms with convergence guarantees.
Causal identification functionals often require integration over conditional densities of continuous variables, such as those arising in nonparametric identification theory of total and mediated causal effects in DAGs with hidden variables. Estimating these densities and evaluating the resulting integrals can be statistically and computationally demanding. A common workaround is to discretize the continuous variable and replace integrals with finite sums. Although convenient, discretization alters the population-level functional and can induce non-negligible approximation bias, even when identification is correct. Under smoothness conditions, we show that the resulting coarsening error is first order in the bin width and arises at the level of the target functional, distinct from statistical estimation error. We propose a simple debiased coarsened functional that evaluates the outcome regression at within-bin conditional means, eliminating the leading coarsening error term and yielding a second-order approximation error. We derive plug-in and one-step estimators for this debiased coarsened functional. Simulations demonstrate substantial bias reduction and near-nominal confidence interval coverage, even under coarse binning. Our results provide a simple framework for controlling the impact of variable discretization on both parameter approximation and statistical estimation.
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.
Time series out-of-distribution generalization requires forecasters to remain reliable when deployment dynamics differ from training conditions due to covariate shift, concept shift, and temporal dependence. Probably Approximately Correct Bayesian domain adaptation provides computable certificates by decomposing target risk into a source risk term, a source-to-target mismatch term, and a complexity term, but standard analyses rely on independent sampling and distributional stability, assumptions that are violated in time series by serial dependence and nonstationary shift. We propose a model-agnostic online martingale Probably Approximately Correct Bayesian framework that yields finite-sample certificates under temporal dependence and distribution shift. The certificate replaces independent-sample concentration with martingale concentration that adapts to loss scale and predictable variation. We use the certificate as a surrogate regularizer for online calibration by training a gated residual Bayesian head on top of a fixed forecasting backbone, producing a corrective update that reverts to the backbone prediction when the gate is closed. Online calibration combines a source risk anchor, a posterior-shift penalty, and a time-adaptive mismatch term computed from target windows observed before forecasting. It follows a predict-then-update protocol in which outcomes become available only after forecasting and are used to update subsequent predictions. Experiments across convolutional, attention-based, and large language model-based forecasters show improved stability and accuracy under covariate and concept shift.
Bayesian inference of Bayesian network structures is often performed by sampling directed acyclic graphs along an appropriately constructed Markov chain. We present two techniques to improve sampling. First, we give an efficient implementation of basic moves, which add, delete, or reverse a single arc. Second, we expedite summing over parent sets, an expensive task required for more sophisticated moves: we devise a preprocessing method to prune possible parent sets so as to approximately preserve the sums. Our empirical study shows that our techniques can yield substantial efficiency gains compared to previous methods.
Probabilistic model checking for Markov decision processes (MDPs) provides quantitative guarantees, but often offers limited insight into why undesired outcomes occur. Probability-raising (PR) causality addresses this by identifying states whose visitation increases the probability of reaching designated states. Existing PR-cause identification methods, however, use MDP modifications ill-suited for learning: the gap between conditional and unconditional reachability probabilities can be hard to detect from samples, and construction requires reachability probabilities of the original MDP, which are unavailable when transition probabilities are unknown. We study unknown MDPs and propose a learning approach with probabilistic guarantees for PR-cause identification. Our key ingredient is a restart-based MDP modification that reduces PR-cause checking to two conditional reachability queries without using reachability values of the original MDP. We prove correctness, establish sample-complexity bounds, and develop an anytime learning-and-checking algorithm based on two-sided value iteration that progressively classifies states as causal, non-causal, or undecided. Experiments on two benchmarks demonstrate reliable and fast identification of PR causes.
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.
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.
Currently, the way deep learning models recognize uncertainty remains inconsistent with human perception. In multi-label classification, quantifying uncertainty at the label level presents challenges, as each label may exhibit distinct model confidence levels. Understanding and decomposing label-specific uncertainty is essential for interpreting model behavior and ensuring reliable predictions. We build a hierarchical Bayesian methodology for multi-label classification that leverages a Type II likelihood and Empirical Bayes. Then we estimate and decompose label-wise uncertainties by the bias-variance decomposition. Our approaches offer four main contributions: (1) Type II likelihood maximization is data likelihood centric; (2) it can decompose label-wise uncertainty into the model variance, the model bias and data noise; (3) our uncertainty represented by model bias is intuitively interpretable when combined with observational data; and (4) when applied to out-of-distribution (OOD) detection task, it achieves a 6.88\% lower FPR95 score on NUS-WIDE.
Reliable uncertainty quantification (UQ) is essential for deploying large language models (LLMs) in safety-critical scenarios, as it enables them to abstain from responding when uncertain, thereby avoiding hallucinations, i.e., plausible yet factually incorrect responses. However, while current semantic UQ methods have achieved state-of-the-art performance, they inherently overlook latent semantic structural information that could enable more precise uncertainty estimates. In this paper, we propose Semantic Structural Entropy (SeSE), a principled black-box UQ framework applicable to both open- and closed-source LLMs. To reveal the intrinsic structure of the LLM semantic space, SeSE constructs its hierarchical abstraction based on the principle of structural entropy minimization. The structural entropy of the resulting optimal hierarchical abstraction thus quantifies the inherent uncertainty within the semantic space after optimal compression. Additionally, unlike existing methods that primarily focus on simple short-form generation, we extend SeSE to provide interpretable and granular uncertainty estimation for long-form outputs. We theoretically prove that SeSE generalizes semantic entropy, the gold standard for UQ in LLMs, and empirically demonstrate its superior performance over baselines across 24 model-dataset combinations.