論文の概要: L1 Regression with Lewis Weights Subsampling

• arxiv url: http://arxiv.org/abs/2105.09433v1
• Date: Wed, 19 May 2021 23:15:00 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-21 22:40:00.576590
• Title: L1 Regression with Lewis Weights Subsampling
• Title（参考訳）: Lewis WeightsサブサンプリングによるL1回帰
• Authors: Aditya Parulekar, Advait Parulekar, Eric Price
• Abstract要約: Lewisの重みに従って$X$からサンプリングし、経験的最小化器を出力すると、1-delta$$$mの確率で成功することを示す。 また、対応する$Omega(fracdvarepsilon2 + (d + frac1varepsilon2) logfrac1delta)$も与えます。
• 参考スコア（独自算出の注目度）: 10.796388585158184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of finding an approximate solution to $\ell_1$ regression while only observing a small number of labels. Given an $n \times d$ unlabeled data matrix $X$, we must choose a small set of $m \ll n$ rows to observe the labels of, then output an estimate $\widehat{\beta}$ whose error on the original problem is within a $1 + \varepsilon$ factor of optimal. We show that sampling from $X$ according to its Lewis weights and outputting the empirical minimizer succeeds with probability $1-\delta$ for $m > O(\frac{1}{\varepsilon^2} d \log \frac{d}{\varepsilon \delta})$. This is analogous to the performance of sampling according to leverage scores for $\ell_2$ regression, but with exponentially better dependence on $\delta$. We also give a corresponding lower bound of $\Omega(\frac{d}{\varepsilon^2} + (d + \frac{1}{\varepsilon^2}) \log\frac{1}{\delta})$.
• Abstract（参考訳）: 我々は,少数のラベルのみを観測しながら,$\ell_1$回帰の近似解を求める問題を考察する。 n \times d$ unlabeled data matrix $x$ が与えられると、ラベルを観察するために m \ll n$ の小さなセットを選択し、元の問題に対するエラーが 1 + \varepsilon$ factor の範囲内にある推定 $\widehat{\beta}$ を出力する必要があります。 ルイス重みによる$X$からのサンプリングと経験的最小値の出力は確率1-\delta$ for $m > O(\frac{1}{\varepsilon^2} d \log \frac{d}{\varepsilon \delta})$で成功することを示す。 これは、$\ell_2$回帰のレバレッジスコアによるサンプリングのパフォーマンスに似ているが、$\delta$への指数的に優れた依存を持つ。 また、対応する下限の$\Omega(\frac{d}{\varepsilon^2} + (d + \frac{1}{\varepsilon^2}) \log\frac{1}{\delta})$を与える。

関連論文リスト

• 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)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• $\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)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression [74.28017932704704]
  我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。 また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。 我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
  論文  参考訳（メタデータ） (2023-03-31T18:12:33Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。 本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
  論文  参考訳（メタデータ） (2022-09-06T23:37:31Z)
• Online Lewis Weight Sampling [62.38157566916501]
  コーエンとペンはルイスの重量サンプリングを理論計算機科学コミュニティに導入した。 この重要なプリミティブを、オンラインコアセット、スライディングウィンドウ、対向ストリーミングモデルなど、他の設定に拡張した作品もいくつかある。 オンラインコアセット,スライディングウィンドウ,および逆ストリーミングモデルにおいて,すべての$pin(0,infty)$に対して,ほぼ最適に近い$ell_p$サブスペース埋め込みを設計する。
  論文  参考訳（メタデータ） (2022-07-17T19:40:51Z)
• Robust Testing in High-Dimensional Sparse Models [0.0]
  2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。 回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
  論文  参考訳（メタデータ） (2022-05-16T07:47:22Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
  i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。 疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
  論文  参考訳（メタデータ） (2020-06-17T09:21:00Z)

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

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