論文の概要: Non-Adaptive Adaptive Sampling on Turnstile Streams

• arxiv url: http://arxiv.org/abs/2004.10969v1
• Date: Thu, 23 Apr 2020 05:00:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-10 12:46:21.175151
• Title: Non-Adaptive Adaptive Sampling on Turnstile Streams
• Title（参考訳）: 旋回性流れにおける非適応適応サンプリング
• Authors: Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, Samson Zhou
• Abstract要約: カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
• 参考スコア（独自算出の注目度）: 57.619901304728366
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adaptive sampling is a useful algorithmic tool for data summarization problems in the classical centralized setting, where the entire dataset is available to the single processor performing the computation. Adaptive sampling repeatedly selects rows of an underlying matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$, where $n\gg d$, with probabilities proportional to their distances to the subspace of the previously selected rows. Intuitively, adaptive sampling seems to be limited to trivial multi-pass algorithms in the streaming model of computation due to its inherently sequential nature of assigning sampling probabilities to each row only after the previous iteration is completed. Surprisingly, we show this is not the case by giving the first one-pass algorithms for adaptive sampling on turnstile streams and using space $\text{poly}(d,k,\log n)$, where $k$ is the number of adaptive sampling rounds to be performed. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model. We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume maximization on turnstile streams that use space sublinear in $n$. We complement our volume maximization algorithmic results with lower bounds that are tight up to lower order terms, even for multi-pass algorithms. By a similar construction, we also obtain lower bounds for volume maximization in the row-arrival model, which we match with competitive upper bounds. See paper for full abstract.
• Abstract（参考訳）: アダプティブサンプリング(Adaptive sample)は、古典的な中央集権的な設定におけるデータ要約問題に対して有用なアルゴリズムツールである。 アダプティブサンプリングは、下層の行列 $\mathbf{A}\in\mathbb{R}^{n\times d}$ の行を繰り返し選択する。 直感的には、アダプティブサンプリングは、前回の繰り返しが完了した後のみ、各行にサンプリング確率を割り当てるという本質的にシーケンシャルな性質から、計算のストリーミングモデルにおける自明なマルチパスアルゴリズムに制限されているようである。 驚くべきことに、ターンタイルストリーム上で適応サンプリングを行うための最初のワンパスアルゴリズムを与え、スペース$\text{poly}(d,k,\log n)$を使用すると、$k$は適応サンプリングラウンドの回数である。 適応サンプリング法では,データ要約問題に対する応用が多岐に渡り,最新技術の改善か,従来より緩和された行配列モデルでのみ研究されてきた。 空間サブリニアを$n$で使用するターンタイルストリームに対して、カラムサブセット選択、部分空間近似、射影クラスタリング、ボリューム最大化のための最初の相対エラーアルゴリズムを提供する。 我々は,マルチパスアルゴリズムにおいても,低次項まで厳密な境界を持つボリューム最大化アルゴリズムを補完する。 また、同様の構成により、競合上界と一致する行-アリーモデルにおける体積最大化のための下限を得る。 完全な要約は紙を参照。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Bayes-optimal learning of an extensive-width neural network from quadratically many samples [28.315491743569897]
  本研究では,単一層ニューラルネットワークに対応する対象関数を学習する問題を考察する。 入力次元とネットワーク幅が比例的に大きい限界を考える。
  論文  参考訳（メタデータ） (2024-08-07T12:41:56Z)
• Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data [17.657917523817243]
  この問題を条件付き最適化問題とみなして,器用変分回帰のためのアルゴリズムを開発し,解析する。 最小二乗変数回帰の文脈では、我々のアルゴリズムは行列逆転やミニバッチを必要としない。 任意の$iota>0$に対して$mathcalO(log T/T)$と$mathcalO(1/T1-iota)$の順の収束率を導出する。
  論文  参考訳（メタデータ） (2024-05-29T19:21:55Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory [6.696267547013535]
  そこで本研究では,データ駆動基準によりパラメータ選択された,近接する隣人の数がパラメータとなる分散適応型NN分類器を提案する。 有限標本性能を向上する最適チューニングパラメータを探索する際,早期停止規則を提案する。 特に、サブサンプルサイズが十分に大きい場合、提案した分類器がほぼ最適な収束率を達成することを示す。
  論文  参考訳（メタデータ） (2021-05-20T14:38:41Z)
• Optimal Sampling Gaps for Adaptive Submodular Maximization [28.24164217929491]
  アダプティブサブモジュラの文脈における確率サンプリングによる性能損失について検討する。 ポリシワイズ・サブモジュラの性質は、現実世界の幅広いアプリケーションで見つけることができることを示しています。
  論文  参考訳（メタデータ） (2021-04-05T03:21:32Z)
• Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
  大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。 提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
  論文  参考訳（メタデータ） (2020-12-07T14:58:16Z)

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

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