Predicting with Distributions

Michael Kearns, Zhiwei Steven Wu
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1214-1241, 2017.

Abstract

We consider a new learning model in which a joint distribution over vector pairs $(x,y)$ is determined by an unknown function $c(x)$ that maps input vectors $x$ not to individual outputs, but to entire \em distributions\/ over output vectors $y$. Our main results take the form of rather general reductions from our model to algorithms for PAC learning the function class and the distribution class separately, and show that virtually every such combination yields an efficient algorithm in our model. Our methods include a randomized reduction to classification noise and an application of Le Cam’s method to obtain robust learning algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-kearns17a, title = {Predicting with Distributions}, author = {Kearns, Michael and Wu, Zhiwei Steven}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1214--1241}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/kearns17a/kearns17a.pdf}, url = {https://proceedings.mlr.press/v65/kearns17a.html}, abstract = { We consider a new learning model in which a joint distribution over vector pairs $(x,y)$ is determined by an unknown function $c(x)$ that maps input vectors $x$ not to individual outputs, but to entire \em distributions\/ over output vectors $y$. Our main results take the form of rather general reductions from our model to algorithms for PAC learning the function class and the distribution class separately, and show that virtually every such combination yields an efficient algorithm in our model. Our methods include a randomized reduction to classification noise and an application of Le Cam’s method to obtain robust learning algorithms.} }
Endnote
%0 Conference Paper %T Predicting with Distributions %A Michael Kearns %A Zhiwei Steven Wu %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-kearns17a %I PMLR %P 1214--1241 %U https://proceedings.mlr.press/v65/kearns17a.html %V 65 %X We consider a new learning model in which a joint distribution over vector pairs $(x,y)$ is determined by an unknown function $c(x)$ that maps input vectors $x$ not to individual outputs, but to entire \em distributions\/ over output vectors $y$. Our main results take the form of rather general reductions from our model to algorithms for PAC learning the function class and the distribution class separately, and show that virtually every such combination yields an efficient algorithm in our model. Our methods include a randomized reduction to classification noise and an application of Le Cam’s method to obtain robust learning algorithms.
APA
Kearns, M. & Wu, Z.S.. (2017). Predicting with Distributions. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1214-1241 Available from https://proceedings.mlr.press/v65/kearns17a.html.

Related Material