基于稳定性分析的非凸损失函数在线点对学习的遗憾界

作者：郎璇聪; 李春生; 刘勇; 王梅^*

来源：计算机研究与发展, 2023, 60(12): 2806-2813.

• 在线点对学习
• 非凸
• 稳定性
• 遗憾界
• 离线优化神谕

点对学习(pairwise learning)是指损失函数依赖于2个实例的学习任务.遗憾界对点对学习的泛化分析尤为重要.现有的在线点对学习分析只提供了凸损失函数下的遗憾界.为了弥补非凸损失函数下在线点对学习理论研究的空白，提出了基于稳定性分析的非凸损失函数在线点对学习的遗憾界.首先提出了一个广义的在线点对学习框架，并给出了具有非凸损失函数的在线点对学习的稳定性分析；然后，根据稳定性和遗憾界之间的关系，对非凸损失函数下的遗憾界进行研究；最后证明了当学习者能够获得离线神谕(oracle)时，具有非凸损失函数的广义在线点对学习框架实现了最佳的遗憾界O(T-1/2).

• 单位
  中国人民大学; 东北石油大学