論文の概要: Omnipredicting Single-Index Models with Multi-Index Models

• arxiv url: http://arxiv.org/abs/2411.13083v1
• Date: Wed, 20 Nov 2024 07:20:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-21 16:12:53.790170
• Title: Omnipredicting Single-Index Models with Multi-Index Models
• Title（参考訳）: 複数インデックスモデルによる単一インデックスモデルの予測
• Authors: Lunjia Hu, Kevin Tian, Chutong Yang,
• Abstract要約: 単調なリプシッツリンク関数によって引き起こされる任意の損失に対して、$varepsilon$-competitive であるオムニプレクタを出力する学習者を与える。 我々のアルゴリズムでは,$approx varepsilon-4$サンプルをほぼ線形時間で実行し,リンク関数がbi-Lipschitzであれば$approx varepsilon-2$に改善する。
• 参考スコア（独自算出の注目度）: 9.794426212144453
• License:
• Abstract: Recent work on supervised learning [GKR+22] defined the notion of omnipredictors, i.e., predictor functions $p$ over features that are simultaneously competitive for minimizing a family of loss functions $\mathcal{L}$ against a comparator class $\mathcal{C}$. Omniprediction requires approximating the Bayes-optimal predictor beyond the loss minimization paradigm, and has generated significant interest in the learning theory community. However, even for basic settings such as agnostically learning single-index models (SIMs), existing omnipredictor constructions require impractically-large sample complexities and runtimes, and output complex, highly-improper hypotheses. Our main contribution is a new, simple construction of omnipredictors for SIMs. We give a learner outputting an omnipredictor that is $\varepsilon$-competitive on any matching loss induced by a monotone, Lipschitz link function, when the comparator class is bounded linear predictors. Our algorithm requires $\approx \varepsilon^{-4}$ samples and runs in nearly-linear time, and its sample complexity improves to $\approx \varepsilon^{-2}$ if link functions are bi-Lipschitz. This significantly improves upon the only prior known construction, due to [HJKRR18, GHK+23], which used $\gtrsim \varepsilon^{-10}$ samples. We achieve our construction via a new, sharp analysis of the classical Isotron algorithm [KS09, KKKS11] in the challenging agnostic learning setting, of potential independent interest. Previously, Isotron was known to properly learn SIMs in the realizable setting, as well as constant-factor competitive hypotheses under the squared loss [ZWDD24]. As they are based on Isotron, our omnipredictors are multi-index models with $\approx \varepsilon^{-2}$ prediction heads, bringing us closer to the tantalizing goal of proper omniprediction for general loss families and comparators.
• Abstract（参考訳）: 教師付き学習 [GKR+22] に関する最近の研究は、オムニプレクタの概念、すなわち、損失関数の族である$\mathcal{L}$を、コンパレータクラス$\mathcal{C}$に対して最小化するために同時に競合する機能に対して$p$という予測関数を定義している。 Omniprediction は損失最小化パラダイムを超えてベイズ最適予測器を近似する必要がある。 しかしながら、単一のインデックスモデル(SIM)を不可知的に学習するといった基本的な設定であっても、既存の全予測構造は、急激に大きいサンプルの複雑さと実行時間を必要とし、複雑な高不適切な仮説を出力する必要がある。 私たちの主な貢献は、SIM用のOmnipredictorを新しく、シンプルに構築することである。 コンパレータクラスが有界線形予測器であるとき、単調リプシッツリンク関数によって誘導される任意の整合損失に対して$\varepsilon$-competitiveのオムニ予測器を出力する。 我々のアルゴリズムは、$\approx \varepsilon^{-4}$サンプルをほぼ直線的に実行し、リンク関数がbi-Lipschitzであれば、そのサンプルの複雑さは$\approx \varepsilon^{-2}$に改善される。 これは、$\gtrsim \varepsilon^{-10}$サンプルを使用した[HJKRR18, GHK+23]のため、既知の唯一の構造よりも大幅に改善されている。 我々は,従来のアイソトロンアルゴリズム[KS09, KKKS11]を,潜在的な独立性のある学習環境において,新しい鋭い解析によって構築する。 以前は、Isotronは、実現可能な環境でSIMを適切に学習し、二乗損失(ZWDD24)の下で一定の要素の競合仮説を学習することが知られていた。 それらはアイソトロンをベースとしており、我々のOmnipredictorは$\approx \varepsilon^{-2}$予測ヘッドを持つマルチインデックスモデルであり、一般の損失族やコンパレータに対する適切なOmnipredictionという具体的な目標に近づいている。

関連論文リスト

• Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
  本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。 ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。 Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
  論文  参考訳（メタデータ） (2024-10-10T06:33:41Z)
• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
  教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。 学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。 時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-01T04:58:36Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Agnostically Learning Single-Index Models using Omnipredictors [15.36798336447733]
  任意のモノトーンとリプシッツのアクティベーションを持つSIM(Single-Index Models)を不可知的に学習する最初の結果を与える。 また、GLMtronのような標準アルゴリズムと非依存設定におけるロジスティック回帰の新しい保証も提供する。
  論文  参考訳（メタデータ） (2023-06-18T18:40:07Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。 計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
  論文  参考訳（メタデータ） (2021-02-12T14:22:05Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
  我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。 実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
  論文  参考訳（メタデータ） (2020-06-29T05:15:32Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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