論文の概要: Computing Approximate $\ell_p$ Sensitivities

• arxiv url: http://arxiv.org/abs/2311.04158v2
• Date: Tue, 21 Nov 2023 14:55:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-23 04:14:58.578068
• Title: Computing Approximate $\ell_p$ Sensitivities
• Title（参考訳）: 約$\ell_p$感度の計算
• Authors: Swati Padmanabhan, David P. Woodruff, and Qiuyi Zhang
• Abstract要約: 我々は、与えられた行列の$ell_p$感度と要約統計を近似する効率的なアルゴリズムを提供する。 実世界のデータセットにおける幅広い種類の行列に対して、全体の感度は素早く近似でき、理論的な予測よりもかなり小さい。
• 参考スコア（独自算出の注目度）: 46.95464524720463
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering provable guarantees on the quality of the approximation after removing low-sensitivity datapoints via subsampling. However, fast algorithms for approximating $\ell_p$ sensitivities, which we show is equivalent to approximate $\ell_p$ regression, are known for only the $\ell_2$ setting, in which they are termed leverage scores. In this work, we provide efficient algorithms for approximating $\ell_p$ sensitivities and related summary statistics of a given matrix. In particular, for a given $n \times d$ matrix, we compute $\alpha$-approximation to its $\ell_1$ sensitivities at the cost of $O(n/\alpha)$ sensitivity computations. For estimating the total $\ell_p$ sensitivity (i.e. the sum of $\ell_p$ sensitivities), we provide an algorithm based on importance sampling of $\ell_p$ Lewis weights, which computes a constant factor approximation to the total sensitivity at the cost of roughly $O(\sqrt{d})$ sensitivity computations. Furthermore, we estimate the maximum $\ell_1$ sensitivity, up to a $\sqrt{d}$ factor, using $O(d)$ sensitivity computations. We generalize all these results to $\ell_p$ norms for $p > 1$. Lastly, we experimentally show that for a wide class of matrices in real-world datasets, the total sensitivity can be quickly approximated and is significantly smaller than the theoretical prediction, demonstrating that real-world datasets have low intrinsic effective dimensionality.
• Abstract（参考訳）: 回帰タスクの次元的削減に関する最近の研究は、データセットにおける特定のデータポイントの重要性を推定する感度の概念を導入し、サブサンプリングによる低感度データポイントの除去後の近似の品質保証を提供する。 しかし、近似的な$\ell_p$回帰と同値である$\ell_p$感度を近似する高速アルゴリズムは、レバレッジスコアと呼ばれる$\ell_2$設定でのみ知られている。 本研究では,与えられた行列の$\ell_p$ 感性および関連する要約統計を近似する効率的なアルゴリズムを提案する。 特に、与えられた$n \times d$ 行列に対して、$o(n/\alpha)$ 感度計算のコストで $\alpha$-approximation をその$\ell_1$ 感度に計算する。 合計$\ell_p$感度(すなわち$\ell_p$感度の和)を推定するために、約$O(\sqrt{d})$感度計算のコストでの総感度に対する定数係数近似を演算する、$\ell_p$Lewis重みの重要サンプリングに基づくアルゴリズムを提供する。 さらに、$O(d)$の感度計算を用いて、最大$\ell_1$の感度を$\sqrt{d}$の係数まで推定する。 これらの結果を全て$\ell_p$ norms for $p > 1$に一般化する。 最後に、実世界のデータセットの幅広いクラスにおいて、全感度を迅速に近似し、理論的予測よりも著しく小さくし、実世界のデータセットは本質的な有効次元が低いことを示した。

関連論文リスト

• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation [56.403488578703865]
  我々は$ell$ Sensitivities を $ell$ Sensitivities で拡張することにより、最適な線形 $tilde O(varepsilon-2mu2 d)$ サンプリング複雑性のより良い境界が得られることを示した。 また、ロジスティック回帰のために、$tilde O(varepsilon-2mu2 d)$ sensitivity sample bound を得る。
  論文  参考訳（メタデータ） (2024-06-01T07:03:40Z)
• Online Robust Mean Estimation [37.746091744197656]
  オンライン環境における高次元ロバスト平均推定問題について検討する。 このモデルでは、オンラインロバスト平均推定の主な2つの結果が証明されている。
  論文  参考訳（メタデータ） (2023-10-24T15:28:43Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Sharper Bounds for $\ell_p$ Sensitivity Sampling [56.45770306797584]
  まず, $ell_p$ 部分空間埋め込みを $p に対して高感度サンプリングする。 また、ルートレバレッジスコアサンプリングアルゴリズムは1leq p2$に対して約$d$を達成し、レバレッジスコアと感度サンプリングの組み合わせにより、約$d2/pmathfrak S2-4/p$を2pinftyで改善することを示した。
  論文  参考訳（メタデータ） (2023-06-01T14:27:28Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)

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

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