論文の概要: 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パラメータの変化だけで実データセット上で観測できることを示す。

関連論文リスト

• Recovering Manifold Structure Using Ollivier-Ricci Curvature [1.9458156037869137]
  我々は、Ollivier-Ricci曲率と推定距離歪みに基づく基準を用いて、隣り合うグラフからスプリアスエッジをプルーする新しいアルゴリズムであるORC-ManLを紹介する。 我々のモチベーションは多様体学習から来ており、最も近い近傍グラフを生成するデータが低次元多様体からのノイズのあるサンプルで構成されている場合、周辺空間をショートカットするエッジは、データ多様体に沿って配置されるエッジよりも負のオリヴィエ・リッチ曲率を持つことを示す。
  論文  参考訳（メタデータ） (2024-10-02T01:00:30Z)
• Entrywise Inference for Missing Panel Data: A Simple and Instance-Optimal Approach [27.301741710016223]
  停滞した採用によって引き起こされたパネルデータの欠落データバージョンに関連する推論的疑問を考察する。 我々は、予め特定されたカバレッジでエントリワイドな信頼区間を構築するためのデータ駆動方式を開発し、分析する。 我々は、欠落したエントリを推定する際に、そのエラーに非漸近的かつ高い確率境界を証明した。
  論文  参考訳（メタデータ） (2024-01-24T18:58:18Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。