Exponential Weight Approachability, Applications to Calibration and Regret Minimization

Vianney Perchet ()

Dynamic Games and Applications, 2015, vol. 5, issue 1, 136-153

Abstract: Basic ideas behind the “exponential weight algorithm” (designed for aggregation or minimization of regret) can be transposed into the theory of Blackwell approachability. Using them, we develop an algorithm—that we call “exponential weight approachability”—bounding the distance of average vector payoffs to some product set, with a logarithmic dependency in the dimension of the ambient space. The classic strategy of Blackwell would get instead a polynomial dependency. This result has important consequences, in several frameworks that emerged both in game theory and machine learning. The most striking application is the construction of algorithms that are calibrated with respect to the family of all balls (we treat in details the case of the uniform norm), with dimension independent and optimal, up to logarithmic factors, rates of convergence. Calibration can also be achieved with respect to all Borel sets, covering and improving the previously known results. Exponential weight approachability can also be used to design an optimal and natural algorithm that minimizes refined notions of regret. Copyright Springer Science+Business Media New York 2015

Keywords: Approachability; Regret; Uncertainty; Calibration; Exponential weights (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s13235-014-0119-x (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:dyngam:v:5:y:2015:i:1:p:136-153

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/13235

DOI: 10.1007/s13235-014-0119-x

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

More articles in Dynamic Games and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().