Surrogate Regret Bounds for Polyhedral Losses
Surrogate Regret Bounds for Polyhedral Losses
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Rafael M. Frongillo;Bo Waggoner
中科院分区：
文献类型：
--
作者：
Rafael M. Frongillo;Bo Waggoner
替代风险最小化是监督机器学习中普遍存在的范式，其中通过最小化数据集上的替代损失来解决目标问题。代理后悔界限，也称为超额风险界限，是证明代理风险最小化的推广率的常用工具。虽然替代遗憾界已开发的某些类别的损失函数，如适当的损失，一般的结果是相对稀疏。我们提供了两个一般结果。第一个给出了一个线性代理遗憾界的任何多面体（分段线性和凸）代理，这意味着代理泛化率直接转化为目标率。第二个表明，充分非多面体代理，遗憾界是一个平方根，这意味着快速代理泛化率转化为目标的速度慢。总之，这些结果表明多面体代理在许多情况下是最佳的。
Surrogate risk minimization is an ubiquitous paradigm in supervised machine learning, wherein a target problem is solved by minimizing a surrogate loss on a dataset. Surrogate regret bounds, also called excess risk bounds, are a common tool to prove generalization rates for surrogate risk minimization. While surrogate regret bounds have been developed for certain classes of loss functions, such as proper losses, general results are relatively sparse. We provide two general results. The first gives a linear surrogate regret bound for any polyhedral (piecewise-linear and convex) surrogate, meaning that surrogate generalization rates translate directly to target rates. The second shows that for sufficiently non-polyhedral surrogates, the regret bound is a square root, meaning fast surrogate generalization rates translate to slow rates for the target. Together, these results suggest polyhedral surrogates are optimal in many cases.