Discrete supervised learning problems such as classification are often tackled by introducing a continuous surrogate problem akin to regression. Bounding the original error, between estimate and solution, by the surrogate error endows discrete problems with convergence rates already shown for continuous instances. Yet, current approaches do not leverage the fact that discrete problems are essentially predicting a discrete output when continuous problems are predicting a continuous value. In this paper, we tackle this issue for general structured prediction problems, opening the way to "super fast" rates, that is, convergence rates for the excess risk faster than $n^{-1}$, where $n$ is the number of observations, with even exponential rates with the strongest assumptions. We first illustrate it for predictors based on nearest neighbors, generalizing rates known for binary classification to any discrete problem within the framework of structured prediction. We then consider kernel ridge regression where we improve known rates in $n^{-1/4}$ to arbitrarily fast rates, depending on a parameter characterizing the hardness of the problem, thus allowing, under smoothness assumptions, to bypass the curse of dimensionality.


翻译:分解监督的学习问题,例如分类,往往通过引入类似于回归的连续代用问题来解决。在替代错误和解决方案之间,根据替代错误的预估和解决方案之间的原始误差,在连续出现的情况下会发现趋同率的分解问题。然而,目前的办法并没有利用下述事实:在连续的问题预测连续的价值时,离散问题基本上预测离散产出。在本文中,我们处理的是一般结构化预测问题,打开“超快”率的通道,即超高风险率的汇合率,即超过1美元(美元至1美元)的超强风险的汇合率,在美元是观测次数,甚至以最强的假设为指数。我们首先用最近的邻居的预测器加以说明,将已知的二元分类率与结构化预测框架内的任何离散问题一般化。我们然后考虑内核脊回归率,即我们提高已知的美元-1/4美元利率到任意的快速率,这取决于问题难度的参数,从而在光滑度假设下可以绕过维度的诅咒。

0
下载
关闭预览

相关内容

让 iOS 8 和 OS X Yosemite 无缝切换的一个新特性。 > Apple products have always been designed to work together beautifully. But now they may really surprise you. With iOS 8 and OS X Yosemite, you’ll be able to do more wonderful things than ever before.

Source: Apple - iOS 8
专知会员服务
50+阅读 · 2020年12月14日
【论文】结构GANs,Structured GANs,
专知会员服务
14+阅读 · 2020年1月16日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
一文读懂Faster RCNN
极市平台
5+阅读 · 2020年1月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Faster R-CNN
数据挖掘入门与实战
4+阅读 · 2018年4月20日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月30日
Arxiv
3+阅读 · 2018年2月20日
VIP会员
相关资讯
一文读懂Faster RCNN
极市平台
5+阅读 · 2020年1月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Faster R-CNN
数据挖掘入门与实战
4+阅读 · 2018年4月20日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员