論文の概要: Improved and Oracle-Efficient Online $\ell_1$-Multicalibration

• arxiv url: http://arxiv.org/abs/2505.17365v1
• Date: Fri, 23 May 2025 00:37:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:33.749782
• Title: Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
• Title（参考訳）: 改善されたOracle効率のオンライン$\ell_1$-Multicalibration
• Authors: Rohan Ghuge, Vidya Muthukumar, Sahil Singla,
• Abstract要約: 本研究では,複数のグループにまたがるキャリブレーション予測を行うフレームワークであるエンフォリン・マルチキャリブレーションについて検討する。 そこで本研究では,$widetildemathcalO(T-1/4)$を改良し,オラクル効率を向上する手法を提案する。 我々のフレームワークは、(ell_H)-multicalibration誤差の1ドルLipschitz特性を利用して、ある無限群の族にも拡張する。
• 参考スコア（独自算出の注目度）: 14.147331133778916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study \emph{online multicalibration}, a framework for ensuring calibrated predictions across multiple groups in adversarial settings, across $T$ rounds. Although online calibration is typically studied in the $\ell_1$ norm, prior approaches to online multicalibration have taken the indirect approach of obtaining rates in other norms (such as $\ell_2$ and $\ell_{\infty}$) and then transferred these guarantees to $\ell_1$ at additional loss. In contrast, we propose a direct method that achieves improved and oracle-efficient rates of $\widetilde{\mathcal{O}}(T^{-1/3})$ and $\widetilde{\mathcal{O}}(T^{-1/4})$ respectively, for online $\ell_1$-multicalibration. Our key insight is a novel reduction of online \(\ell_1\)-multicalibration to an online learning problem with product-based rewards, which we refer to as \emph{online linear-product optimization} ($\mathtt{OLPO}$). To obtain the improved rate of $\widetilde{\mathcal{O}}(T^{-1/3})$, we introduce a linearization of $\mathtt{OLPO}$ and design a no-regret algorithm for this linearized problem. Although this method guarantees the desired sublinear rate (nearly matching the best rate for online calibration), it becomes computationally expensive when the group family \(\mathcal{H}\) is large or infinite, since it enumerates all possible groups. To address scalability, we propose a second approach to $\mathtt{OLPO}$ that makes only a polynomial number of calls to an offline optimization (\emph{multicalibration evaluation}) oracle, resulting in \emph{oracle-efficient} online \(\ell_1\)-multicalibration with a rate of $\widetilde{\mathcal{O}}(T^{-1/4})$. Our framework also extends to certain infinite families of groups (e.g., all linear functions on the context space) by exploiting a $1$-Lipschitz property of the \(\ell_1\)-multicalibration error with respect to \(\mathcal{H}\).
• Abstract（参考訳）: 本研究は,複数グループにまたがる校正予測をT$ラウンドで保証するフレームワークであるemph{online multicalibrationについて検討する。 オンライン校正は、通常$\ell_1$ノルムで研究されるが、オンライン多重校正の以前のアプローチは、他のノルム(例えば$\ell_2$や$\ell_{\infty}$)で利率を得るという間接的なアプローチを取っており、さらに損失がある場合は$\ell_1$に移行している。 対照的に、オンラインの$\ell_1$-multicalibrationに対して、$\widetilde{\mathcal{O}}(T^{-1/3})$と$\widetilde{\mathcal{O}}(T^{-1/4})$の改善とオラクル効率の向上を達成する直接的な方法を提案する。 我々の重要な洞察は、オンラインの \(\ell_1\)-multicalibration を、製品ベースの報酬を伴うオンライン学習問題に還元することである。 改良された$\widetilde{\mathcal{O}}(T^{-1/3})$を得るために、$\mathtt{OLPO}$の線形化を導入し、この線形化問題に対する非回帰アルゴリズムを設計する。 この方法では、所望のサブリニアレート(オンラインキャリブレーションの最良のレートにほぼ一致する)を保証するが、すべての可能な群を列挙するので、群族 \(\mathcal{H}\) が大きいか無限であるときに計算コストがかかる。 スケーラビリティに対処するために、$\mathtt{OLPO}$に対する2番目のアプローチを提案し、これはオフライン最適化(\emph{multicalibration evaluation})またはoracleに対して1つの多項式数しか呼ばないようにし、その結果、$\widetilde{\mathcal{O}}(T^{-1/4})$で \emph{oracle-efficient} オンライン \(\ell_1\)-multicalibration となる。 我々のフレームワークはまた、ある無限個の群の族(例えば、文脈空間上のすべての線型函数)にも拡張し、 \(\mathcal{H}\) に関する \(\ell_1\)-乗算誤差の 1$-Lipschitz 特性を利用する。

関連論文リスト

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
  現在のメソッドは、$mathcalO(n3)$または$mathcalO(n2)$スペースの複雑さでグラフカーネルランタイムマトリックスを反転させるか、ランダムなスパンニングツリーを大量にサンプリングする。 本稿では,一連の研究によって導入されたテクスチトリン緩和技術に基づく改善を提案する。
  論文  参考訳（メタデータ） (2023-05-25T17:13:08Z)
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
  VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。 そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:29:14Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Fast and Near-Optimal Diagonal Preconditioning [46.240079312553796]
  左か右の対角線再スケーリングにより$mathbfA$の条件数を改善する方法を示す。 構造化混合パッキングと半定値プログラムを対象とし,$widetildeO(textnnz(mathbfA) cdot textpoly(kappastar))$ timeに対して,$mathbfA$の定数係数最適スケーリングを計算する。
  論文  参考訳（メタデータ） (2020-08-04T17:53:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。