論文の概要: Minimum complexity interpolation in random features models
- arxiv url: http://arxiv.org/abs/2103.15996v1
- Date: Tue, 30 Mar 2021 00:00:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-31 15:07:00.979917
- Title: Minimum complexity interpolation in random features models
- Title(参考訳): ランダム特徴モデルにおける最小複雑性補間
- Authors: Michael Celentano, Theodor Misiakiewicz, Andrea Montanari
- Abstract要約: カーネルメソッドは 次元の呪いの影響を強く受けています
我々は,$mathcalF_p$ノルムを用いた学習が無限次元凸問題において抽出可能であることを示す。
双対における一様濃度に基づく証明手法を提案する。
- 参考スコア(独自算出の注目度): 16.823029377470366
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite their many appealing properties, kernel methods are heavily affected
by the curse of dimensionality. For instance, in the case of inner product
kernels in $\mathbb{R}^d$, the Reproducing Kernel Hilbert Space (RKHS) norm is
often very large for functions that depend strongly on a small subset of
directions (ridge functions). Correspondingly, such functions are difficult to
learn using kernel methods.
This observation has motivated the study of generalizations of kernel
methods, whereby the RKHS norm -- which is equivalent to a weighted $\ell_2$
norm -- is replaced by a weighted functional $\ell_p$ norm, which we refer to
as $\mathcal{F}_p$ norm. Unfortunately, tractability of these approaches is
unclear. The kernel trick is not available and minimizing these norms requires
to solve an infinite-dimensional convex problem.
We study random features approximations to these norms and show that, for
$p>1$, the number of random features required to approximate the original
learning problem is upper bounded by a polynomial in the sample size. Hence,
learning with $\mathcal{F}_p$ norms is tractable in these cases. We introduce a
proof technique based on uniform concentration in the dual, which can be of
broader interest in the study of overparametrized models.
- Abstract(参考訳): 多くの魅力的な性質にもかかわらず、カーネルメソッドは次元性の呪いの影響を強く受けている。
例えば、$\mathbb{r}^d$ の内部積核の場合、再生成核ヒルベルト空間(英語版)(rkhs)ノルムは、方向の小さな部分集合(リッジ関数)に強く依存する函数に対して非常に大きい。
それに対応して、そのような関数はカーネルメソッドを使って学習するのは難しい。
この観察は、カーネルメソッドの一般化の研究を動機付けており、RKHSノルムは重み付き$\ell_2$ノルムと等価であり、重み付き函数 $\ell_p$ノルムに置き換えられ、$\mathcal{F}_p$ノルムと呼ばれる。
残念ながら、これらのアプローチのトラクタビリティは不明確である。
カーネルトリックは利用できず、これらのノルムを最小化するには無限次元凸問題を解く必要がある。
本研究では,これらのノルムに対するランダムな特徴の近似について検討し,$p>1$の場合,元の学習問題を近似するために必要なランダムな特徴の数は,サンプルサイズの多項式によって上限づけられていることを示す。
したがって、これらの場合、$\mathcal{f}_p$ ノルムで学習することは扱いやすい。
双対における一様濃度に基づく証明手法を導入し、過度なパラメータ化モデルの研究に広く関心を持つことができる。
関連論文リスト
- The $L^\infty$ Learnability of Reproducing Kernel Hilbert Spaces [3.2931415075553576]
カーネル空間の学習可能性(RKHS)を$Linfty$ノルムで解析する。
球面上のドット積核に対しては、ヒルベルトサンプルを用いて$Linfty$学習が達成できる条件を特定する。
論文 参考訳(メタデータ) (2023-06-05T12:29:13Z) - A duality framework for generalization analysis of random feature models
and two-layer neural networks [3.2931415075553576]
我々は$mathcalF_p,pi$およびBarron空間における関数の学習問題を考察する。
双対性解析により、これらの空間の近似と推定は、ある意味で等価であると考えることができる。
論文 参考訳(メタデータ) (2023-05-09T17:41:50Z) - Toward $L_\infty$-recovery of Nonlinear Functions: A Polynomial Sample
Complexity Bound for Gaussian Random Fields [35.76184529520015]
多くの機械学習アプリケーションは、入力ドメイン全体、すなわち$L_infty$-errorで最小ケースエラーの関数を学習する必要がある。
既存の理論的研究の多くは、$L$-errorのような平均エラーの回復を保証するだけである。
本稿では, 地絡関数のランダム性を生かして, 不合理性以外のいくつかの初期ステップについて述べる。
論文 参考訳(メタデータ) (2023-04-29T18:33:39Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳(メタデータ) (2023-02-03T03:19:14Z) - Learning Globally Smooth Functions on Manifolds [94.22412028413102]
スムーズな関数の学習は、線形モデルやカーネルモデルなどの単純なケースを除いて、一般的に難しい。
本研究は,半無限制約学習と多様体正規化の技法を組み合わせることで,これらの障害を克服することを提案する。
軽度条件下では、この手法は解のリプシッツ定数を推定し、副生成物として大域的に滑らかな解を学ぶ。
論文 参考訳(メタデータ) (2022-10-01T15:45:35Z) - Deformed semicircle law and concentration of nonlinear random matrices
for ultra-wide neural networks [29.03095282348978]
本稿では、$f(X)$に付随する2つの経験的カーネル行列のスペクトル分布の制限について検討する。
経験的カーネルによって誘導されるランダムな特徴回帰は、超広範体制下でのカーネル回帰の制限と同じ性能を達成することを示す。
論文 参考訳(メタデータ) (2021-09-20T05:25:52Z) - Feature Cross Search via Submodular Optimization [58.15569071608769]
機能工学の基本的な基礎として機能横断探索について研究する。
この問題に対して単純なgreedy $(1-1/e)$-approximationアルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2021-07-05T16:58:31Z) - High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。
最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
論文 参考訳(メタデータ) (2021-02-15T13:24:41Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z) - 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) - RFN: A Random-Feature Based Newton Method for Empirical Risk
Minimization in Reproducing Kernel Hilbert Spaces [14.924672048447334]
大規模な有限サム問題はニュートン法の効率的な変種を用いて解くことができ、ヘッセンはデータのサブサンプルによって近似される。
本稿では,このような問題に対して,ニュートン法を高速化するためにカーネル近似を自然に利用できることを考察する。
局所超線型収束と大域線形収束を両立させる新しい2次アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-12T01:14:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。