Online Learning with Primary and Secondary Losses
  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.
