論文の概要: 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$で使用するターンタイルストリームに対して、カラムサブセット選択、部分空間近似、射影クラスタリング、ボリューム最大化のための最初の相対エラーアルゴリズムを提供する。
我々は,マルチパスアルゴリズムにおいても,低次項まで厳密な境界を持つボリューム最大化アルゴリズムを補完する。
また、同様の構成により、競合上界と一致する行-アリーモデルにおける体積最大化のための下限を得る。
完全な要約は紙を参照。
関連論文リスト
- Stochastic optimization with arbitrary recurrent data sampling [2.5382095320488673]
最も一般的に使われているデータサンプリングアルゴリズムは、軽度な仮定の下にある。
特定のクラスの繰り返し最適化アルゴリズムに対して、他のプロパティは不要であることを示す。
我々は,データセットをカバーするサンプリングアルゴリズムを選択することで,収束を加速できることを示す。
論文 参考訳(メタデータ) (2024-01-15T14:04:50Z) - Weighted Sparse Partial Least Squares for Joint Sample and Feature
Selection [7.219077740523681]
本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。
我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
論文 参考訳(メタデータ) (2023-08-13T10:09:25Z) - 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) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。