Hedging on the frontier: Learning new tasks with few samples

When a learner is faced with a new task, but is given very few samples, it must leverage any available side-information. In practice, this often comes in the form of benchmarks, where there is abundant data to evaluate model performance on related tasks. Though task relatedness is difficult to formalize theoretically, it can be empirically observed through weak monotonicity: if a model dominates another on all benchmarks, it also tends to outperform the other on the new task. We explore the statistical complexity of learning under weak monotonicity, leveraging it within two learning paradigms: transfer learning and model selection aggregation. We show that not only can we prune the model class based on monotonicity, but that we can further adapt to the geometry of the available trade-offs by hedging on the frontier.