IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2101.01739.html
   My bibliography  Save this paper

Online Multivalid Learning: Means, Moments, and Prediction Intervals

Author

Listed:
  • Varun Gupta
  • Christopher Jung
  • Georgy Noarov
  • Mallesh M. Pai
  • Aaron Roth

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 \in G$ for any $G$ belonging to an arbitrary intersecting collection of groups $\mathcal{G}$. We provide three instantiations of this framework. The first is mean prediction, which corresponds to an online algorithm satisfying the notion of multicalibration from Hebert-Johnson et al. 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. 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.

Suggested Citation

  • Varun Gupta & Christopher Jung & Georgy Noarov & Mallesh M. Pai & Aaron Roth, 2021. "Online Multivalid Learning: Means, Moments, and Prediction Intervals," Papers 2101.01739, arXiv.org.
  • Handle: RePEc:arx:papers:2101.01739
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2101.01739
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Foster, Dean P. & Hart, Sergiu, 2018. "Smooth calibration, leaky forecasts, finite recall, and Nash dynamics," Games and Economic Behavior, Elsevier, vol. 109(C), pages 271-293.
    2. Foster, Dean P., 1999. "A Proof of Calibration via Blackwell's Approachability Theorem," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 73-78, October.
    3. Dean P. Foster & Sergiu Hart, 2021. "Forecast Hedging and Calibration," Journal of Political Economy, University of Chicago Press, vol. 129(12), pages 3447-3490.
    4. Fudenberg, Drew & Levine, David K., 1999. "Conditional Universal Consistency," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 104-130, October.
    5. Jing Lei & Max G’Sell & Alessandro Rinaldo & Ryan J. Tibshirani & Larry Wasserman, 2018. "Distribution-Free Predictive Inference for Regression," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 113(523), pages 1094-1111, July.
    6. Alvaro Sandroni & Rann Smorodinsky & Rakesh V. Vohra, 2003. "Calibration with Many Checking Rules," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 141-153, February.
    7. Victor Chernozhukov & Kaspar Wüthrich & Yinchu Zhu, 2018. "Exact and robust conformal inference methods for predictive machine learning with dependent data," CeMMAP working papers CWP16/18, Centre for Microdata Methods and Practice, Institute for Fiscal Studies.
    8. Lehrer, Ehud, 2001. "Any Inspection Is Manipulable," Econometrica, Econometric Society, vol. 69(5), pages 1333-1347, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Eddie Dekel & Yossi Feinberg, 2006. "Non-Bayesian Testing of a Stochastic Prediction," Review of Economic Studies, Oxford University Press, vol. 73(4), pages 893-906.
    2. Mannor, Shie & Shimkin, Nahum, 2008. "Regret minimization in repeated matrix games with variable stage duration," Games and Economic Behavior, Elsevier, vol. 63(1), pages 227-258, May.
    3. Feinberg, Yossi & Dekel, Eddie, 2004. "A True Expert Knows which Question Should Be Asked," Research Papers 1856, Stanford University, Graduate School of Business.
    4. Wojciech Olszewski & Alvaro Sandroni, 2006. "Strategic Manipulation of Empirical Tests," Discussion Papers 1425, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    5. Yossi Feinberg & Colin Stewart, 2008. "Testing Multiple Forecasters," Econometrica, Econometric Society, vol. 76(3), pages 561-582, May.
    6. Eddie Dekel & Yossi Feinberg, 2005. "No Manipulation Results for Non-Bayesian Tests," Levine's Working Paper Archive 784828000000000217, David K. Levine.
    7. David Lagziel & Ehud Lehrer, 2021. "Transferable deposits as a screening mechanism," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(2), pages 483-504, March.
    8. Foster, Dean & Hart, Sergiu, 2023. ""Calibeating": beating forecasters at their own game," Theoretical Economics, Econometric Society, vol. 18(4), November.
    9. Dean Foster & Rakesh Vohra, 2011. "Calibration: Respice, Adspice, Prospice," Discussion Papers 1537, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    10. Colin, Stewart, 2011. "Nonmanipulable Bayesian testing," Journal of Economic Theory, Elsevier, vol. 146(5), pages 2029-2041, September.
    11. Al-Najjar, Nabil I. & Sandroni, Alvaro & Smorodinsky, Rann & Weinstein, Jonathan, 2010. "Testing theories with learnable and predictive representations," Journal of Economic Theory, Elsevier, vol. 145(6), pages 2203-2217, November.
    12. Victor Chernozhukov & Kaspar Wuthrich & Yinchu Zhu, 2019. "Distributional conformal prediction," Papers 1909.07889, arXiv.org, revised Aug 2021.
    13. Dean P. Foster & Sergiu Hart, 2021. "Forecast Hedging and Calibration," Journal of Political Economy, University of Chicago Press, vol. 129(12), pages 3447-3490.
    14. Ehud Lehrer & Eilon Solan, 2016. "A General Internal Regret-Free Strategy," Dynamic Games and Applications, Springer, vol. 6(1), pages 112-138, March.
    15. Sandroni, Alvaro & Smorodinsky, Rann, 2004. "Belief-based equilibrium," Games and Economic Behavior, Elsevier, vol. 47(1), pages 157-171, April.
    16. Kavaler, Itay & Smorodinsky, Rann, 2019. "On comparison of experts," Games and Economic Behavior, Elsevier, vol. 118(C), pages 94-109.
    17. Wojciech Olszewski & Alvaro Sandroni, 2008. "Manipulability of Future-Independent Tests," Econometrica, Econometric Society, vol. 76(6), pages 1437-1466, November.
    18. Yuichi Noguchi, 2009. "Note on universal conditional consistency," International Journal of Game Theory, Springer;Game Theory Society, vol. 38(2), pages 193-207, June.
    19. Fudenberg, Drew & Levine, David K., 1999. "An Easier Way to Calibrate," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 131-137, October.
    20. Itay Kavaler & Rann Smorodinsky, 2019. "A Cardinal Comparison of Experts," Papers 1908.10649, arXiv.org, revised Feb 2020.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2101.01739. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.