acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Maximum a posteriori inference in a finite Markov random field is generally NP-hard. We study an instance-wise optimizer that minimizes the exact multilinear energy under product marginals. The canonical parameterization adds a GNN output to free per-node logits. This residual bypass is a global change of coordinates, so the lifting preserves the infimum, critical points, local extrema (modulo the GNN-parameter fiber), and Hessian inertia of the free-logit problem. Joint gradient flow then induces the preconditioner : the GNN cannot enlarge the feasible set, but it can add dissipation . For a two-layer branch this extra coupling is four-hop local. We also show that every finite critical point of a nonconstant multilinear objective is a saddle, and that a unique MAP gap makes conditional-expectation rounding exact once the relaxed gap falls below ; residual gradient flow and joint gradient descent then obey explicit and rates in a small-gap region, with an improved bound under residual alignment. Experiments on synthetic MRFs, UAI 2022 benchmarks, and Physical Cell Identity (PCI) problems evaluate this residual geometry at scale.

Primary area:
optimization
Keywords:
Markov random fields, Unsupervised learning, Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_baiQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes a method for discrete energy minimization that combines a graph neural network to update free logits through a process called residual GNN lifting. A number of theoretical results are presented with proofs included in the appendix. Experimental results show that the method is competitive with older message passing approaches such as LBP and TRBP, and more recent solvers (toulbar2), although move making (alpha expansion, etc.), primal-dual optimization approaches (e.g., Komodakis et al.) and cutting-plane methods (e.g., Sontag et al.) are missing. The experimental results also do not go so far as to validate details of the theory itself.

Critical strengths
  1. The paper proposes a novel approach for discrete energy minimization that combines graph neural networks with an efficient second-order pre-conditioner. Moreover, the approach is supported by theoretical statements that are proved.
  2. Empirical results show that the method is competitive with standard message passing approaches on standard benchmarks.
Critical weaknesses
  1. I found the paper very difficult to read. Many technical terms and notation are introduced before they are defined. Moreover, there are several places where the same variable is used in very different contexts. For example, a. Phrases in the abstract such as "this residual bypass is a global change of coordinates, so the lifting preserves the infimum, critical points, local extrema (modulo the GNN-parameter fiber), and Hessian inertia of the free-logit problem" and "the GNN cannot enlarge the feasible set" make no sense out of context. Also JJ, ∇ℓ\nabla \ell and tt are all undefined in the abstract. b. The expression z=u+ρv(Gz = u + \rho_v(G is used several times before any of the terms are defined. c. Variables xi∈Xx_i \in {\cal X} suggest the same cardinality for all variables, which contradicts the earlier suggestion that the work addresses heterogeneous label cardinalities (later corrected by introducing variables sis_i). d. Symbols V{\cal V} and Δ\Delta are used to represent different objects at different places in the paper.

  2. Experimental results are lacking. a. I would have liked to have seen results from primal-dual methods and move-making algorithms reported. b. Table 1 claims REMAP is reported as the best of fix seeds. Other methods should similarly be given the benefit of multiple starting seeds/configurations. c. The experiments don't really validate the theory itself, only that the method is competitive with other approaches. It would be good to link empirical observations to some of the bounds and results derived in Section 4.

Questions for authors

Please address the concerns raised above. Namely, that notation and writing can be improved as evidenced by the quality of the rebuttal, and experimental findings especially with respect to empirical validation of the theory.

2 comments

W1 — Readability, definitions, and notation

Thank you for identifying these presentation issues. To meet the page limit, we compressed the exposition too aggressively, particularly in the abstract and the method-to-theory transition. Readers should not need to reconstruct definitions from later sections. We will introduce the method more clearly, define notation before use, and move secondary technical details to the appendix.

The central idea is straightforward:

ReMAP adds graph-neural-network outputs to unrestricted per-node scores and optimizes both for each MRF instance. The unrestricted scores preserve the expressive power of direct score optimization, while the neural component changes the gradient dynamics. Conditional-expectation rounding produces a discrete assignment whose energy is no greater than the resulting distribution’s expected energy.

We will replace the abstract’s discussion of coordinate transformations, parameter fibers, and Hessian inertia with this intuition, reserving formal statements for Section 4. Specifically, “the GNN cannot enlarge the feasible set” means that unrestricted logits already represent every strictly positive categorical distribution over valid labels. The GNN changes the parametrization, not the representable distributions; boundary distributions are approached as limits.

We will make three specific corrections:

  1. Definitions before use. Introduce the communication graph, unrestricted logits, GNN parameters and outputs, temperature, and expected-energy objective before their composite expressions.
  2. Heterogeneous label cardinalities throughout. Use xi∈Xix_i\in\mathcal X_i, si=∣Xi∣s_i=|\mathcal X_i|, and D=∑isiD=\sum_i s_i valid logits from the outset. Padding is only an implementation device: invalid labels are masked before softmax and receive zero probability.
  3. Consistent notation. Remove conflicting symbols, add a notation table, and introduce each theoretical result with its assumptions and intuition.

W2(a) — Strength and coverage of the baseline comparison (primal-dual and move-making methods)

Additional primal-dual and move-making comparisons could broaden the evaluation, but our current baselines are established, competitive MRF solvers. LBP and TRBP are mainstream message-passing methods; SRMP is a strong dual message-passing method included in our higher-order experiments; and Toulbar2 is a leading complete solver that won all MPE and MMAP task categories in the UAI 2022 Inference Competition.

These methods provide substantial coverage of approximate message passing and complete search. Toulbar2 offers a demanding solution-quality comparison, and we report both instances where ReMAP improves upon its returned solution and those where Toulbar2 is stronger. Our empirical claims therefore rest on strong established solvers, not merely ablations or weak baselines.

The absence of additional solver families does not invalidate this evidence. Moreover, ReMAP directly supports arbitrary finite factor tables without metric or submodularity requirements. Comparisons with specialized methods should identify their supported problem classes and account for required reductions.

W2(b) — Multiple runs and best-of-five reporting

Repeated-run selection was not restricted to ReMAP: baseline results were also the best obtained across repeated runs. Thus, ReMAP was not given multiple trials against an arbitrarily selected baseline run.

For ReMAP, Tables 1 and 6 report the best of five seeds, while Table 7 reports mean ± standard deviation over the same trials. Best-of-five measures solution quality with multiple starts; mean ± standard deviation describes typical-run performance and variability.

We will explicitly document each baseline’s run count and initialization or configuration choices, and distinguish best-run from average-run results in the captions and experimental protocol.

Finally, best-of-multiple-run reporting does not itself establish equal-compute performance. We will distinguish solution-quality comparisons under the reported protocols from runtime claims and make the total cost of repeated runs explicit.

W2(c) Experimental Validation of the Theory

Response. Thank you for this suggestion. We agree that competitiveness comparisons alone do not directly validate the theoretical mechanism. We have therefore added Section 5.5, “Empirical diagnostics of the theoretical prediction” (Figures 2–3), and Appendix I, “Multi-seed validation of the local descent prediction” (Figure 6). These additions are marked in red in the revised manuscript.

The new experiments directly examine the dissipation identity in Theorem 4.6, Eq. (16). Using the notation of Section 4, we define

A=∥q∥22,B=∥Jv⊤q∥22=Be+BωA=\|q\|_2^2,\qquad B=\|J_v^\top q\|_2^2=B_e+B_\omega,

where q=∇ℓτ(z)q=\nabla\ell_\tau(z), and BeB_e and BωB_\omega are the squared gradient norms associated with node embeddings and shared GNN weights, respectively. Thus, B/AB/A is precisely the diagnostic alignment ratio βt\beta_t introduced in Section 4. At a fixed checkpoint, the corresponding first-order predictions for ordinary-gradient probes are

Δf=ηA+o(η),Δr=η(A+B)+o(η),\Delta_f=\eta A+o(\eta),\qquad \Delta_r=\eta(A+B)+o(\eta),

so the predicted extra decrease in the relaxed objective is ηB\eta B. We test this connection in three complementary ways:

  1. Predicted versus measured extra descent (Section 5.5, Figure 2). At sampled Adam training checkpoints, we initialize the free and residual branches at identical logits and apply independent ordinary-gradient probes, each starting afresh from the checkpoint. Figure 2 displays the individual checkpoint–step-size pairs for seed 1211 on PCI.1–PCI.5. Smaller-step probes closely track Δr−Δf=ηB\Delta_r-\Delta_f=\eta B, whereas larger steps exhibit greater deviations, including negative extra descent at some checkpoints. Valid nonpositive measurements are retained in the error analysis, although they cannot appear on the logarithmic vertical axis.

  2. Multi-seed quantitative agreement on fixed checkpoint subsets (Appendix I, Figure 6). We repeat the analysis for five seeds, {1211,66,88,6688,42}\{1211,66,88,6688,42\}, using the relative discrepancy ε=∣Δr−ΔfηB−1∣.\varepsilon=\left|\frac{\Delta_r-\Delta_f}{\eta B}-1\right|. Within each instance–seed pair, we use the same checkpoints at every tested step size: all required diagnostic quantities must be finite and ηB>10−8\eta B>10^{-8} at every step size. This prevents step-size-dependent filtering from changing the checkpoints being compared. We first compute the median error within each seed and then aggregate across seeds, rather than treating checkpoints as independent replicates. Across all five instances, the aggregate error generally decreases as the probe step size is reduced, supporting the local first-order prediction without claiming strict monotonicity or a particular convergence order.

  3. Magnitude and source of the additional dissipation (Section 5.5, Figure 3). We report B/AB/A and the components AA, BB, BeB_e, and BωB_\omega over the five seeds. Ratios are computed within each seed before aggregation. Across the displayed checkpoints and seeds, B/AB/A remains far above one, and the additional term is dominated by the shared-weight contribution BωB_\omega. This shows that the additional dissipation term in Theorem 4.6 is substantial relative to the baseline term on the tested trajectories, rather than merely being present symbolically.

We also clarify the scope of these observations in Section 5.5 and Appendix I. They support the local dissipation mechanism of Theorem 4.6 and quantify its parameter-block contributions; they do not establish a trajectory-wide alignment bound, verify the two-layer four-hop locality claim of Proposition 4.8, or guarantee faster end-to-end Adam training. In particular, the checkpoints are generated by Adam, but the probes test ordinary-gradient updates, matching the local theoretical prediction rather than the Adam update rule.

These additions therefore connect measured quantities directly to a specific theoretical identity and its alignment ratio, going beyond the original performance comparisons.

Reviewer_aPr6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces a method, ReMAP, to find incumbents, i.e., lower-energy MAP solutions, for Markov random field instances. The method employs a graph neural network to extract features from the clique-expanded graph and adds the extracted features to free logits. The authors show that their method does not change either the optimal energy value or the set of optimal incumbents. Using the synthetic and real-world benchmarks, the authors compare ReMAP to the state-of-the-art baselines.

The paper is well-written, but sometimes the notations precede the definitions, which forces the reader to guess their meanings (e.g., sis_i on line 176 or the meaning of vv in ρv\rho_v). The main text does not include the Related Work and does not discuss the existing state-of-the-art message-passing baselines. I find that a short discussion on the existing methods can help the reader to better position ReMAP among existing methods (for instance by sacrificing Section 3.3).

Although being a theoretically justified method, ReMAP fails to outperform other baselines on both synthetic and real-world benchmarks. The results provided in Tables 1 – 3 show mixed results. Moreover, additional results on the UAI challenge from the Appendix show that ReMAP falls short for any instance it was tested on. From the tables reported, it is hard to judge why ReMAP is beneficial compared to other methods.

Overall, in its current state, the paper lacks enough evidence to show why the proposed and justified method is preferable to existing approaches.

Critical strengths
  • The main strength of the paper is its theoretical justification of the method. The authors show that adding a free-logit bypass does not change the optimal value or the set of reachable optima.
Critical weaknesses
  • The results the authors show are not sufficient to convince the reader that the proposed method is advantageous. The results on the synthetic datasets are mixed (please see the Questions section). On the real-world datasets, ReMAP outperforms the benchmarks on 2 of 5 PCI instances (Table 3 in the paper) and does not improve on any of the UAI instances reported in Table 8.
Questions for authors
  1. From Table 1, ReMAP outperforms other methods as the problem size scales up. However, it is hard to draw insightful conclusions from the table, as both graph size and average degree (2 * #Edges / #Nodes) change. It seems that in Table 6 in the Appendix, the authors keep the same average degree for smaller graphs (1k, 5k, and 10k), and test under varying average degree for larger graphs, i.e., #Nodes = 50k. As Table 6 indicates, for the fixed average degree d_avg = 15, ReMAP is able to catch up to the performance of other methods for graphs with 50k nodes.
    1. Will ReMAP outperform the baselines when the graph size is further scaled up?
    2. What is the performance of the baselines on smaller graphs (#Nodes = 1k, 5k, 10k) at other average degrees, such as 10 (P_potts_4 and 5)?
    3. Why do LBP and TRBP perform so differently for P_potts_4 and 5?
  2. From the text, it was not straightforward for me how the synthetic high-order instances were generated. Can the authors make it more explicit? This will make reading the results from Table 2 easier.
  3. Can the authors specify the time limit for the methods in Table 2? What was the incumbent’s energy found by Toulbar2 during the given time constraints? Can the authors specify how energy changes over time for the methods they compare?
  4. What is the time required by the methods reported in Tables 6 and 8?
  5. Possible typos:
    1. Line 30: An orphaned dot; perhaps it belongs to the abstract.
    2. Line 401: Should it be “Pairwise”?
2 comments

W1 & Q1.1.Q1.2

Our main finding is that ReMAP matches the strongest traditional baselines on small-scale problems and outperforms them on the tested large-scale, complex problems, as supported by Table 6 and the PCI experiments in Tables 3 and 4. These comparisons establish an empirical performance advantage, not a claim that node count alone causes it. While Table 6 does not cover the requested smaller graphs at average degree 10, those configurations would further characterize the performance boundary rather than invalidate the reported improvements. To directly address scalability beyond 50k nodes, we conducted additional experiments under the same settings and evaluation budgets. As shown below, ReMAP continues to outperform the baselines on these larger instances.

Instances#Nodes/#EdgesLBPTRBPToulbar2Remap
P_Potts_80k80k/19981-160439-143354-161734-167217
P_potts_100k100k/249485-200782-181988-205685-210513
P_random_80k80k/199710-147012-146135-149672-149764
P_random_100k100k/249819-183404-182268-186880-186970

Q1.3 — LBP versus TRBP on P_potts_4/5

Similar average degree does not imply similar inference difficulty. Degree omits cycle structure and the configuration of potentials; moreover, LBP and TRBP use different update rules and need not rank instances identically. Their differing behavior is therefore not, by itself, an inconsistency in the benchmark.

Q2 — Higher-order instance generation

We construct the higher-order instances by first generating a random graph and then augmenting it with randomly sampled cliques. At each step, we randomly select a group of 3–6 nodes and add any missing edges among them to form a clique. Each selected group defines the scope of a higher-order factor. We repeat this process until the graph reaches the prescribed average-degree limit, and then populate the factor energy tables with random values.

Importantly, the clique edges provide the communication structure for the GNN; they do not replace a higher-order factor with pairwise factors. Each higher-order factor is evaluated on the joint label assignment of all variables in its scope, and ReMAP retains these original higher-order factors in its expected-energy objective. Thus, clique expansion is used for message passing, not as a pairwise approximation to the higher-order objective.

We have added Appendix.N “Generation of synthetic higher-order instances” to describe the instance-generation procedure and clarify that clique expansion is used only for GNN message passing, while the original higher-order factors are retained in the expected-energy objective without pairwise approximation.

Q3 — Table 2 budgets and Toulbar2 incumbents

Thank you for highlighting the distinction between a timeout and the absence of a feasible solution. In our Table 2 experiments, Toulbar2 did not return a feasible assignment within the 18,000-second time limit. The NA entries therefore indicate that no feasible incumbent was available to report, rather than merely that Toulbar2 failed to certify optimality. We will clarify this meaning in the table caption and experimental protocol. In contrast, both SRMP and ReMAP reached their convergence criteria and returned feasible solutions. Thus, Table 2 compares their converged solution energies, while recording that Toulbar2 produced no feasible solution within the allotted budget. This is a practical outcome under the reported settings, not a claim that Toulbar2 could not find a feasible or better solution with additional time. We will also make the stopping criteria and computational budgets for each method explicit.

Q4 — Runtime for Tables 6 and 8

The existing settings are: Table 6 uses 60 LBP/TRBP iterations, an 18,000-second Toulbar2 cap, and up to 150 ReMAP iterations with five seeds; Appendix G specifies 30 LBP/TRBP iterations, a 1,200-second Toulbar2 cap, and up to 100 ReMAP iterations for Table 8.

Q5 — Typos

We have fixed the typos in the revised paper. Thanks for your advice.

Reviewer_aPr6OpenReview ↗

Thank you for the answers, but the main weakness remains unresolved

I thank the authors for their response and the additional results provided. The new results on larger synthetic graphs suggest that GNNs could achieve potential gains in finding MAP solutions. I also appreciate the added Appendix section explaining how the high-order instances are generated. However, the advantage of ReMAP in the large-scale synthetic setup does not generalize to real-world benchmarks. I therefore think the main weakness has not yet been resolved.

Reviewer_h2SCOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper tackles the problem of finding the MAP assignment in an MRF. To do this, the authors add a residual GNN lifting. The authors prove convergence rates for gradient flow, and show conditions for exact recovery. Experiments on synthetic high-order MRFs, UAI 2022 benchmarks, and real-world problems show the value of the approach.

Critical strengths

MAP inference is a classic problem, and the use of a powerful GNN to solve the problem in a continuous lifted space makes sense at a hgih-level. Experimental results show that the method is comparable to other MAP solvers.

Critical weaknesses

My main problem with this paper is that I found it very difficult to understand. The MAP inference problem and GNNs are clear, but beyond that, there is a lot of jargon (free per-node logits, residual bypass, GNN-parameter fiber, Hessian inertia) that was a bit impenetrable. It would be helpful to at least have a complete description of the method (just like section 2 has a complete description of preliminaries). The theory section is a bit hard to grok since it is just a march of theorems without much intuition or sense of direction. Given this, it is very hard for me to assess the soundness of the paper.

Questions for authors
  • What is the time complexity of the proposed method compared to others?
  • How should we interpret the differences in the MAP values - what is considered significant? Is there any variance on the results?
  • I assume there are no guarantees on optimality. The theory section suggests that there is some guarantee, but are these conditions realistic / possible to evaluate?
2 comments

W1. Detailed explanation of the method

Sorry for the comfusion, we may simply too much in to fit in the page limit, we will give a detailed introduction in the revised paper. The method and theory are around three questions: What objective is optimized? What does the residual preserve? What can the GNN improve? ReMAP optimizes each MRF instance independently. Let nn be the number of variables, indexed by i∈{1,…,n}i\in\{1,\ldots,n\}, and let sis_i be the number of valid labels for variable ii.

  1. Introduce free logits ui∈Rsiu_i\in\mathbb R^{s_i}, meaning independently adjustable label scores for variable ii. Let uu denote their concatenation.
  2. Construct a message-passing graph GG connecting variables that share a factor. A graph neural network (GNN), with trainable parameters vv, produces scores ρv(G)\rho_v(G) with the same dimensions as uu.
  3. Form the total logits and label probabilities:
p_i=\operatorname{softmax}(z_i/\tau).$$ Here, $z_i$ is the score vector for variable $i$, $\tau>0$ is the softmax temperature, and $p_i(a)$ is the probability assigned to valid label $a$. Invalid labels are masked when a padded representation is used. 4. Jointly optimize $u$ and $v$ to minimize $$F(p)=\mathbb E_{X\sim\prod_{i=1}^{n}p_i}[E(X)],$$ where $p=(p_1,\ldots,p_n)$, $X=(X_1,\ldots,X_n)$ is a random assignment with independent components $X_i\sim p_i$, $E(X)$ is the original MRF energy, and $F(p)$ is its exact expectation under this product distribution. 5. Periodically apply conditional-expectation rounding: fix variables sequentially to labels that do not increase the conditional expected energy, and retain the best discrete assignment obtained. The original higher-order factors define the objective; Graph expansion is used only for GNN message passing, not to approximate those factors. No pretrained model or labeled solutions are required. The theoretical terminology describes concrete properties of this construction. The residual bypass is the additive free-logit term $u$. A parameter fiber is the collection of parameter pairs $(u,v)$ representing the same total logits $z$: for any $z$ and any $v$, choosing\$u=z-\rho_v(G)\$ recovers $z$. Thus, the GNN cannot exclude a solution accessible to free logits. Hessian inertia counts positive, negative, and zero eigenvalues of the Hessian, which describe local curvature. Under the stated differentiability assumptions, the residual parametrization preserves the positive and negative counts at critical points of the logit-space objective and adds redundant zero-curvature directions. The central message is therefore unchanged representational capacity with potentially improved optimization, not that neural parametrization removes the computational difficulty of maximum a posteriori (MAP) inference. > **Q1: Time complexity** We distinguish per-iteration cost from end-to-end performance. Let: - $n$: number of MRF variables; - $G$, $m_G$: message-passing graph and its edge count; - $K$, $d$: GraphSAGE depth and hidden width; - $\mathcal C$: factor scopes, with $|C|$ denoting factor order; - $s_i$: label count of variable $i$; - $q_C=\prod_{i\in C}s_i$: dense table size of factor $C$. For bounded factor order and fixed input/output dimensions, one optimization iteration costs $O\!\left(K(nd^2+m_Gd)+\sum_{C\in\mathcal C}q_C\right)$, covering neural computation and expected-energy evaluation. Backpropagation has the same asymptotic order. The theoretical Jacobian-based metric is not explicitly constructed. For unbounded factor order, straightforward energy evaluation costs $O(\sum_C|C|q_C)$. Total runtime also depends on iteration counts, restarts, preprocessing, and rounding frequency. A conservative conditional-expectation rounding sweep costs $O(\sum_C|C|q_C)$. Dense factor storage requires $O(\sum_Cq_C)$ memory, excluding parameters and activations. Clique expansion for $G$ can generate $O(\sum_C|C|^2)$ candidate edges before deduplication. For pairwise MRFs with $m$ edges and maximum label count $s$, generic LBP/TRBP sweeps cost $O(ms^2)$, with faster updates possible for structured potentials. ReMAP adds neural computation; we do not claim cheaper iterations. Its quality–time trade-off also depends on convergence, iteration counts, and assignment quality. Toulbar2 has instance-dependent, potentially exponential search complexity. ReMAP’s arbitrary-order support likewise does not imply polynomial complexity in factor order: dense table size $q_C$ grows exponentially with $|C|$ for fixed label counts greater than one. We will distinguish these bounds from measured end-to-end runtime, including preprocessing, rounding, and all restarts.

Q2 — Meaning of energy differences and variability

On the same instance, a lower feasible energy is an unambiguous improvement in the MAP objective. Thus, differences cannot be dismissed merely because their practical interpretation depends on scale. Nevertheless, raw energies should not be compared across differently scaled instances, and improvement over another feasible solution is not an optimality certificate. Let x^\hat x be the returned discrete assignment, E⋆E^\star the optimal energy, and BB a valid lower bound on E⋆E^\star. Then 0≤E(x^)−E⋆≤E(x^)−B.0\le E(\hat x)-E^\star\le E(\hat x)-B. Thus, E(x^)−BE(\hat x)-B provides a certified upper bound on suboptimality whenever such a lower bound is available.

Variability is not entirely absent from the paper: Table 7 reports mean ± standard deviation over five ReMAP seeds, and Tables 3–4 report PCI variability. Tables 1 and 6 instead report best-of-five performance. These answer different questions: typical-run reliability versus performance with a multi-start budget. Best-of-five is meaningful for an optimization heuristic, provided its full computational cost is counted.

Q3 — What the guarantees do and do not establish

The absence of a global convergence guarantee does not make the guarantees vacuous. They establish three different properties:

  1. Objective exactness: minimizing the expected energy over the closed product of probability simplices has the same optimal value as discrete MAP. A probability simplex is the set of nonnegative label-probability vectors whose entries sum to one.
  2. Representational safety: the residual parametrization preserves the free-logit search space.
  3. Certified rounding: conditional-expectation rounding gives E(x^)≤F(p),E(\hat x)\le F(p), where pp is the product distribution obtained by optimization, F(p)F(p) is its expected MRF energy, and x^\hat x is the rounded discrete assignment.

These properties do not require the optimizer to find the global optimum. In particular, rounding applies to the distribution actually obtained. Objective exactness concerns optimization over the closed simplices; finite softmax logits generally represent only their interiors, so a boundary optimum may be approached rather than attained at finite logits.

The stronger local-recovery results do require a unique optimum and entry into the stated neighborhood; they are sufficient-condition results, not a claim that those conditions are cheaply verifiable on every instance. The optimization analysis likewise distinguishes gradient flow or suitably step-sized gradient descent from the Adam implementation.

Finally, the residual contributes a positive-semidefinite term to the logit-space gradient-flow metric. This establishes non-decreased instantaneous dissipation at the same logits, with strict improvement when the added term acts nontrivially on the gradient; it does not establish universal wall-clock acceleration. The theory therefore provides a precise mechanism and safeguards, while the experiments assess whether that mechanism is useful in practice. We will make this division explicit rather than overstate the guarantee.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.