|
适当复合损失的指数-凹凸性
Exp-Concavity of Proper Composite Losses |
|
| |
| 课程网址: |
https://videolectures.net/videos/colt2015_kamalaruban_composite_l...
|
| 主讲教师: |
Parameswaran Kamalaruban
|
| 开课单位: |
信息不详。欢迎您在右侧留言补充。
|
| 开课时间: |
2025-02-04
|
| 课程语种: |
英语
|
| 中文简介: |
基于专家建议的在线预测的目标是找到一种决策策略，在给定的专家池中，在任何结果序列上，它的表现几乎与最好的专家一样好。这个问题已经得到了广泛的研究，对于凸损失（Zinkevich(2003)）和具有一阶导数和二阶导数有界的严格凸损失（Hazan et al.(2007)），分别可以实现O（T^0.5）和O（log T）遗憾界。在特殊情况下，如具有混合损失的聚合算法（Vovk(1995)）和具有指数凹损失的加权平均算法（Kivinen和Warmuth(1999)），有可能实现O(1)个后悔界。van Erven（2012）认为，混合性和指数凹凸性在某些条件下大致等效。因此，通过理解这两个概念之间的潜在关系，我们可以获得两种算法的最佳效果（聚合算法的强大理论性能保证和加权平均算法的计算效率）。本文给出了任意适当复合损耗的指数凹凸性的完整表征。利用这一表征和固有损失的可混性条件（Van Erven et al.(2012)），我们证明了将任何β -可混性固有损失转换（重新参数化）为具有相同β -的β -exp-凹复合损失是可能的。
|
| 课程简介: |
The goal of on-line prediction with expert advice is to find a decision strategy which will perform almost as well as the best expert in a given pool of experts, on any sequence of outcomes. This problem has been widely studied and O(T^0.5) and O(log T) regret bounds can be achieved for convex losses (Zinkevich (2003)) and strictly convex losses with bounded first and second derivatives (Hazan et al. (2007)) respectively. In special cases like the Aggregating Algorithm (Vovk (1995)) with mixable losses and the Weighted Average Algorithm (Kivinen and Warmuth (1999)) with exp-concave losses, it is possible to achieve O(1) regret bounds. van Erven (2012) has argued that mixability and exp-concavity are roughly equivalent under certain conditions. Thus by understanding the underlying relationship between these two notions we can gain the best of both algorithms (strong theoretical performance guarantees of the Aggregating Algorithm and the computational efficiency of the Weighted Average Algorithm). In this paper we provide a complete characterization of the exp-concavity of any proper composite loss. Using this characterization and the mixability condition of proper losses (Van Erven et al. (2012)), we show that it is possible to transform (re-parameterize) any beta-mixable proper loss into a beta-exp-concave composite loss with the same beta.
|
| 关 键 词: |
复合损失; 后悔界; 聚合算法
|
| 课程来源: |
视频讲座网
|
| 数据采集: |
2025-03-31：zsp
|
| 最后编审: |
2025-03-31：zsp
|
| 阅读次数: |
3
|
|
图 书 馆