(weak) Calibration is Computationally Hard

Elad Hazan, Sham M. Kakade
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:3.1-3.10, 2012.

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 this Paper

BibTeX
@InProceedings{pmlr-v23-hazan12a, title = {(weak) Calibration is Computationally Hard}, author = {Hazan, Elad and Kakade, Sham M.}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {3.1--3.10}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/hazan12a/hazan12a.pdf}, url = {https://proceedings.mlr.press/v23/hazan12a.html}, 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.} }
Endnote
%0 Conference Paper %T (weak) Calibration is Computationally Hard %A Elad Hazan %A Sham M. Kakade %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-hazan12a %I PMLR %P 3.1--3.10 %U https://proceedings.mlr.press/v23/hazan12a.html %V 23 %X 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.
RIS
TY - CPAPER TI - (weak) Calibration is Computationally Hard AU - Elad Hazan AU - Sham M. Kakade BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-hazan12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 3.1 EP - 3.10 L1 - http://proceedings.mlr.press/v23/hazan12a/hazan12a.pdf UR - https://proceedings.mlr.press/v23/hazan12a.html AB - 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. ER -
APA
Hazan, E. & Kakade, S.M.. (2012). (weak) Calibration is Computationally Hard. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:3.1-3.10 Available from https://proceedings.mlr.press/v23/hazan12a.html.

Related Material