論文の概要: Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression

• arxiv url: http://arxiv.org/abs/2304.00051v1
• Date: Fri, 31 Mar 2023 18:12:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-04 19:58:16.533635
• Title: Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression
• Title（参考訳）: $\ell_1$ とロジスティック回帰に対する近似定数因子スケッチ
• Authors: Alexander Munteanu, Simon Omlor, David Woodruff
• Abstract要約: 我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。 また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。 我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
• 参考スコア（独自算出の注目度）: 74.28017932704704
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We improve upon previous oblivious sketching and turnstile streaming results for $\ell_1$ and logistic regression, giving a much smaller sketching dimension achieving $O(1)$-approximation and yielding an efficient optimization problem in the sketch space. Namely, we achieve for any constant $c>0$ a sketching dimension of $\tilde{O}(d^{1+c})$ for $\ell_1$ regression and $\tilde{O}(\mu d^{1+c})$ for logistic regression, where $\mu$ is a standard measure that captures the complexity of compressing the data. For $\ell_1$-regression our sketching dimension is near-linear and improves previous work which either required $\Omega(\log d)$-approximation with this sketching dimension, or required a larger $\operatorname{poly}(d)$ number of rows. Similarly, for logistic regression previous work had worse $\operatorname{poly}(\mu d)$ factors in its sketching dimension. We also give a tradeoff that yields a $1+\varepsilon$ approximation in input sparsity time by increasing the total size to $(d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for $\ell_1$ and to $(\mu d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for logistic regression. Finally, we show that our sketch can be extended to approximate a regularized version of logistic regression where the data-dependent regularizer corresponds to the variance of the individual logistic losses.
• Abstract（参考訳）: 我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$\ell_1$とロジスティック回帰で改善し,より小さなスケッチ次元で$O(1)$-approximationを実現し,スケッチ空間における効率的な最適化問題をもたらす。 すなわち、任意の定数$c>0$に対して$\tilde{O}(d^{1+c})$ for $\ell_1$ regression と $\tilde{O}(\mu d^{1+c})$ for logistic regression を達成します。 例えば、$\ell_1$-regression のスケッチ次元はニアリニアであり、このスケッチ次元で$\omega(\log d)$近似を必要とするか、より大きい$\operatorname{poly}(d)$ 行数を必要とする以前の作業を改善する。 同様に、ロジスティック回帰では、以前の仕事はスケッチ次元においてより悪い$\operatorname{poly}(\mu d)$ factorsであった。 また、合計サイズを$(d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for $\ell_1$ and $(\mu d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for logistic regression に拡大することで、入力空間の間隔で1+\varepsilon$を近似するトレードオフを与える。 最後に,データ依存正規化器が個々のロジスティック損失の分散に対応するロジスティック回帰の正規化バージョンを近似するために,スケッチを拡張可能であることを示す。

関連論文リスト

• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations [51.14495595270775]
  我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。 この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
  論文  参考訳（メタデータ） (2023-10-30T19:52:43Z)
• 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)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Oblivious sketching for logistic regression [72.42202783677811]
  本稿では,ロジスティック回帰のための最初のデータ難読スケッチを示す。 私たちのスケッチは速く、シンプルで、実装も簡単です。
  論文  参考訳（メタデータ） (2021-07-14T11:29:26Z)
• L1 Regression with Lewis Weights Subsampling [10.796388585158184]
  Lewisの重みに従って$X$からサンプリングし、経験的最小化器を出力すると、1-delta$$$mの確率で成功することを示す。 また、対応する$Omega(fracdvarepsilon2 + (d + frac1varepsilon2) logfrac1delta)$も与えます。
  論文  参考訳（メタデータ） (2021-05-19T23:15:00Z)
• Truncated Linear Regression in High Dimensions [26.41623833920794]
  truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。 目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。 我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
  論文  参考訳（メタデータ） (2020-07-29T00:31:34Z)

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

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