論文の概要: Coresets for Multiple $\ell_p$ Regression

• arxiv url: http://arxiv.org/abs/2406.02432v1
• Date: Tue, 4 Jun 2024 15:50:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-05 15:30:46.794780
• Title: Coresets for Multiple $\ell_p$ Regression
• Title（参考訳）: Coresets for multiple $\ell_p$ Regression
• Authors: David P. Woodruff, Taisuke Yasuda,
• Abstract要約: サイズ $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である。
• 参考スコア（独自算出の注目度）: 47.790126028106734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A coreset of a dataset with $n$ examples and $d$ features is a weighted subset of examples that is sufficient for solving downstream data analytic tasks. Nearly optimal constructions of coresets for least squares and $\ell_p$ linear regression with a single response are known in prior work. However, for multiple $\ell_p$ regression where there can be $m$ responses, there are no known constructions with size sublinear in $m$. In this work, we construct coresets of size $\tilde O(\varepsilon^{-2}d)$ for $p<2$ and $\tilde O(\varepsilon^{-p}d^{p/2})$ for $p>2$ independently of $m$ (i.e., dimension-free) that approximate the multiple $\ell_p$ regression objective at every point in the domain up to $(1\pm\varepsilon)$ relative error. If we only need to preserve the minimizer subject to a subspace constraint, we improve these bounds by an $\varepsilon$ factor for all $p>1$. All of our bounds are nearly tight. We give two application of our results. First, we settle the number of uniform samples needed to approximate $\ell_p$ Euclidean power means up to a $(1+\varepsilon)$ factor, showing that $\tilde\Theta(\varepsilon^{-2})$ samples for $p = 1$, $\tilde\Theta(\varepsilon^{-1})$ samples for $1 < p < 2$, and $\tilde\Theta(\varepsilon^{1-p})$ samples for $p>2$ is tight, answering a question of Cohen-Addad, Saulpic, and Schwiegelshohn. Second, we show that for $1<p<2$, every matrix has a subset of $\tilde O(\varepsilon^{-1}k)$ rows which spans a $(1+\varepsilon)$-approximately optimal $k$-dimensional subspace for $\ell_p$ subspace approximation, which is also nearly optimal.
• Abstract（参考訳）: n$サンプルと$d$機能を備えたデータセットのコアセットは、下流のデータ分析タスクを解決するのに十分なサンプルの重み付けされたサブセットである。 最小二乗のコアセットと1つの応答を持つ$\ell_p$線形回帰のほぼ最適構成は、以前の研究で知られている。 しかし、$m$レスポンスがある複数の$\ell_p$回帰の場合、$m$のサブリニアを持つ既知の構造は存在しない。 本研究では、$\tilde O(\varepsilon^{-2}d)$ for $p<2$ and $\tilde O(\varepsilon^{-p}d^{p/2})$ for $p>2$ of $m$(つまり、次元のない)とは独立に、ドメイン内の各点における複数の$\ell_p$回帰目標を(1\pm\varepsilon)$ 相対誤差に近似するコアセットを構築する。 部分空間制約の対象となる最小値を保存する必要がなければ、すべての$p>1$に対して$\varepsilon$ factorでこれらの境界を改善する。 私たちの境界はどれもほとんどきつい。 我々はその結果を2つ応用する。 まず、$\tilde\Theta(\varepsilon^{-2})$ sample for $p = 1$, $\tilde\Theta(\varepsilon^{-1})$ sample for $1 < p < 2$, $\tilde\Theta(\varepsilon^{1-p})$ sample for $p>2$ is tight, and answering a question of Cohen-Addad, Saulpic, and Schwiegelshohn。 第二に、$<p<2$の場合、すべての行列は$\tilde O(\varepsilon^{-1}k)$ rows の部分集合を持ち、$(1+\varepsilon)$-atimate optimal $k$-dimensional subspace for $\ell_p$ subspace approximation もほぼ最適である。

関連論文リスト

• 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)
• Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
  ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。 mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。 これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
  論文  参考訳（メタデータ） (2023-11-17T18:01:58Z)
• $\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)
• Sparse Dimensionality Reduction Revisited [13.170012290527017]
  スパースジョンソン・リンデンシュトラウス変換は次元還元の中心的な手法の一つである。 疎な埋め込みを再検討し、下界の抜け穴を同定する。 また,最適埋め込み次元に対する最適半空間埋め込みの空隙性も改善する。
  論文  参考訳（メタデータ） (2023-02-13T08:01:25Z)
• 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)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• 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)

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

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