Related papers: Online selective conformal inference: adaptive scores, convergence rate and optimality

Online selective conformal inference: adaptive scores, convergence rate and optimality

URL: http://arxiv.org/abs/2508.10336v1
Date: Thu, 14 Aug 2025 04:36:14 GMT
Title: Online selective conformal inference: adaptive scores, convergence rate and optimality
Authors: Pierre Humbert, Ulysse Gazin, Ruth Heller, Etienne Roquain,
Abstract summary: We introduce an extended version of the point-prediction algorithm, called OnlineSCI, allowing the user to select times where such an inference should be made.<n>OnlineSCI encompasses several prominent online selective tasks, such as building prediction intervals for extreme outcomes, classification with abstention, and online testing.<n>We show that the adaptive versions of OnlineSCI can convergence to an optimal solution and provide an explicit convergence rate in each of the aforementioned application cases.
Score: 4.7198252163006345
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In a supervised online setting, quantifying uncertainty has been proposed in the seminal work of \cite{gibbs2021adaptive}. For any given point-prediction algorithm, their method (ACI) produces a conformal prediction set with an average missed coverage getting close to a pre-specified level $\alpha$ for a long time horizon. We introduce an extended version of this algorithm, called OnlineSCI, allowing the user to additionally select times where such an inference should be made. OnlineSCI encompasses several prominent online selective tasks, such as building prediction intervals for extreme outcomes, classification with abstention, and online testing. While OnlineSCI controls the average missed coverage on the selected in an adversarial setting, our theoretical results also show that it controls the instantaneous error rate (IER) at the selected times, up to a non-asymptotical remainder term. Importantly, our theory covers the case where OnlineSCI updates the point-prediction algorithm at each time step, a property which we refer to as {\it adaptive} capability. We show that the adaptive versions of OnlineSCI can convergence to an optimal solution and provide an explicit convergence rate in each of the aforementioned application cases, under specific mild conditions. Finally, the favorable behavior of OnlineSCI in practice is illustrated by numerical experiments.

Related papers

Optimal training-conditional regret for online conformal prediction [20.643619398558315]
We study online conformal prediction for non-stationary data streams subject to unknown distribution drift.<n>We specifically focus on independently generated data with two types of distribution shift: abrupt change points and smooth drift.<n>We establish non-asymptotic regret guarantees for our online full conformal algorithm, which match the minimax lower bound under appropriate restrictions on the prediction sets.
arXiv Detail & Related papers (2026-02-18T15:31:15Z)
Distribution-informed Online Conformal Prediction [53.674678995825666]
We propose Conformal Optimistic Prediction (COP), an online conformal prediction algorithm incorporating underlying data pattern into the update rule.<n>COP produces tighter prediction sets when predictable pattern exists, while retaining valid coverage guarantees even when estimates are inaccurate.<n>We prove that COP can achieve valid coverage and construct shorter prediction intervals than other baselines.
arXiv Detail & Related papers (2025-12-08T17:51:49Z)
AdaSwitch: An Adaptive Switching Meta-Algorithm for Learning-Augmented Bounded-Influence Problems [9.387255955861162]
We study a class of multi-period online decision-making problems with sequence-based predictions.<n>In each period, the decision-maker observes the realized request and must take an irrevocable action that yields a reward or incurs a cost.<n>We introduce a bounded-influence framework, in which past decisions and requests exert only limited impact on the future optimal reward.<n>Within this framework, we propose the AdaSwitch meta-algorithm, which exploits predictions to attain performance close to the offline benchmark when predictions are accurate.
arXiv Detail & Related papers (2025-09-02T13:26:23Z)
Conformal Information Pursuit for Interactively Guiding Large Language Models [68.16703423481935]
This paper explores sequential querying strategies that aim to minimize the expected number of queries.<n>One such strategy is Information Pursuit (IP), a greedy algorithm that at each iteration selects the query that maximizes information gain or equivalently minimizes uncertainty.<n>We propose Conformal Information Pursuit (C-IP), an alternative approach to sequential information gain based on conformal prediction sets.
arXiv Detail & Related papers (2025-07-04T03:55:39Z)
Online Conformal Probabilistic Numerics via Adaptive Edge-Cloud Offloading [52.499838151272016]
This work introduces a new method to calibrate the HPD sets produced by PLS with the aim of guaranteeing long-term coverage requirements.<n>The proposed method, referred to as online conformal prediction-PLS (OCP-PLS), assumes sporadic feedback from cloud to edge.<n>The validity of OCP-PLS is verified via experiments that bring insights into trade-offs between coverage, prediction set size, and cloud usage.
arXiv Detail & Related papers (2025-03-18T17:30:26Z)
Adaptive Conformal Inference by Betting [51.272991377903274]
We consider the problem of adaptive conformal inference without any assumptions about the data generating process.<n>Existing approaches for adaptive conformal inference are based on optimizing the pinball loss using variants of online gradient descent.<n>We propose a different approach for adaptive conformal inference that leverages parameter-free online convex optimization techniques.
arXiv Detail & Related papers (2024-12-26T18:42:08Z)
CAP: A General Algorithm for Online Selective Conformal Prediction with FCR Control [4.137346786534721]
It is important to control the real-time false coverage-statement rate (FCR) which measures the overall miscoverage level.<n>We develop a general framework named CAP that performs an adaptive pick rule on historical data to construct a calibration set.<n>We prove that CAP can achieve an exact selection-conditional coverage guarantee in the finite-sample and distribution-free regimes.
arXiv Detail & Related papers (2024-03-12T15:07:20Z)
Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
We develop new online conformal prediction methods that minimize the strongly adaptive regret. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks.
arXiv Detail & Related papers (2023-02-15T18:59:30Z)
Structure-Adaptive Sequential Testing for Online False Discovery Rate Control [1.456699007803424]
This work develops a new class of structure--adaptive sequential testing (SAST) rules for online false discover rate (FDR) control. A key element in our proposal is a new alpha--investment algorithm that precisely characterizes the gains and losses in sequential decision making.
arXiv Detail & Related papers (2020-02-28T23:16:44Z)
Toward Optimal Adversarial Policies in the Multiplicative Learning System with a Malicious Expert [87.12201611818698]
We consider a learning system that combines experts' advice to predict a sequence of true outcomes. It is assumed that one of the experts is malicious and aims to impose the maximum loss on the system. We show that a simple greedy policy of always reporting false prediction is optimal with an approximation ratio of $1+O(sqrtfracln NN)$. For the online setting where the malicious expert can adaptively make its decisions, we show that the optimal online policy can be efficiently computed by solving a dynamic program in $O(N3)$.
arXiv Detail & Related papers (2020-01-02T18:04:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.