論文の概要: Learning Partitions with Optimal Query and Round Complexities
- arxiv url: http://arxiv.org/abs/2505.05009v1
- Date: Thu, 08 May 2025 07:27:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-07 02:47:44.228715
- Title: Learning Partitions with Optimal Query and Round Complexities
- Title（参考訳）: 最適クエリとラウンド複雑度を用いた分割学習
- Authors: Hadley Black, Arya Mazumdar, Barna Saha,
- Abstract要約: 未知の$n$要素を少なくとも$k$集合に分割することの基本的な問題を考える。
非適応アルゴリズムには$Theta(n2)$クエリが必要ですが、適応アルゴリズムには$Theta(nk)$クエリが必要です。
我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(log log n)$ラウンドしか必要としない。
- 参考スコア（独自算出の注目度）: 16.815943270621638
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the basic problem of learning an unknown partition of $n$ elements into at most $k$ sets using simple queries that reveal information about a small subset of elements. Our starting point is the well-studied pairwise same-set queries which ask if a pair of elements belong to the same class. It is known that non-adaptive algorithms require $\Theta(n^2)$ queries, while adaptive algorithms require $\Theta(nk)$ queries, and the best known algorithm uses $k-1$ rounds. This problem has been studied extensively over the last two decades in multiple communities due to its fundamental nature and relevance to clustering, active learning, and crowd sourcing. In many applications, it is of high interest to reduce adaptivity while minimizing query complexity. We give a complete characterization of the deterministic query complexity of this problem as a function of the number of rounds, $r$, interpolating between the non-adaptive and adaptive settings: for any constant $r$, the query complexity is $\Theta(n^{1+\frac{1}{2^r-1}}k^{1-\frac{1}{2^r-1}})$. Our algorithm only needs $O(\log \log n)$ rounds to attain the optimal $O(nk)$ query complexity. Next, we consider two generalizations of pairwise queries to subsets $S$ of size at most $s$: (1) weak subset queries which return the number of classes intersected by $S$, and (2) strong subset queries which return the entire partition restricted on $S$. Once again in crowd sourcing applications, queries on large sets may be prohibitive. For non-adaptive algorithms, we show $\Omega(n^2/s^2)$ strong queries are needed. Perhaps surprisingly, we show that there is a non-adaptive algorithm using weak queries that matches this bound up to log-factors for all $s \leq \sqrt{n}$. More generally, we obtain nearly matching upper and lower bounds for algorithms using subset queries in terms of both the number of rounds, $r$, and the query size bound, $s$.
- Abstract（参考訳）: 簡単なクエリを使って、未知の$n$要素を少なくとも$k$集合に分割し、要素の小さな部分集合に関する情報を明らかにするという基本的な問題を考える。
私たちの出発点は、一対の要素が同じクラスに属するかどうかを問う、よく研究されたペアワイズな同セットクエリです。
非適応アルゴリズムは$\Theta(n^2)$クエリを必要とし、適応アルゴリズムは$\Theta(nk)$クエリを必要とし、最もよく知られているアルゴリズムは$k-1$ラウンドを使用する。
この問題は、クラスタリング、アクティブラーニング、クラウドソーシングといった基本的な性質と関連性から、過去20年間に複数のコミュニティで広く研究されてきた。
多くのアプリケーションにおいて、クエリの複雑さを最小限に抑えながら適応性を低下させることが大きな関心事である。
任意の定数$r$に対して、クエリ複雑性は$\Theta(n^{1+\frac{1}{2^r-1}}k^{1-\frac{1}{2^r-1}})$である。
我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(\log \log n)$ラウンドしか必要としない。
次に、ペアワイズクエリを2つのサブセットに一般化する。$S$: (1)$S$で区切られたクラスの数を返す弱いサブセットクエリ、(2)$S$で制限されたパーティション全体を返す強いサブセットクエリ。
クラウドソーシングのアプリケーションでは、大きなセットのクエリは禁じられるかもしれない。
非適応アルゴリズムでは、$\Omega(n^2/s^2)$ strong queryが必要である。
意外なことに、弱いクエリを使った非適応アルゴリズムが、すべての$s \leq \sqrt{n}$のログファクタに一致している。
より一般的には、ラウンド数、$r$およびクエリサイズ、$s$の両方の観点から、サブセットクエリを使ってアルゴリズムの上限値と下限値にほぼ一致する値を得る。
関連論文リスト
- Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文 参考訳（メタデータ） (2024-09-17T05:56:07Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - 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) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Query complexity of heavy hitter estimation [6.373263986460191]
我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-05-29T07:15:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。