論文の概要: On a Near-Optimal \& Efficient Algorithm for the Sparse Pooled Data
Problem
- arxiv url: http://arxiv.org/abs/2312.14588v1
- Date: Fri, 22 Dec 2023 10:24:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-25 15:31:31.376155
- Title: On a Near-Optimal \& Efficient Algorithm for the Sparse Pooled Data
Problem
- Title（参考訳）: Sparse Pooled Data 問題に対する準最適 \& Efficient アルゴリズムについて
- Authors: Max Hahn-Klimroth, Remco van der Hofstad, Noela M\"uller, Connor
Riddlesden
- Abstract要約: プールされたデータ問題は、凝縮された測定値から、アイテムのセットの未知のラベルを特定するように要求する。
SIGMA$ の 0 でないエントリの数が $k sim ntheta$ for $theta in (0,1)$ である場合、プールされたデータ問題はスパース(sparse)と呼ぶ。
最も基本的な問題は、SIGMA$を高い確率で再構築しながら、できるだけ少数のプールを使用するプーリングスキームを設計することである。
- 参考スコア（独自算出の注目度）: 3.1591462359227136
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The pooled data problem asks to identify the unknown labels of a set of items
from condensed measurements. More precisely, given $n$ items, assume that each
item has a label in $\cbc{0,1,\ldots, d}$, encoded via the ground-truth
$\SIGMA$. We call the pooled data problem sparse if the number of non-zero
entries of $\SIGMA$ scales as $k \sim n^{\theta}$ for $\theta \in (0,1)$. The
information that is revealed about $\SIGMA$ comes from pooled measurements,
each indicating how many items of each label are contained in the pool. The
most basic question is to design a pooling scheme that uses as few pools as
possible, while reconstructing $\SIGMA$ with high probability. Variants of the
problem and its combinatorial ramifications have been studied for at least 35
years. However, the study of the modern question of \emph{efficient} inference
of the labels has suggested a statistical-to-computational gap of order $\log
n$ in the minimum number of pools needed for theoretically possible versus
efficient inference. In this article, we resolve the question whether this
$\log n$-gap is artificial or of a fundamental nature by the design of an
efficient algorithm, called \algoname, based upon a novel pooling scheme on a
number of pools very close to the information-theoretic threshold.
- Abstract（参考訳）: プールデータ問題は、凝縮された測定値から、一連の未知のラベルを識別することを要求する。
より正確には、$n$ アイテムが与えられたとき、各アイテムが$\cbc{0,1,\ldots, d}$ というラベルを持つと仮定する。
もし$\sigma$のゼロでないエントリ数が$\theta \in (0,1)$に対して$k \sim n^{\theta}$であるなら、プールデータ問題 sparse と呼ぶ。
$\SIGMA$に関する情報はプールされた測定値から得られ、各ラベルのアイテムがプールに含まれているかを示す。
最も基本的な問題は、できるだけ少数のプールを使用するプーリングスキームを設計し、高い確率で$\SIGMA$を再構築することである。
問題の変種とその組合せの分岐は少なくとも35年間研究されてきた。
しかし、ラベルの 'emph{efficient} 推論に関する現代の問題の研究は、理論上可能か効率の良い推論に必要となるプールの最小数の$$\log n$の統計的-計算的ギャップを示唆している。
本稿では,この$\log n$-gapが人工的か,あるいは,情報理論のしきい値に非常に近い複数のプール上の新しいプールプール方式に基づいて,効率的なアルゴリズムである \algoname を設計することで,基本的な問題を解決する。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Active Local Learning [22.823171570933397]
クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。
特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。
これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
論文 参考訳（メタデータ） (2020-08-31T05:39:35Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Efficient active learning of sparse halfspaces with arbitrary bounded
noise [34.406103025985445]
我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。
高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。
これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2020-02-12T08:28:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。