Deterministic and Stochastic Frank-Wolfe Recursion on Probability Spaces

Yu Di

doi:10.1287/moor.2024.0584

2025-09-01

PRE

Yu Di

Shane G. Henderson

Raghu Pasupathy *

DOI：10.1287/moor.2024.0584

原文链接

原文求助

摘要

En 中文

受应急管理与实验设计应用启发，我们考虑在欧几里得空间紧子集上支撑的概率测度上的光滑随机优化问题。以影响函数作为变分对象，我们为概率空间构建了一个确定性的Frank-Wolfe (dFW)递归。该dFW递归的实现得益于一个引理，该引理将无限维Frank-Wolfe子问题的解识别为在当前迭代点影响函数最小值处集中的狄拉克测度。因此，dFW递归中的每个迭代通过粒子更新表示，作为当前迭代与狄拉克测度的凸组合。为处理仅能获取目标函数与影响函数蒙特卡罗观测值的常见应用场景，我们构建了一个随机Frank-Wolfe (sFW)变体，其生成一个随机概率测度序列，这些测度基于对影响函数精度逐渐提高的估计最小值构造。我们证明，对于光滑凸目标函数，sFW的最优性间隙序列几乎必然且在期望下具有O(k-1)迭代复杂度；对于光滑非凸目标函数，在Frank-Wolfe间隙下为O(k-1/2)。此外，我们展示了一种易于实现的固定步长、固定样本的sFW方法版本可指数收敛至ε-最优性。最后，我们对生成随机测度序列上观察到的目标函数值给出了中心极限定理。为增强直观理解，我们包含若干包含精确影响函数计算的说明性示例。

Keyword:

optimization over probability spaces

Frank-Wolfe

conditional gradient