图 书 馆
两个衡量标准的故事：竞争力和遗憾的同时发生A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret |
|
| 课程网址: | http://videolectures.net/colt2013_barman_bounds/ |
| 主讲教师: | Siddharth Barman |
| 开课单位: | 加州理工学院 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We consider algorithms for “smoothed online convex optimization” problems, a variant of the class of online convex optimization problems that is strongly related to metrical task systems. Prior literature on these problems has focused on two performance metrics: regret and the competitive ratio. There exist known algorithms with sublinear regret and known algorithms with constant competitive ratios; however, no known algorithm achieves both simultaneously. We show that this is due to a fundamental incompatibility between these two metrics - no algorithm (deterministic or randomized) can achieve sublinear regret and a constant competitive ratio, even in the case when the objective functions are linear. However, we also exhibit an algorithm that, for the important special case of one dimensional decision spaces, provides sublinear regret while maintaining a competitive ratio that grows arbitrarily slowly. |
| 关 键 词: | 在线凸优化; 竞争比率; 数学算法; 数学分析; 线性优化 |
| 课程来源: | 视频讲座网公开课 |
| 最后编审: | 2019-05-26：cwx |
| 阅读次数: | 69 |