arXiv:2611.21542v1 math.ST

장기 커버리지 강제의 비용: 온라인 컨포멀 예측에서의 상전이

The cost of enforcing long-run coverage: a phase transition in online conformal prediction

Yu Gui, Rina Foygel Barber, Cong Ma

제출 2026-11-16

한국어 초록

매 시점마다 새로운 특징 벡터가 주어지고, 해당 응답을 포함할 가능성이 높은 예측 구간 또는 예측 집합을 제공해야 하는 온라인 예측 설정을 考える. 이 설정에서 데이터 포인트가 i.i.d.(또는 더 일반적으로 교환 가능)이면, 컨포멀 예측은 임의의 학습된 모델의 출력 주위에 유효한 예측 집합을 구성하는 메커니즘을 제공하여 각 시점 $t$에서 $\geq 1-\alpha$의 커버리지 확률을 보장한다. 그러나 실제로는 분포 드리프트, 변화점 등의 문제로 i.i.d. 가정이 위반될 수 있다. 이러한 적대적 설정에서도 온라인 컨포멀 예측 방법은 장기 경험적 커버리지에 대한 보장을 제공할 수 있다. 하지만 이 두 가지 목표 사이에는 상충 관계가 있다. 적대적 설정에 대비하여 장기 경험적 커버리지에 엄격한 제약을 강제하면, i.i.d. 설정에서 순간적인 학습 조건부 커버리지가 불안정하게 진동할 수 있다. 본 연구에서는 i.i.d. 설정에서는 순간적 학습 조건부 커버리지의 누적 오차를 최소화하면서 적대적 설정에서는 장기 경험적 커버리지 보장도 제공하는, 두 세계의 장점을 모두 갖춘 알고리즘을 추구한다. 구체적으로, 어떤 $\beta\in[0,1]$에 대해 장기 경험적 커버리지가 목표 수준 $1-\alpha$에서 최대 $\mathcal{O}(T^{-\beta})$만큼만 벗어나도록 요구하는 조건을 생각한다. 우리는 이 조건들의 족이 상전이로 기술될 수 있음을 증명한다. $\beta\in[0,\frac{1}{2}]$인 경우, 적대적 설정에서 이러한 제약을 만족하면서도 데이터가 실제로 i.i.d.일 때 분할 컨포멀 예측과 동일한 순간 커버리지 성능을 제공하는 알고리즘을 구성할 수 있다. 반면 $\beta\in(\frac{1}{2},1]$인 경우 이러한 조건은 비용을 수반하며 두 세계의 장점을 모두 갖춘 동작을 달성하지 못한다.

원문 초록

Consider an online prediction setting, where at each time, we are given a new feature vector and asked to provide a prediction interval or prediction set that will likely contain the corresponding response. In this setting, if the data points are i.i.d. (or more generally, exchangeable), conformal prediction provides a mechanism for building valid prediction sets around the output of any trained model, offering coverage probability $\geq 1-\alpha$ at each time $t$. In practice, however, issues such as distribution drift, changepoints, or other challenges may cause violations of the i.i.d. assumption. In this adversarial setting, online conformal prediction methods can still offer guarantees on long-run empirical coverage. However, there is a trade-off between these two types of goals: enforcing tight constraints on long-run empirical coverage to protect against the adversarial setting can lead to unstable oscillations in the instantaneous training-conditional coverage in the i.i.d. setting. In this work, we seek best-of-both-worlds algorithms that aim to minimize cumulative error in instantaneous training-conditional coverage when in the i.i.d. setting, while also offering long-run empirical coverage guarantees in the adversarial setting. Specifically, consider a condition that requires long-run empirical coverage to deviate from the target level $1-\alpha$ by at most $\mathcal{O}(T^{-\beta})$, for some $\beta\in[0,1]$. We prove that this family of conditions can be described with a phase transition. For $\beta\in[0,\frac{1}{2}]$, it is possible to construct algorithms satisfying such a constraint in the adversarial setting, while offering the same instantaneous coverage performance as split conformal prediction if the data is in fact i.i.d. On the other hand, for $\beta\in(\frac{1}{2},1]$, this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.21542v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.