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美元利率到任意的快速率,这取决于问题难度的参数,从而在光滑度假设下可以绕过维度的诅咒。