論文の概要: Accumulations of Projections--A Unified Framework for Random Sketches in Kernel Ridge Regression

• arxiv url: http://arxiv.org/abs/2103.04031v1
• Date: Sat, 6 Mar 2021 05:02:17 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-09 15:50:56.393020
• Title: Accumulations of Projections--A Unified Framework for Random Sketches in Kernel Ridge Regression
• Title（参考訳）: 投影の蓄積--カーネルリッジ回帰におけるランダムスケッチの統一的枠組み
• Authors: Yifan Chen, Yun Yang
• Abstract要約: n-by-n 経験的カーネル行列のスケッチを構築することは、多くのカーネルメソッドの計算を加速するための一般的なアプローチである。 カーネルリッジ回帰におけるスケッチ手法を構築するための統一フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 12.258887270632869
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Building a sketch of an n-by-n empirical kernel matrix is a common approach to accelerate the computation of many kernel methods. In this paper, we propose a unified framework of constructing sketching methods in kernel ridge regression (KRR), which views the sketching matrix S as an accumulation of m rescaled sub-sampling matrices with independent columns. Our framework incorporates two commonly used sketching methods, sub-sampling sketches (known as the Nystr\"om method) and sub-Gaussian sketches, as special cases with m=1 and m=infinity respectively. Under the new framework, we provide a unified error analysis of sketching approximation and show that our accumulation scheme improves the low accuracy of sub-sampling sketches when certain incoherence characteristic is high, and accelerates the more accurate but computationally heavier sub-Gaussian sketches. By optimally choosing the number m of accumulations, we show that a best trade-off between computational efficiency and statistical accuracy can be achieved. In practice, the sketching method can be as efficiently implemented as the sub-sampling sketches, as only minor extra matrix additions are needed. Our empirical evaluations also demonstrate that the proposed method may attain the accuracy close to sub-Gaussian sketches, while is as efficient as sub-sampling-based sketches.
• Abstract（参考訳）: n-by-n 経験的カーネル行列のスケッチを構築することは、多くのカーネルメソッドの計算を加速するための一般的なアプローチである。 本稿では, スケッチ行列 s を独立列を持つ m 再スケールされた部分サンプリング行列の蓄積と見なすkernel ridge regression (krr) において, スケッチ法を構築するための統一的な枠組みを提案する。 本手法は, m=1 と m=infinity の特殊ケースとして, サブサンプリングスケッチ (nystr\"om 法) とサブガウススケッチ (sub-gaussian sketches) の2つの手法を組み込んでいる。 新たな枠組みでは,スケッチ近似の統一誤差解析を行い,特定の非一貫性特性が高い場合のサブサンプリングスケッチの精度を低下させ,より正確だが計算量の多いサブガウススケッチを高速化することを示す。 累積数 m を最適に選択することにより,計算効率と統計精度の最良のトレードオフが達成できることを示す。 実際、スケッチはサブサンプリングのスケッチと同等に効率的に実装できるが、追加のマトリックスの追加は必要である。 実験により,提案手法はガウス以下のスケッチに近い精度を達成できるが,サブサンプリングに基づくスケッチと同じくらい効率がよいことを示す。

関連論文リスト

• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  emphdone right -- 最適化とカーネルコミュニティからの具体的な洞察を使用するという意味で -- が、勾配降下は非常に効果的であることを示している。 本稿では,直感的に設計を記述し,設計選択について説明する。 本手法は,分子結合親和性予測のための最先端グラフニューラルネットワークと同程度にガウス過程の回帰を配置する。
  論文  参考訳（メタデータ） (2023-10-31T16:15:13Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs [22.925108493465363]
  平均化によるデータ分布のガウシアン化のためのアルゴリズムフレームワークを提供する。 我々は、ガウス以下のランダムな設計とほとんど区別できないデータスケッチを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2022-06-21T12:16:45Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。 学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-02-24T14:50:59Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。 従来のスケッチ手法に対する新しい近似保証を導出し、分散スケッチにおけるパラメータ平均化の精度を解析する。 大規模実験によるサーバレスコンピューティングプラットフォームにおける分散スケッチのパフォーマンスについて説明する。
  論文  参考訳（メタデータ） (2020-02-16T08:35:48Z)

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

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