論文の概要: Oblivious sketching for logistic regression
- arxiv url: http://arxiv.org/abs/2107.06615v1
- Date: Wed, 14 Jul 2021 11:29:26 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-15 14:23:05.534438
- Title: Oblivious sketching for logistic regression
- Title(参考訳): ロジスティック回帰のための斜めスケッチ
- Authors: Alexander Munteanu, Simon Omlor, David Woodruff
- Abstract要約: 本稿では,ロジスティック回帰のための最初のデータ難読スケッチを示す。
私たちのスケッチは速く、シンプルで、実装も簡単です。
- 参考スコア(独自算出の注目度): 72.42202783677811
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: What guarantees are possible for solving logistic regression in one pass over
a data stream? To answer this question, we present the first data oblivious
sketch for logistic regression. Our sketch can be computed in input sparsity
time over a turnstile data stream and reduces the size of a $d$-dimensional
data set from $n$ to only $\operatorname{poly}(\mu d\log n)$ weighted points,
where $\mu$ is a useful parameter which captures the complexity of compressing
the data. Solving (weighted) logistic regression on the sketch gives an $O(\log
n)$-approximation to the original problem on the full data set. We also show
how to obtain an $O(1)$-approximation with slight modifications. Our sketches
are fast, simple, easy to implement, and our experiments demonstrate their
practicality.
- Abstract(参考訳): データストリームを1回のパスでロジスティック回帰を解決できる保証は何だろうか?
この疑問に答えるために、ロジスティック回帰のための最初のデータ難読スケッチを示す。
私たちのスケッチは、回転するデータストリーム上の入力スパーシティタイムで計算でき、$n$から$\operatorname{poly}(\mu d\log n)$の重み付きポイントまで、$d$次元のデータのサイズを縮小します。
スケッチ上で(重み付けされた)ロジスティック回帰を解くと、データセット全体の元の問題に対して$o(\log n)$-approximationが得られる。
また、わずかな修正を加えて$O(1)$-approximationを得る方法を示す。
私たちのスケッチは速く、シンプルで、実装も簡単です。
関連論文リスト
- Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。
特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
論文 参考訳(メタデータ) (2024-10-30T10:09:05Z) - 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) - Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic
Regression [74.28017932704704]
我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。
また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。
我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
論文 参考訳(メタデータ) (2023-03-31T18:12:33Z) - 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) - WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement [75.12782480740822]
We design novel composable sketches for WOR $ell_p$ sample。
私たちのスケッチは、サンプルサイズと直線的にしか成長しないサイズです。
我々の方法は、最初に$p>1$の重要なレギュレーションでWORサンプリングを提供し、最初に$p>0$で署名された更新を処理する。
論文 参考訳(メタデータ) (2020-07-14T00:19:27Z) - Online Robust Regression via SGD on the l1 loss [19.087335681007477]
ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。
この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
論文 参考訳(メタデータ) (2020-07-01T11:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。