Online Importance Weight Aware Updates
Nikos Karampatziakis Department of Computer Science Cornell University、John Langford Yahoo! Research Research done while author was at Yahoo! Research
Abstract
An importance weight quantifies the relative importance of one example over another, coming up in applications of boosting, asymmetric classification costs, reductions, and active learning. The standard approach for dealing with importance weights in gradient descent is via multiplication of the gradient. We first demonstrate the problems of this approach when importance weights are large, and argue in favor of more sophisticated ways for dealing with them. We then develop an approach which enjoys an invariance property: that updating twice with importance weight $h$ is equivalent to updating once with importance weight $2h$ . For many important losses this has a closed form update which satisfies standard regret guarantees when all examples have $h=1$ . We also briefly discuss two other reasonable approaches for handling large importance weights. Empirically, these approaches yield substantially superior prediction with similar computational performance while reducing the sensitivity of the algorithm to the exact setting of the learning rate. We apply these to online active learning yielding an extraordinarily fast active learning algorithm that works even in the presence of adver
中文速览
重要性权重（importance weight）在主动学习、Boosting 和协变量偏移等场景中无处不在，但在在线梯度下降里处理大权重时，传统做法——把梯度直接乘以权重 $h$——会因一阶近似失效而导致更新严重过冲，效果很差。本文提出了一种"重要性不变"更新方法：其核心思想是把"用权重 $h$ 更新一次"等价地定义为"用权重 $h/2$ 连续更新两次"，再通过将离散梯度下降推向学习率无穷小的极限，把问题转化为一个常微分方程，从而为平方损失、逻辑损失、Hinge 损失等几乎所有常用损失函数推导出了解析闭式更新公式。理论上这些更新满足标准遗憾界，实践中它们在平滑插值激进投影与保守梯度衰减之间，显著降低了学习率调参的敏感性，并在含或不含重要性权重的多种任务上大幅提升了预测精度，同时几乎不增加计算开销；将其应用于在线主动学习后，即便面对对抗噪声也能得到一个速度极快、效果出色的学习算法。
原文 arXiv:1011.1576;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1011.1576v4