CS Paper Radar

On the Complexity of Bayesian Signal Processing

Yi Liu

cs.CC econ.TH ·submitted 2026-08-30 15:13 UTC · v1

Abstract

We develop a computational framework for Bayesian decision-making. We show that as long as no action is optimal in every state, Bayes-optimal choice is intractable. This hardness need not arise from large action, state, or signal spaces, nor from a complicated represented utility function: extracting enough information from a hard-to-interpret signal to act optimally can itself be computationally hard. We also characterize tractability across approximation notions and identify their sources of difficulty. Under the probably approximately correct criterion, sample-based Bayesian learning is tractable if and only if the signal support is bounded. Our results provide justifications for bounded rationality, costly Bayesian inference, and sample-based Bayesian learning.

Closest papers

Nearest neighbours by meaning across the whole index.

Probabilistic Circuits as Reasoning Machines in Artificial Intelligence (Part I)

cs.AI cs.LGmath.PR ·2026-08-17 ·Robert Peharz
similarity 0.58
Abstract · Habilitation Thesis

This cumulative habilitation thesis studies probabilistic circuits (PCs) as a powerful and tractable framework for reasoning and learning under uncertainty in artificial intelligence (AI). It first advocates for probability as a core language for AI, emphasizing its connections to logic and information theory; the conceptual simplicity of probabilistic reasoning---based primarily on the sum and product rules; the parallels between probabilistic inference and human cognition; and the role of probability in optimal decision making. However, probability also faces significant computational challenges, as probabilistic inference is NP-hard in almost all probabilistic models. PCs address these challenges through structural constraints that ensure exact computation of a wide range of inference queries in polynomial time, such as marginals, conditionals, most probable explanations, expectations, and more advanced inference tasks. This thesis synthesizes a decade of research across foundations, algorithmic developments, and empirical validation of PCs. Key contributions highlighted in this work are foundational theory of PCs, Bayesian approaches for learning PCs, scalable implementations and integration with deep learning, hybrid models that combine PCs with intractable models, and connections with symbolic machine learning paradigms. This is the first part of my Habilitation Thesis. The second part is omitted, as it comprises the cumulative part of the thesis and has been published at various venues (see Chapter 5).

0.20

A Unifying Perspective on Probabilities as Model Predictions

cs.CY stat.MLcs.LGmath.ST ·2026-09-09 ·Benedikt Höltgen
position similarity 0.57
Abstract

Although probabilistic statements are ubiquitous, foundational disagreements persist about their understanding, as exemplified by debates between Bayesians and frequentists; moreover, it is unclear when and why acting on them actually leads to desirable outcomes. Here, we argue that every probability is the output of a \emph{prediction method}, that is, it depends on both a particular way of constructing abstractions and a way of transforming them into predictions. Through this, we provide a unifying perspective on supposedly different kinds of probabilities and show that even supposedly objective ones are model-dependent. We demonstrate that when a finite calibration criterion is met, one can anticipate the distribution of utilities for a given policy and inform successful decision-making on finite sets of events. Based on the notion of prediction methods, inductive arguments, and the probability calculus, we explain the feasibility of the calibration criterion in many settings. Overall, we develop a coherent perspective on probabilities and their use, connecting key intuitions behind other interpretations along the way.

0.24

Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization

cs.AI math.OC ·2026-08-11 ·Sohaib Afifi
publishedtheory similarity 0.57
Abstract · 9 pages, 1 figure, 3 tables. Accepted at BELIEF 2026

Reducing the number of focal elements of a mass function is classically driven by an intrinsic distance, such as Jaccard or Jousselme, that keeps the approximation close to the original as a body of evidence. We consider instead the case where the mass function feeds a linear combinatorial optimisation problem with evidential costs. What should then be preserved is not the closeness of the two mass functions, but the quality of the decision they induce. We introduce a decision-aware approximation that targets the regret of the decision: one decides with the cheaper approximation and is evaluated under the true mass function. On a minimal shortest path, the distance-optimal approximation flips the decision while a decision-aware merge preserves it, and this occurs on a non-negligible fraction of random instances. We prove a one-point bound that localises the regret at the true optimum, turn it into an exact dynamic program for the scalar case, and extend it to an online version that prunes focal elements before the final cost is known. In experiments the decision-aware compressor flips the decision less often than representation-aware compression, for both the linear criterion and a non-linear proxy read-out.

0.25

HapBO: Harnessed $α$-$π$ Bayesian Optimization via Expert Natural Language Priors

cs.LG stat.ML ·2026-11-18 ·Jean-Sébastien Giroux, Rose Guay Hottin, Marco Bonizzato
theorycode/data similarity 0.57
Abstract · 41 pages, 22 figures, 8 tables. Code: https://github.com/mbonizzato/HapBO

Bayesian Optimization (BO) can be substantially more sample-efficient when informed by prior knowledge about the problem. In practice, however, such knowledge is often available only in natural language, e.g., expert intuitions or documentation, rather than as the explicit probability distribution landscape that prior-guided BO methods may require. Leveraging it effectively demands both an expressive mapping from language to priors and robustness to information that may be misleading. We propose HapBO (Harnessed $α$-$π$ Bayesian Optimization), which elicits beliefs once from a human expert, a large language model (LLM), or both, and deterministically compiles a structured specification into a reusable belief function ($π: \mathcal{X} \to[0,1]$), with a rich representation not restricted to a Gaussian family. Building on $α$-$π$BO, HapBO applies this belief function through a bounded positive multiplier on any nonnegative acquisition, preserving positive acquisition support and requiring no LLM calls during optimization. We prove that, for the Expected Improvement acquisition function (EI), HapBO preserves the standard simple-regret rate up to a bounded factor, even under adversarial beliefs. We evaluate HapBO on 40 HPOBench tasks, a synthetic suite in 6-15 dimensions and two real-world applications: cortical neurostimulation and constrained solar design. HapBO achieves the lowest aggregate HPOBench regret and strong real-world task performance, with zero in-loop token cost. In real-world applications it improves the optimization outcome even at budgets of 12-20 queries, and at a small fraction of the wall-clock and token costs of other LLM-based methods.

0.28

When Has a Bayesian Neural Network Sampled Enough? Adaptive Inference Time with Statistical Guarantees

cs.AI ·2026-10-08 ·Fabian Denoodt, Sibylle Hess
published similarity 0.56
Abstract · 40th Conference on Neural Information Processing Systems (NeurIPS 2026). Workshop: E-Values: From Statistics to ML

Bayesian neural network predictions are commonly approximated using a fixed number of Monte Carlo samples per input, without controlling the resulting error that comes from this finite sample. We propose the use of confidence sequences to dynamically determine how many samples are needed while maintaining statistical guarantees. We consider several ways in which predictive probabilities are used, including identifying the most likely class, approximating the full predictive distribution, and resolving probability-threshold decisions. Sampling stops once the corresponding decision can be made with the desired guarantee. Experiments show that the method allocates the computational budget efficiently, assigning more samples to ambiguous inputs than to easy inputs while preserving reliable decisions and reducing overall latency relative to a fixed Monte Carlo budget.

0.39

IQS-BO: In-Context Query Selection for Bayesian Optimisation

cs.LG stat.ML ·2026-10-01 ·Luca Geminiani, Nadja Klein
similarity 0.55
Abstract

Bayesian Optimisation (BO) is a powerful framework for the optimisation of expensive black-box functions, but typically requires refitting a surrogate and maximising an acquisition function at every evaluation step. In-context approaches based on Prior-data Fitted Networks (PFNs) amortise part of this cost by pre-training transformers on functions drawn from synthetic priors. PFNs4BO amortises the surrogate but still relies on a numerically maximised acquisition function, while FIBO performs BO fully in-context by sampling optimiser locations from a learned density, which fixes the decision rule and admits no surrogate. Learned acquisition functions score a finite candidate set with a trained network, but, lacking a label for the query, learn the score by reinforcement learning on previously solved tasks. We propose IQS-BO, a PFN that learns the query decision by supervised learning on synthetic priors. In a single forward pass, IQS-BO predicts the probability that each candidate maximises the objective over the set, and we show that the minimiser of its objective is the posterior probability of this event. The model can be pre-trained without a surrogate for fully in-context BO, or take the predictions of a fixed probabilistic surrogate as additional input, amortising only the decision step. Our method proposes queries at a fraction of the cost of acquisition-based methods, while either matching or outperforming standard BO with Gaussian processes (GPs) and available in-context methods on synthetic and real-world benchmarks. Finally, we propose a mixture prior for pre-training PFNs which combines samples from GPs with functions exhibiting warped inputs, isolated narrow optima, or plateaus that are poorly modeled by stationary kernels common in GP surrogates. We show that pre-training on this prior can lead to improved optimisation performance.

0.12

On the Structural Limits of Machine Learning Decision Systems: An Information-Theoretic, Interaction-Based, and Stochastic-Dynamical Perspective

cs.LG math.ST ·2026-08-13 ·Nestor R. Barraza, Gabriel Pena
published similarity 0.55
Abstract

Machine learning procedures are commonly evaluated in terms of predictive accuracy and computational efficiency. However, their achievable performance is fundamentally constrained by structural properties of the underlying data-generating process, which are formalized in terms of informational bounds. In this work we examine intrinsic limits of data-driven decision systems from an information-theoretic and interaction-based perspective. We analyze minimal achievable error in classification through Fano-type bounds and precision limits in parametric estimation via the Cramér-Rao inequality, emphasizing that such limits depend on the underlying model rather than on algorithmic sophistication alone. We further discuss how implicit assumptions, such as independence, ergodicity, and distributional stability, affect the validity of inferential procedures. Building on interaction-based modeling principles, we review typical frameworks such as Markov Random Fields and potential based representations for encoding dependence mechanisms. We also describe decision systems, including LLM-integrated agent architectures, as feedback-driven stochastic processes where state-dependent dynamics may induce emergent macroscopic behavior. This perspective highlights the importance of having adequate models for the data as a prerequi- site for expanding predictive capability, and situates algorithmic learning within the informational limits imposed by the models.

0.28

Large-System Analysis of Sparse Bayesian Learning

eess.SP cs.IT ·2026-09-06 ·Fangqing Xiao, Dirk T. M. Slock
similarity 0.55
Abstract

Sparse Bayesian learning is widely used for sparse linear inverse problems, yet its large-system stationary behavior remains poorly understood because all variance hyperparameters are estimated from the same data. We study classical sparse Bayesian learning, formulated as evidence maximization (type-II maximum likelihood), for underdetermined linear models with sensing matrices having independent and identically distributed Gaussian entries, Gaussian measurement noise, and an unknown deterministic signal sequence. Hyperparameter reoptimization induces a nonvanishing feedback term: a typical coordinate obeys a reoptimization-corrected scalar Gaussian law whose signal coefficient is governed by the normalized adaptive response rather than the frozen resolvent trace. A one-coordinate leave-one-out construction gives an exact conditional Gaussian law, which is transferred to a selected full stationary branch without assuming asymptotic closeness of the reduced and full stationary vectors. Combining this law with the Karush--Kuhn--Tucker conditions of the evidence objective yields a generally set-valued scalar relation and three branchwise large-system consistency relations. If the model noise variance is jointly estimated by evidence maximization, interior joint stationarity yields an exact finite-dimensional equality between the normalized residual energy and normalized resolvent trace. When the limiting signal law has nonzero mass at zero, this identity further yields a parameter-free asymptotic chi-square null law. Under an additional differentiability condition on the selected scalar branch, the large-system characterization also gives a closed relation for the reconstruction error of the posterior mean. The analysis is stationary-point based and permits multiple stationary branches.

0.32