arXiv:2610.07740v2 stat.ML

조화 가중치를 이용한 고차원 온라인 보정

High-Dimensional Online Calibration from Harmonic Weights

Maxwell Fishelson, Mehryar Mohri

제출 2026-11-16

한국어 초록

우리는 임의의 볼록 집합 $Y\subseteq\mathbb{R}^d$ 위에서 임의의 오차 노름 $\|\cdot\|_L$에 대한 다차원 예측의 온라인 보정을 연구한다. $d$개의 이진 결과를 동시에 예측하는 경우($Y=[0,1]^d$), 모든 고정된 정확도에 대해 $d$에 대한 다항식 수의 라운드 안에 $\varepsilon$-보정을 달성하는 최초의 알고리즘을 제시한다. 이 알고리즘은 $d^{O(1/\varepsilon)}$ 라운드를 요구하며, 기존 한계의 차원 의존성을 지수적으로 개선한다. 다중 클래스 예측($Y=\Delta_d$)에서도 동일한 $d^{O(1/\varepsilon)}$ 비율을 얻으며, 이는 Peng 및 Fishelson, Golowich, Mohri, Schneider의 $d^{\widetilde{O}(1/\varepsilon^2)}$ 한계를 개선한다. 우리의 알고리즘은 단순하다. 각 라운드에서 조화적으로 평활화된 과거 결과들에 대한 조화 가중 분포를 출력한다. 동일한 알고리즘이 모든 예측 집합과 오차 노름에 대해 작동한다. 더 일반적으로, 행렬 불일치 문제로 정의되는 기하학적 모수 $\gamma(Y,L)$에 대해 $\exp(O(\gamma(Y,L)/\varepsilon))$ 라운드 후에 $\varepsilon$-보정을 달성한다. 조화 가중치는 이산 힐베르트 변환 행렬이 모든 $L$에 대해 동시에 보편 상수 배 이내의 최적 불일치를 달성한다는 사실에서 동기를 얻는다. 이 최적성 결과는 독립적으로도 흥미로울 수 있다. 동일한 조화 응답은 고차원 Blackwell 접근 가능성을 위한 알고리즘 또한 제공한다. 그 보장은 결과 집합과 행동 집합의 결합 기하를 포착하는 더욱 정밀한 기하학적 모수에 의해 결정된다.

원문 초록

We study the online calibration of multidimensional forecasts over an arbitrary convex set $Y\subseteq\mathbb{R}^d$ relative to an arbitrary error norm $\|\cdot\|_L$. For forecasting $d$ binary outcomes simultaneously ($Y=[0,1]^d$), we give the first algorithm that achieves $\varepsilon$-calibration in a number of rounds that is polynomial in $d$ for every fixed accuracy. It requires $d^{O(1/\varepsilon)}$ rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting ($Y=\Delta_d$), we obtain the same $d^{O(1/\varepsilon)}$ rate, improving the $d^{\widetilde{O}(1/\varepsilon^2)}$ bounds of Peng and Fishelson, Golowich, Mohri, and Schneider. Our algorithm is simple: on each round, it outputs a harmonically weighted distribution over harmonically smoothed past outcomes. The same algorithm works for every forecast set and error norm. More generally, it achieves $\varepsilon$-calibration after $\exp(O(\gamma(Y,L)/\varepsilon))$ rounds, where $\gamma(Y,L)$ is a geometric parameter defined by a matrix discrepancy problem. The harmonic weights are motivated by the fact that the discrete Hilbert transform matrix achieves the optimal discrepancy up to a universal constant, simultaneously for every $L$. This optimality result may be of independent interest. The same harmonic responses also yield an algorithm for high-dimensional Blackwell approachability. Its guarantees are governed by a sharpened geometric parameter that captures the joint geometry of the outcome and action sets.

제출 이력

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

  1. arXiv:2610.07740v2제출 시각 미확인
  2. arXiv:2610.07740v1

함께 살펴볼 논문

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

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

토론

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