图 书 馆
论强盗与无导数随机凸优化的复杂性On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization |
|
| 课程网址: | http://videolectures.net/colt2013_shamir_optimization/ |
| 主讲教师: | Ohad Shamir |
| 开课单位: | 魏茨曼科学研究所 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | The problem of stochastic convex optimization with bandit feedback (in the learning community) or without knowledge of gradients (in the optimization community) has received much attention in recent years, in the form of algorithms and performance upper bounds. However, much less is known about the inherent complexity of these problems, and there are few lower bounds in the literature, especially for nonlinear functions. In this paper, we investigate the attainable error/regret in the bandit and derivative-free settings, as a function of the dimension d and the available number of queries T. We provide a precise characterization of the attainable performance for strongly-convex and smooth functions, which also imply a non-trivial lower bound for more general problems. Moreover, we prove that in both the bandit and derivative-free setting, the required number of queries must scale at least quadratically with the dimension. Finally, we show that on the natural class of quadratic functions, it is possible to obtain a “fast” O(1/T) error rate in terms of T, under mild assumptions, even without having access to gradients. To the best of our knowledge, this is the first such rate in a derivative-free stochastic setting, and holds despite previous results which seem to imply the contrary. |
| 关 键 词: | 非线性函数; 凸和平滑函数; 衍生自由随机设置 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-03-10：mmx |
| 阅读次数: | 110 |