CS Paper Radar

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

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

cs.LG cs.AI ·submitted 2026-11-14 07:22 UTC · v1
top venuetheory

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.

Comment
NeurIPS 2026 (Spotlight). 40 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG cs.AI ·2026-10-29 ·Akshay Vyas, Hailiang Dong, Shivvrat Arya, Brij Malhotra, Tahrima Rahman +2 more
similarity 0.71
Abstract · 37 pages, 4 figures

Probabilistic graphical models (PGMs) compactly encode structured joint distributions, but Most Probable Explanation (MPE), which finds the highest-probability assignment to unobserved variables, remains computationally intractable in large, densely structured models. Anytime systematic search, such as branch-and-bound (B&B), is a popular approach, but its efficiency depends on tight admissible upper bounds that are often prohibitively expensive to compute using classical methods like Mini-Bucket Elimination (MBE). We introduce Learning to Bound (L2B), a data-driven framework that amortizes bound computation cost by training a neural predictor. L2B targets two key properties required for effective search bounds: admissibility, which is achieved via statistical calibration techniques, and progressive tightening as evidence accumulates, which is enforced through structural architectural constraints that ensure monotonicity by construction. Across challenging benchmarks, L2B delivers tighter, monotonic bounds at orders-of-magnitude lower cost on every PGM family, and yields measurable improvements when integrated with branch-and-bound on high-treewidth instances.

0.21

Neural Algorithmic Reasoning for Graph Saddle Point Problems

cs.LG ·2026-10-05 ·Samantha Chen, Jesse He, Coleman Clougherty, Gal Mishne, Chester Holtz
similarity 0.64
Abstract

Neural algorithmic reasoning, or aligning a neural network with an algorithmic paradigm, has emerged as an approach to solving polynomial-time-solvable and computationally harder combinatorial optimization problems. We propose a new message-passing framework based on the Chambolle-Pock Primal--Dual Hybrid Gradient (PDHG) method called \textsc{GraphPDHG} for solving general graph saddle-point problems. Theoretically, we show that \textsc{GraphPDHG} can efficiently solve a family of graph saddle-point problems by simulating PDHG. We also show that our network can learn an accelerated PDHG algorithm. Experimentally, we support our results on accelerated PDHG by evaluating the performance of our model as a learned warm start for second-order optimization techniques (SSNAL). We also show that alignment with PDHG leads to stronger size generalization than non-aligned graph neural network (GNN) baselines. Overall, we propose a novel architecture for solving a general family of optimization problems on graphs.

0.24

Mitigating Representation Gaps in Amortized Bayesian Inference with Auxiliary Supervision

cs.LG stat.MLstat.COstat.ME ·2026-09-30 ·Hans Olischläger, Svenja Jedhoff, Šimon Kucharský, Aayush Mishra, Stefan T. Radev +1 more
similarity 0.62
Abstract

Casting Bayesian inference as a neural network optimization problem targeting an amortized posterior is attractive, as it extends to otherwise intractable statistical models and offers near instantaneous inference for new datasets after prepaying the training cost. Although theory guarantees faithfulness under ideal convergence, practical amortized inference still requires iterating over architectures and optimization choices and ultimately ``satisficing'' under finite simulation, compute, and time budgets. Even the best-performing solution may thus retain avoidable representation gaps that typically require problem-specific fixes. Here, we propose a generic alternative which improves training dynamics with auxiliary guidance losses applied to internal representations. Specifically, we show how such guidance leads to faster convergence when training data is abundant and to better performance when it is scarce. We formalize representation gaps as getting stuck in a local optimum at the information bottleneck between the parts of the network tasked with feature learning and those tasked with conditional distribution learning, and offer a generic diagnostic to separate summary failures from inference failures. Finally, we demonstrate that auxiliary supervision improves convergence speed and accuracy on a range of challenging real-world inference problems.

0.27

Looped GNNs Beyond Fixed Depth: Graph Size Generalization and Parameter-Efficient Adaptation

cs.LG ·2026-10-16 ·Zhiyang Wang, Zhishang Luo, Yusu Wang
similarity 0.61
Abstract · 36 pages, 12 figures

Generalizing from small graphs to larger ones can require computation beyond the depth of a neural model used during training. We study target tasks that admit a common local iterative computation and whose effective dependency radius grows with graph size. The central idea is to learn a local update rule through GNN pretraining, then repeatedly apply the same learned processor beyond the training depth to extend information reach on larger graphs without retraining. Calling such parameter-shared architecture a \emph{looped GNN}, we categorize six schemes for looped GNNs to separate the effects of depth extension, fine-tuning, and freeze-and-steer adaptation. Our analysis establishes fixed-depth information limits and sufficient conditions under which accurate iterative reuse overcomes them. To improve beyond unadapted reuse, we introduce \emph{Loop-Freeze-Steer} (LFS), which freezes the pretrained processor and learns a small controller to steer its repeated application, using much fewer trainable parameters than full fine-tuning. Our finite-sample analysis gives sufficient conditions for adaptation to improve performance on larger graphs. Experiments on synthetic tasks and chip placement evaluate depth extension and adaptation, highlighting LFS's accuracy--trainable-parameter trade-off for size generalization.

0.20

GEAR: A GPU-Accelerated Global Solver for Bounded Continuous Nonlinear Programs via Linear Bound Propagation

cs.LG math.OCcs.MSmath.NA ·2026-11-07 ·Duo Zhou, Hesun Chen, Xiangru Zhong, Grani A. Hanasusanto, Huan Zhang
top venuecode/data similarity 0.61
Abstract · Accepted by NeurIPS 2026

We present a novel GPU-accelerated global solver for constrained nonlinear programming (NLP) inspired by the efficient linear bound propagation framework in neural network (NN) verification. Existing work on NN verification, a problem that can be cast as feasibility detection for a nonlinear objective, demonstrated orders-of-magnitude speedups with the linear bound propagation-based framework when compared to traditional solvers. Extending this paradigm to global nonlinear programming requires addressing many challenges: a global constrained NLP solver must effectively exploit all, possibly unstructured, nonlinear constraints to improve the objective, whereas NN verification typically handles simple input box constraints over a well-structured NN and does not directly optimize an objective function. We address these challenges by fully exploiting the linear bounds produced by bound propagation: these linear bounds can be viewed as relaxations of nonlinear constraints and used to provide lower bounds, check infeasibility, and guide the search for a primal solution. In addition, we propose tighter linear relaxations for bilinear, quotient, and other commonly used nonlinear functions in NLP problems, and a projected augmented Lagrangian method tightly coupled to our dual solving procedure to produce primal solutions. Our method solves 421 of 505 bounded and continuous NLP problems in the GAMS and MINLPLib benchmarks under a 180-second limit, more than each of the six global solvers we compare with, including Gurobi and BARON (commercial), and SCIP (open-source). Sixteen of these problems are certified by none of the six global solvers; all of them contain exponential, logarithmic, or trigonometric terms, which are often challenging for traditional approaches. Project webpage is at https://verified-intelligence.github.io/GEAR.

0.38

Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning

cs.LG ·2026-10-05 ·Nicolas Hochuli, Lorenzo Miele, Kristina Shea, Tino Stankovic
benchmark similarity 0.60
Abstract

Planar graphs are central to applications across science and engineering, yet existing generators provide limited support for goal-directed generation under hard structural and geometric feasibility constraints. We propose a dataset-free method for generating planar graph embeddings by combining parametric graph grammars with safe reinforcement learning to optimize generic task-specific objectives while satisfying constraints during construction. We formulate the generation process as a constrained Markov decision process, where the graph grammar defines the state and action spaces. We further introduce an action projection that maps sampled actions toward state-dependent safe sets, improving constraint satisfaction during training. In contrast to classical graph generators and deep generative models, which typically offer limited goal-directed control or rely on weak constraint satisfaction, our method constructs feasible planar graph embeddings directly during generation. We also introduce a benchmark suite for constrained and goal-directed planar graph generation, together with classical and deep generative baselines. Across all benchmark tasks, our method consistently outperforms baselines while satisfying the formulated constraints.

0.20

CONSTRAINER: Promptable Graph-Structured Optimization via Constraint Conditioning

cs.LG ·2026-11-07 ·Zeeshan Memon, Mingke Tian, Xinyuan Song, Hongwei Jin, Kibaek Kim +1 more
similarity 0.59
Abstract

Neural methods for graph-structured optimization have achieved strong performance within individual problem classes, but are typically trained for fixed formulations, limiting reuse across related problem variants. Recent progress in foundation models has motivated shared neural backbones trained across multiple graph-structured optimization tasks; however, existing approaches primarily share instance-level representations while treating feasibility constraints implicitly. A key source of shared structure across constrained optimization problems is the constraint set itself, which often exhibits substantial overlap across tasks. We propose CONSTRAINER, a constraint-conditioned framework for graph-structured optimization that treats constraints as structured inputs. Constraint specifications are parsed into operator graphs and encoded using a graph neural network to produce invariant constraint embeddings, which condition a shared backbone model for solution prediction. We evaluate our approach on power grid optimization and mixed-integer linear programming problems, where it shows improved solution optimality and enables efficient transfer learning and generalization compared to baseline methods.

0.07

Probe-Space Preconditioning for Fast and Stable Zero-Order Training

cs.LG ·2026-09-29 ·Francois Chaubard, Mykel J. Kochenderfer, Chris Ré
similarity 0.59
Abstract · 16 pages, 12 figures

Backpropagation (BP) dominates deep learning but imposes a massive memory tax. For example, training OPT-30B with Adam requires $\approx$ 600GB of GPU memory (assuming batch size 8 and sequence length 2048). Alternatively, zero-order optimization (ZOO) trains in inference-mode (requiring only $\approx$ 60GB for the same model): no stored activations, no gradients, and no optimizer states. However, ZOO convergence has lagged behind BP. In this work, we evaluate two methods to close this gap. First, we show that reallocating training compute budget from many steps to large effective batch sizes with many perturbations (or probes) but fewer steps, allows 1SPSA (Spall, 1992) to outperform zero order methods like MeZO (Malladi et al., 2023) with less training compute. Next, we introduce 1.5-SPSA, adding a single "clean" forward-pass per step to 1SPSA to calculate a cheap diagonal preconditioner in probe-space, which improves convergence rate and convergence by down-weighting high curvature directions. Benchmarking on 6 post-training datasets on both Qwen3 and OPT model families, we show that 1.5-SPSA achieves State-of-the-Art results over previous ZOO solvers with much less optimization steps. For example, we train OPT-13B (for direct comparison to MeZO) and find 1.5-SPSA achieves +3.1% accuracy on SST-2 over both MeZO and BP in only 70 steps vs. MeZO's 100,000 steps. Finally, we combine an 8-bit-packing random generator, triton fused unpack/apply kernels, and distributed parallelism to achieve fast and stable training of models as large as OPT-30B in-place on commodity GPUs (e.g. A100).

0.31