Prediction with Expert Advice: A PDE Perspective
Prediction with Expert Advice: A PDE Perspective
复制标题
根据专家建议进行预测：偏微分方程 (PDE) 视角
DOI：
10.1007/s00332-019-09570-3
复制
发表时间：
2019
影响因子：
3
通讯作者：
R. Kohn
中科院分区：
文献类型：
--
作者：
Nadejda Drenska;R. Kohn
这项工作通过专家建议解决了在线预测的经典问题。我们假设一个敌对对手，并考虑这种零和两人游戏的有限视野和随机停止版本。着眼于适当的连续极限并使用最优控制方法，我们将博弈的值表征为某个非线性偏微分方程的粘度解。该分析还揭示了预测者和对手的极小极大最优策略。我们的工作特别为 Gravin 等人最近的工作提供了一个连续的视角。 （摘自：第 27 届 ACM-SIAM 离散算法年度研讨会论文集，SODA '16，（美国宾夕法尼亚州费城），工业与应用数学学会，2016 年）。我们的技术类似于 Kohn 和 Serfaty 的技术（Commun Pure Appl Math 63(10):1298–1350, 2010），其中一些两人游戏的缩放限制导致椭圆形或抛物线偏微分方程。
This work addresses a classic problem of online prediction with expert advice. We assume an adversarial opponent, and we consider both the finite horizon and random stopping versions of this zero-sum, two-person game. Focusing on an appropriate continuum limit and using methods from optimal control, we characterize the value of the game as the viscosity solution of a certain nonlinear partial differential equation. The analysis also reveals the predictor’s and the opponent’s minimax optimal strategies. Our work provides, in particular, a continuum perspective on recent work of Gravin et al. (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, SODA ’16, (Philadelphia, PA, USA), Society for Industrial and Applied Mathematics, 2016). Our techniques are similar to those of Kohn and Serfaty (Commun Pure Appl Math 63(10):1298–1350, 2010), where scaling limits of some two-person games led to elliptic or parabolic PDEs.