論文の概要: Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method
- arxiv url: http://arxiv.org/abs/2002.09073v3
- Date: Fri, 18 Dec 2020 21:19:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 00:34:22.429879
- Title: Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method
- Title(参考訳): Column Subset Selection と Nystr\"om 法における改善された保証と多重差分曲線
- Authors: Micha{\l} Derezi\'nski, Rajiv Khanna and Michael W. Mahoney
- Abstract要約: 我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
- 参考スコア(独自算出の注目度): 76.73096213472897
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Column Subset Selection Problem (CSSP) and the Nystr\"om method are among
the leading tools for constructing small low-rank approximations of large
datasets in machine learning and scientific computing. A fundamental question
in this area is: how well can a data subset of size k compete with the best
rank k approximation? We develop techniques which exploit spectral properties
of the data matrix to obtain improved approximation guarantees which go beyond
the standard worst-case analysis. Our approach leads to significantly better
bounds for datasets with known rates of singular value decay, e.g., polynomial
or exponential decay. Our analysis also reveals an intriguing phenomenon: the
approximation factor as a function of k may exhibit multiple peaks and valleys,
which we call a multiple-descent curve. A lower bound we establish shows that
this behavior is not an artifact of our analysis, but rather it is an inherent
property of the CSSP and Nystr\"om tasks. Finally, using the example of a
radial basis function (RBF) kernel, we show that both our improved bounds and
the multiple-descent curve can be observed on real datasets simply by varying
the RBF parameter.
- Abstract(参考訳): Column Subset Selection Problem (CSSP) と Nystr\"om method は、機械学習と科学計算における大規模データセットの小さな低ランク近似を構築するための主要なツールの一つである。
この領域の根本的な疑問は、サイズ k のデータのサブセットが最高ランク k の近似とどの程度うまく競合できるか、ということです。
我々は,データマトリックスのスペクトル特性を利用して,標準的な最悪の解析以上の近似保証を得る手法を開発した。
このアプローチは、特異値減衰率(例えば多項式または指数的崩壊)の既知のデータセットの境界を著しく改善する。
k の関数としての近似係数は、複数のピークと谷を呈しうるが、これは多重輝線曲線(multi-descent curve)と呼ばれる。
下限では、この振る舞いは分析の成果物ではなく、csspとnystr\"omタスクに固有の特性であることが示されています。
最後に、放射基底関数(RBF)カーネルの例を用いて、改良された境界線と多重発散曲線の両方を、RBFパラメータの変化だけで実データセット上で観測できることを示す。
関連論文リスト
- On the Size and Approximation Error of Distilled Sets [57.61696480305911]
カーネル・インジェクション・ポイント(Kernel Inducing Points)などのデータセット蒸留のカーネル・リッジ回帰に基づく手法について理論的に考察する。
我々は、RFF空間におけるその解が元のデータの解と一致するように、元の入力空間に小さな一組のインスタンスが存在することを証明した。
KRR溶液は、全入力データに最適化されたKRR溶液に対して近似を与えるこの蒸留されたインスタンスセットを用いて生成することができる。
論文 参考訳(メタデータ) (2023-05-23T14:37:43Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳(メタデータ) (2023-05-22T17:43:34Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Local Random Feature Approximations of the Gaussian Kernel [14.230653042112834]
本稿では,一般的なガウスカーネルと,ランダムな特徴近似を用いてカーネルベースモデルを線形化する手法に着目する。
このような手法は、高周波データをモデル化する際、悪い結果をもたらすことを示すとともに、カーネル近似と下流性能を大幅に改善する新たなローカライズ手法を提案する。
論文 参考訳(メタデータ) (2022-04-12T09:52:36Z) - Spectrahedral Regression [7.2361978133966165]
入力-出力ペアからなるデータセットに凸関数を適合させる問題に対する新しいアプローチを提案する。
統計的リスク統計解析の凸関数を近似できることを示す。
本研究では, 経済工学設計などの応用における実データだけでなく, 合成データセットの実験によるアプローチを実証する。
論文 参考訳(メタデータ) (2021-10-27T21:21:19Z) - Kernel k-Means, By All Means: Algorithms and Strong Consistency [21.013169939337583]
Kernel $k$クラスタリングは、非線形データの教師なし学習のための強力なツールである。
本稿では,最適化された局所解に対処するための一般的な手法を応用した結果を一般化する。
我々のアルゴリズムは、この非線形分離問題をよりよく解くために、Magricalization-minimization (MM) を利用している。
論文 参考訳(メタデータ) (2020-11-12T16:07:18Z) - Tight Nonparametric Convergence Rates for Stochastic Gradient Descent
under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。
特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文 参考訳(メタデータ) (2020-06-15T08:25:50Z) - Bayesian Sparse Factor Analysis with Kernelized Observations [67.60224656603823]
多視点問題は潜在変数モデルに直面することができる。
高次元問題と非線形問題は伝統的にカーネルメソッドによって扱われる。
両アプローチを単一モデルにマージすることを提案する。
論文 参考訳(メタデータ) (2020-06-01T14:25:38Z) - SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for
Gaussian Process Regression with Derivatives [86.01677297601624]
本稿では,2次フーリエ特徴に基づく導関数によるGP回帰のスケーリング手法を提案する。
我々は、近似されたカーネルと近似された後部の両方に適用される決定論的、非漸近的、指数関数的に高速な崩壊誤差境界を証明した。
論文 参考訳(メタデータ) (2020-03-05T14:33:20Z) - Diversity sampling is an implicit regularization for kernel methods [13.136143245702915]
多様なランドマークを持つNystrのカーネルレグレッションにより,データセットのスペーサー領域におけるレグレッションの精度が向上することを示す。
正確な DPP サンプリングが現実的に実現不可能な場合, 大規模なデータセット内で大きなサイズのサンプルを選択するために, グリーディも提案されている。
論文 参考訳(メタデータ) (2020-02-20T08:24:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。