論文の概要: Sharper Bounds for $\ell_p$ Sensitivity Sampling

• arxiv url: http://arxiv.org/abs/2306.00732v1
• Date: Thu, 1 Jun 2023 14:27:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-02 15:35:36.987359
• Title: Sharper Bounds for $\ell_p$ Sensitivity Sampling
• Title（参考訳）: 感度サンプリング$\ell_p$のシャープ境界
• Authors: David P. Woodruff, Taisuke Yasuda
• Abstract要約: 大規模な機械学習において、ランダムサンプリングは、サンプルの小さな代表部分集合によってデータセットを近似する一般的な方法である。 本研究では,$ell_p$部分空間埋め込みに対して$pne$q 2$に対する感度サンプリングの最初の境界を示す。 我々の感度サンプリングの結果は、より小さな$ell_pの感度を持つ広範囲の構造化行列に対して、最もよく知られたサンプルの複雑さをもたらす。
• 参考スコア（独自算出の注目度）: 62.38157566916501
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In large scale machine learning, random sampling is a popular way to approximate datasets by a small representative subset of examples. In particular, sensitivity sampling is an intensely studied technique which provides provable guarantees on the quality of approximation, while reducing the number of examples to the product of the VC dimension $d$ and the total sensitivity $\mathfrak S$ in remarkably general settings. However, guarantees going beyond this general bound of $\mathfrak S d$ are known in perhaps only one setting, for $\ell_2$ subspace embeddings, despite intense study of sensitivity sampling in prior work. In this work, we show the first bounds for sensitivity sampling for $\ell_p$ subspace embeddings for $p\neq 2$ that improve over the general $\mathfrak S d$ bound, achieving a bound of roughly $\mathfrak S^{2/p}$ for $1\leq p<2$ and $\mathfrak S^{2-2/p}$ for $2<p<\infty$. For $1\leq p<2$, we show that this bound is tight, in the sense that there exist matrices for which $\mathfrak S^{2/p}$ samples is necessary. Furthermore, our techniques yield further new results in the study of sampling algorithms, showing that the root leverage score sampling algorithm achieves a bound of roughly $d$ for $1\leq p<2$, and that a combination of leverage score and sensitivity sampling achieves an improved bound of roughly $d^{2/p}\mathfrak S^{2-4/p}$ for $2<p<\infty$. Our sensitivity sampling results yield the best known sample complexity for a wide class of structured matrices that have small $\ell_p$ sensitivity.
• Abstract（参考訳）: 大規模な機械学習において、ランダムサンプリングは、サンプルの小さな代表部分集合によってデータセットを近似する一般的な方法である。 特に、感度サンプリングは、非常に一般的な設定でvc次元 $d$ と総感度 $\mathfrak s$ の積に例の数を減少させながら、近似の質を証明可能な保証を提供する、非常に研究された技術である。 しかし、この一般的な境界である$\mathfrak s d$ を超える保証は、以前の仕事における感度サンプリングの徹底的な研究にもかかわらず、$\ell_2$ 部分空間埋め込みに対しておそらく1つの設定で知られている。 この研究では、$\ell_p$ 部分空間埋め込みに対する$p\neq 2$ に対する感度サンプリングの最初のバウンドを示す。これは一般的な$\mathfrak S d$ よりも改善され、約$\mathfrak S^{2/p} のバウンドを$1\leq p<2$ および$\mathfrak S^{2-2/p} に対して$2<p<\infty$ で達成する。 $1\leq p<2$ の場合、この境界は、$\mathfrak S^{2/p} のサンプルが必要とされる行列が存在するという意味で、厳密であることを示す。 さらに,本手法はサンプリングアルゴリズムの研究においてさらに新たな結果をもたらし,ルートレバレッジスコアサンプリングアルゴリズムが約$d$1\leq p<2$,レバレッジスコアと感度サンプリングの組み合わせで約$d^{2/p}\mathfrak S^{2-4/p}$2<p<\infty$とした。 感度サンプリングの結果、$\ell_p$の感度の小さい構造行列の最もよく知られたサンプル複雑性が得られる。

関連論文リスト

• Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams [0.0]
  本稿では,主成分分析 (PCA) のための新しいアルゴリズムについて紹介する。 外れ値が存在する場合でも、PCAの最適部分空間にナビゲートする。 このアプローチは、$nd+mathcalO(1)textpoly(n,d)$の時間複雑性を持つ最適解を得る。
  論文  参考訳（メタデータ） (2024-08-13T13:05:36Z)
• 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)
• Computing Approximate $\ell_p$ Sensitivities [46.95464524720463]
  我々は、与えられた行列の$ell_p$感度と要約統計を近似する効率的なアルゴリズムを提供する。 実世界のデータセットにおける幅広い種類の行列に対して、全体の感度は素早く近似でき、理論的な予測よりもかなり小さい。
  論文  参考訳（メタデータ） (2023-11-07T17:34:56Z)
• 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)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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