arXiv:2610.15954v1 cs.LG

인스턴스 적응형 온라인 다중 클래스 다중 보정

Instance-Adaptive Online Multiclass Multicalibration

Zhiming Huang, Jamie Morgenstern, Aaron Roth, Claire Jie Zhang

제출 2026-10-11

저자 비고

arXiv Comments

52 pages

한국어 초록

본 논문에서는 $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 원문에서 확인하세요.

  1. arXiv:2610.15954v1

함께 살펴볼 논문

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

arXiv:2607.12928v1cs.LG공통 태그 calibration, online learning

오차 경계 $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} 예측기의 희소성을 함께 사용하여 제어된다.

arXiv:2606.18527v1stat.ML공통 태그 calibration, online learning

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 분석과 상당히 다르며, 그 자체로도 독립적인 가치가 있을 수 있습니다.

토론

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