Fugu-MT 論文翻訳(概要): High-Dimensional Calibration from Swap Regret

論文の概要: High-Dimensional Calibration from Swap Regret

arxiv url: http://arxiv.org/abs/2505.21460v1
Date: Tue, 27 May 2025 17:31:47 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-28 17:05:58.83387
Title: High-Dimensional Calibration from Swap Regret
Title（参考訳）: スワップレグレットからの高次元キャリブレーション
Authors: Maxwell Fishelson, Noah Golowich, Mehryar Mohri, Jon Schneider,
Abstract要約: 任意の凸集合 $mathcalP 部分集合 mathbbRd$ 上での多次元予測のオンライン校正について検討する。我々は、$O(sqrtrho T)$$$T$ラウンド後の最悪の後悔を保証できるならば、$T = exp(logd/epsilon2) の後、$epsilon$-calibrated 予測を得ることができることを示した。
参考スコア（独自算出の注目度）: 40.9736612423411
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the online calibration of multi-dimensional forecasts over an arbitrary convex set $\mathcal{P} \subset \mathbb{R}^d$ relative to an arbitrary norm $\Vert\cdot\Vert$. We connect this with the problem of external regret minimization for online linear optimization, showing that if it is possible to guarantee $O(\sqrt{\rho T})$ worst-case regret after $T$ rounds when actions are drawn from $\mathcal{P}$ and losses are drawn from the dual $\Vert \cdot \Vert_*$ unit norm ball, then it is also possible to obtain $\epsilon$-calibrated forecasts after $T = \exp(O(\rho /\epsilon^2))$ rounds. When $\mathcal{P}$ is the $d$-dimensional simplex and $\Vert \cdot \Vert$ is the $\ell_1$-norm, the existence of $O(\sqrt{T\log d})$-regret algorithms for learning with experts implies that it is possible to obtain $\epsilon$-calibrated forecasts after $T = \exp(O(\log{d}/\epsilon^2)) = d^{O(1/\epsilon^2)}$ rounds, recovering a recent result of Peng (2025). Interestingly, our algorithm obtains this guarantee without requiring access to any online linear optimization subroutine or knowledge of the optimal rate $\rho$ -- in fact, our algorithm is identical for every setting of $\mathcal{P}$ and $\Vert \cdot \Vert$. Instead, we show that the optimal regularizer for the above OLO problem can be used to upper bound the above calibration error by a swap regret, which we then minimize by running the recent TreeSwap algorithm with Follow-The-Leader as a subroutine. Finally, we prove that any online calibration algorithm that guarantees $\epsilon T$ $\ell_1$-calibration error over the $d$-dimensional simplex requires $T \geq \exp(\mathrm{poly}(1/\epsilon))$ (assuming $d \geq \mathrm{poly}(1/\epsilon)$). This strengthens the corresponding $d^{\Omega(\log{1/\epsilon})}$ lower bound of Peng, and shows that an exponential dependence on $1/\epsilon$ is necessary.
Abstract（参考訳）: 任意のノルム $\Vert\cdot\Vert$ に対して、任意の凸集合 $\mathcal{P} \subset \mathbb{R}^d$ 上の多次元予測のオンライン校正について検討する。このことはオンライン線形最適化における外部後悔最小化の問題と結びつき、$O(\sqrt{\rho T})$$$$T$ラウンド後の最悪の後悔が$\mathcal{P}$から引き出され、double $\Vert \cdot \Vert_*$ユニットノルムボールから損失が引き出される場合、$T = \exp(O(\rho /\epsilon^2))$ラウンド後に$\epsilon$-calibrated予測を得ることもできることを示す。 $\mathcal{P}$が$d$-dimensional simplexで$\Vert \cdot \Vert$が$\ell_1$-normであるとき、エキスパートと学習するための$O(\sqrt{T\log d})$-regretアルゴリズムの存在は、$T = \exp(O(\log{d}/\epsilon^2) = d^{O(1/\epsilon^2)} の後に$\epsilon$-calibrated予測を得られることを示唆している。興味深いことに、我々のアルゴリズムは、オンライン線形最適化サブルーチンへのアクセスや最適なレートの知識を必要とせずに、この保証を得る。代わりに、上述のOLO問題に対する最適正則化器を用いて、スワップリフレクションにより上述のキャリブレーション誤差を上限にすることができることを示し、Follow-The-Leaderをサブルーチンとして、最近のTreeSwapアルゴリズムを実行することにより、最小化することができる。最後に、$\epsilon T$ $\ell_1$-calibration error over the $d$-dimensional simplex requires $T \geq \exp(\mathrm{poly}(1/\epsilon))$ ($d \geq \mathrm{poly}(1/\epsilon)$)。これは対応する$d^{\Omega(\log{1/\epsilon})}$ Peng の下位境界を強化し、$/\epsilon$ への指数的依存が必要であることを示す。

論文の概要: High-Dimensional Calibration from Swap Regret

関連論文リスト