論文の概要: Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds

• arxiv url: http://arxiv.org/abs/2608.02176v1
• Date: Mon, 03 Aug 2026 12:56:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-04 15:07:25.570305
• Title: Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
• Title（参考訳）: ランダム化アルゴリズムによる一定ラウンドにおける最適クエリ複素数近傍の分割の学習
• Abstract要約: ペアクエリ: PAIR($x,y$)は、$x$と$y$がパーティションの同じ部分に属しているかどうかを教えてくれます。 確率の高い$O(nklog n)$クエリを使って単純な3ラウンドランダム化アルゴリズムを与え、2ラウンドは決定論的アルゴリズムと同じ$(n4/3k2/3)$クエリを必要とすることを証明した。
• 参考スコア（独自算出の注目度）: 5.302996125520601
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the round complexity of learning a hidden partition $\mathcal{P}$ of an $n$-element universe using PAIR queries: PAIR($x,y$) tells us whether $x$ and $y$ belong to the same part of the partition or not. While it is easy to learn using $n|\mathcal{P}|$ queries using a basic algorithm and this query complexity is optimal, this basic algorithm is highly sequential. Black, Mazumdar, and Saha [COLT 2025] recently gave tight deterministic round/query tradeoffs when the number of parts of $\mathcal{P}$ is known. In particular they prove $Θ(\log\log n)$ rounds are sufficient and necessary to limit the number of queries to $n|\mathcal{P}|$. They leave proving a randomized lower bound as an open direction. We show that randomization dramatically changes the picture. When the number of parts $k = |\mathcal{P}|$ is known, we give a simple 3-round randomized algorithm using $O(nk\log n)$ queries with high probability, and prove that 2 rounds require $Ω(n^{4/3}k^{2/3})$ queries -- the same as deterministic algorithms. We also study a more general setting where the number of parts is unknown. In this case, we give a 4-round randomized algorithm using $O(n|\mathcal P|\log^2 n)$ queries with high probability, and prove that 3-rounds cannot achieve near-optimal query complexity. Furthermore, we show an even bigger separation in this regime between randomized and deterministic algorithms: for the latter, $Θ(\log n/\log\log n)$ rounds are necessary and sufficient to obtain near-optimal query complexity.
• Abstract（参考訳）: PAIR($x,y$)は、$x$と$y$がパーティションの同じ部分に属しているかどうかを教えてくれます。 基本アルゴリズムを用いて$n|\mathcal{P}|$クエリを学習することは容易であるが、このクエリの複雑さは最適であるが、この基本アルゴリズムは非常に逐次的である。 Black, Mazumdar, Saha [COLT 2025]は、最近$\mathcal{P}$の部品数を知ると、厳密な決定論的ラウンド/クエリのトレードオフを行った。 特に、$(\log\log n)$のラウンドは十分であり、クエリの数を$n|\mathcal{P}|$に制限する必要があることを証明している。 彼らは無作為な下界を開方向として証明する。 ランダム化によって画像が劇的に変化することを示す。 部品数$k = |\mathcal{P}|$が知られているとき、確率の高い$O(nk\log n)$クエリを使って単純な3ラウンドランダム化アルゴリズムを与え、2ラウンドは決定論的アルゴリズムと同じ$Ω(n^{4/3}k^{2/3})$クエリを必要とすることを証明する。 また、部品の数が不明なより一般的な設定についても検討する。 この場合、確率の高い$O(n|\mathcal P|\log^2 n)$クエリを用いて、4ラウンドのランダム化アルゴリズムを与え、3ラウンドがほぼ最適なクエリ複雑性を達成できないことを示す。 さらに、ランダム化アルゴリズムと決定論的アルゴリズムの間には、さらに大きな分離があることが示される:後者の場合、$(\log n/\log n)$ラウンドは、ほぼ最適なクエリ複雑性を得るのに必要で十分である。

関連論文リスト

• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。 まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。 決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
  論文  参考訳（メタデータ） (2026-07-21T00:40:59Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。 クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。 このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
  論文  参考訳（メタデータ） (2026-01-07T22:07:44Z)
• Quantum Search on Computation Trees [0.0]
  モンタナロ(ToC)によるバックトラック木探索のための量子ウォークアルゴリズムの一般化を示す。 このフレームワークは、変数時間探索、量子分割と圧縮、爆弾クエリアルゴリズムなど、他の多くの量子フレームワークを再定義するための、簡単で便利な方法を提供する。
  論文  参考訳（メタデータ） (2025-05-28T14:35:18Z)
• Learning Partitions with Optimal Query and Round Complexities [16.815943270621638]
  未知の$n$要素を少なくとも$k$集合に分割することの基本的な問題を考える。 非適応アルゴリズムには$Theta(n2)$クエリが必要ですが、適応アルゴリズムには$Theta(nk)$クエリが必要です。 我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(log log n)$ラウンドしか必要としない。
  論文  参考訳（メタデータ） (2025-05-08T07:27:29Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。 我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
  論文  参考訳（メタデータ） (2024-05-08T02:17:10Z)
• 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)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。 本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
  論文  参考訳（メタデータ） (2021-05-18T06:51:11Z)
• Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
  語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。 LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-17T03:13:45Z)
• 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)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。 任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
  論文  参考訳（メタデータ） (2019-12-29T01:42:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。