Learning Effective Loss Functions Efficiently
  We consider the problem of learning a loss function which, when minimized
over a training dataset, yields a model that approximately minimizes a
validation error metric. Though learning an optimal loss function is NP-hard,
we present an anytime algorithm that is asymptotically optimal in the worst
case, and is provably efficient in an idealized "easy" case. Experimentally, we
show that this algorithm can be used to tune loss function hyperparameters
orders of magnitude faster than state-of-the-art alternatives. We also show
that our algorithm can be used to learn novel and effective loss functions
on-the-fly during training.
