한국어 초록
보정(calibration)된 온라인 예측을 수행하는 것은 현대 AI 시스템의 핵심 과제이다. 기존 문헌의 상당수는 결과가 임의적일 수 있는 완전 적대적 환경에 초점을 맞추며, 이로 인해 결과가 거의 정상적인 경우와 같은 더 온건한 환경에서는 최적에 미치지 못할 수 있는 보수적인 알고리즘이 나타난다. 이러한 간극은 자연스러운 질문을 낳는다. 보정 오차가 환경의 비정상성 정도에 자동으로 적응하여 i.i.d. 체제와 적대적 체제 사이를 매끄럽게 보간하는 온라인 예측 알고리즘을 설계할 수 있는가? 본 연구는 이 질문에 긍정적으로 답하며, 여러 보정 척도에 대해 적응형 보정 보장을 달성하는 일련의 알고리즘을 개발한다. 구체적으로, $T$를 라운드 수, $W$를 환경의 알려지지 않은 i.i.d. 구간 수, $C\in[0,T]$를 평균 결과의 최소 $\ell_1$ 편차로 정의되는 또 다른 알려지지 않은 비정상성 척도라 할 때, 제안 알고리즘은 $\ell_1$ 보정 오차에 대해 $\widetilde{\mathcal{O}}(\min\{\sqrt{T}+(TC)^{\frac{1}{3}}, \sqrt{WT}\})$를, $\ell_2$ 및 의사 KL 보정 오차 모두에 대해 $\widetilde{\mathcal{O}}(\min\{(1+C)^{\frac{1}{3}}, W\})$를 달성한다. 이러한 한계는 정상 상태($C=0$ 및 $W=1$)에서의 최적 비율과 일치하며, 완전 적대적 체제($C, W=\Omega(T)$)에서 알려진 보장을 회복한다. 본 접근법은 선행 연구(Hu et al., 2026; Luo et al., 2025)를 기반으로 확장하여, 에폭 기반 스케줄링과 실제 참값 근처에 더 세밀한 해상도를 할당하는 새로운 비균일 예측 공간 분할을 도입한다.
원문 초록
Making calibrated online predictions is a central challenge in modern AI systems. Much of the existing literature focuses on fully adversarial environments where outcomes may be arbitrary, leading to conservative algorithms that can perform suboptimally in more benign settings, such as when outcomes are nearly stationary. This gap raises a natural question: can we design online prediction algorithms whose calibration error automatically adapts to the degree of non-stationarity in the environment, smoothly interpolating between i.i.d. and adversarial regimes? We answer this question in the affirmative and develop a suite of algorithms that achieve adaptive calibration guarantees under multiple calibration measures. Specifically, with $T$ being the number of rounds, $W$ being the unknown number of i.i.d. segments of the environment, and $C\in[0,T]$ being another unknown non-stationary measure defined as the minimal $\ell_1$ deviation of the mean outcomes, our algorithms attain $\widetilde{\mathcal{O}}(\min\{\sqrt{T}+(TC)^{\frac{1}{3}}, \sqrt{WT}\})$ for $\ell_1$ calibration error and $\widetilde{\mathcal{O}}(\min\{(1+C)^{\frac{1}{3}}, W\})$ for both $\ell_2$ and pseudo KL calibration error. These bounds match the optimal rates in the stationary case ($C=0$ and $W=1$) and recover known guarantees in the fully adversarial regime ($C, W=\Omega(T)$). Our approach builds on and extends prior work (Hu et al., 2026; Luo et al., 2025), introducing an epoch-based scheduling together with a novel non-uniform partition of the prediction space that allocates finer resolution near the underlying ground truth.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2605.11490v3제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.