PaperlayerView exact revision on arXiv

Source-linked AI summary

Cost-augmented Schr\"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control

Akshay Balsubramani

arXiv:2610.02195v1cs.LG

TL;DR

Graph bridges with state costs have been approached through learned controlled rates and a temporal-difference penalty. This paper folds the cost into a tilted reference and solves the bridge exactly; its evaluations report lower folding barriers and road-network roll-outs matching the target within sampling error.

  • Problem

    Learned graph-bridge methods use a temporal-difference penalty to restore state costs that cancel from endpoint fitting.

    Source: §2 · p. 3

  • Method

    The method absorbs state costs into a Feynman–Kac tilt and computes the resulting plain bridge by alternating endpoint rescalings with sparse matrix exponentials.

    Source: §1 · p. 1

  • Results

    On chignolin, the expected barrier falls from 6.20 at λ = 0 to 5.64 at λ = 30, and road-network roll-outs match the target within sampling error.

    Source: §1 · p. 2, §5.2 · p. 8

  • Takeaways & Limitations

    For quadratic congestion costs on time-averaged occupancies, damped best response around the exact bridge has a residual that bounds its distance to equilibrium at every step.

    Source: §1 · p. 2

    The exact solver requires an explicit reference generator and enumeration of the state space.

    Source: §6 · p. 10

Abstract

from arXiv · show

The generalized Schr\"odinger bridge on a graph moves mass between two distributions while charging a cost for the states visited. It has been approached by learning the rates of a controlled continuous-time Markov chain, with a temporal-difference penalty that restores the cost. A state cost folds into the reference process as a Feynman-Kac tilt. The cost-augmented bridge is then a plain bridge against the tilted reference, and the penalty is unnecessary. The bridge is computed exactly by alternating two endpoint rescalings, each one sparse matrix-exponential application; nothing is discretized in time or learned. The alternation converges at a rate set by the endpoint coupling alone. For a quadratic congestion cost on time-averaged occupancies, damped best response around the exact bridge is gradient descent on a strongly convex function, and its residual bounds its error. On a protein-folding model, a free-energy cost lowers the expected barrier of the folding paths. On the learned approach's road network, roll-outs of the exact bridge match the target within sampling error, and on networks with millions of intersections its memory grows linearly.

1 Introduction

The paper replaces learned control for cost-augmented graph bridges with an exact sparse-linear-algebra solution for state costs, while handling congestion through a separate equilibrium iteration. Evaluations cover assignment, protein folding, and road-network settings.

1 Introduction

  • Earlier graph methods learned controlled-chain rates and added a tuned temporal-difference penalty to restore the running cost that endpoint fitting cancels.The penalty trades cost against terminal matching, and the learned formulation was motivated partly by the perceived prohibitive cost of direct solution on large graphs.Source: §1 · p. 1
  • A state-dependent running cost can be absorbed into an exponential tilt of the reference, turning the generalized bridge into a plain bridge against that tilted process.The resulting finite-graph solver uses sparse matrix exponentials without time discretization or learning.Source: §1 · p. 1
  • For quadratic congestion costs on time-averaged occupancies, damped best response uses the exact bridge as an inner oracle and is gradient descent on a strongly convex function.Its residual bounds distance to equilibrium at every iterate; convergence from any start holds below a curvature-based step threshold.Source: §1 · p. 2
  • On the tested assignment instances, the exact solution recovered every cost-optimal assignment within the main table’s concentration band, while the learned solver misplaced a pair at the largest tested size.The exact bridge also matches road-network roll-outs to the target within sampling error; on chignolin, free-energy cost lowers the expected folding-path barrier.Source: §1 · p. 2
  • The paper evaluates the exact solver on assignment, chignolin-folding, and Washington DC road-network models, where it meets endpoint marginals and scales in memory linearly with node count.The road-network tests extend to 2.07 million intersections.Source: §1 · p. 2

2 The tilt identity

A state-only running cost changes the reference path measure by an exponential tilt, so the cost-augmented bridge is a plain bridge against that tilted reference. The tilt preserves graph support, and fitting the tilted bridge keeps the cost visible without a temporal-difference penalty.

2 The tilt identity

  • Theorem 2.1 defines a tilted path measure by weighting the reference paths exponentially by their accumulated state cost; the generalized bridge is the plain bridge between the endpoints against this measure.The tilted reference is the normalized path measure of the semigroup generated by A.Source: §2 · p. 2
  • The diagonal shift A = Q − diag(f) preserves off-diagonal rates and graph support; for f ≥ 0, its semigroup describes a process killed at rate f.The normalization defect is absorbed by the endpoint rescalings, and reachability between endpoint supports ensures positive, unique scalings up to reciprocal factors.Source: §2 · p. 2
  • The optimal controlled rate is an executable policy that consults only out-neighbors, preserving the graph topology and matching the form targeted by the learned approach.It can substitute for that approach without reformulating the problem.Source: §2 · p. 3
  • The tilt and potential-ratio control are classical, with related formulations for diffusion, discrete-time networks [8] [15], and jump processes [37].The paper combines these ingredients for an exact sparse-linear-algebra solve on finite graphs.Source: §2 · p. 3
  • Against the untilted reference, the cost terms cancel from the evolution of the joint density and from endpoint-fitting, so the fitting objective alone does not enforce cost consistency.Against the tilted reference, the cost remains visible to iterative proportional fitting, eliminating the need for a temporal-difference penalty.Source: §2 · p. 3

3 An exact continuous-time solver

The bridge is solved by alternating endpoint rescalings propagated through sparse matrix-exponential applications, without discretizing time. Its iteration rate is set by the endpoint coupling, and reported road-network counts track the resulting prediction.

3 An exact continuous-time solver

  • Each fitting half-step applies a matrix exponential to a vector using sparse products, and the full time axis is handled without a time grid.The potentials at any time can be recovered with one further application.Source: §3 · p. 3
  • Near the fixed point, fitting error contracts by the second singular value of the endpoint coupling, which determines the iteration count up to a starting-point offset.Source: §3 · p. 4
  • Road-network iteration counts were 0.81 to 1.76 times the predicted law, with rank correlation 1.00; every solve met both marginals below 3 × 10−13 total variation.Source: Figure 1 · p. 4, §3 · p. 4
  • Peak allocation grows proportionally with node count, from 346 to 412 bytes per node across the road networks.The figure also reports per-iteration time scaling with arc count times τ maxx |Axx|.Source: Figure 1 · p. 4
  • Propagation is chunked and vectors are renormalized between chunks, preserving exactness despite large potential-scale changes.The fitting iteration and marginal are invariant to a global rescaling of the potential.Source: §3 · p. 4

4 Marginal-dependent costs

Marginal-dependent congestion costs fall outside the state-cost tilt identity, so the paper solves for equilibrium occupancy by iterating exact state-cost bridges. Damped best response is gradient descent on a strongly convex objective, with an error certificate from its residual.

4 Marginal-dependent costs

  • A congestion cost depends on the marginal, so the state-cost tilt identity does not apply; quadratic cost on time-averaged occupancy instead gives a strictly convex path-law objective with a unique minimizer.Source: §4 · pp. 4–5
  • Each damped best-response update mixes the current occupancy with the exact bridge response to the state cost βp.Source: §4 · p. 5
  • Damped best response is gradient descent on an objective with Hessian bounded between I and (1 + βτ/2)I, whose minimizer is the equilibrium occupancy.Source: §4 · p. 5
  • The fixed-point residual bounds equilibrium error for every occupancy; tested dampings exceed the narrow global convergence range by factors of 22 to 449, with guarantees applying only locally.Source: §4 · p. 5
  • Started from plain-bridge occupancy, damped best response is also a generalized conditional-gradient method and coincides with gradient ascent on the dual.Source: §4 · p. 5

5 Experiments

Across assignment, folding, and routing experiments, the exact bridge meets its endpoint marginals and reproduces the target in road-network roll-outs within sampling error. The experiments also show how entropy, running costs, congestion, and endpoint coupling shape outcomes and computation.

5.1 Assignment

  • At the main-table entropy band 0.07–0.17, the exact bridge recovers cost-optimal assignments on every tested instance; at 0.22, 19 of 20 K = 20 instances do.At K = 20, the learned solver reports 90% agreement and cost 546 against an optimum of 538; the exact sweep isolates error from entropic regularization alone.Source: §5.1 · p. 6, Figure 2 · p. 7

5.2 Rare-event steering

  • Expected barrier falls from 6.20 at λ = 0 to 5.64 at λ = 30, and its distribution is stochastically smaller than under the plain bridge at every strength.At every λ, endpoint total variation is below 10^-16; all 4,000 roll-outs fold, compared with learned-bridge rates of 99.70% without cost and 99.36% with cost.Source: Figure 3 · p. 8, §5.2 · p. 8

5.3 Supply-chain routing with congestion

  • At βτ = 2500, congestion lowers mean occupancy of the 100 most occupied nodes from 13.4 to 10.4 particles per 5,000, but endpoint-excluded costs barely shift peak flow.Peak flow into the largest demand node is 1.09 times capacity per 5,000 particles, versus 1.38 for the 6,360-unit instance; congestion changes it only to 1.08 and 1.05.Source: §5.3 · p. 9
  • Damped best response converges in 42 rounds at damping 0.35 for both tested congestion strengths; the undamped response settles into a two-cycle at βτ = 2500.The critical damping is 1.73 at βτ = 250 and 0.80 at βτ = 2500.Source: §5.3 · p. 9

5.4 Scale

  • Across road networks from 9,559 to 2,073,870 intersections, peak memory is 346–412 bytes per node, or 743 MB on Texas.Iteration time stays within a factor of 2.4 of proportional to arc count times horizon-scaled maximum diagonal magnitude; changing horizon from 25 to 400 changes time proportionally within 3%.Source: §5.4 · p. 9
  • Across 11 problems, iteration counts are 0.81–1.07 times the endpoint-coupling prediction; Texas takes 1,973 iterations, while a nearly split New Hampshire coupling takes 7,313.On Texas, the endpoint-block iteration takes 28 minutes on four cores; Delaware’s 49,109-node problem uses 18 MB and takes 26 seconds on different hardware.Source: §5.4 · p. 9
  • A stopping rule based on the largest scaling can leave terminal total variation at 0.094 when smaller scalings are still changing; the logarithmic rule converges in 837 iterations.Across horizons 25 to 400, counts under the logarithmic rule are 1.09–1.76 times the asymptotic count.Source: §5.4 · pp. 9–10

5.3 Supply-chain routing with congestion

  • On Washington DC roads, controlled-rate roll-outs end at total variation 0.016 from target, within the target-draw range; the learned solver gives 0.03 and attraction-flow baseline 0.27.The exact endpoint marginals meet total variation below 10^-12.Source: §5.3 · p. 9, Figure 4 · p. 10

6 Discussion

A change of reference measure turns the state-cost bridge into a problem solved by sparse linear algebra, while congestion requires an outer iteration whose residual bounds equilibrium error.

6 Discussion

  • Changing the reference measure converts the learned-control formulation into a sparse-linear-algebra solve.The congestion-cost identity adds an outer iteration, whose residual bounds its distance to equilibrium at every step.Source: §6 · p. 10
  • The exact solver requires the reference generator explicitly, as does the learned approach.The paper says this requirement does not bind in its three scenarios because the reference is known or estimated from trajectories.Source: §6 · p. 10
  • Enumerating the state space is another requirement; a 24 × 24 Ising lattice has 2576 states in the cited product-space example.The optimal rate retains the potential-ratio form, which discrete Schrödinger-bridge samplers learn with a neural network [16].Source: §6 · p. 10

A.1 Proofs for Section 2

The proofs show that the generalized-bridge objective is equivalent to a plain bridge against a normalized Feynman–Kac tilt, and derive the resulting controlled rates.

A.1 Proofs for Section 2

  • The generalized-bridge objective and KL(q∥eR) differ only by the q-independent constant log Z, so their minimizers coincide.The proof identifies this equality by expanding the KL objective.Source: §A.1 · p. 15
  • The Feynman–Kac representation makes eR the normalized path measure of e^tA, with the running cost subtracting from the diagonal and leaving off-diagonal rates unchanged.The unnormalized tilted measure is normalized by its total mass.Source: §A.1 · p. 15
  • The h-transform gives the controlled off-diagonal rate as A_xy φ_t(y)/φ_t(x), which equals Q_xy φ_t(y)/φ_t(x) for x ≠ y.The tilt changes only the diagonal, so the optimal control retains the reference process’s off-diagonal support.Source: §A.1 · p. 15

A.2 Proofs for Section 4

The proof connects endpoint-scaled bridge occupation times to a strongly convex objective, yielding a gradient-descent interpretation and convergence bounds for damped best response.

A.2 Proofs for Section 4

  • The cost-weighted path law uses endpoint scalings and occupation times, and its dual objective has gradient equal to expected occupation time.The endpoint scalings enforce the two marginal constraints; the gradient is τ times the time-averaged marginal.Source: §A.2 · p. 15
  • The Hessian argument bounds ∇²h(p) between I and (1 + βτ/2)I, establishing strong convexity and a unique equilibrium fixed point.The bound follows from controlling the variance of the cost-weighted occupation time.Source: §A.2 · p. 15
  • The damped best-response step is p − α∇h(p), and its global contraction is bounded using the spectrum of the step’s difference matrix.Near equilibrium, continuity of the Hessian gives a local contraction rate determined by the eigenvalue bounds involving m and L.Source: §A.2 · p. 15
  • Strong convexity bounds the distance to equilibrium by the gradient norm, so the stopping residual controls the iterate’s error.The proof gives ∥p − p◦∥₂ ≤ ∥∇h(p)∥₂.Source: §A.2 · p. 15
Loading 2610.02195v1…