从上下文分布中学习，提升随机优化的样本效率
Contextual Learning for Stochastic Optimization
- 基于上下文值分布构建凸损失函数进行学习
- 在强单调稳定问题中实现多项式样本复杂度
- 适用于单物品收益最大化等经典优化场景
受随机优化启发，我们提出从上下文值分布的样本中学习的问题。上下文值分布可理解为一组实值分布，每个样本包含一个上下文 $x$ 及来自对应分布 $D_x$ 的随机变量。通过最小化凸代理损失，我们为每个上下文学习到一个经验分布 $D'_x$，使其与 $D_x$ 的 Lévy 距离较小。该结果用于推导未知上下文值分布上 $ε$-最优策略的学习样本复杂度。对于强单调且稳定的优化问题（包括单物品收益最大化、潘多拉盒子和最优停止），样本复杂度被证明为多项式。
原文摘要 · Abstract (English)
Motivated by stochastic optimization, we introduce the problem of learning from samples of contextual value distributions. A contextual value distribution can be understood as a family of real-valued distributions, where each sample consists of a context $x$ and a random variable drawn from the corresponding real-valued distribution $D_x$. By minimizing a convex surrogate loss, we learn an empirical distribution $D'_x$ for each context, ensuring a small Lévy distance to $D_x$. We apply this result to obtain the sample complexity bounds for the learning of an $ε$-optimal policy for stochastic optimization problems defined on an unknown contextual value distribution. The sample complexity is shown to be polynomial for the general case of strongly monotone and stable optimization problems, including Single-item Revenue Maximization, Pandora's Box and Optimal Stopping.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。