論文の概要: One-pass additive-error subset selection for $\ell_{p}$ subspace approximation

• arxiv url: http://arxiv.org/abs/2204.12073v1
• Date: Tue, 26 Apr 2022 04:51:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-27 22:05:44.043205
• Title: One-pass additive-error subset selection for $\ell_{p}$ subspace approximation
• Title（参考訳）: $\ell_{p}$部分空間近似のための1パス加法エラー部分集合選択
• Authors: Amit Deshpande and Rameshwar Pratap
• Abstract要約: 我々は $ell_p$ 部分空間近似に対する部分集合選択の問題を考える。 我々は、$ell_p$ subspace approximationの加算近似を保証した1パスのサブセット選択を与える。
• 参考スコア（独自算出の注目度）: 6.186553186139257
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of subset selection for $\ell_{p}$ subspace approximation, that is, to efficiently find a \emph{small} subset of data points such that solving the problem optimally for this subset gives a good approximation to solving the problem optimally for the original input. Previously known subset selection algorithms based on volume sampling and adaptive sampling \cite{DeshpandeV07}, for the general case of $p \in [1, \infty)$, require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for $\ell_{p}$ subspace approximation, for any $p \in [1, \infty)$. Earlier subset selection algorithms that give a one-pass multiplicative $(1+\epsilon)$ approximation work under the special cases. Cohen \textit{et al.} \cite{CohenMM17} gives a one-pass subset section that offers multiplicative $(1+\epsilon)$ approximation guarantee for the special case of $\ell_{2}$ subspace approximation. Mahabadi \textit{et al.} \cite{MahabadiRWZ20} gives a one-pass \emph{noisy} subset selection with $(1+\epsilon)$ approximation guarantee for $\ell_{p}$ subspace approximation when $p \in \{1, 2\}$. Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any $p \in [1, \infty)$.
• Abstract（参考訳）: 我々は、$\ell_{p}$部分空間近似に対する部分集合選択の問題、すなわち、この部分集合に対して最適に解くことが元の入力に対して最適に解くよい近似を与えるような、データ点の半点部分集合を効率的に見つけることを考える。 従来知られていたボリュームサンプリングと適応サンプリングに基づくサブセット選択アルゴリズムは、$p \in [1, \infty)$の一般的な場合、データに対する複数のパスを必要とする。 本稿では、任意の$p \in [1, \infty)$に対して、$\ell_{p}$ subspace approximationに対して加法近似の保証付きワンパス部分集合選択を与える。 1パス乗算(1+\epsilon)$近似作業を特殊ケースで与えた初期の部分集合選択アルゴリズム。 Cohen \textit{et al. } \cite{cohenmm17} は、$\ell_{2}$ 部分空間近似の特別な場合に対する乗法 $(1+\epsilon)$ の近似保証を提供する1パスのサブセットセクションを与える。 Mahabadi \textit{et al. } \cite{mahabadirwz20} は、$p \in \{1, 2\}$ のとき、$(1+\epsilon)$ の近似保証を持つ1パスの \emph{noisy} 部分選択を与える。 我々の部分集合選択アルゴリズムはより弱で加法的な近似を保証するが、任意の$p \in [1, \infty)$に対して作用する。

関連論文リスト

• Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
  $ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。 我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。 我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この論文は、一般的なマルコフ的な設定でステップサイズの選択を再考する。 大きな結論は、$rho =0$ または $rho1/2$ の選択は、選択した設定でのみ正当化されるということである。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。 局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
  論文  参考訳（メタデータ） (2021-05-31T14:41:40Z)
• On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling [3.1822873305165618]
  サンプリングベースのサブセット選択技術は、データに複数のパスを持つ適応的なサンプリングイテレーションを必要とする。 従来のサブセット選択アルゴリズムで必要となるパス数を削減するMCMCアルゴリズムを提案する。 このアルゴリズムは$mathrmpoly(k/epsilon)$のサブセットを選び、最適部分空間に$(1+epsilon)$近似を与えます。
  論文  参考訳（メタデータ） (2021-03-20T06:07:30Z)
• Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation [0.0]
  カラムサブセット選択をベースとした$ell_p$ローランク近似アルゴリズムで$tildeO(k)$カラムをサンプリングする。 我々は、カラム部分集合選択に基づく$ell_p$低階近似を1p2$で厳密な上限と下限を得るように、結果を拡張した。
  論文  参考訳（メタデータ） (2020-07-20T17:50:30Z)
• Subspace approximation with outliers [6.186553186139257]
  本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。 我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
  論文  参考訳（メタデータ） (2020-06-30T07:22:33Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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