論文の概要: WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement

• arxiv url: http://arxiv.org/abs/2007.06744v3
• Date: Sat, 15 Aug 2020 06:12:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-10 14:05:48.530870
• Title: WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement
• Title（参考訳）: WOR と $p$'s: $\ell_p$-Sampling の置き換えなしのスケッチ
• Authors: Edith Cohen, Rasmus Pagh, David P. Woodruff
• Abstract要約: We design novel composable sketches for WOR $ell_p$ sample。 私たちのスケッチは、サンプルサイズと直線的にしか成長しないサイズです。 我々の方法は、最初に$p>1$の重要なレギュレーションでWORサンプリングを提供し、最初に$p>0$で署名された更新を処理する。
• 参考スコア（独自算出の注目度）: 75.12782480740822
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weighted sampling is a fundamental tool in data analysis and machine learning pipelines. Samples are used for efficient estimation of statistics or as sparse representations of the data. When weight distributions are skewed, as is often the case in practice, without-replacement (WOR) sampling is much more effective than with-replacement (WR) sampling: it provides a broader representation and higher accuracy for the same number of samples. We design novel composable sketches for WOR $\ell_p$ sampling, weighted sampling of keys according to a power $p\in[0,2]$ of their frequency (or for signed data, sum of updates). Our sketches have size that grows only linearly with the sample size. Our design is simple and practical, despite intricate analysis, and based on off-the-shelf use of widely implemented heavy hitters sketches such as CountSketch. Our method is the first to provide WOR sampling in the important regime of $p>1$ and the first to handle signed updates for $p>0$.
• Abstract（参考訳）: 重み付けサンプリングは、データ分析と機械学習パイプラインの基本的なツールである。 サンプルは、統計の効率的な推定やデータのスパース表現に使用される。 重量分布が歪む場合、実際にはそうであるように、非置換(WOR)サンプリングは非置換(WR)サンプリングよりもはるかに効果的である。 我々は、新しい合成可能なスケッチをwor $\ell_p$サンプリング用に設計し、その周波数のパワー$p\in[0,2]$(または符号付きデータ、更新総和)に従ってキーの重み付けサンプリングを行う。 私たちのスケッチは、サンプルサイズと直線的にしか成長しないサイズです。 我々の設計は複雑に分析されているにもかかわらずシンプルで実用的であり、CountSketchのような広く実装されたヘビーヒッタースケッチを市販している。 我々の方法は、最初に$p>1$の重要なレギュレーションでWORサンプリングを提供し、最初に$p>0$で署名された更新を処理する。

関連論文リスト

• Mini-batch Submodular Maximization [5.439020425819001]
  単調デコンポーザブルな部分モジュラ関数,$F=sum_i=1N fi$ を制約の下で最大化する,最初のミニバッチアルゴリズムを提案する。 我々は、一様と重み付けの2つのサンプリング手法を検討する。 意外なことに, 実験結果から, 均一サンプリングは加重サンプリングよりも優れていることが示された。
  論文  参考訳（メタデータ） (2024-01-23T04:16:58Z)
• Massively Parallel Reweighted Wake-Sleep [29.436464740855598]
  Re-weighted wake-sleep (RWS) は、ベイズ推論を非常に一般的なモデルのクラスで実行するための機械学習手法である。 近年の研究では、有効な重み付けに必要なサンプルの数は潜伏変数の数で指数関数的であることが示されている。 標準の「グローバル」RWSよりも大幅に改善され、全関節から$K$のサンプルが引き出される。
  論文  参考訳（メタデータ） (2023-05-18T15:03:56Z)
• Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams [35.943447765433774]
  完全動的グラフストリームにおける部分グラフ数を推定するための重み付きサンプリングアルゴリズムWSDを提案する。 強化学習に基づく新しい手法を用いて,エッジの重みをデータ駆動方式で決定する。
  論文  参考訳（メタデータ） (2022-11-13T03:01:34Z)
• Bias Mimicking: A Simple Sampling Approach for Bias Mitigation [57.17709477668213]
  本稿では,新しいクラス条件サンプリング手法であるBias Mimickingを紹介する。 Bias Mimickingは、4つのベンチマークで3%の精度でサンプリングの精度を向上する。
  論文  参考訳（メタデータ） (2022-09-30T17:33:00Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Meta-Sampler: Almost-Universal yet Task-Oriented Sampling for Point Clouds [46.33828400918886]
  複数のタスクにまたがって、ほぼ普遍的なメタサンプルをトレーニングする方法を示します。 このメタサンプルは、異なるデータセットやネットワーク、あるいは異なるタスクに適用した場合、迅速に微調整できる。
  論文  参考訳（メタデータ） (2022-03-30T02:21:34Z)
• Oblivious sketching for logistic regression [72.42202783677811]
  本稿では,ロジスティック回帰のための最初のデータ難読スケッチを示す。 私たちのスケッチは速く、シンプルで、実装も簡単です。
  論文  参考訳（メタデータ） (2021-07-14T11:29:26Z)
• Learning a Unified Sample Weighting Network for Object Detection [113.98404690619982]
  地域サンプリングや重み付けは、現代の地域ベースの物体検出器の成功に極めて重要である。 サンプル重み付けはデータ依存でタスク依存であるべきだと我々は主張する。 サンプルのタスク重みを予測するための統一的なサンプル重み付けネットワークを提案する。
  論文  参考訳（メタデータ） (2020-06-11T16:19:16Z)

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

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