(weak) Calibration is Computationally Hard

Elad Hazan; Sham M. Kakade

(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.

Related Material

Download PDF

@InProceedings{pmlr-v23-hazan12a, title = {(weak) Calibration is Computationally Hard}, author = {Elad Hazan and Sham M. Kakade}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {3.1--3.10}, year = {2012}, editor = {Shie Mannor and Nathan Srebro and Robert C. Williamson}, 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 = {http://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.} }

%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 %J Proceedings of Machine Learning Research %P 3.1--3.10 %U http://proceedings.mlr.press %V 23 %W PMLR %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.

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 PY - 2012/06/16 DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-hazan12a PB - PMLR SP - 3.1 DP - PMLR EP - 3.10 L1 - http://proceedings.mlr.press/v23/hazan12a/hazan12a.pdf UR - http://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 -