論文の概要: Generalization error of random features and kernel methods:
hypercontractivity and kernel matrix concentration
- arxiv url: http://arxiv.org/abs/2101.10588v1
- Date: Tue, 26 Jan 2021 06:46:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-13 19:37:58.244915
- Title: Generalization error of random features and kernel methods:
hypercontractivity and kernel matrix concentration
- Title（参考訳）: ランダムな特徴とカーネル手法の一般化誤差:超収縮性とカーネルマトリックス濃度
- Authors: Song Mei, Theodor Misiakiewicz, Andrea Montanari
- Abstract要約: 特徴空間 $mathbb RN$ におけるリッジ回帰と併用したランダム特徴量法の利用について検討する。
これは、カーネルリッジ回帰(KRR)の有限次元近似、またはいわゆる遅延訓練体制におけるニューラルネットワークの様式化されたモデルと見なすことができる。
- 参考スコア（独自算出の注目度）: 19.78800773518545
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the classical supervised learning problem: we are given data
$(y_i,{\boldsymbol x}_i)$, $i\le n$, with $y_i$ a response and ${\boldsymbol
x}_i\in {\mathcal X}$ a covariates vector, and try to learn a model
$f:{\mathcal X}\to{\mathbb R}$ to predict future responses. Random features
methods map the covariates vector ${\boldsymbol x}_i$ to a point ${\boldsymbol
\phi}({\boldsymbol x}_i)$ in a higher dimensional space ${\mathbb R}^N$, via a
random featurization map ${\boldsymbol \phi}$. We study the use of random
features methods in conjunction with ridge regression in the feature space
${\mathbb R}^N$. This can be viewed as a finite-dimensional approximation of
kernel ridge regression (KRR), or as a stylized model for neural networks in
the so called lazy training regime.
We define a class of problems satisfying certain spectral conditions on the
underlying kernels, and a hypercontractivity assumption on the associated
eigenfunctions. These conditions are verified by classical high-dimensional
examples. Under these conditions, we prove a sharp characterization of the
error of random features ridge regression. In particular, we address two
fundamental questions: $(1)$~What is the generalization error of KRR? $(2)$~How
big $N$ should be for the random features approximation to achieve the same
error as KRR?
In this setting, we prove that KRR is well approximated by a projection onto
the top $\ell$ eigenfunctions of the kernel, where $\ell$ depends on the sample
size $n$. We show that the test error of random features ridge regression is
dominated by its approximation error and is larger than the error of KRR as
long as $N\le n^{1-\delta}$ for some $\delta>0$. We characterize this gap. For
$N\ge n^{1+\delta}$, random features achieve the same error as the
corresponding KRR, and further increasing $N$ does not lead to a significant
change in test error.
- Abstract（参考訳）: y_i,{\boldsymbol x}_i)$, $i\le n$, with $y_i$ a response and ${\boldsymbol x}_i\in {\mathcal x}$ a covariates vector, and try to learn a model $f:{\mathcal x}\to{\mathbb r}$ to predict future response. と題された。
ランダムの特徴は、共変ベクトル ${\boldsymbol x}_i$ を高次元空間 ${\mathbb R}^N$ 上の点 ${\boldsymbol \phi}({\boldsymbol x}_i)$ に写すことである。
本研究では,特徴空間 ${\mathbb r}^n$ におけるリッジ回帰を伴うランダム特徴法の利用について検討する。
これは、カーネルリッジ回帰(KRR)の有限次元近似、またはいわゆる遅延訓練体制におけるニューラルネットワークの様式化されたモデルと見なすことができる。
基底核上の特定のスペクトル条件を満たす問題のクラスと、関連する固有関数に対する超収縮仮定を定義する。
これらの条件は古典的な高次元の例によって検証される。
これらの条件下では,ランダム特徴のリッジ回帰の誤差を鋭く評価する。
特に、2つの基本的な問題に対処する:$(1)$~KRRの一般化誤差は何か?
$(2)$~KRRと同じエラーを達成するためにランダムな機能近似には、どのくらい大きな$N$が必要ですか?
この設定では、KRR がカーネルのトップ $\ell$ 固有関数への射影によってよく近似されることを証明し、$\ell$ はサンプルサイズ $n$ に依存する。
ランダムな特徴のリッジ回帰のテスト誤差は近似誤差によって支配され、ある $\delta>0$ に対して $N\le n^{1-\delta}$ であれば KRR の誤差よりも大きいことを示す。
このギャップを特徴付ける。
N の n^{1+\delta}$ の場合、ランダムな特徴は対応する KRR と同じ誤差を達成し、さらに$N$ の増加はテストエラーに大きな変化をもたらすことはない。
関連論文リスト
- Asymptotics of Random Feature Regression Beyond the Linear Scaling
Regime [22.666759017118796]
機械学習の最近の進歩は、トレーニングデータの近くにトレーニングされた過度にパラメータ化されたモデルを使用することによって達成されている。
モデル複雑性と一般化はパラメータ数$p$にどのように依存するか?
特に、RFRRは近似と一般化パワーの直感的なトレードオフを示す。
論文 参考訳（メタデータ） (2024-03-13T00:59:25Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Optimal Rates of Kernel Ridge Regression under Source Condition in Large
Dimensions [15.988264513040903]
そこで,カーネルリッジ回帰 (KRR) の大規模挙動について検討し,サンプルサイズ$n asymp dgamma$ for some $gamma > 0$について検討した。
以上の結果から,ガンマ$で変動する速度曲線は周期的台地挙動と多重降下挙動を示すことが明らかとなった。
論文 参考訳（メタデータ） (2024-01-02T16:14:35Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture
Models [12.746888269949407]
2進隠れマルコフモデルに対する高次元平均推定問題を考える。
ほぼ最小限の誤差率(対数係数まで)を $|theta_*|,delta,d,n$ の関数として確立する。
論文 参考訳（メタデータ） (2022-06-06T09:34:04Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Universality of empirical risk minimization [12.764655736673749]
例えば、$boldsymbol x_i inmathbbRp$ が特徴ベクトルで $y in mathbbR$ がラベルであるような i.d. サンプルからの教師付き学習を考える。
我々は$mathsfkによってパラメータ化される関数のクラスに対する経験的リスク普遍性について研究する。
論文 参考訳（メタデータ） (2022-02-17T18:53:45Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。