論文の概要: On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling

• arxiv url: http://arxiv.org/abs/2103.11107v1
• Date: Sat, 20 Mar 2021 06:07:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-26 04:46:25.429715
• Title: On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling
• Title（参考訳）: MCMCサンプリングによる低域通過における部分空間近似とサブセット選択について
• Authors: Amit Deshpande and Rameshwar Pratap
• Abstract要約: サンプリングベースのサブセット選択技術は、データに複数のパスを持つ適応的なサンプリングイテレーションを必要とする。 従来のサブセット選択アルゴリズムで必要となるパス数を削減するMCMCアルゴリズムを提案する。 このアルゴリズムは$mathrmpoly(k/epsilon)$のサブセットを選び、最適部分空間に$(1+epsilon)$近似を与えます。
• 参考スコア（独自算出の注目度）: 3.1822873305165618
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of subset selection for $\ell_{p}$ subspace approximation, i.e., given $n$ points in $d$ dimensions, we need to pick a small, representative subset of the given points such that its span gives $(1+\epsilon)$ approximation to the best $k$-dimensional subspace that minimizes the sum of $p$-th powers of distances of all the points to this subspace. Sampling-based subset selection techniques require adaptive sampling iterations with multiple passes over the data. Matrix sketching techniques give a single-pass $(1+\epsilon)$ approximation for $\ell_{p}$ subspace approximation but require additional passes for subset selection. In this work, we propose an MCMC algorithm to reduce the number of passes required by previous subset selection algorithms based on adaptive sampling. For $p=2$, our algorithm gives subset selection of nearly optimal size in only $2$ passes, whereas the number of passes required in previous work depend on $k$. Our algorithm picks a subset of size $\mathrm{poly}(k/\epsilon)$ that gives $(1+\epsilon)$ approximation to the optimal subspace. The running time of the algorithm is $nd + d~\mathrm{poly}(k/\epsilon)$. We extend our results to the case when outliers are present in the datasets, and suggest a two pass algorithm for the same. Our ideas also extend to give a reduction in the number of passes required by adaptive sampling algorithms for $\ell_{p}$ subspace approximation and subset selection, for $p \geq 2$.
• Abstract（参考訳）: 我々は、$\ell_{p}$ 部分空間近似に対する部分集合選択の問題、すなわち$d$次元の$n$ポイントが与えられたとき、そのスパンが$(1+\epsilon)$ 最高の$k$次元部分空間への近似が、この部分空間へのすべての点の距離の合計の$p$-次元パワーの和を最小化するような、与えられた点の小さい代表部分集合を選ぶ必要がある。 サンプリングベースのサブセット選択技術は、データに複数のパスを持つ適応的なサンプリングイテレーションを必要とする。 行列スケッチ技術は、単パス$(1+\epsilon)$ approximation for $\ell_{p}$ subspace approximationを与えるが、サブセット選択のために追加のパスを必要とする。 本研究では,アダプティブサンプリングに基づいて,前回のサブセット選択アルゴリズムで要求されるパス数を削減するMCMCアルゴリズムを提案する。 p=2$の場合、アルゴリズムは2ドルのパスでほぼ最適サイズのサブセット選択を与えるが、以前の作業で必要とされるパス数は$k$に依存する。 このアルゴリズムは、最適な部分空間に対して$(1+\epsilon)$近似を与える$\mathrm{poly}(k/\epsilon)$のサブセットを選択する。 アルゴリズムの実行時間は$nd + d~\mathrm{poly}(k/\epsilon)$である。 我々は,データセットに異常値が存在する場合に結果を拡張し,それと同じ2パスアルゴリズムを提案する。 我々のアイデアはまた、$\ell_{p}$部分空間近似と部分集合選択のための適応サンプリングアルゴリズムが要求するパス数を$p \geq 2$で減らすように拡張しています。

関連論文リスト

• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。 $mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-17T15:27:33Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• One-pass additive-error subset selection for $\ell_{p}$ subspace approximation [6.186553186139257]
  我々は $ell_p$ 部分空間近似に対する部分集合選択の問題を考える。 我々は、$ell_p$ subspace approximationの加算近似を保証した1パスのサブセット選択を与える。
  論文  参考訳（メタデータ） (2022-04-26T04:51:36Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。 提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
  論文  参考訳（メタデータ） (2020-09-08T20:32:26Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Subspace approximation with outliers [6.186553186139257]
  本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。 我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
  論文  参考訳（メタデータ） (2020-06-30T07:22:33Z)

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

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