論文の概要: Near-Optimal Algorithms for Omniprediction
- arxiv url: http://arxiv.org/abs/2501.17205v2
- Date: Thu, 30 Jan 2025 01:45:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-31 11:53:03.869686
- Title: Near-Optimal Algorithms for Omniprediction
- Title（参考訳）: Omniprediction の近似アルゴリズム
- Authors: Princewill Okoroafor, Robert Kleinberg, Michael P. Kim,
- Abstract要約: オンライン設定とオフライン設定の両方で、オムニプレディションのためのほぼ最適学習アルゴリズムを提供します。
オンライン学習アルゴリズムは、様々な尺度でほぼ最適な複雑さを実現する。
オフライン学習アルゴリズムは効率的な$(mathcalL_mathrmBV,mathcalH,varepsilon(m)$)を返す
- 参考スコア（独自算出の注目度）: 6.874077229518565
- License:
- Abstract: Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class $\mathcal{H}$, simultaneously for every loss function within a class of losses $\mathcal{L}$. In this work, we give near-optimal learning algorithms for omniprediction, in both the online and offline settings. To begin, we give an oracle-efficient online learning algorithm that acheives $(\mathcal{L},\mathcal{H})$-omniprediction with $\tilde{O}(\sqrt{T \log |\mathcal{H}|})$ regret for any class of Lipschitz loss functions $\mathcal{L} \subseteq \mathcal{L}_\mathrm{Lip}$. Quite surprisingly, this regret bound matches the optimal regret for \emph{minimization of a single loss function} (up to a $\sqrt{\log(T)}$ factor). Given this online algorithm, we develop an online-to-offline conversion that achieves near-optimal complexity across a number of measures. In particular, for all bounded loss functions within the class of Bounded Variation losses $\mathcal{L}_\mathrm{BV}$ (which include all convex, all Lipschitz, and all proper losses) and any (possibly-infinite) $\mathcal{H}$, we obtain an offline learning algorithm that, leveraging an (offline) ERM oracle and $m$ samples from $\mathcal{D}$, returns an efficient $(\mathcal{L}_{\mathrm{BV}},\mathcal{H},\varepsilon(m))$-omnipredictor for $\varepsilon(m)$ scaling near-linearly in the Rademacher complexity of $\mathrm{Th} \circ \mathcal{H}$.
- Abstract（参考訳）: Omnipredictors は、損失最小化予測を仮説クラス $\mathcal{H}$ にエンコードする単純な予測関数である。
本研究では,オンライン設定とオフライン設定の両方において,オムニプレディクションのための準最適学習アルゴリズムを提案する。
まずは、99(\mathcal{L},\mathcal{H})$-omniprediction with $\tilde{O}(\sqrt{T \log |\mathcal{H}|})$ regret for any class of Lipschitz loss function $\mathcal{L} \subseteq \mathcal{L}_\mathrm{Lip}$とする。
驚くべきことに、この後悔は単一損失関数の \emph{minimization of a single loss function} (最大$\sqrt{\log(T)}$ factor に対する最適の後悔と一致する。
このオンラインアルゴリズムを前提として,多くの尺度でほぼ最適な複雑性を実現するオンライン・オフライン変換を開発した。
特に、境界変動のクラス内のすべての有界損失関数に対して、$\mathcal{L}_\mathrm{BV}$(すべての凸、すべてのリプシッツ、および全ての適切な損失を含む)と$\mathcal{H}$(英語版)は、オフライン学習アルゴリズムを取得し、$\mathcal{D}$から(オフライン) ERM oracleと$m$のサンプルを利用して、効率の良い$(\mathcal{L}_{\mathrm{BV}},\mathcal{H},\varepsilon(m))$-omnipredictor for $\varepsilon(m)$$=\mathrm \circal{H}$(英語版)$(英語版)$(英語版)$-omnipredictor for $\varepsilon(m)$(英語版)$(英語版)$(英語版) $\mathcal{H}$(英語版)$(英語版)$(英語版)$(英語版)$(オフライン学習アルゴリズムを得る。
関連論文リスト
- Full Swap Regret and Discretized Calibration [18.944031222413294]
構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。
我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する
また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
論文 参考訳（メタデータ） (2025-02-13T13:49:52Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using
Online Function Approximation [47.18926328995424]
我々は,敵対的文脈 MDP における後悔最小化のためのOMG-CMDP!アルゴリズムを提案する。
我々のアルゴリズムは効率的であり(効率的なオンライン回帰オラクルを仮定する)、近似誤差に対して単純で堅牢である。
論文 参考訳（メタデータ） (2023-03-02T18:27:00Z) - Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。
我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
論文 参考訳（メタデータ） (2022-11-27T20:38:47Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳（メタデータ） (2022-10-06T06:49:48Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - 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) - Phase Transitions in Rate Distortion Theory and Deep Learning [5.145741425164946]
もし$mathcalS$をエンコードするために$mathcalO(R-s)$のエラーを達成できれば、$mathcalS$は$s$で圧縮できると言う。
ある"ニッチ"信号クラスに対して、$mathcalS$が相転移を起こすことを示す。
論文 参考訳（メタデータ） (2020-08-03T16:48:49Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。