Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Ashok Cutkosky;Francesco Orabona
中科院分区：
文献类型：
--
作者：
Ashok Cutkosky;Francesco Orabona
我们介绍了几个新的黑盒约简，通过简化分析，提高遗憾保证，有时甚至提高运行时间，显着改善自适应和无参数在线学习算法的设计。我们将无参数在线学习减少到在线指数凹优化，将Banach空间中的优化减少到一维优化，将约束域上的优化减少到无约束优化。我们所有的缩减都和在线梯度下降一样快。我们使用我们的新技术，以改善以前的最佳遗憾界的参数自由学习，这样做的任意规范。
We introduce several new black-box reductions that significantly improve the design of adaptive and parameter-free online learning algorithms by simplifying analysis, improving regret guarantees, and sometimes even improving runtime. We reduce parameter-free online learning to online exp-concave optimization, we reduce optimization in a Banach space to one-dimensional optimization, and we reduce optimization over a constrained domain to unconstrained optimization. All of our reductions run as fast as online gradient descent. We use our new techniques to improve upon the previously best regret bounds for parameter-free learning, and do so for arbitrary norms.