cs.LGNov 14, 2026

Neural Dual Bounds: Valid-by-Construction JGLP Warm-Starts for MAP and Constrained MAP

Authors: Akshay Vyas, Shivvrat Arya, Brij Malhotra, Tahrima Rahman, Vibhav Gogate, Nicholas Ruozzi

Organizations: Department of Computer Science, The University of Texas at Dallas · Department of Computer Science, New Jersey Institute of Technology

Abstract

We present Neural Dual Bounds, a calibration-free framework that produces deterministic upper bounds for MAP inference in probabilistic graphical models using a single neural-network forward pass. The framework trains a network to output the edge messages of a mini-bucket style upper bound on a given join-graph decomposition in a self-supervised manner by directly minimizing a smooth dual objective. The output of this network can be used at test time to warm-start a standard JGLP optimizer. Across diverse benchmarks, this warm start yields dual gaps that are orders of magnitude tighter than those from zero initialization, with the largest gains in the early-iteration regime. We also apply our framework for the constrained MAP (CMPE) task, where neural warm starts with test-time adaptation are comparable to the adaptive baseline on Bayesian networks and achieve the tightest dual gaps, by one to two orders of magnitude, on the grid and segmentation families.

Figures & tables

Appendix figures & tables41 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference

    Oct 29, 2026Akshay Vyas, Hailiang Dong, Shivvrat Arya +4Probabilistic Graphical ModelsAmortized Inference

  2. ReMAP: Lossless Residual Neural Lifting for Scalable MAP Inference in Arbitrary-Order Markov Random Fields

    Nov 28, 2024Yaomin Wang, Chaolong Ying, Xiaodong Luo +1MAP EstimationMarkov Random Fields

  3. Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs

    Sep 24, 2026Ralf Herbrich, Rainer Schlosser, Jan Lemcke +11Efficient InferenceUncertainty Quantification