  The classical problem of supervised learning is to infer an accurate
predictor of a target variable $Y$ from a measured variable $X$ by using a
finite number of labeled training samples. Motivated by the increasingly
distributed nature of data and decision making, in this paper we consider a
variation of this classical problem in which the prediction is performed
remotely based on a rate-constrained description $M$ of $X$. Upon receiving
$M$, the remote node computes an estimate $\hat Y$ of $Y$. We follow the recent
minimax approach to study this learning problem and show that it corresponds to
a one-shot minimax noisy source coding problem. We then establish information
theoretic bounds on the risk-rate Lagrangian cost and a general method to
design a near-optimal descriptor-estimator pair, which can be viewed as a
rate-constrained analog to the maximum conditional entropy principle used in
the classical minimax learning problem. Our results show that a naive
estimate-compress scheme for rate-constrained prediction is not in general
optimal.
