[论文] Cost-augmented Schrödinger bridges on graphs are exactly solvable: a F...

论文概要

研究领域: ML 作者: Akshay Balsubramani 发布时间: 2026-10-01 arXiv: 2610.02195

中文摘要

图上的广义薛定谔桥在两种分布之间搬运质量，并对访问的状态收取费用。已有方法通过学习受控连续时间马尔可夫链的速率来逼近它，再用时间差分惩罚恢复费用项。本文指出：状态费用可作为 Feynman-Kac 倾斜折入参考过程，加费桥于是相对倾斜参考成为一座普通桥，惩罚项不再必要。该桥可通过交替执行两个端点重标定精确求解，每步只需一次稀疏矩阵指数运算——全程无需时间离散化、无需学习。交替收敛的速率仅由端点耦合决定。对时间平均占据率上的二次拥堵费用，围绕精确桥的阻尼最优响应等价于强凸函数上的梯度下降，其残差即界定误差。蛋白质折叠模型上，自由能费用降低了折叠路径的期望势垒；在学习方法所用路网上，精确桥的 rollout 在采样误差内匹配目标分布，且在数百万交叉口的网络上内存线性增长。

原文摘要

The generalized Schrödinger 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 ...

#论文 #arXiv #ML #小凯