The Limits of Tractable Marginalization

• URL: http://arxiv.org/abs/2506.12020v2
• Date: Mon, 14 Jul 2025 18:43:07 GMT
• Title: The Limits of Tractable Marginalization
• Authors: Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck, Markus Bläser,
• Abstract summary: Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem.<n>We show that when there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation.<n>We conclude with a result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation.
• Score: 23.716205079188608
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem with applications from probabilistic inference to formal verification. Despite its computational hardness in general, there exist many classes of functions (e.g., probabilistic models) for which marginalization remains tractable, and they can be commonly expressed by polynomial size arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming $\textsf{FP}\neq\#\textsf{P}$ (an assumption implied by $\textsf{P} \neq \textsf{NP}$). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation.

Related papers

• On the Hardness of Approximating Distributions with Probabilistic Circuits [8.582070926175966]
  We show that approximating an arbitrary distribution with bounded $f$-divergence is $mathsfNP$-hard for any model that can tractably compute marginals.<n>We then prove an exponential size gap for approximation between the class of decomposable PCs and additionally deterministic PCs.
  arXiv  Detail & Related papers  (2025-06-02T03:35:07Z)
• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  Reinforcement learning with outcome-based feedback faces a fundamental challenge.<n>How do we assign credit to the right actions?<n>This paper provides the first comprehensive analysis of this problem in online RL with general function approximation.
  arXiv  Detail & Related papers  (2025-05-26T17:44:08Z)
• Complementary polynomials in quantum signal processing [0.0]
  To implement a given $P$, one must first construct a corresponding complementary $Q$.<n>Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis.<n>We present a new approach to complementarys using complex analysis.
  arXiv  Detail & Related papers  (2024-06-06T16:47:11Z)
• Polynomial Semantics of Tractable Probabilistic Circuits [29.3642918977097]
  We show that each of these circuit models is equivalent in the sense that any circuit for one of them can be transformed into a circuit for any of the others with only an increase in size. They are all tractable for marginal inference on the same class of distributions.
  arXiv  Detail & Related papers  (2024-02-14T11:02:04Z)
• Provable General Function Class Representation Learning in Multitask Bandits and MDPs [58.624124220900306]
  multitask representation learning is a popular approach in reinforcement learning to boost the sample efficiency. In this work, we extend the analysis to general function class representations. We theoretically validate the benefit of multitask representation learning within general function class for bandits and linear MDP.
  arXiv  Detail & Related papers  (2022-05-31T11:36:42Z)
• On the energy landscape of symmetric quantum signal processing [1.5301252700705212]
  We prove that one particular global (called the global minimum) solution belongs to a $0$ on which the cost function is on which the cost function is a global. We provide an explanation of a partial explanation of optimization algorithms.
  arXiv  Detail & Related papers  (2021-10-11T04:16:48Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.