論文の概要: 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を得る方法を示す。
私たちのスケッチは速く、シンプルで、実装も簡単です。
関連論文リスト
- 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) - Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic
Regression [74.28017932704704]
我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。
また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。
我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
論文 参考訳(メタデータ) (2023-03-31T18:12:33Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳(メタデータ) (2021-11-30T14:16:48Z) - Variational Bayesian Unlearning [54.26984662139516]
本研究では, ベイズモデルの学習を, 消去する訓練データの小さな部分集合から, ほぼ非学習する問題について検討する。
消去されたデータから完全に学習されていないデータと、過去の信念を完全に忘れていないデータとをトレードオフする証拠を最小化するのと等価であることを示す。
VI を用いたモデルトレーニングでは、完全なデータから近似した(正確には)後続の信念しか得られず、未学習をさらに困難にしている。
論文 参考訳(メタデータ) (2020-10-24T11:53: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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。