(Weak) calibration is computationally hard

Elad Hazan, Sham Kakade

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations


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 PPAD is solvable in polynomial time.

Original languageEnglish (US)
Pages (from-to)3.1-3.10
JournalJournal of Machine Learning Research
StatePublished - 2012
Externally publishedYes
Event25th Annual Conference on Learning Theory, COLT 2012 - Edinburgh, United Kingdom
Duration: Jun 25 2012Jun 27 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of '(Weak) calibration is computationally hard'. Together they form a unique fingerprint.

Cite this