Convex repeated games and Fenchel duality

Shai Shalev-Shwartz, Yoram Singer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

Abstract

We describe an algorithmic framework for an abstract game which we term a convex repeated game. We show that various online learning and boosting algorithms can be all derived as special cases of our algorithmic framework. This unified view explains the properties of existing algorithms and also enables us to derive several new interesting algorithms. Our algorithmic framework stems from a connection that we build between the notions of regret in game theory and weak duality in convex optimization.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference
Pages1265-1272
Number of pages8
StatePublished - Dec 1 2007
Externally publishedYes
Event20th Annual Conference on Neural Information Processing Systems, NIPS 2006 - Vancouver, BC, Canada
Duration: Dec 4 2006Dec 7 2006

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258

Other

Other20th Annual Conference on Neural Information Processing Systems, NIPS 2006
CountryCanada
CityVancouver, BC
Period12/4/0612/7/06

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint Dive into the research topics of 'Convex repeated games and Fenchel duality'. Together they form a unique fingerprint.

  • Cite this

    Shalev-Shwartz, S., & Singer, Y. (2007). Convex repeated games and Fenchel duality. In Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference (pp. 1265-1272). (Advances in Neural Information Processing Systems).