图 书 馆
超越后悔最小化障碍：随机强凸优化的一个优化算法Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization |
|
| 课程网址: | http://videolectures.net/colt2011_kale_optimization/ |
| 主讲教师: | Satyen Kale |
| 开课单位: | 雅虎公司 |
| 开课时间: | 2011-08-02 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We give a novel algorithm for stochastic strongly-convex optimization in the gradient oracle model which returns an O(1/T)-approximate solution after T gradient updates. This rate of convergence is optimal in the gradient oracle model. This improves upon the previously known best rate of O(log(T)/T), which was obtained by applying an online strongly-convex optimization algorithm with regret O(log(T)) to the batch setting. We complement this result by proving that any algorithm has expected regret of Ω(log(T)) in the online stochastic strongly-convex optimization setting. This lower bound holds even in the full-information setting which reveals more information to the algorithm than just gradients. This shows that any online-to-batch conversion is inherently suboptimal for stochastic strongly-convex optimization. This is the first formal evidence that online convex optimization is strictly more difficult than batch stochastic convex optimization. |
| 关 键 词: | 计算机科学; 优化方法; 随机优化 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-01-13：chenxin |
| 阅读次数: | 34 |