图 书 馆
标记在线本地学习的最佳后悔界限Label optimal regret bounds for online local learning |
|
| 课程网址: | https://videolectures.net/videos/colt2015_risteski_local_learning |
| 主讲教师: | Andrej Risteski |
| 开课单位: | 信息不详。欢迎您在右侧留言补充。 |
| 开课时间: | 2025-02-04 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We resolve an open question from Christiano (2014b) posed in COLT’14 regarding the optimal dependency of the regret achievable for online local learning on the size of the label set. In this framework the algorithm is shown a pair of items at each step, chosen from a set of n items. The learner then predicts a label for each item, from a label set of size L and receives a real valued payoff. This is a natural framework which captures many interesting scenarios such as collaborative filtering, online gambling, and online max cut among others. Christiano (2014a) designed an efficient online learning algorithm for this problem achieving a regret of O(\sqrt{nL^3T}), where T is the number of rounds. Information theoretically, one can achieve a regret of O(\sqrt{n log LT}). One of the main open questions left in this framework concerns closing the above gap. In this work, we provide a complete answer to the question above via two main results. We show, via a tighter analysis, that the semi-definite programming based algorithm of Christiano (2014a), in fact achieves a regret of O(\sqrt{n L T}). Second, we show a matching computational lower bound. Namely, we show that a polynomial time algorithm for online local learning with lower regret would imply a polynomial time algorithm for the planted clique problem in regimes widely believed to be hard. We prove a similar hardness result under a related conjecture concerning planted dense subgraphs that we put forth. Unlike planted clique, the dense subgraph version does not have quasi-polynomial time algorithms. Computational lower bounds for online learning are relatively rare, and we hope that the ideas developed in this work will lead to lower bounds for other online learning scenarios as well. |
| 关 键 词: | 局部学习; 标签集大小; 协同过滤 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2025-03-30：zsp |
| 最后编审: | 2025-03-30：zsp |
| 阅读次数: | 3 |