Certifiable Estimation with Factor Graphs

• URL: http://arxiv.org/abs/2603.01267v1
• Date: Sun, 01 Mar 2026 20:50:51 GMT
• Title: Certifiable Estimation with Factor Graphs
• Authors: Zhexin Xu, Nikolas R. Sanderson, Hanna Jiamei Zhang, David M. Rosen,
• Abstract summary: We show that factor graph structure is preserved under Shor's relaxation and Burer-Monteiro factorization.<n>Applying these transformations to a QCQP with an associated factor graph representation yields a lifted problem admitting a factor graph model with identical connectivity.
• Score: 11.391420452904166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Factor graphs provide a convenient modular modeling language that enables practitioners to design and deploy high-performance robotic state estimation systems by composing simple, reusable building blocks. However, inference in these models is typically performed using local optimization methods that can converge to suboptimal solutions, a serious reliability concern in safety-critical applications. Conversely, certifiable estimators based on convex relaxation can recover verifiably globally optimal solutions in many practical settings, but the computational cost of solving their large-scale relaxations necessitates specialized, structure-exploiting solvers that require substantial expertise to implement, significantly hampering practical deployment. In this paper, we show that these two paradigms, which have thus far been treated as independent in the literature, can be naturally synthesized into a unified framework for certifiable factor graph optimization. The key insight is that factor graph structure is preserved under Shor's relaxation and Burer-Monteiro factorization: applying these transformations to a QCQP with an associated factor graph representation yields a lifted problem admitting a factor graph model with identical connectivity, in which variables and factors are simple one-to-one algebraic transformations of those in the original QCQP. This structural preservation enables the Riemannian Staircase methodology for certifiable estimation to be implemented using the same mature, highly-performant factor graph libraries and workflows already ubiquitously employed throughout robotics and computer vision, making certifiable estimation as straightforward to design and deploy as conventional factor graph inference.

Related papers

• Structure-Aware Robust Counterfactual Explanations via Conditional Gaussian Network Classifiers [0.26999000177990923]
  This work presents a structure-aware robustness-and-counterfactual search method based on conditional conditional graphs.<n>Results show that our method achieves strong consistency, with direct optimization of the original formulation providing especially stable dependencies.<n>The proposed framework lays the groundwork for future advances in counterfactual reasoning under noncyclic constraints.
  arXiv  Detail & Related papers  (2026-02-08T15:51:45Z)
• Graph Reasoning Paradigm: Structured and Symbolic Reasoning with Topology-Aware Reinforcement Learning for Large Language Models [45.28250076657801]
  Long Chain-of-Thought (LCoT) has proven effective in enhancing the reasoning capabilities of Large Language Models (LLMs)<n>Despite RLVR-based optimization, existing methods still suffer from coarse-grained supervision, reward hacking, high training costs, and poor generalization.<n>We propose the Graph Reasoning Paradigm (GRP), which realizes structured and symbolic reasoning, implemented via graph-structured representations with step-level cognitive labels.
  arXiv  Detail & Related papers  (2026-01-19T12:23:00Z)
• Theoretical Foundations of Scaling Law in Familial Models [46.506708373314375]
  We introduce Granularity (G) as a fundamental scaling variable alongside model size (N) and training tokens (D)<n>Our results reveal that the granularity penalty follows a multiplicative power law with an extremely small exponent.<n> Practically, it validates the "train once, deploy many" paradigm, demonstrating that deployment flexibility is achievable.
  arXiv  Detail & Related papers  (2025-12-29T12:01:58Z)
• Deep Unfolding: Recent Developments, Theory, and Design Guidelines [99.63555420898554]
  This article provides a tutorial-style overview of deep unfolding, a framework that transforms optimization algorithms into structured, trainable ML architectures.<n>We review the foundations of optimization for inference and for learning, introduce four representative design paradigms for deep unfolding, and discuss the distinctive training schemes that arise from their iterative nature.
  arXiv  Detail & Related papers  (2025-12-03T13:16:35Z)
• Graph-Memoized Reasoning: Foundations Structured Workflow Reuse in Intelligent Systems [0.0]
  We introduce Graph-Memoized Reasoning, a formal framework for representing, storing and reusing reasoning as graph-structured memory.<n>By encoding past decision graphs and retrieving them through structural and semantic similarity, our approach enables compositional reuse of subgraphs across new reasoning tasks.
  arXiv  Detail & Related papers  (2025-11-11T07:42:37Z)
• A General and Streamlined Differentiable Optimization Framework [10.851559133306196]
  This paper presents the DiffOptl interface for Julia optimization framework.<n>A first-class JuMP-native API allows users to obtain named parameters derivatives directly with respect to them.<n>Results demonstrate that differentiing a routine can be as a training tool for experimentation, learning, and design-without deviating from standard JuMP modeling practices.
  arXiv  Detail & Related papers  (2025-10-29T21:42:36Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  We propose an end-to-end deep learning (DL) framework with low inference complexity for symbol-level precoding.<n>We show that the proposed framework captures substantial performance gains of optimal SLP, while achieving an approximately 80-times speedup over conventional methods.
  arXiv  Detail & Related papers  (2025-10-02T15:15:50Z)
• TRACE: Learning to Compute on Graphs [15.34239150750753]
  We introduce textbfTRACE, a new paradigm built on an architecturally sound backbone and a principled learning objective.<n>First, TRACE employs a Hierarchical Transformer that mirrors the step-by-step flow of computation.<n>Second, we introduce textbffunction shift learning, a novel objective that decouples the learning problem.
  arXiv  Detail & Related papers  (2025-09-26T05:22:32Z)
• A Theory of Inference Compute Scaling: Reasoning through Directed Stochastic Skill Search [15.387256204743407]
  Large language models (LLMs) demand considerable computational, energy, and financial resources during both training and deployment.<n>Inference costs now represent a significant and growing component of the overall resource burden.<n>We introduce directed skill search (DS3), a general framework that represents inference as expressive over a learned skill graph.
  arXiv  Detail & Related papers  (2025-06-10T14:47:48Z)
• Partial Transportability for Domain Generalization [56.37032680901525]
  Building on the theory of partial identification and transportability, this paper introduces new results for bounding the value of a functional of the target distribution.<n>Our contribution is to provide the first general estimation technique for transportability problems.<n>We propose a gradient-based optimization scheme for making scalable inferences in practice.
  arXiv  Detail & Related papers  (2025-03-30T22:06:37Z)
• Enhancing LLM Reliability via Explicit Knowledge Boundary Modeling [41.19330514054401]
  Large language models (LLMs) are prone to hallucination stemming from misaligned self-awareness.<n>We propose the Explicit Knowledge Boundary Modeling framework to integrate fast and slow reasoning systems to harmonize reliability and usability.
  arXiv  Detail & Related papers  (2025-03-04T03:16:02Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  This paper proposes the first end-to-end differentiable meta-BO framework that generalises neural processes to learn acquisition functions via transformer architectures. We enable this end-to-end framework with reinforcement learning (RL) to tackle the lack of labelled acquisition data.
  arXiv  Detail & Related papers  (2023-05-25T10:58:46Z)
• Accurate and Robust Feature Importance Estimation under Distribution Shifts [49.58991359544005]
  PRoFILE is a novel feature importance estimation method. We show significant improvements over state-of-the-art approaches, both in terms of fidelity and robustness.
  arXiv  Detail & Related papers  (2020-09-30T05:29:01Z)

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.