(Weak) calibration is computationally hard

Elad Hazan, Sham Kakade

Research output: Contribution to journalConference article

1 Scopus citations

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

Original languageEnglish (US)
JournalJournal of Machine Learning Research
Volume23
StatePublished - Jan 1 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

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

  • Cite this