論文の概要: Turnstile $\ell_p$ leverage score sampling with applications

• arxiv url: http://arxiv.org/abs/2406.00339v1
• Date: Sat, 1 Jun 2024 07:33:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 07:34:33.657101
• Title: Turnstile $\ell_p$ leverage score sampling with applications
• Title（参考訳）: Turnstile $\ell_p$ leverage score sample with application
• Authors: Alexander Munteanu, Simon Omlor,
• Abstract要約: 我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 56.403488578703865
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The turnstile data stream model offers the most flexible framework where data can be manipulated dynamically, i.e., rows, columns, and even single entries of an input matrix can be added, deleted, or updated multiple times in a data stream. We develop a novel algorithm for sampling rows $a_i$ of a matrix $A\in\mathbb{R}^{n\times d}$, proportional to their $\ell_p$ norm, when $A$ is presented in a turnstile data stream. Our algorithm not only returns the set of sampled row indexes, it also returns slightly perturbed rows $\tilde{a}_i \approx a_i$, and approximates their sampling probabilities up to $\varepsilon$ relative error. When combined with preconditioning techniques, our algorithm extends to $\ell_p$ leverage score sampling over turnstile data streams. With these properties in place, it allows us to simulate subsampling constructions of coresets for important regression problems to operate over turnstile data streams with very little overhead compared to their respective off-line subsampling algorithms. For logistic regression, our framework yields the first algorithm that achieves a $(1+\varepsilon)$ approximation and works in a turnstile data stream using polynomial sketch/subsample size, improving over $O(1)$ approximations, or $\exp(1/\varepsilon)$ sketch size of previous work. We compare experimentally to plain oblivious sketching and plain leverage score sampling algorithms for $\ell_p$ and logistic regression.
• Abstract（参考訳）: ターンタイルデータストリームモデルは、データを動的に操作できる最も柔軟なフレームワークを提供する。例えば、行、列、さらには入力行列の単一エントリも、データストリームで複数回追加、削除、または更新できる。 我々は,行列$A\in\mathbb{R}^{n\times d}$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプリングされた行インデックスの集合を返すだけでなく、わずかに摂動された行を $\tilde{a}_i \approx a_i$ で返し、サンプリング確率を $\varepsilon$ の相対誤差に近似する。 プリコンディショニング技術と組み合わせると、我々のアルゴリズムはターンタイルデータストリーム上でのスコアサンプリングに$\ell_p$まで拡張する。 これらの特性により、重要な回帰問題に対するコアセットのサブサンプリング構造をシミュレートし、各オフラインサブサンプリングアルゴリズムと比較して非常にオーバーヘッドの少ないターンタイルデータストリームを操作することができる。 ロジスティック回帰のために、我々のフレームワークは、1+\varepsilon)$近似を達成し、多項式スケッチ/サブサンプルサイズを使用してターンタイルデータストリームで動作し、$O(1)$近似、または$\exp(1/\varepsilon)$以前の作業のスケッチサイズを改善する最初のアルゴリズムを生成する。 実験では, 粗悪なスケッチと, 平均値$\ell_p$とロジスティック回帰のための平易なレバレッジスコアサンプリングアルゴリズムを比較した。

関連論文リスト

• Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
  我々は,$d$変数の統計的関係を,mathbbRn times d$の$n$サンプル$Xのデータセットからモデル化するグラフの学習問題を考察する。 サイズ $m=Omegaleft((d+2k)log(d)right)$ ここで、$k$は基礎となるグラフのエッジの最大数である。 本稿では, グラフィカルラッソに基づく反復アルゴリズムを用いて, 具体的デノイザとみなす実用的リカバリを実現する可能性について検討する。
  論文  参考訳（メタデータ） (2023-11-08T13:29:08Z)
• 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)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression [74.28017932704704]
  我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。 また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。 我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
  論文  参考訳（メタデータ） (2023-03-31T18:12:33Z)
• Online Active Regression [8.397196353612042]
  学習者はデータポイントを1つずつ受け取り、対応するラベルを収集すべきかを判断する。 目標は、ラベルクエリの少ない予算で、受信したデータポイントのレグレッションを効率的に維持することである。
  論文  参考訳（メタデータ） (2022-07-13T03:53:25Z)
• 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)
• 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)
• A Deterministic Streaming Sketch for Ridge Regression [15.256452294422294]
  リッジ回帰を推定するための決定論的空間効率アルゴリズムを提案する。 これは、ソリューションエラーが保証された最初の$o(d2)$空間決定論的ストリーミングアルゴリズムである。 合成データセットと実世界のデータセットのランダムなスケッチアルゴリズムと比較して、我々のアルゴリズムは空間と類似時間が少なくて経験的誤差が少ない。
  論文  参考訳（メタデータ） (2020-02-05T22:08:29Z)

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

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