장기 커버리지 강제의 비용: 온라인 컨포멀 예측에서의 상전이
The cost of enforcing long-run coverage: a phase transition in online conformal prediction
한국어 초록
매 시점마다 새로운 특징 벡터가 주어지고, 해당 응답을 포함할 가능성이 높은 예측 구간 또는 예측 집합을 제공해야 하는 온라인 예측 설정을 考える. 이 설정에서 데이터 포인트가 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 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.