論文の概要: Kernel approximation on algebraic varieties
- arxiv url: http://arxiv.org/abs/2106.02755v1
- Date: Fri, 4 Jun 2021 23:42:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 17:26:08.432603
- Title: Kernel approximation on algebraic varieties
- Title(参考訳): 代数多様体上のカーネル近似
- Authors: Jason M. Altschuler and Pablo A. Parrilo
- Abstract要約: スパースデータやローランクデータにまつわる問題において, より優れた近似が得られることを示す。
この結果は、アプリケーションで使用されるカーネルの主要なクラスであるスムーズな等方性カーネルに対して提示される。
- 参考スコア(独自算出の注目度): 0.7614628596146599
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Low-rank approximation of kernels is a fundamental mathematical problem with
widespread algorithmic applications. Often the kernel is restricted to an
algebraic variety, e.g., in problems involving sparse or low-rank data. We show
that significantly better approximations are obtainable in this setting: the
rank required to achieve a given error depends on the variety's dimension
rather than the ambient dimension, which is typically much larger. This is true
in both high-precision and high-dimensional regimes. Our results are presented
for smooth isotropic kernels, the predominant class of kernels used in
applications. Our main technical insight is to approximate smooth kernels by
polynomial kernels, and leverage two key properties of polynomial kernels that
hold when they are restricted to a variety. First, their ranks decrease
exponentially in the variety's co-dimension. Second, their maximum values are
governed by their values over a small set of points. Together, our results
provide a general approach for exploiting (approximate) "algebraic structure"
in datasets in order to efficiently solve large-scale data science problems.
- Abstract(参考訳): カーネルの低ランク近似はアルゴリズム応用における基本的な数学的問題である。
しばしばカーネルは代数多様体(例えば、スパースデータやローランクデータを含む問題)に制限される。
与えられた誤差を達成するのに必要なランクは、通常より大きい周囲の次元ではなく、多様体の次元に依存する。
これは、高精度と高次元のレギュレーションの両方において当てはまる。
本研究は,アプリケーションで使用される主要なカーネル群である滑らかな等方性カーネルについて述べる。
我々の主要な技術的洞察は、多項式カーネルによって滑らかなカーネルを近似し、それらに制限されたときに保持される多項式カーネルの2つのキー特性を活用することである。
まず、それらのランクは品種の共次元において指数関数的に減少する。
第二に、それらの最大値は小さな点からなる値によって支配される。
その結果,大規模データサイエンスの問題を効率的に解決するために,データセットの「代数的構造」を活用(近似)するための一般的なアプローチが得られた。
関連論文リスト
- The phase diagram of kernel interpolation in large dimensions [8.707305374058794]
大きな次元におけるカーネルの一般化能力は、最近のカーネル回帰のルネサンスにおいて、最も興味深い問題の1つかもしれない。
各種ソース条件$sgeq 0$において,大次元カーネルの偏差と偏差の正確な順序を完全に特徴づけた。
我々は、カーネルが極小最適、準最適、矛盾する$(s,gamma)$-planeの領域を決定した。
論文 参考訳(メタデータ) (2024-04-19T03:04:06Z) - On the Approximation of Kernel functions [0.0]
論文はカーネル自体の近似に対処する。
単位立方体上のヒルベルト・ガウス核に対して、この論文は関連する固有関数の上界を確立する。
この改良により、Nystr"om法のような低階近似法が確かめられる。
論文 参考訳(メタデータ) (2024-03-11T13:50:07Z) - Reconstructing Kernel-based Machine Learning Force Fields with
Super-linear Convergence [0.18416014644193063]
我々は、プレコンディショナーを構築するためのNystr"om-typeメソッドの幅広いクラスについて考察する。
検討されたすべての方法は、支配的なカーネルスペクトルを近似するために、インジェクション(カーネル)列の代表的なサブセットを特定することを目的としている。
論文 参考訳(メタデータ) (2022-12-24T13:45:50Z) - Interpolation with the polynomial kernels [5.8720142291102135]
カーネルは機械学習で広く使われており、カーネルベースの回帰モデルを開発するためのデフォルトの選択肢の1つである。
厳密な正定性がないため、数値解析ではほとんど使われない。
本論文は,これらのカーネルとその関連アルゴリズムの研究において,いくつかの初期結果を確立することを目的としている。
論文 参考訳(メタデータ) (2022-12-15T08:30:23Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。
分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
論文 参考訳(メタデータ) (2022-02-28T13:01:04Z) - Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。
スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。
我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
論文 参考訳(メタデータ) (2021-08-21T02:14:55Z) - How rotational invariance of common kernels prevents generalization in
high dimensions [8.508198765617196]
カーネルリッジ回帰は、低次元設定で最小の最適速度を達成するためによく知られている。
最近の研究は、基底真理関数と入力データの分布を仮定して、カーネル回帰の整合性を確立する。
論文 参考訳(メタデータ) (2021-04-09T08:27:37Z) - Random Features for the Neural Tangent Kernel [57.132634274795066]
完全接続型ReLUネットワークのニューラルタンジェントカーネル(NTK)の効率的な特徴マップ構築を提案する。
得られた特徴の次元は、理論と実践の両方で比較誤差境界を達成するために、他のベースライン特徴マップ構造よりもはるかに小さいことを示しています。
論文 参考訳(メタデータ) (2021-04-03T09:08:12Z) - High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。
最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
論文 参考訳(メタデータ) (2021-02-15T13:24:41Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
論文 参考訳(メタデータ) (2020-02-21T00:43:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。