論文の概要: Query complexity of heavy hitter estimation
- arxiv url: http://arxiv.org/abs/2005.14425v2
- Date: Wed, 10 Feb 2021 12:18:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 23:22:48.144246
- Title: Query complexity of heavy hitter estimation
- Title（参考訳）: ヘビーヒッター推定の問合せ複雑性
- Authors: Sahasrajit Sarmasarkar, Kota Srinivas Reddy, and Nikhil Karamchandani
- Abstract要約: 我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 6.373263986460191
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of identifying the subset
$\mathcal{S}^{\gamma}_{\mathcal{P}}$ of elements in the support of an
underlying distribution $\mathcal{P}$ whose probability value is larger than a
given threshold $\gamma$, by actively querying an oracle to gain information
about a sequence $X_1, X_2, \ldots$ of $i.i.d.$ samples drawn from
$\mathcal{P}$. We consider two query models: $(a)$ each query is an index $i$
and the oracle return the value $X_i$ and $(b)$ each query is a pair $(i,j)$
and the oracle gives a binary answer confirming if $X_i = X_j$ or not. For each
of these query models, we design sequential estimation algorithms which at each
round, either decide what query to send to the oracle depending on the entire
history of responses or decide to stop and output an estimate of
$\mathcal{S}^{\gamma}_{\mathcal{P}}$, which is required to be correct with some
pre-specified large probability. We provide upper bounds on the query
complexity of the algorithms for any distribution $\mathcal{P}$ and also derive
lower bounds on the optimal query complexity under the two query models. We
also consider noisy versions of the two query models and propose robust
estimators which can effectively counter the noise in the oracle responses.
- Abstract（参考訳）: 確率値が与えられたしきい値よりも大きいような分布のサポートにおいて、部分集合 $\mathcal{S}^{\gamma}_{\mathcal{P}}$ を識別する問題は、その確率値が与えられたしきい値より大きい$\mathcal{P}$ を積極的に問合せ、列 $X_1, X_2, \ldots$ $ $i.i.d.$ のサンプルを $\mathcal{P}$ から引き出すことで得られる。
2つのクエリモデルを検討します。
(a)$ 各クエリは$i$のインデックスであり、oracleは$x_i$と$を返す。
(b)$ 各クエリは$(i,j)$のペアであり、oracleは$x_i = x_j$かどうかを確認するバイナリを返す。
それぞれの問合せモデルに対して、各ラウンドにおいて、応答の履歴全体に応じてどの問合せをオラクルに送るかを決定するか、または、事前に特定された大きな確率で修正する必要がある$\mathcal{S}^{\gamma}_{\mathcal{P}}$の見積を停止して出力するかを決定するシーケンシャルな推定アルゴリズムを設計する。
任意の分散 $\mathcal{p}$ に対するアルゴリズムの問合せ複雑性の上界を提供し、また2つの問合せモデルの下で最適な問合せ複雑性の下界を導出する。
また、2つのクエリモデルのノイズバージョンも検討し、オラクル応答のノイズを効果的に対処できるロバストな推定器を提案する。
関連論文リスト
- Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文 参考訳（メタデータ） (2024-09-17T05:56:07Z) - Parallel Sampling via Counting [3.6854430278041264]
任意の分布からのサンプリングを高速化するために並列化を用いる方法を示す。
我々のアルゴリズムは、$O(n2/3cdot operatornamepolylog(n,q))$ parallel timeである。
この結果は自己回帰モデルにおけるサンプリングに影響を及ぼす。
論文 参考訳（メタデータ） (2024-08-18T11:42:54Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
論文 参考訳（メタデータ） (2022-11-19T11:14:19Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。
一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。
情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-18T22:20:12Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。