{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T01:59:11Z","timestamp":1792547951583,"version":"4.5.0"},"reference-count":33,"publisher":"Institute of Mathematical Statistics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"In a supervised learning problem, given a predicted value that is the output of some trained model, how can we quantify our uncertainty around this prediction? Distribution-free predictive inference aims to construct prediction intervals around this output, with valid coverage that does not rely on assumptions on the distribution of the data or the nature of the model training algorithm. Existing methods in this area, including conformal prediction and jackknife+, offer theoretical guarantees that hold marginally (i.e., on average over a draw of training and test data). In contrast, training-conditional coverage is a stronger notion of validity that ensures predictive coverage of the test point for most draws of the training data, and is thus a more desirable property in practice. Training-conditional coverage was shown by Vovk (Mach. Learn. 92 (2013) 349\u2013376) to hold for the split conformal method, but recent work by Bian and Barber (Electron. J. Stat. 17 (2023) 2044\u20132066) proves that such validity guarantees are not possible for the full conformal and jackknife+ methods without further assumptions. In this paper, we show that an assumption of algorithmic stability ensures that the training-conditional coverage property holds for the full conformal and jackknife+ methods.<\/jats:p>","DOI":"10.1214\/25-aos2510","type":"journal-article","created":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T05:22:49Z","timestamp":1757654569000},"page":"1457-1482","source":"Crossref","is-referenced-by-count":2,"title":["Algorithmic stability implies training-conditional coverage for distribution-free prediction methods"],"prefix":"10.1214","volume":"53","author":[{"given":"Ruiting","family":"Liang","sequence":"first","affiliation":[{"name":"Committee on Computational and Applied Mathematics, University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rina Foygel","family":"Barber","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"18","doi-asserted-by":"publisher","unstructured":"Lei, J.<\/small>, G\u2019Sell, M.<\/small>, Rinaldo, A.<\/small>, Tibshirani, R. J.<\/small> and Wasserman, L.<\/small> (2018). Distribution-free predictive inference for regression. J. Amer. Statist. Assoc.<\/i> 113<\/b> 1094\u20131111.","DOI":"10.1080\/01621459.2017.1307116"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Vovk, V.<\/small> (2013). Conditional validity of inductive conformal predictors. Mach. Learn.<\/i> 92<\/b> 349\u2013376.","DOI":"10.1007\/s10994-013-5355-6"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Breiman, L.<\/small> (1996). Bagging predictors. Mach. Learn.<\/i> 24<\/b> 123\u2013140.","DOI":"10.1007\/BF00058655"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Breiman, L.<\/small> (2001). Random forests. Mach. Learn.<\/i> 45<\/b> 5\u201332.","DOI":"10.1023\/A:1010933404324"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Meinshausen, N.<\/small> and B\u00fchlmann, P.<\/small> (2010). Stability selection. J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> 72<\/b> 417\u2013473.","DOI":"10.1111\/j.1467-9868.2010.00740.x"},{"key":"22","doi-asserted-by":"publisher","unstructured":"ROGERS, R.<\/small>, ROTH, A.<\/small>, SMITH, A.<\/small> and THAKKAR, O.<\/small> (2016). Max-information, differential privacy, and post-selection hypothesis testing. In 57th Annual IEEE Symposium on Foundations of Computer Science\u2014FOCS<\/i> 2016 487\u2013494. IEEE Computer Soc., Los Alamitos, CA.","DOI":"10.1109\/FOCS.2016.59"},{"key":"29","doi-asserted-by":"publisher","unstructured":"STEINBERGER, L.<\/small> and LEEB, H.<\/small> (2023). Conditional predictive inference for stable algorithms. Ann. Statist.<\/i> 51<\/b> 290\u2013311.","DOI":"10.1214\/22-aos2250"},{"key":"21","doi-asserted-by":"publisher","unstructured":"PAPADOPOULOS, H.<\/small>, PROEDROU, K.<\/small>, VOVK, V.<\/small> and GAMMERMAN, A.<\/small> (2002). Inductive confidence machines for regression. In Machine Learning<\/i>: ECML<\/i> 2002. Lecture Notes in Computer Science<\/i> 2430<\/b> 345\u2013356. Springer, Berlin.","DOI":"10.1007\/3-540-36755-1_29"},{"key":"2","doi-asserted-by":"publisher","unstructured":"BARBER, R. F.<\/small>, CAND\u00c8S, E. J.<\/small>, RAMDAS, A.<\/small> and TIBSHIRANI, R. J.<\/small> (2021). Predictive inference with the jackknife+. Ann. Statist.<\/i> 49<\/b> 486\u2013507.","DOI":"10.1214\/20-AOS1965"},{"key":"31","doi-asserted-by":"publisher","unstructured":"VOVK, V.<\/small> (2015). Cross-conformal predictors. Ann. Math. Artif. Intell.<\/i> 74<\/b> 9\u201328.","DOI":"10.1007\/s10472-013-9368-4"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Bousquet, O.<\/small> and Elisseeff, A.<\/small> (2002). Stability and generalization. J. Mach. Learn. Res.<\/i> 2<\/b> 499\u2013526.","DOI":"10.1162\/153244302760200704"},{"key":"23","doi-asserted-by":"crossref","unstructured":"Rogers, W. H.<\/small> and Wagner, T. J.<\/small> (1978). A finite sample distribution-free performance bound for local discrimination rules. Ann. Statist.<\/i> 6<\/b> 506\u2013514.","DOI":"10.1214\/aos\/1176344196"},{"key":"32","unstructured":"Vovk, V.<\/small>, Gammerman, A.<\/small> and Shafer, G.<\/small> (2005). Algorithmic Learning in a Random World<\/i>. Springer, New York."},{"key":"33","doi-asserted-by":"publisher","unstructured":"ZRNIC, T.<\/small> and JORDAN, M. I.<\/small> (2023). Post-selection inference via algorithmic stability. Ann. Statist.<\/i> 51<\/b> 1666\u20131691.","DOI":"10.1214\/23-aos2303"},{"key":"25","doi-asserted-by":"publisher","unstructured":"SESIA, M.<\/small> and CAND\u00c8S, E. J.<\/small> (2020). A comparison of some conformal quantile regression methods. Stat<\/i> 9<\/b> e261, 8.","DOI":"10.1002\/sta4.261"},{"key":"1","unstructured":"AMANN, N.<\/small>, LEEB, H.<\/small> and STEINBERGER, L.<\/small> (2023). Assumption-lean conditional predictive inference via the Jackknife and the Jackknife+<\/b>. Preprint. Available at arXiv:2312.14596<\/a>."},{"key":"3","doi-asserted-by":"publisher","unstructured":"BIAN, M.<\/small> and BARBER, R. F.<\/small> (2023). Training-conditional coverage for distribution-free predictive inference. Electron. J. Stat.<\/i> 17<\/b> 2044\u20132066.","DOI":"10.1214\/23-ejs2145"},{"key":"8","doi-asserted-by":"publisher","unstructured":"DEVROYE, L. P.<\/small> and WAGNER, T. J.<\/small> (1979a). Distribution-free performance bounds for potential function rules. IEEE Trans. Inf. Theory<\/i> 25<\/b> 601\u2013604.","DOI":"10.1109\/TIT.1979.1056087"},{"key":"9","doi-asserted-by":"publisher","unstructured":"DEVROYE, L. P.<\/small> and WAGNER, T. J.<\/small> (1979b). Distribution-free inequalities for the deleted and holdout error estimates. IEEE Trans. Inf. Theory<\/i> 25<\/b> 202\u2013207.","DOI":"10.1109\/TIT.1979.1056032"},{"key":"10","doi-asserted-by":"crossref","unstructured":"DIETTERICH, T. G.<\/small> (2000). Ensemble methods in machine learning. In International Workshop on Multiple Classifier Systems<\/i> 1\u201315. Springer, Berlin.","DOI":"10.1007\/3-540-45014-9_1"},{"key":"11","unstructured":"DWORK, C.<\/small>, FELDMAN, V.<\/small>, HARDT, M.<\/small>, PITASSI, T.<\/small>, REINGOLD, O.<\/small> and ROTH, A.<\/small> (2015a). Generalization in adaptive data analysis and holdout reuse. Adv. Neural Inf. Process. Syst.<\/i> 28<\/b>."},{"key":"12","doi-asserted-by":"crossref","unstructured":"DWORK, C.<\/small>, FELDMAN, V.<\/small>, HARDT, M.<\/small>, PITASSI, T.<\/small>, REINGOLD, O.<\/small> and ROTH, A.<\/small> (2015b). Preserving statistical validity in adaptive data analysis [extended abstract]. In STOC\u2019<\/i>15\u2014Proceedings of the<\/i> 2015 ACM Symposium on Theory of Computing<\/i> 117\u2013126. ACM, New York.","DOI":"10.1145\/2746539.2746580"},{"key":"13","unstructured":"ELISSEEFF, A.<\/small>, EVGENIOU, T.<\/small> and PONTIL, M.<\/small> (2005). Stability of randomized learning algorithms. J. Mach. Learn. Res.<\/i> 6<\/b> 55\u201379."},{"key":"14","doi-asserted-by":"crossref","unstructured":"GRANDVALET, Y.<\/small> (2004). Bagging equalizes influence. Mach. Learn.<\/i> 55<\/b> 251\u2013270.","DOI":"10.1023\/B:MACH.0000027783.34431.42"},{"key":"15","doi-asserted-by":"crossref","unstructured":"KEARNS, M.<\/small> and RON, D.<\/small> (1997). Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. In Proceedings of the Tenth Annual Conference on Computational Learning Theory<\/i> 152\u2013162.","DOI":"10.1145\/267460.267491"},{"key":"16","doi-asserted-by":"publisher","unstructured":"KIM, B.<\/small> and BARBER, R. F.<\/small> (2023). Black-box tests for algorithmic stability. Inf. Inference<\/i> 12<\/b> Paper No. iaad039, 30.","DOI":"10.1093\/imaiai\/iaad039"},{"key":"17","unstructured":"LANGE, T.<\/small>, BRAUN, M.<\/small>, ROTH, V.<\/small> and BUHMANN, J.<\/small> (2002). Stability-based model selection. Adv. Neural Inf. Process. Syst.<\/i> 15<\/b>."},{"key":"19","doi-asserted-by":"crossref","unstructured":"LIANG, R.<\/small> and BARBER, R. F<\/small> (2025). Supplement to \u201cAlgorithmic stability implies training-conditional coverage for distribution-free prediction methods.\u201d https:\/\/doi.org\/10.1214\/25-AOS2510SUPP<\/a>","DOI":"10.1214\/25-AOS2510SUPP"},{"key":"27","unstructured":"SOLOFF, J. A.<\/small>, BARBER, R. F.<\/small> and WILLET, R.<\/small> (2024a). Stability via resampling: Statistical problems beyond the real line. Preprint. Available at arXiv:2405.09511<\/a>."},{"key":"28","unstructured":"SOLOFF, J. A.<\/small>, BARBER, R. F.<\/small> and WILLETT, R.<\/small> (2024b). Bagging provides assumption-free stability. J. Mach. Learn. Res.<\/i> 25<\/b> Paper No. [131], 35."},{"key":"26","doi-asserted-by":"publisher","unstructured":"SHAH, R. D.<\/small> and SAMWORTH, R. J.<\/small> (2013). Variable selection with error control: Another look at stability selection. J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> 75<\/b> 55\u201380.","DOI":"10.1111\/j.1467-9868.2011.01034.x"},{"key":"24","unstructured":"ROMANO, Y.<\/small>, PATTERSON, E.<\/small> and CANDES, E.<\/small> (2019). Conformalized quantile regression. Adv. Neural Inf. Process. Syst.<\/i> 32<\/b>."},{"key":"7","doi-asserted-by":"publisher","unstructured":"B\u00dcHLMANN, P.<\/small> and YU, B.<\/small> (2002). Analyzing bagging. Ann. Statist.<\/i> 30<\/b> 927\u2013961.","DOI":"10.1214\/aos\/1031689014"}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T16:37:42Z","timestamp":1791391062000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-53\/issue-4\/Algorithmic-stability-implies-training-conditional-coverage-for-distribution-free-prediction\/10.1214\/25-AOS2510.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"references-count":33,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,8,1]]}},"URL":"https:\/\/doi.org\/10.1214\/25-aos2510","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,1]]}}}