論文の概要: Near-Optimal Algorithms for Omniprediction

• arxiv url: http://arxiv.org/abs/2501.17205v1
• Date: Tue, 28 Jan 2025 02:58:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-30 22:32:42.436019
• Title: Near-Optimal Algorithms for Omniprediction
• Title（参考訳）: Omniprediction の近似アルゴリズム
• Authors: Princewill Okoroafor, Robert Kleinberg, Michael P. Kim,
• Abstract要約: Omnipredictors は損失最小化予測を仮説クラス $H$ にエンコードする。 オンライン設定とオフライン設定の両方で、オムニプレディションのためのほぼ最適学習アルゴリズムを提供します。
• 参考スコア（独自算出の注目度）: 6.874077229518565
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class $\H$, simultaneously for every loss function within a class of losses $\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 $(\L,\H)$-omniprediction with $\tilde{O}(\sqrt{T \log |\H|})$ regret for any class of Lipschitz loss functions $\L \subseteq \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 $\L_\mathrm{BV}$ (which include all convex, all Lipschitz, and all proper losses) and any (possibly-infinite) $\H$, we obtain an offline learning algorithm that, leveraging an (offline) ERM oracle and $m$ samples from $\D$, returns an efficient $(\L_{\mathrm{BV}},\H,\eps(m))$-omnipredictor for $\eps(m)$ scaling near-linearly in the Rademacher complexity of $\mathrm{Th} \circ \H$.
• Abstract（参考訳）: Omnipredictors は、損失最小化予測を仮説クラス $\H$ にエンコードする単純な予測関数である。 本研究では,オンライン設定とオフライン設定の両方において,オムニプレディクションのための準最適学習アルゴリズムを提案する。 まず、Lipschitz の損失関数のクラスに対して $(\L,\H)$-omniprediction with $\tilde{O}(\sqrt{T \log |\H|})$ regret for any class of Lipschitz loss function $\L \subseteq \L_\mathrm{Lip}$。 驚くべきことに、この後悔は単一損失関数の \emph{minimization of a single loss function} (最大$\sqrt{\log(T)}$ factor に対する最適の後悔と一致する。 このオンラインアルゴリズムを前提として,多くの尺度でほぼ最適な複雑性を実現するオンライン・オフライン変換を開発した。 特に、境界変動のクラス内のすべての有界損失関数に対して、$\L_\mathrm{BV}$(すべての凸、すべてのリプシッツ、および全ての適切な損失を含む)と$\H$は、(オフラインの)ERMオラクルと$m$サンプルを$$D$から活用して、効率的な$(\L_{\mathrm{BV}},\H,\eps(m)$-omnipredictor for $\eps(m)$をラドマチャー複雑性のほぼ直線的にスケーリングするオフライン学習アルゴリズムを得る。

関連論文リスト

• 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)
• Full Swap Regret and Discretized Calibration [18.944031222413294]
  構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。 我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
  論文  参考訳（メタデータ） (2025-02-13T13:49:52Z)
• 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 $(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)
• Online Learning with Bounded Recall [11.046741824529107]
  本研究では,繰り返しゲーム研究に人気がある「バウンド・リコール」環境において,オンライン学習の完全情報化の課題について検討する。 オンライン学習アルゴリズム $mathcalA$ が$M$-$textitbounded-recall$ であるとき、$t$ の出力が$M$以前の報酬の関数として記述できる。
  論文  参考訳（メタデータ） (2022-05-28T20:52:52Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• 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)
• Adaptive Online Learning with Varying Norms [45.11667443216861]
  オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。 この結果を用いて新しい「完全行列」型後悔境界を得る。
  論文  参考訳（メタデータ） (2020-02-10T17:22:08Z)

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

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