Fitted value iteration methods for bicausal optimal transport
Erhan Bayraktar, Bingyan Han
我们开发了一个拟合值迭代(FVI)方法来计算耦合物具有适应结构的双子座最优传输(OT)。 基于动态编程的制定,FVI采用函数类来近似bicausal OT中的价值函数。 在集中条件和近似完整性假设下,我们使用(本地)Rademacher复杂性证明了样品的复杂性。 此外,我们证明具有适当结构的多层神经网络满足了样本复杂性证明中所需的关键假设。 数字实验表明,随着时间范围的增加,FVI在可扩展性方面优于线性编程,并调整了Sinkhorn方法,同时仍然保持可接受的准确性。
We develop a fitted value iteration (FVI) method to compute bicausal optimal transport (OT) where couplings have an adapted structure. Based on the dynamic programming formulation, FVI adopts a function class to approximate the value functions in bicausal OT. Under the concentrability condition and approximate completeness assumption, we prove the sample complexity using (local) Rademacher complexity. Furthermore, we demonstrate that multilayer neural networks with appropriate structures satisfy...