論文の概要: Exploration with Limited Memory: Streaming Algorithms for Coin Tossing,
Noisy Comparisons, and Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2004.04666v1
- Date: Thu, 9 Apr 2020 16:54:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-15 03:30:16.578742
- Title: Exploration with Limited Memory: Streaming Algorithms for Coin Tossing,
Noisy Comparisons, and Multi-Armed Bandits
- Title（参考訳）: 限定記憶による探索:コイントスキング,雑音比較,マルチアーマッド帯域に対するストリーミングアルゴリズム
- Authors: Sepehr Assadi, Chen Wang
- Abstract要約: バイアスが未知の$n$コインが与えられた場合、最小限のコイントスを用いて最もバイアスの多いコインを見つける。
大量のデータセットを処理するための応用によって動機付けられ、最適なコイントス数でこの問題を解決するための空間的複雑さについて研究する。
- 参考スコア（独自算出の注目度）: 8.966425067585108
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the following abstract coin tossing problem: Given a set of $n$
coins with unknown biases, find the most biased coin using a minimal number of
coin tosses. This is a common abstraction of various exploration problems in
theoretical computer science and machine learning and has been studied
extensively over the years. In particular, algorithms with optimal sample
complexity (number of coin tosses) have been known for this problem for quite
some time.
Motivated by applications to processing massive datasets, we study the space
complexity of solving this problem with optimal number of coin tosses in the
streaming model. In this model, the coins are arriving one by one and the
algorithm is only allowed to store a limited number of coins at any point --
any coin not present in the memory is lost and can no longer be tossed or
compared to arriving coins. Prior algorithms for the coin tossing problem with
optimal sample complexity are based on iterative elimination of coins which
inherently require storing all the coins, leading to memory-inefficient
streaming algorithms.
We remedy this state-of-affairs by presenting a series of improved streaming
algorithms for this problem: we start with a simple algorithm which require
storing only $O(\log{n})$ coins and then iteratively refine it further and
further, leading to algorithms with $O(\log\log{(n)})$ memory, $O(\log^*{(n)})$
memory, and finally a one that only stores a single extra coin in memory -- the
same exact space needed to just store the best coin throughout the stream.
Furthermore, we extend our algorithms to the problem of finding the $k$ most
biased coins as well as other exploration problems such as finding top-$k$
elements using noisy comparisons or finding an $\epsilon$-best arm in
stochastic multi-armed bandits, and obtain efficient streaming algorithms for
these problems.
- Abstract（参考訳）: 以下の抽象的なコイントスリング問題を考える: 未知のバイアスを持つ$n$コインのセットが与えられたとき、最小数のコイントスを使用して最も偏りのあるコインを見つける。
これは理論計算機科学と機械学習における様々な探索問題の共通の抽象化であり、長年にわたって広く研究されてきた。
特に、最適なサンプル複雑性(コイントスの数)を持つアルゴリズムは、この問題に対してかなり前から知られていた。
大規模データセット処理への応用により、ストリーミングモデルにおいて最適なコイントス数でこの問題を解決するための空間的複雑さについて検討する。
このモデルでは、コインは1枚ずつ到着し、アルゴリズムは任意の時点で限られた数のコインしか保存できない。
最適なサンプル複雑性を伴うコイン投げ問題の以前のアルゴリズムは、コインを全て保存する必要のある反復的な排除に基づいているため、メモリ非効率なストリーミングアルゴリズムに繋がる。
まず、$o(\log{n})$コインのみを保存し、その後、さらに繰り返し精錬する簡単なアルゴリズムから始め、$o(\log\log{(n)})$メモリ、$o(\log^*{(n)})$メモリ、そして最後に1つの追加コインだけをメモリに格納するアルゴリズムへと至ります。
さらに、我々はアルゴリズムを、最も偏りが強いコインの$k$や、ノイズ比較を用いた上位$k$要素の探索問題、確率的マルチアームバンディットにおける$\epsilon$-bestアームの発見の問題にまで拡張し、これらの問題に対する効率的なストリーミングアルゴリズムを得る。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。
一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
論文 参考訳（メタデータ） (2022-10-20T19:35:50Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
論文 参考訳（メタデータ） (2022-05-27T14:50:45Z) - High robustness quantum walk search algorithm with qudit Householder
traversing coin, machine learning study [0.0]
本研究では,一般世帯反射法と位相乗算器を用いて構築したウォークコインを用いたランダムウォーク探索アルゴリズムについて検討した。
コインレジスタは任意の次元を持つ1つのキューディットである。モンテカルロシミュレーションは、教師付き機械学習と組み合わせて、量子アルゴリズムがコインのパラメータの偏差に対してより堅牢になるウォークコインを見つけるために使用される。
論文 参考訳（メタデータ） (2021-11-21T23:58:17Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。