arXiv:2611.22646v1 cs.LG

온라인 컨포멀 예측에서 포함률을 엄격히 보장하는 비용

The Price of Hard Coverage Constraints in Online Conformal Prediction

Mingrui Liu

제출 2026-11-18

한국어 초록

컨포멀 예측은 분포에 의존하지 않고 불확실성을 정량화한다. 하지만 순차적으로 운용할 때 표준 포함률 보장을 만족해도 예측 집합이 실제값을 포함하지 못한 횟수는 시간에 따라 크게 요동칠 수 있다. 매 라운드 하나의 예측 집합을 내고, 운용 내내 미포함 누적 횟수가 정해진 예산을 넘지 않아야 하는 온라인 설정을 연구한다. 예측 집합을 넓히면 이러한 엄격한 포함률 제약을 지킬 수 있다. 집합 크기가 최소한 얼마나 더 커져야 하는지는 불분명하다. 예측 라운드 $T$회에 걸쳐 피할 수 없는 효율 비용을 규명한다. 데이터가 독립적이고 동일한 분포를 따르며, 점수 분포와 모집단 최적 예측 집합을 정확히 알아도 이 비용은 남는다. 포함률과 예측 집합 크기의 관계에 적절한 정칙성 조건을 적용해, 엄격한 포함률 제약을 충족하는 온라인 방법에 필요한 최소 누적 초과 집합 크기를 구한다. 평가 시점을 미리 고정하면 기대 비용의 최솟값은 $\Theta(\log T)$다. $T$까지 가능한 고정 시점 중 가장 큰 기대 비용을 취하면 $\Theta(T^{1/3})$이고, 실현한 비용 중 최악의 경우를 사후에 골라 그 기댓값을 취하면 $\Theta(\sqrt{T})$다. 점수 분포를 모르는 경우에도 과거 점수만으로 이 증가율을 달성할 수 있음을 보인다. 통계적 특성을 완전히 알아도 순차 예측의 신뢰성을 보장하려면 비용이 든다.

원문 초록

Conformal prediction provides distribution-free uncertainty quantification, but in sequential deployment, standard coverage guarantees can still allow substantial fluctuations in the number of miscoverages over time. We study an online setting in which prediction sets are produced one round at a time and the cumulative number of miscoverages must stay within a prescribed budget throughout deployment.Such a hard coverage guarantee can be enforced by enlarging prediction sets, but how much additional prediction-set size is fundamentally necessary remains unclear. We characterize this unavoidable efficiency cost over $T$ prediction rounds. Remarkably, the cost persists even with i.i.d.\ data, a known score distribution, and perfect knowledge of the population-optimal prediction set. Under suitable regularity conditions relating coverage and prediction-set size, we determine the minimum cumulative excess prediction-set size required by any online method satisfying the hard coverage constraint. This minimum cost is $\Theta(\log T)$ for expected cost at a fixed time known in advance, $\Theta(T^{1/3})$ for the largest expected cost over all fixed times up to $T$, and $\Theta(\sqrt{T})$ for the expected worst realized cost when the evaluation time is chosen in hindsight. We further show that these rates can be attained using past scores, without knowing the score distribution. Thus, even perfect statistical knowledge does not make sequential reliability free.

제출 이력

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

  1. arXiv:2611.22646v1제출 시각 미확인

함께 살펴볼 논문

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

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

토론

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