論文の概要: Agnostically Learning Multi-index Models with Queries
- arxiv url: http://arxiv.org/abs/2312.16616v1
- Date: Wed, 27 Dec 2023 15:50:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-29 18:41:21.375836
- Title: Agnostically Learning Multi-index Models with Queries
- Title（参考訳）: クエリによる複数インデックスモデルの自動学習
- Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos,
Nikos Zarifis
- Abstract要約: 本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
- 参考スコア（独自算出の注目度）: 54.290489524576756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the power of query access for the task of agnostic learning under
the Gaussian distribution. In the agnostic model, no assumptions are made on
the labels and the goal is to compute a hypothesis that is competitive with the
{\em best-fit} function in a known class, i.e., it achieves error
$\mathrm{opt}+\epsilon$, where $\mathrm{opt}$ is the error of the best function
in the class. We focus on a general family of Multi-Index Models (MIMs), which
are $d$-variate functions that depend only on few relevant directions, i.e.,
have the form $g(\mathbf{W} \mathbf{x})$ for an unknown link function $g$ and a
$k \times d$ matrix $\mathbf{W}$. Multi-index models cover a wide range of
commonly studied function classes, including constant-depth neural networks
with ReLU activations, and intersections of halfspaces.
Our main result shows that query access gives significant runtime
improvements over random examples for agnostically learning MIMs. Under
standard regularity assumptions for the link function (namely, bounded
variation or surface area), we give an agnostic query learner for MIMs with
complexity $O(k)^{\mathrm{poly}(1/\epsilon)} \; \mathrm{poly}(d) $. In
contrast, algorithms that rely only on random examples inherently require
$d^{\mathrm{poly}(1/\epsilon)}$ samples and runtime, even for the basic problem
of agnostically learning a single ReLU or a halfspace.
Our algorithmic result establishes a strong computational separation between
the agnostic PAC and the agnostic PAC+Query models under the Gaussian
distribution. Prior to our work, no such separation was known -- even for the
special case of agnostically learning a single halfspace, for which it was an
open problem first posed by Feldman. Our results are enabled by a general
dimension-reduction technique that leverages query access to estimate gradients
of (a smoothed version of) the underlying label function.
- Abstract（参考訳）: ガウス分布下での非依存学習課題に対するクエリアクセスのパワーについて検討する。
不可知モデルでは、ラベルの仮定は行われず、既知のクラスにおける {\em best-fit} 関数と競合する仮説を計算すること、すなわち、エラー $\mathrm{opt}+\epsilon$ を達成すること、すなわち、$\mathrm{opt}$ はクラス内の最良関数の誤差である。
例えば、未知リンク関数 $g$ と a $k \times d$ matrix $\mathbf{W}$ に対して $g(\mathbf{W} \mathbf{x})$ という形式を持つ。
マルチインデックスモデルは、ReLUアクティベーションを持つ定数深度ニューラルネットワークやハーフスペースの交叉など、広く研究されている関数クラスをカバーする。
我々の主な結果は、クエリアクセスは、MIMを不可知的に学習するランダムな例よりも大幅に実行時の改善をもたらすことを示している。
リンク関数の標準的な正則性仮定(つまり、有界変動や表面積)の下では、複雑性が$O(k)^{\mathrm{poly}(1/\epsilon)} \; \mathrm{poly}(d) $ のMIMに対して非依存的なクエリ学習を行う。
対照的に、ランダムな例のみに依存するアルゴリズムは、単一のReLUまたはハーフスペースを不可知的に学習する基本的な問題であっても、$d^{\mathrm{poly}(1/\epsilon)}$サンプルとランタイムを必要とする。
アルゴリズムの結果, ガウス分布下でのpacとpac+queryモデルとの強い計算的分離が確立された。
私たちの研究以前には、そのような分離は知られていなかった -- 単一のハーフスペースを不可知的に学習する特別なケースであっても。
その結果,基礎となるラベル関数の勾配(平滑化バージョン)を推定するために,問合せアクセスを利用する一般次元推論手法が有効となった。
関連論文リスト
- Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。
2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
論文 参考訳（メタデータ） (2024-06-17T17:59:17Z) - Agnostic Active Learning of Single Index Models with Linear Sample Complexity [27.065175036001246]
F(mathbf x) = f(langle mathbf w, mathbf xrangle)$。
論文 参考訳（メタデータ） (2024-05-15T13:11:28Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。
実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
論文 参考訳（メタデータ） (2020-06-29T05:15:32Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。