論文の概要: Spectrum of inner-product kernel matrices in the polynomial regime and
multiple descent phenomenon in kernel ridge regression
- arxiv url: http://arxiv.org/abs/2204.10425v1
- Date: Thu, 21 Apr 2022 22:20:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-25 14:16:39.357482
- Title: Spectrum of inner-product kernel matrices in the polynomial regime and
multiple descent phenomenon in kernel ridge regression
- Title（参考訳）: 多項式状態における内積核行列のスペクトルとカーネルリッジ回帰における多重降下現象
- Authors: Theodor Misiakiewicz
- Abstract要約: カーネル行列はその次数-$ell$近似によってよく近似される。
行列のスペクトルが分布に収束することを示す。
- 参考スコア（独自算出の注目度）: 3.997680012976965
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the spectrum of inner-product kernel matrices, i.e., $n \times n$
matrices with entries $h (\langle \textbf{x}_i ,\textbf{x}_j \rangle/d)$ where
the $( \textbf{x}_i)_{i \leq n}$ are i.i.d.~random covariates in
$\mathbb{R}^d$. In the linear high-dimensional regime $n \asymp d$, it was
shown that these matrices are well approximated by their linearization, which
simplifies into the sum of a rescaled Wishart matrix and identity matrix. In
this paper, we generalize this decomposition to the polynomial high-dimensional
regime $n \asymp d^\ell,\ell \in \mathbb{N}$, for data uniformly distributed on
the sphere and hypercube. In this regime, the kernel matrix is well
approximated by its degree-$\ell$ polynomial approximation and can be
decomposed into a low-rank spike matrix, identity and a `Gegenbauer matrix'
with entries $Q_\ell (\langle \textbf{x}_i , \textbf{x}_j \rangle)$, where
$Q_\ell$ is the degree-$\ell$ Gegenbauer polynomial. We show that the spectrum
of the Gegenbauer matrix converges in distribution to a Marchenko-Pastur law.
This problem is motivated by the study of the prediction error of kernel
ridge regression (KRR) in the polynomial regime $n \asymp d^\kappa, \kappa >0$.
Previous work showed that for $\kappa \not\in \mathbb{N}$, KRR fits exactly a
degree-$\lfloor \kappa \rfloor$ polynomial approximation to the target
function. In this paper, we use our characterization of the kernel matrix to
complete this picture and compute the precise asymptotics of the test error in
the limit $n/d^\kappa \to \psi$ with $\kappa \in \mathbb{N}$. In this case, the
test error can present a double descent behavior, depending on the effective
regularization and signal-to-noise ratio at level $\kappa$. Because this double
descent can occur each time $\kappa$ crosses an integer, this explains the
multiple descent phenomenon in the KRR risk curve observed in several previous
works.
- Abstract（参考訳）: 内積核行列のスペクトル、すなわち、h (\langle \textbf{x}_i ,\textbf{x}_j \rangle/d)$ ここで、$( \textbf{x}_i)_{i \leq n}$ は i.i.d.~random covariates in $\mathbb{r}^d$ である。
線形高次元レジーム $n \asymp d$ において、これらの行列は線形化によってよく近似され、再スケールされたウィッシュアート行列と恒等行列の和に単純化されることを示した。
本稿では,この分解を,球面と超キューブ上に一様分布するデータに対して,多項式高次元レジーム $n \asymp d^\ell,\ell \in \mathbb{n}$ に一般化する。
この方法では、カーネル行列は次数-$\ell$多項式近似によりよく近似され、単位元は低ランクのスパイク行列に分解され、エントリ $q_\ell (\langle \textbf{x}_i , \textbf{x}_j \rangle)$ を持つ 'gegenbauer matrix' となる。
ゲゲンバウアー行列のスペクトルは分布的にマルケンコ・パストゥル則に収束することを示した。
この問題は、多項式状態 $n \asymp d^\kappa, \kappa > 0$ におけるカーネルリッジ回帰(KRR)の予測誤差の研究によって動機付けられる。
以前の研究は、$\kappa \not\in \mathbb{N}$に対して、KRR はちょうど次数-$\lfloor \kappa \rfloor$多項式近似を対象関数に適合させることを示した。
本稿では,核行列のキャラクタリゼーションを用いてこの図を完結させ,極限 $n/d^\kappa \to \psi$ と $\kappa \in \mathbb{n}$ におけるテスト誤差の正確な漸近値を計算する。
この場合、テストエラーは、レベル$\kappa$の効果的な正規化と信号対雑音比に依存する二重降下挙動を示すことができる。
この二重降下は$\kappa$が整数を渡るたびに起こるので、これは以前のいくつかの研究で観察されたKRRリスク曲線における多重降下現象を説明する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Universality for the global spectrum of random inner-product kernel
matrices in the polynomial regime [12.221087476416056]
本稿では、この現象が普遍であることを示し、X$がすべての有限モーメントを持つi.d.エントリを持つとすぐに保持する。
非整数$ell$の場合、Marvcenko-Pastur項は消滅する。
論文 参考訳（メタデータ） (2023-10-27T17:15:55Z) - Data-Driven Linear Complexity Low-Rank Approximation of General Kernel
Matrices: A Geometric Approach [0.9453554184019107]
K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ はカーネル関数である。
我々は、点の集合 X$ と $Y$ が大きいカーネル行列に対する低ランク近似を求める。
論文 参考訳（メタデータ） (2022-12-24T07:15:00Z) - 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) - Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics [8.90202564665576]
一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。
3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
論文 参考訳（メタデータ） (2022-03-19T07:26:45Z) - On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of
$\mathbb{R}^N$ with Boundary [0.4125187280299246]
mathbbRm × N$ のランダム行列 $A がバイリプシッツ函数 $A: MathcalM rightarrow mathbbRm$ とビリプシッツ定数が 1 に近い確率を考える。
我々は、$mathbbRN$ の十分低次元部分多様体を埋め込むための、高度に構造化された分布の新しいクラスを示す。
論文 参考訳（メタデータ） (2021-10-08T15:27:52Z) - 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) - Two-way kernel matrix puncturing: towards resource-efficient PCA and
spectral clustering [43.50783459690612]
この方法は、データマトリックス$XinmathbbCptimes n$と対応するカーネル(Gram)マトリックス$K$の両方をBernoulliマスクを介してランダムに「切断」する。
我々は、GAN生成した画像データベースを実証的に確認し、データを劇的にパンクし、巨大な計算とストレージのゲインを提供することができることを確認した。
論文 参考訳（メタデータ） (2021-02-24T14:01:58Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。