论文标题
主要和次要损失的在线学习
Online Learning with Primary and Secondary Losses
论文作者
论文摘要
我们研究了在线学习的问题，并以初级和次要损失的方式研究。例如，招聘人员决定要雇用的工作申请人可能会平等地称为假阳性和假否定因素（主要损失），但申请人可能称为虚假负面因素（次要损失）。我们考虑以下问题：我们是否可以将“专家建议”结合起来，以在主要损失方面获得低遗憾，而同时进行{\ em比最糟糕的专家}对次要损失差得多？不幸的是，我们表明这个目标是无法实现的，而没有任何有限的差异假设对次要损失。更笼统地，我们考虑到将对主要损失的遗憾最小化，并通过线性阈值界定次要损失的目标。从积极的一面来看，我们表明，如果所有专家都满足以下假设，即在任何时间间隔中，所有专家都无法超过$ O（t）$的线性阈值，则运行任何开关限制算法都可以实现此目标。如果并非所有的专家都满足这一假设，我们的算法可以实现此目标，鉴于可以访问某些外部神话，这些外部神话可以决定何时停用和重新激活专家。
We study the problem of online learning with primary and secondary losses. For example, a recruiter making decisions of which job applicants to hire might weigh false positives and false negatives equally (the primary loss) but the applicants might weigh false negatives much higher (the secondary loss). We consider the following question: Can we combine "expert advice" to achieve low regret with respect to the primary loss, while at the same time performing {\em not much worse than the worst expert} with respect to the secondary loss? Unfortunately, we show that this goal is unachievable without any bounded variance assumption on the secondary loss. More generally, we consider the goal of minimizing the regret with respect to the primary loss and bounding the secondary loss by a linear threshold. On the positive side, we show that running any switching-limited algorithm can achieve this goal if all experts satisfy the assumption that the secondary loss does not exceed the linear threshold by $o(T)$ for any time interval. If not all experts satisfy this assumption, our algorithms can achieve this goal given access to some external oracles which determine when to deactivate and reactivate experts.
