Multiclass logistic regression is a fundamental task in machine learning with applications in classification and boosting. Previous work (Foster et al., 2018) has highlighted the importance of improper predictors for achieving "fast rates" in the online multiclass logistic regression problem without suffering exponentially from secondary problem parameters, such as the norm of the predictors in the comparison class. While Foster et al. (2018) introduced a statistically optimal algorithm, it is in practice computationally intractable due to its run-time complexity being a large polynomial in the time horizon and dimension of input feature vectors. In this paper, we develop a new algorithm, FOLKLORE, for the problem which runs significantly faster than the algorithm of Foster et al.(2018) -- the running time per iteration scales quadratically in the dimension -- at the cost of a linear dependence on the norm of the predictors in the regret bound. This yields the first practical algorithm for online multiclass logistic regression, resolving an open problem of Foster et al.(2018). Furthermore, we show that our algorithm can be applied to online bandit multiclass prediction and online multiclass boosting, yielding more practical algorithms for both problems compared to the ones in Foster et al.(2018) with similar performance guarantees. Finally, we also provide an online-to-batch conversion result for our algorithm.


翻译:多级物流回归是机器学习的基本任务,包括应用分类和提升。 先前的工作( Foster 等人, 2018年)已经强调了在不因次要问题参数(如比较类中的预测者标准)而导致指数化变化的情况下,在网上多级物流回归问题中实现“ 快速率”的不适当预测器的重要性。 Foster 等人( 2018年) 引入了一个统计上最优化的算法, 在实践中, 由于其运行时的复杂性, 在时间范围与输入特性矢量的尺寸, 是一个巨大的多级多功能化问题, 而在本文中, 我们开发了一种新的算法, FOLKLORE, 其运行速度大大快于Foster等人的算法( 2018年) -- -- 其运行时间在规模上不因二次问题而成倍增速。 尽管Fosteration 等值的运行时间, 却以直线线性依赖在遗憾圈中的预测者标准为代价。 这产生了第一个实际的在线多级物流回归算法, 解决Foster et al. (20) 。 此外, 我们的算算法可以应用于在线多级多级多级预测和多级的在线推进系统转换, 。 最后, 将产生结果, 与我们的软化结果。

0
下载
关闭预览

相关内容

深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
专知会员服务
159+阅读 · 2020年1月16日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【泡泡一分钟】无监督学习的立体匹配方法(ICCV-2017)
泡泡机器人SLAM
8+阅读 · 2018年10月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
逻辑回归(Logistic Regression) 模型简介
全球人工智能
5+阅读 · 2017年11月1日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年11月29日
Arxiv
0+阅读 · 2021年11月25日
Arxiv
7+阅读 · 2020年5月25日
VIP会员
相关资讯
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【泡泡一分钟】无监督学习的立体匹配方法(ICCV-2017)
泡泡机器人SLAM
8+阅读 · 2018年10月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
逻辑回归(Logistic Regression) 模型简介
全球人工智能
5+阅读 · 2017年11月1日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员