論文の概要: Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation

• arxiv url: http://arxiv.org/abs/2406.00328v1
• Date: Sat, 1 Jun 2024 07:03:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 07:34:33.671090
• Title: Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
• Title（参考訳）: $\ell_2$拡張による$\ell_p$感度サンプリングのための最適境界
• Authors: Alexander Munteanu, Simon Omlor,
• Abstract要約: 我々は$ell$ Sensitivities を $ell$ Sensitivities で拡張することにより、最適な線形 $tilde O(varepsilon-2mu2 d)$ サンプリング複雑性のより良い境界が得られることを示した。 また、ロジスティック回帰のために、$tilde O(varepsilon-2mu2 d)$ sensitivity sample bound を得る。
• 参考スコア（独自算出の注目度）: 56.403488578703865
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Data subsampling is one of the most natural methods to approximate a massively large data set by a small representative proxy. In particular, sensitivity sampling received a lot of attention, which samples points proportional to an individual importance measure called sensitivity. This framework reduces in very general settings the size of data to roughly the VC dimension $d$ times the total sensitivity $\mathfrak S$ while providing strong $(1\pm\varepsilon)$ guarantees on the quality of approximation. The recent work of Woodruff & Yasuda (2023c) improved substantially over the general $\tilde O(\varepsilon^{-2}\mathfrak Sd)$ bound for the important problem of $\ell_p$ subspace embeddings to $\tilde O(\varepsilon^{-2}\mathfrak S^{2/p})$ for $p\in[1,2]$. Their result was subsumed by an earlier $\tilde O(\varepsilon^{-2}\mathfrak Sd^{1-p/2})$ bound which was implicitly given in the work of Chen & Derezinski (2021). We show that their result is tight when sampling according to plain $\ell_p$ sensitivities. We observe that by augmenting the $\ell_p$ sensitivities by $\ell_2$ sensitivities, we obtain better bounds improving over the aforementioned results to optimal linear $\tilde O(\varepsilon^{-2}(\mathfrak S+d)) = \tilde O(\varepsilon^{-2}d)$ sampling complexity for all $p \in [1,2]$. In particular, this resolves an open question of Woodruff & Yasuda (2023c) in the affirmative for $p \in [1,2]$ and brings sensitivity subsampling into the regime that was previously only known to be possible using Lewis weights (Cohen & Peng, 2015). As an application of our main result, we also obtain an $\tilde O(\varepsilon^{-2}\mu d)$ sensitivity sampling bound for logistic regression, where $\mu$ is a natural complexity measure for this problem. This improves over the previous $\tilde O(\varepsilon^{-2}\mu^2 d)$ bound of Mai et al. (2021) which was based on Lewis weights subsampling.
• Abstract（参考訳）: データサブサンプリングは、小さな代表プロキシによって設定された巨大なデータセットを近似する最も自然な方法の1つである。 特に感度サンプリングには多くの注意が払われており、これは感度と呼ばれる個々の重要度に比例する。 このフレームワークは、データのサイズをおよそVC次元の$d$の合計感度の$\mathfrak S$の約$d$に減らし、強い$(1\pm\varepsilon)$近似の品質を保証する。 Woodruff & Yasuda (2023c) の最近の研究は、一般の$\tilde O(\varepsilon^{-2}\mathfrak Sd)$ と $\tilde O(\varepsilon^{-2}\mathfrak S^{2/p})$ に$\ell_p$ の部分空間埋め込みの重要な問題に対する$ を$p\in[1,2]$ に限定して大幅に改善した。 それらの結果は、より初期の$\tilde O(\varepsilon^{-2}\mathfrak Sd^{1-p/2})$boundによって仮定され、これはChen & Derezinski (2021) の研究で暗黙的に与えられた。 通常の$\ell_p$ Sensitivitiesに従ってサンプリングすると,結果が厳密であることを示す。 我々は、$\ell_p$ Sensitivities を$\ell_2$ Sensitivities で増すことにより、上記の結果よりもより良い境界を最適線型 $\tilde O(\varepsilon^{-2}(\mathfrak S+d)) = \tilde O(\varepsilon^{-2}d)$ sample complexity for all $p \in [1,2]$ とする。 特に、このことはWoodruff & Yasuda (2023c) を$p \in [1,2]$で肯定的に解決し、以前ルイス重みを使ってしかできなかった体制に感度サブサンプリングをもたらす(Cohen & Peng, 2015)。 主な結果の応用として、ロジスティック回帰のために束縛された$\tilde O(\varepsilon^{-2}\mu d)$感度サンプリングも得られる。 これは以前の$\tilde O(\varepsilon^{-2}\mu^2 d)$ bound of Mai et al (2021)よりも改善される。

関連論文リスト

• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。 1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
  論文  参考訳（メタデータ） (2024-06-04T15:50:42Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• 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)
• The Price of Tolerance in Distribution Testing [31.10049510641336]
  サンプルの複雑さは [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2 であることが示され、この2つの既知事例の間に円滑なトレードオフをもたらす。 また、p$ と$q$ の両方が未知である寛容同値検定の問題についても同様の特徴を与える。
  論文  参考訳（メタデータ） (2021-06-25T03:59:42Z)
• 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)

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

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