  The label shift problem refers to the supervised learning setting where the
train and test label distributions do not match. Existing work addressing label
shift usually assumes access to an \emph{unlabelled} test sample. This sample
may be used to estimate the test label distribution, and to then train a
suitably re-weighted classifier. While approaches using this idea have proven
effective, their scope is limited as it is not always feasible to access the
target domain; further, they require repeated retraining if the model is to be
deployed in \emph{multiple} test environments. Can one instead learn a
\emph{single} classifier that is robust to arbitrary label shifts from a broad
family? In this paper, we answer this question by proposing a model that
minimises an objective based on distributionally robust optimisation (DRO). We
then design and analyse a gradient descent-proximal mirror ascent algorithm
tailored for large-scale problems to optimise the proposed objective. %, and
establish its convergence. Finally, through experiments on CIFAR-100 and
ImageNet, we show that our technique can significantly improve performance over
a number of baselines in settings where label shift is present.
