論文の概要: An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$-Regret Minimization

• arxiv url: http://arxiv.org/abs/2604.19592v1
• Date: Tue, 21 Apr 2026 15:43:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-22 22:41:49.852085
• Title: An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$-Regret Minimization
• Title（参考訳）: オンライン学習からマルチ校正への効率的なブラックボックス削減と$$$-regret最小化への新たな道
• Authors: Gabriele Farina, Juan Carlos Perdomo,
• Abstract要約: オンライン学習からオンラインマルチ校正まで,GGM(Gordon-Greenwald-Marks)スタイルのブラックボックスを削減した。 その結果,H 上の非regret学習者と予測変分不等式解法を組み合わせれば十分であることがわかった。 また、効率的なマルチキャリブレーションは効率的なEVI解決を意味することを示す。
• 参考スコア（独自算出の注目度）: 32.283056647528845
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a Gordon-Greenwald-Marks (GGM) style black-box reduction from online learning to online multicalibration. Concretely, we show that to achieve high-dimensional multicalibration with respect to a class of functions H, it suffices to combine any no-regret learner over H with an expected variational inequality (EVI) solver. We also prove a converse statement showing that efficient multicalibration implies efficient EVI solving, highlighting how EVIs in multicalibration mirror the role of fixed points in the GGM result for $Φ$-regret. This first set of results resolves the main open question in Garg, Jung, Reingold, and Roth (SODA '24), showing that oracle-efficient online multicalibration with $\sqrt{T}$-type guarantees is possible in full generality. Furthermore, our GGM-style reduction unifies the analyses of existing online multicalibration algorithms, enables new algorithms for challenging environments with delayed observations or censored outcomes, and yields the first efficient black-box reduction between online learning and multiclass omniprediction. Our second main result is a fine-grained reduction from high-dimensional online multicalibration to (contextual) $Φ$-regret minimization. Together with our first result, this establishes a new route from external regret to Phi-regret that bypasses sophisticated fixed-point or semi-separation machinery, dramatically simplifies a result of Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '25) while improving rates, and yields new algorithms that are robust to richer deviation classes, such as those belonging to any reproducing kernel Hilbert space.
• Abstract（参考訳）: オンライン学習からオンラインマルチ校正まで,GGM(Gordon-Greenwald-Marks)スタイルのブラックボックスを削減した。 具体的には,関数 H のクラスに対して高次元多重校正を実現するためには,H 上の任意の非regret 学習者と予測変分不等式(EVI)解決者を組み合わせるのに十分であることを示す。 また、効率的なマルチキャリブレーションが効率的なEVI解決を意味することを示す逆言を証明し、マルチキャリブレーションにおけるEVIがGGM結果における固定点の役割を$$$-regretでどのように反映しているかを強調した。 この最初の一連の結果は、Garg, Jung, Reingold, and Roth (SODA '24) における主要な開問題(英語版)を解決し、総じて$\sqrt{T}$型保証によるオラクル効率の良いオンライン多重校正が可能であることを示す。 さらに、GGMスタイルの削減は、既存のオンラインマルチキャリブレーションアルゴリズムの分析を統一し、遅延観測や検閲結果のある環境に挑戦するための新しいアルゴリズムを可能にし、オンライン学習とマルチクラスオムニプレディションの間の最初の効率的なブラックボックス削減をもたらす。 2つ目の結果は、高次元オンラインマルチキャリブレーションから(文脈的に)$$$-regret最小化へのきめ細かい縮小である。 最初の結果と合わせて、Phi-regretへの外部後悔から、洗練された固定点または半分離機械をバイパスし、ダスカラキス、ファリーナ、フィッシュルソン、ピピス、シュナイダー(STOC '25)の結果を劇的に単純化し、レートを改善しつつ、再生されたカーネルヒルベルト空間に属するようなよりリッチな偏差クラスに頑健な新しいアルゴリズムを生成する新しい経路を確立する。

関連論文リスト

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Universal Online Convex Optimization with $1$ Projection per Round [31.16522982351235]
  我々は,複数種類の凸関数に対して同時にミニマックスレートを得るユニバーサルアルゴリズムを開発した。 我々は、単純なドメイン上で定義された代理損失を用いて、1ドルのプロジェクションしか必要としない普遍的なOCOアルゴリズムを開発する。 我々の分析は、サロゲート損失に新たな光を当て、元の損失の後悔とサロゲート損失の相違点の厳密な検証を容易にする。
  論文  参考訳（メタデータ） (2024-05-30T05:29:40Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)

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

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