2 Search Results for "Hart, Sergiu"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.82
Online Multivalid Learning: Means, Moments, and Prediction Intervals

Authors: Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We present a general, efficient technique for providing contextual predictions that are "multivalid" in various senses, against an online sequence of adversarially chosen examples (x,y). This means that the resulting estimates correctly predict various statistics of the labels y not just marginally - as averaged over the sequence of examples - but also conditionally on x ∈ G for any G belonging to an arbitrary intersecting collection of groups 𝒢. We provide three instantiations of this framework. The first is mean prediction, which corresponds to an online algorithm satisfying the notion of multicalibration from [Hébert-Johnson et al., 2018]. The second is variance and higher moment prediction, which corresponds to an online algorithm satisfying the notion of mean-conditioned moment multicalibration from [Jung et al., 2021]. Finally, we define a new notion of prediction interval multivalidity, and give an algorithm for finding prediction intervals which satisfy it. Because our algorithms handle adversarially chosen examples, they can equally well be used to predict statistics of the residuals of arbitrary point prediction methods, giving rise to very general techniques for quantifying the uncertainty of predictions of black box algorithms, even in an online adversarial setting. When instantiated for prediction intervals, this solves a similar problem as conformal prediction, but in an adversarial environment and with multivalidity guarantees stronger than simple marginal coverage guarantees.
Cite as

Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online Multivalid Learning: Means, Moments, and Prediction Intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 82:1-82:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ITCS.2022.82,
  author =	{Gupta, Varun and Jung, Christopher and Noarov, Georgy and Pai, Mallesh M. and Roth, Aaron},
  title =	{{Online Multivalid Learning: Means, Moments, and Prediction Intervals}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{82:1--82:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.82},
  URN =		{urn:nbn:de:0030-drops-156785},
  doi =		{10.4230/LIPIcs.ITCS.2022.82},
  annote =	{Keywords: Uncertainty Estimation, Calibration, Online Learning}
}
Document
DOI: 10.4230/DagRep.3.4.69
Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161)

Authors: Sergiu Hart, Éva Tardos, and Bernhard von Stengel

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13161 "Interface of Computation, Game Theory, and Economics". The workshop was strongly interdisciplinary, on the leading edge of current topics generally connected to algorithmic game theory: Mechanism design and auctions, interactions in networks, social models, and dynamics and equilibrium in games and markets. We summarize these topics, give the talk abstracts, and comment on experiences related to the organization of the workshop.
Cite as

Sergiu Hart, Éva Tardos, and Bernhard von Stengel. Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161). In Dagstuhl Reports, Volume 3, Issue 4, pp. 69-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{hart_et_al:DagRep.3.4.69,
  author =	{Hart, Sergiu and Tardos, \'{E}va and von Stengel, Bernhard},
  title =	{{Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161)}},
  pages =	{69--90},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Hart, Sergiu and Tardos, \'{E}va and von Stengel, Bernhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.4.69},
  URN =		{urn:nbn:de:0030-drops-41341},
  doi =		{10.4230/DagRep.3.4.69},
  annote =	{Keywords: Algorithmic Game Theory, Economics, Internet, Nash Equilibrium, Mechanism Design, Auctions}
}
  • Refine by Author
  • 1 Gupta, Varun
  • 1 Hart, Sergiu
  • 1 Jung, Christopher
  • 1 Noarov, Georgy
  • 1 Pai, Mallesh M.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Online learning theory

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Auctions
  • 1 Calibration
  • 1 Economics
  • 1 Internet
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2013
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact