Online Learning to Transport via the Minimal Selection Principle
Online Learning to Transport via the Minimal Selection Principle
复制标题
DOI：
--
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Wenxuan Guo;Y. Hur;Tengyuan Liang;Christopher Ryan
中科院分区：
文献类型：
--
作者：
Wenxuan Guo;Y. Hur;Tengyuan Liang;Christopher Ryan
受运筹学中稳健的动态资源分配的启发，我们研究了决策变量为概率度量的在线学习运输问题，它是fi中的一个无维对象。我们通过一种被称为最小选择原理的观点将在线学习、最优传输和偏微分方程组联系起来，该原理最初由Ambrosio等人在ffGendentflow设置中研究过。[2005][2005]。这使我们能够无缝地将标准在线学习框架扩展到InfiNite-维度设置。基于我们的框架，我们提出了一种新的方法，称为最小选择或探索算法，利用Mean-fi场近似和离散化技术来解决OLT问题。在位移凸集下，支持我们方法的主要理论信息是随着时间的推移最小化运输成本(通过最小选择原则)确保最优累积后悔上界。在算法方面，我们的MSoE算法超越了位移凸设置，使得最优运输的数学理论实际上与动态资源分配中常见的非凸设置相关。
Motivated by robust dynamic resource allocation in operations research, we study the Online Learning to Transport (OLT) problem where the decision variable is a probability measure, an infinite-dimensional object. We draw connections between online learning, optimal transport, and partial differential equations through an insight called the minimal selection principle, orig-inally studied in the Wasserstein gradient flow setting by Ambrosio et al. [2005]. This allows us to extend the standard online learning framework to the infinite-dimensional setting seamlessly. Based on our framework, we derive a novel method called the minimal selection or exploration (MSoE) algorithm to solve OLT problems using mean-field approximation and discretization techniques. In the displacement convex setting, the main theoretical message underpinning our approach is that minimizing transport cost over time (via the minimal selection principle) en-sures optimal cumulative regret upper bounds. On the algorithmic side, our MSoE algorithm applies beyond the displacement convex setting, making the mathematical theory of optimal transport practically relevant to non-convex settings common in dynamic resource allocation.