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.
@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 -
Hazan, E. & Kakade, S.M.. (2012). (weak) Calibration is Computationally Hard. Proceedings of the 25th Annual Conference on Learning Theory, in PMLR 23:3.1-3.10
This site last compiled Sun, 15 Jul 2018 13:29:10 +0000