인스턴스 적응형 온라인 다중 클래스 다중 보정
Instance-Adaptive Online Multiclass Multicalibration
한국어 초록
본 논문에서는 $T$ 라운드에 걸친 온라인 다중 클래스 다중 보정(online multiclass multicalibration)을 연구하고, 최악의 경우를 넘어서는(beyond-worst-case) 보장을 제공하는 알고리즘을 제시한다. $n$개의 가능한 결과가 주어질 때, 예측값은 $d=n-1$ 차원의 심플렉스(simplex) 내에 존재한다. 최악의 경우 누적 $\ell_1$ 다중 보정 오차의 스케일링은 $\widetildeΘ(T^{(d+1)/(d+2)})$를 따르며, 이는 $d$가 작은 상수를 넘어서면 감당하기 어려워진다. 본 연구의 알고리즘은 실현된 시퀀스의 기하학적 구조에 적응한다. 즉, 적대적으로 선택된 결과 평균의 시퀀스가 $s$ 차원의 아핀 부분공간(affine subspace)에 속하는 경우, 높은 확률로 $\widetilde O(n^{1/(s+2)}T^{(s+1)/(s+2)})$의 오차를 달성한다. 이 알고리즘은 해당 부분공간이나 그 차원을 알지 못하더라도 이러한 구조에 적응한다. $T\ge n\ge2$에 대해 이 속도는 다항 로그(polylogarithmic) 인수를 제외하고 미니맥스 최적(minimax optimal)이다. 고정된 조건부 평균을 갖는 확률적 인스턴스의 경우, 이 상한은 $\widetilde O(\sqrt{nT})$로 특화되어 시계(horizon)에 대해 제곱근 의존성을 제공한다.
원문 초록
We study online multiclass multicalibration over $T$ rounds, and give an algorithm with beyond-worst-case guarantees. With $n$ possible outcomes, forecasts lie in a simplex of dimension $d=n-1$. In the worst case, cumulative $\ell_1$ multicalibration error scales with $\widetildeΘ(T^{(d+1)/(d+2)})$, which becomes untenable once $d$ exceeds a small constant. Our algorithm adapts to the geometry of the realized sequence: if the sequence of adversarially selected outcome means lies in an affine subspace of dimension $s$, it obtains error $\widetilde O(n^{1/(s+2)}T^{(s+1)/(s+2)})$ with high probability. The algorithm adapts to this structure without knowing the subspace or its dimension. For $T\ge n\ge2$, this rate is minimax optimal up to polylogarithmic factors. For a stochastic instance with a fixed conditional mean, the bound specializes to $\widetilde O(\sqrt{nT})$, giving a square-root dependence on the horizon.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
오차 경계 $O(T^{2/3-ε})$를 갖는 효율적 순차 보정
Efficient Sequential Calibration with $O(T^{2/3-ε})$ Error Bound
온라인 이진 순차 보정(sequential calibration) 문제를 연구한다. \citet{dagan2024breaking}의 최근 돌파구는 보정 오차(calibration error)에 대한 고전적인 \(T^{2/3}\) 장벽을 극복한다. 이 결과를 바탕으로, 상수 \(\varepsilon>0\)에 대해 기대 보정 오차 \(O(T^{2/3-\varepsilon})\)를 달성하는 효율적인 확률적 예측기(forecaster)를 제시한다. 우리의 예측기는 \textsc{SPR-Calibration} 절차 \citep{dagan2024breaking}와 외부 Blackwell형 보정 층(correction layer)을 결합한다. \textsc{SPR-Calibration} 절차는 조건부 평균 추정치의 대리(surrogate) 서열에 대한 보정을 제어하고, 보정 층은 이러한 대리값이 실제 결과를 근사할 때 발생하는 추가 오차를 제어한다. 분석은 총 보정 오차를 대리 보정 오차와 대리 서열과 실제 결과 사이의 잔차 불일치(residual discrepancy)로 분해한다. 전자는 \citet{dagan2024breaking}의 \textsc{SPR-Calibration} 보장으로 경계가 주어지며, 후자는 이차 포텐셜(quadratic potential) 논증과 \textsc{SPR-Calibration} 예측기의 희소성을 함께 사용하여 제어된다.
U-보정(U-calibration)에서 동시적 최적 후회를 향하여
Toward Simultaneously Optimal Regret in U-Calibration
U-보정(U-calibration)은 알 수 없는 다운스트림 에이전트가 소비할 수 있는 예측을 수행하는 온라인 예측 알고리즘을 연구하며, 모든 proper 손실 함수에 대해 동시에 준선형 후회를 보장합니다. 기존 U-보정 알고리즘은 모든 유계 proper 손실에 대해 최악의 경우 최적인 $O(\sqrt{T})$ 후회를 달성하지만, 더 쉬운 손실에는 적응하지 못합니다. 본 연구에서 보여드리듯이, 제곱 손실과 같은 매끄러운 손실의 경우에도 최적의 $O(\log T)$ 후회 대신 $Ω(\sqrt{T})$ 후회가 발생합니다. 본 연구에서 우리는 이러한 한계가 본질적인 것이 아님을 보여줍니다. 구체적으로, 우리는 모든 유계 proper 손실에 대해 $\tilde O(\sqrt{T})$ 후회를, 그리고 모든 유계 매끄러운 proper 손실에 대해 $O(\log T)$ 후회를 동시에 달성하는 단일 예측 알고리즘을 설계합니다. 더 일반적으로, 우리의 알고리즘은 여러 non-Lipschitz 예제를 포함하는 로그 장벽(log-barrier)에 대해 상대적으로 매끄러운 손실에 대해서도 로그 후회를 달성합니다. 우리의 접근 방식은 self-concordant 노이즈를 사용하여 예측 공간에 직접 섭동을 적용하는 Follow-the-Perturbed-Leader (FTPL)의 새로운 변형에 기반합니다. 결과적인 분석은 이 노이즈의 복잡한 성질로 인해 기존 FTPL 분석과 상당히 다르며, 그 자체로도 독립적인 가치가 있을 수 있습니다.
TIP-Search: Time-Predictable Inference Scheduling for Market Prediction under Uncertain Load
매개변수 없는 그룹 조건부 온라인 컨포멀 예측
Parameter-Free and Group Conditional Online Conformal Prediction
A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
일반 함수 근사 하에서의 최적·효율적 문맥적 조합 세미-밴딧
Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
52 pages