4 Search Results for "Vohra, Rakesh"


Document
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
On Revenue Equivalence in Truthful Mechanisms

Authors: Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra

Published in: Dagstuhl Seminar Proceedings, Volume 7271, Computational Social Systems and the Internet (2007)


Abstract
The property of an allocation rule to be implementable in dominant strategies by a unique payment scheme is called revenue equivalence. In this paper we give a characterization of revenue equivalence based on a graph theoretic interpretation of the incentive compatibility constraints. The characterization holds for any (possibly infinite) outcome space and many of the known results about revenue equivalence are immediate consequences.

Cite as

Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra. On Revenue Equivalence in Truthful Mechanisms. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.07271.11,
  author =	{Heydenreich, Birgit and M\"{u}ller, Rudolf and Uetz, Marc and Vohra, Rakesh},
  title =	{{On Revenue Equivalence in Truthful Mechanisms}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7271},
  editor =	{Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07271.11},
  URN =		{urn:nbn:de:0030-drops-11581},
  doi =		{10.4230/DagSemProc.07271.11},
  annote =	{Keywords: Mechanism Design, Revenue Equivalence, Graph Theory}
}
Document
Dominant Strategy Mechanisms with Multidimensional Types

Authors: Hongwei Gui, Rudolf Müller, and Rakesh V. Vohra

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)


Abstract
This paper provides a characterization of dominant strategy mechanisms with quasi-linear utilities and multi-dimensional types for a variety of preference domains. These characterizations are in terms of a monotonicity property on the underlying allocation rule.

Cite as

Hongwei Gui, Rudolf Müller, and Rakesh V. Vohra. Dominant Strategy Mechanisms with Multidimensional Types. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{hongweigui_et_al:DagSemProc.05011.8,
  author =	{Hongwei Gui and M\"{u}ller, Rudolf and Vohra, Rakesh V.},
  title =	{{Dominant Strategy Mechanisms with Multidimensional Types}},
  booktitle =	{Computing and Markets},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.8},
  URN =		{urn:nbn:de:0030-drops-2107},
  doi =		{10.4230/DagSemProc.05011.8},
  annote =	{Keywords: Dominant Strategy, Farkas Lemma,}
}
Document
Electronic Market Design (Dagstuhl Seminar 02241)

Authors: Daniel Lehmann, Rudolf Müller, Tuomas Sandholm, and Rakesh V. Vohra

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Daniel Lehmann, Rudolf Müller, Tuomas Sandholm, and Rakesh V. Vohra. Electronic Market Design (Dagstuhl Seminar 02241). Dagstuhl Seminar Report 344, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)


Copy BibTex To Clipboard

@TechReport{lehmann_et_al:DagSemRep.344,
  author =	{Lehmann, Daniel and M\"{u}ller, Rudolf and Sandholm, Tuomas and Vohra, Rakesh V.},
  title =	{{Electronic Market Design (Dagstuhl Seminar 02241)}},
  pages =	{1--18},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{344},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.344},
  URN =		{urn:nbn:de:0030-drops-152250},
  doi =		{10.4230/DagSemRep.344},
}
  • Refine by Author
  • 3 Müller, Rudolf
  • 2 Vohra, Rakesh V.
  • 1 Gupta, Varun
  • 1 Heydenreich, Birgit
  • 1 Hongwei Gui
  • Show More...

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

  • Refine by Keyword
  • 1 Calibration
  • 1 Dominant Strategy
  • 1 Farkas Lemma,
  • 1 Graph Theory
  • 1 Mechanism Design
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2002
  • 1 2005
  • 1 2007
  • 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