論文の概要: How isotropic kernels perform on simple invariants
- arxiv url: http://arxiv.org/abs/2006.09754v5
- Date: Mon, 14 Dec 2020 20:20:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 20:17:33.772725
- Title: How isotropic kernels perform on simple invariants
- Title(参考訳): 単純不変量上での等方核の作用
- Authors: Jonas Paccolat, Stefano Spigler and Matthieu Wyart
- Abstract要約: 等方性カーネル手法のトレーニング曲線は、学習すべきタスクの対称性に依存するかを検討する。
大規模な帯域幅では、$beta = fracd-1+xi3d-3+xi$, where $xiin (0,2)$ がカーネルのストライプを原点とする指数であることを示す。
- 参考スコア(独自算出の注目度): 0.5729426778193397
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate how the training curve of isotropic kernel methods depends on
the symmetry of the task to be learned, in several settings. (i) We consider a
regression task, where the target function is a Gaussian random field that
depends only on $d_\parallel$ variables, fewer than the input dimension $d$. We
compute the expected test error $\epsilon$ that follows $\epsilon\sim
p^{-\beta}$ where $p$ is the size of the training set. We find that $\beta\sim
1/d$ independently of $d_\parallel$, supporting previous findings that the
presence of invariants does not resolve the curse of dimensionality for kernel
regression. (ii) Next we consider support-vector binary classification and
introduce the stripe model where the data label depends on a single coordinate
$y(\underline{x}) = y(x_1)$, corresponding to parallel decision boundaries
separating labels of different signs, and consider that there is no margin at
these interfaces. We argue and confirm numerically that for large bandwidth,
$\beta = \frac{d-1+\xi}{3d-3+\xi}$, where $\xi\in (0,2)$ is the exponent
characterizing the singularity of the kernel at the origin. This estimation
improves classical bounds obtainable from Rademacher complexity. In this
setting there is no curse of dimensionality since $\beta\rightarrow 1 / 3$ as
$d\rightarrow\infty$. (iii) We confirm these findings for the spherical model
for which $y(\underline{x}) = y(|\underline{x}|)$. (iv) In the stripe model, we
show that if the data are compressed along their invariants by some factor
$\lambda$ (an operation believed to take place in deep networks), the test
error is reduced by a factor $\lambda^{-\frac{2(d-1)}{3d-3+\xi}}$.
- Abstract(参考訳): 等方性カーネル手法のトレーニング曲線は,学習すべきタスクの対称性にどのように依存するかを,いくつかの設定で検討する。
(i)対象関数が、入力次元$d$よりも少ない$d_\parallel$変数のみに依存するガウス確率場である回帰タスクを考える。
期待されるテストエラー $\epsilon$ は、トレーニングセットのサイズである$\epsilon\sim p^{-\beta}$ に従って計算する。
我々は$\beta\sim 1/d$が$d_\parallel$とは独立であることに気付き、不変量の存在はカーネル回帰に対する次元性の呪いを解決しないという以前の知見を支持する。
(ii)次に、サポートベクトルのバイナリ分類を検討し、データラベルが単一の座標 $y(\underline{x}) = y(x_1)$ に依存するstripeモデルを導入する。
大帯域では、$\beta = \frac{d-1+\xi}{3d-3+\xi}$, ここで$\xi\in (0,2)$は核の特異点を特徴付ける指数である。
この推定はラデマッハ複雑性から得られる古典境界を改善する。
この設定では、$\beta\rightarrow 1 / 3$ as $d\rightarrow\infty$ から次元性の呪いはない。
(iii)これらの結果は、$y(\underline{x}) = y(|\underline{x}|)$ の球面モデルに対して確認される。
(iv) ストライプモデルでは、ある係数$\lambda$(ディープネットワークで発生すると思われる演算)によってデータが不変量に沿って圧縮された場合、テストエラーは$\lambda^{-\frac{2(d-1)}{3d-3+\xi}}$で減少する。
関連論文リスト
- A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
一対のランダムグラフにおける相関性の検出は、近年広く研究されている基本的な統計的および計算上の問題である。
一対の相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ からサブサンプリングする。
隣接部のエントリーのエンスロー度に基づくテストに焦点をあてる
論文 参考訳(メタデータ) (2024-09-02T06:14:05Z) - 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) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳(メタデータ) (2022-05-06T19:24:44Z) - 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) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳(メタデータ) (2021-01-29T18:57:52Z) - Geometric compression of invariant manifolds in neural nets [2.461575510055098]
ニューラルネットワークは、データが$d$次元にあるモデルにおいて、不定形入力空間をいかに圧縮するかを研究する。
勾配勾配勾配で訓練された一重層FCネットワークの場合、第一重みの層は、$d_perp=d-d_parallel$非形式的方向に対してほとんど無関心になる。
次に、圧縮がニューラルカーネル(NTK)の進化を経時的に形作っていることを示し、その最上位の固有ベクトルがより情報的になり、ラベルにより大きな投影を表示する。
論文 参考訳(メタデータ) (2020-07-22T14:43:49Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。