論文の概要: Learning the mapping $\mathbf{x}\mapsto \sum_{i=1}^d x_i^2$: the cost of
finding the needle in a haystack
- arxiv url: http://arxiv.org/abs/2002.10561v2
- Date: Sat, 16 May 2020 21:14:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 03:37:09.569398
- Title: Learning the mapping $\mathbf{x}\mapsto \sum_{i=1}^d x_i^2$: the cost of
finding the needle in a haystack
- Title（参考訳）: 写像 {\mathbf{x}\mapsto \sum_{i=1}^d x_i^2$: 干し草の山で針を見つけるコスト
- Authors: Jiefu Zhang, Leonardo Zepeda-N\'u\~nez, Yuan Yao, Lin Lin
- Abstract要約: 干し草の山で針を見つけるコストは,その関数のバロンノルムと関係があることが示される。
一般化ギャップのサイズを制御するために、d$が増加するにつれて、明示的な正規化の使用がますます重要になる。
- 参考スコア（独自算出の注目度）: 6.436049723896002
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The task of using machine learning to approximate the mapping
$\mathbf{x}\mapsto\sum_{i=1}^d x_i^2$ with $x_i\in[-1,1]$ seems to be a trivial
one. Given the knowledge of the separable structure of the function, one can
design a sparse network to represent the function very accurately, or even
exactly. When such structural information is not available, and we may only use
a dense neural network, the optimization procedure to find the sparse network
embedded in the dense network is similar to finding the needle in a haystack,
using a given number of samples of the function. We demonstrate that the cost
(measured by sample complexity) of finding the needle is directly related to
the Barron norm of the function. While only a small number of samples is needed
to train a sparse network, the dense network trained with the same number of
samples exhibits large test loss and a large generalization gap. In order to
control the size of the generalization gap, we find that the use of explicit
regularization becomes increasingly more important as $d$ increases. The
numerically observed sample complexity with explicit regularization scales as
$\mathcal{O}(d^{2.5})$, which is in fact better than the theoretically
predicted sample complexity that scales as $\mathcal{O}(d^{4})$. Without
explicit regularization (also called implicit regularization), the numerically
observed sample complexity is significantly higher and is close to
$\mathcal{O}(d^{4.5})$.
- Abstract（参考訳）: 機械学習を用いてマッピングを近似するタスク $\mathbf{x}\mapsto\sum_{i=1}^d x_i^2$ with $x_i\in[-1,1]$ は自明なものであるようだ。
関数の分離可能な構造に関する知識を考えると、関数を非常に正確に、あるいは正確に表現するためのスパースネットワークを設計することができる。
このような構造情報が得られず、高密度ニューラルネットワークのみを使用する場合、高密度ネットワークに埋め込まれたスパースネットワークを見つけるための最適化手順は、関数の所定の数のサンプルを使用して、干し草スタック内の針を見つけるのと似ている。
針を見つけるコスト(サンプルの複雑さによって測定される)が関数のバロンノルムと直接関係があることを実証する。
スパースネットワークのトレーニングには少数のサンプルしか必要ではないが、同じ数のサンプルでトレーニングされた密集したネットワークは、大きなテスト損失と大きな一般化ギャップを示す。
一般化ギャップの大きさを制御するために、明示的な正規化の使用は、$d$が増加するにつれてますます重要になる。
数値的に観察されたサンプル複雑性と明示的な正則化のスケールは$\mathcal{O}(d^{2.5})$であり、実際には$\mathcal{O}(d^{4})$としてスケールする理論上予測されたサンプル複雑性よりも優れている。
明示的な正規化(暗黙的正規化とも呼ばれる)がなければ、数値的に観測されるサンプルの複雑性は著しく高く、$\mathcal{o}(d^{4.5})$に近い。
関連論文リスト
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。
適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文 参考訳（メタデータ） (2024-11-08T17:10:38Z) - Optimal Sample Complexity of Contrastive Learning [12.108926584457736]
比較学習の複雑さ、すなわち、高い精度を得るのに十分なラベル付き一般化の最小数について研究する。
我々は、任意の距離関数に焦点をあてて、様々な設定でサンプルの複雑さに厳密な境界を与える。
本稿では,VC/ナタラジャンによる試料の複雑さに関する理論的境界が,実験結果に強い予測力を持つことを示す。
論文 参考訳（メタデータ） (2023-12-01T06:57:11Z) - 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Is Stochastic Gradient Descent Near Optimal? [0.0]
本研究では,多数のサンプルとクエリの総数を用いて,勾配勾配勾配の誤差が小さいことを示す。
このことは、SGDがJoen & Van Roy (arXiv:2203.00246) の情報理論的なサンプル複雑性境界を計算的に効率よく達成していることを示唆している。
論文 参考訳（メタデータ） (2022-09-18T18:26:43Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - Why Are Convolutional Nets More Sample-Efficient than Fully-Connected
Nets? [33.51250867983687]
標準学習アルゴリズムにおいて、証明可能なサンプル複雑性のギャップを示すことができる自然なタスクを示す。
単一の対象関数を示し、可能なすべての分布について、$O(1)$対$Omega(d2/varepsilon)$ギャップを学習する。
同様の結果が$ell$回帰およびAdamやAdaGradといった適応型トレーニングアルゴリズムに対して達成される。
論文 参考訳（メタデータ） (2020-10-16T17:15:39Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。