(weak) Calibration Is Computationally Hard
Abstract
We show that the existence of a computationally efficient calibration algorithm, with a low weak calibration rate, would imply the existence of an efficient algorithm for computing approximate Nash equilibria – thus implying the unlikely conclusion that every problem in \emphPPAD is solvable in polynomial time.
Cite
Text
Hazan and Kakade. "(weak) Calibration Is Computationally Hard." Proceedings of the 25th Annual Conference on Learning Theory, 2012.Markdown
[Hazan and Kakade. "(weak) Calibration Is Computationally Hard." Proceedings of the 25th Annual Conference on Learning Theory, 2012.](https://mlanthology.org/colt/2012/hazan2012colt-weak/)BibTeX
@inproceedings{hazan2012colt-weak,
title = {{(weak) Calibration Is Computationally Hard}},
author = {Hazan, Elad and Kakade, Sham M.},
booktitle = {Proceedings of the 25th Annual Conference on Learning Theory},
year = {2012},
pages = {3.1-3.10},
volume = {23},
url = {https://mlanthology.org/colt/2012/hazan2012colt-weak/}
}