Technical Summary: Probably Approximately Correct Maximum A Posteriori Inference

Problem Statement

The Maximum A Posteriori (MAP) assignment—the computation of the conditional mode of a distribution given evidence—is a fundamental task in probabilistic inference, with applications ranging from disease diagnosis to image correction. However, MAP inference is generally intractable. Even under common structural constraints (such as those in Bayesian Networks or Probabilistic Graphical Models) and approximation schemes, the problem remains NP-complete (for Most Probable Explanation, MPE) or NPPP-complete (for Marginal MAP, MMAP). Exact polynomial-time solutions are typically restricted to deterministic circuits, which severely limit expressive capacity.

Existing supervised learning approaches often fail to address the generative nature of MAP, as they require a priori selection of outcome variables and complete feature vectors. Furthermore, while randomized MAP solvers exist in the literature, they often rely on strong parametric assumptions and lack rigorous theoretical guarantees regarding solution quality.

Methodology

The authors propose a novel approach inspired by multi-armed bandits, recasting the MAP problem as a Best Arm Identification (BAI) task. In this formulation, each possible assignment $q$ in the query space represents an "arm," and its reward is the conditional probability $p(q|e)$. The goal is to identify an arm that is "probably approximately correct" (PAC)—specifically, an assignment $\hat{q}$ such that $p(\hat{q}|e) \geq p^*(1-\epsilon)$ with probability at least $1-\delta$, where $p^*$ is the true maximum probability.

The paper introduces three primary algorithmic strategies:

1. Purely Random PAC-MAP ($\pi_R$):
   This algorithm performs uniform exploration by drawing independent and identically distributed (i.i.d.) samples from the conditional distribution $P(Q|e)$. It maintains a lower bound on the maximum probability ($\hat{p}$) based on the best sample found and an upper bound ($\check{p}$) based on the residual mass of unobserved assignments. The algorithm terminates when the lower bound exceeds the upper bound scaled by $(1-\epsilon)$, or when a probabilistic stopping criterion based on the sample count is met. Theoretical analysis shows this approach is uniformly optimal among purely random strategies, with complexity governed by the min-entropy of the distribution.

2. Smooth PAC-MAP ($\pi_S$):
   To address high-entropy distributions where purely random sampling is inefficient, this method incorporates a "smoothness" assumption. It posits that the probability mass function is modally Lipschitz, meaning nearby assignments (in Hamming distance) have similar probabilities. The algorithm augments random exploration with an exploitation step: when a new candidate is found, it performs a "sweep" of a Hamming ball around that candidate, evaluating all neighbors via an oracle. This leverages local structure to accelerate convergence. The complexity is shown to be minimax optimal under the smoothness assumption, with a speedup factor determined by the effective mass of the near-modal region.

3. Budget PAC-MAP ($\pi_B$):
   Recognizing that fixed-confidence guarantees may be infeasible for high-dimensional problems within practical time limits, the authors propose a fixed-budget variant. Instead of stopping at a target confidence, this algorithm runs for a pre-specified number of samples $M$. It then outputs a Pareto frontier of admissible $(\epsilon, \delta)$ pairs, describing the trade-off between error tolerance and failure probability given the observed data. This provides "anytime-valid" certificates for heuristic solutions.

The algorithms are implemented using Probabilistic Circuits (PCs), specifically Sum-Product Networks (SPNs), which serve as both the sampler (generating $q \sim P(Q|e)$) and the oracle (computing exact $p(q|e)$ values).

Key Contributions

The paper makes four primary contributions:

1. Reformulation: It reformulates MAP inference as a Best Arm Identification task, developing provably optimal PAC-MAP solvers under minimal assumptions.
2. Tractability Characterization: It characterizes the conditions for tractability using information-theoretic measures (min-entropy and Rényi divergence) that can be estimated or bounded from finite samples. Specifically, it establishes that purely random PAC-MAP is tractable if and only if the min-entropy grows at most logarithmically with the dimension $n$.
3. Fixed-Budget Policies: It derives Pareto-optimal PAC-MAP policies for fixed-budget scenarios, inverting standard bounds to provide rigorous guarantees even when exact convergence is not reached.
4. PAC Certificates for Heuristics: The framework allows any existing MAP approximator to be paired with these solvers to issue PAC certificates, fortifying heuristic solutions with rigorous theoretical guarantees.

Experimental Results

The authors evaluated their methods on the "Twenty Datasets" benchmark using trained Sum-Product Networks. They compared $\pi_R$ and $\pi_S$ against several state-of-the-art approximate MAP solvers, including Independent (Ind), MaxProduct (MP), ArgMaxProduct (AMP), Hybrid Belief-Propagation (HBP), and the neural-network-based ITSELF.

• Performance: The smooth PAC-MAP solver ($\pi_S$) consistently dominated the purely random version ($\pi_R$) and outperformed competitors in low-dimensional settings (query proportion $\leq 20\%$). In high-dimensional settings (50% query), AMP often performed better, though $\pi_S$ typically secured second place.
• Warm Starts: When initialized with the output of the AMP heuristic, $\pi_S$ improved upon the AMP solution in 40% of trials. Crucially, even when it did not find a better solution, it provided a PAC certificate for the AMP result, increasing confidence in the heuristic's output.
• Relaxed Guarantees: In cases where fixed-confidence algorithms timed out, the fixed-budget approach successfully generated Pareto-optimal certificates. For example, on the baudio dataset, a solution was certified with $\epsilon=0.01$ and $\delta=0.011$, very close to the target $\delta=0.01$.
• Runtime: As expected, the randomized solvers incurred higher computational costs than linear-time heuristics like MaxProduct, reflecting the overhead required for theoretical guarantees. However, they remained competitive with other complex solvers like ITSELF and HBP.

Significance and Claims

The paper claims to be the first work to apply a bandit-theoretic approach to MAP inference. Its significance lies in bridging the gap between the theoretical rigor of PAC reasoning and the practical capabilities of probabilistic models.

The authors argue that while exact MAP inference is often intractable, introducing non-zero error tolerance ($\epsilon$) and failure probability ($\delta$) allows for efficient, provably optimal solutions in many practical cases. They emphasize that their methods do not merely replace existing heuristics but can enhance them: by using PAC solvers as a "warm start" or a verification layer, practitioners can obtain solutions that are either improved or rigorously certified.

The paper acknowledges limitations, noting that it does not provide exact solutions (except in simple cases) and that tractability depends on the min-entropy of the distribution. However, it posits that the fixed-budget approach offers a viable alternative for high-entropy problems, returning the best possible guarantees within a given computational budget. The work suggests that randomization is an underexplored avenue in Probabilistic Circuits, which are traditionally valued for exact inference, and opens new directions for adaptive search and randomized MAP inference.