Proper losses regret at least 1/2-order

机器学习中的一个基本挑战是选择损失函数，因为它描述了我们的学习任务，在训练阶段被最小化，并作为评估估计量的标准。通常会选择适当的损失函数，以确保全风险的最小化与真实概率向量匹配。从适当损失函数中引出的估计量被广泛用于构建用于分类和排序等下游任务的预测器。在这个过程中，基于获得的估计量的预测器在给定的下游任务下表现良好，这个问题与估计量和真实概率向量之间的$p$-范数的行为密切相关。在适当的损失框架中，估计概率向量与真实概率向量之间的次优性由一个代理遗憾度量。首先，我们分析了代理遗憾度量，并表明损失函数的严格适当性是建立非平凡代理遗憾度量上界的必要和充分条件。其次，我们解决了一个重要的开放性问题，即对于一类广泛的严格适当的损失函数，p-范数的收敛顺序不能比代理遗憾度量的1/2顺序更快。这意味着强适当损失函数具有最优的收敛速度。

论文研究了机器学习中损失函数的选择对于构建分类和排名预测器的影响，以及损失函数的严格适用性与估计器的性能之间的关系。

论文提出了一个代理后悔的概念来衡量估计器从真实概率向量中估计出的概率向量的次优性，并证明了损失函数的严格适用性是确保非空代理后悔界限的必要和充分条件。论文还证明了对于一类广泛的严格适用性损失函数，p-范数的收敛顺序不能快于代理后悔的1/2顺序，这意味着强适用性损失函数具有最佳的收敛速率。

论文的实验结果表明，强适用性损失函数在构建分类和排名预测器时具有优异的性能。论文还提供了一些开源的数据集和代码供研究者使用。

相关研究包括但不限于：《A convex formulation for learning task-specific word embeddings》、《On the Convergence of Adam and Beyond》、《A Unified Optimization Framework for Structured Output Learning》等。