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Ŷ 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 rateconstrained prediction is not in general optimal.
In REF , the minimax approach is studied for a problem of remote prediction and is shown to correspond to a one-shot minimax noisy source coding problem.
Minimax Learning for Remote Prediction
2018 IEEE International Symposium on Information Theory (ISIT)
2018 IEEE International Symposium on Information Theory (ISIT)
Computer Science Mathematics