論文の概要: Exponential Speedups by Rerooting Levin Tree Search

• arxiv url: http://arxiv.org/abs/2412.05196v1
• Date: Fri, 06 Dec 2024 17:20:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-09 15:56:26.499266
• Title: Exponential Speedups by Rerooting Levin Tree Search
• Title（参考訳）: レビン木探索による指数的高速化
• Authors: Laurent Orseau, Marcus Hutter, Levi H. S. Lelis,
• Abstract要約: Levin Tree Search (LTS) は、ユーザが指定したポリシーを使って探索を誘導する決定論的環境の探索アルゴリズムである。 我々は、検索ツリーの各ノードにルートされたLTS検索を暗黙的に開始する、$sqrttextLTS$ (pronounce root-LTS)と呼ばれる新しいアルゴリズムを導入する。 我々は、$sqrttextLTS$が持つ探索ステップの数が、再ルートの不確実性に関連する因子の価格で、サブタスクへの最良の分解と競合していることを証明する。
• 参考スコア（独自算出の注目度）: 28.0272050696211
• License:
• Abstract: Levin Tree Search (LTS) (Orseau et al., 2018) is a search algorithm for deterministic environments that uses a user-specified policy to guide the search. It comes with a formal guarantee on the number of search steps for finding a solution node that depends on the quality of the policy. In this paper, we introduce a new algorithm, called $\sqrt{\text{LTS}}$ (pronounce root-LTS), which implicitly starts an LTS search rooted at every node of the search tree. Each LTS search is assigned a rerooting weight by a (user-defined or learnt) rerooter, and the search effort is shared between all LTS searches proportionally to their weights. The rerooting mechanism implicitly decomposes the search space into subtasks, leading to significant speedups. We prove that the number of search steps that $\sqrt{\text{LTS}}$ takes is competitive with the best decomposition into subtasks, at the price of a factor that relates to the uncertainty of the rerooter. If LTS takes time $T$, in the best case with $q$ rerooting points, $\sqrt{\text{LTS}}$ only takes time $O(q\sqrt[q]{T})$. Like the policy, the rerooter can be learnt from data, and we expect $\sqrt{\text{LTS}}$ to be applicable to a wide range of domains.
• Abstract（参考訳）: Levin Tree Search (LTS) (Orseau et al , 2018) は、ユーザが指定したポリシーを使って検索を誘導する決定論的環境の探索アルゴリズムである。 これは、ポリシーの品質に依存するソリューションノードを見つけるための検索ステップの数に関する正式な保証が付属している。 本稿では,検索ツリーの各ノードにルートされたLTS検索を暗黙的に開始する,$\sqrt{\text{LTS}}$(pronounce root-LTS)という新しいアルゴリズムを提案する。 各LTS検索は(ユーザ定義または学習した)再ルートによって再ルートウェイトを割り当て、検索作業はその重みに比例してすべてのLTS検索間で共有される。 再ルート機構は暗黙的にサーチスペースをサブタスクに分解し、大幅なスピードアップをもたらす。 我々は、$\sqrt{\text{LTS}}$が持つ探索ステップの数が、再ルートの不確実性に関連する因子の価格で、サブタスクへの最良の分解と競合することを証明する。 LTSが$T$を取るなら、$q$再ルートポイントのベストケースでは、$\sqrt{\text{LTS}}$は$O(q\sqrt[q]{T})$のみを取る。 このポリシーと同様に、rerooterはデータから学ぶことができ、$\sqrt{\text{LTS}}$が幅広いドメインに適用できることを期待しています。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Fast Exact Retrieval for Nearest-neighbor Lookup (FERN) [0.0]
  厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 近距離近傍探索(FERN)のための対数的高速エクササイズ検索のための新しいアルゴリズムを提案する。 このアルゴリズムは1000万ドルの$d=128$に対して100%リコールした$O(dlog N)$ルックアップを達成する。
  論文  参考訳（メタデータ） (2024-05-07T15:57:39Z)
• A Bi-directional Quantum Search Algorithm [30.62704006898929]
  本稿では、パーシャルグローバーの探索アルゴリズムと双方向探索を組み合わせて、高速グローバーの量子探索アルゴリズムを作成する。 両方向探索手法をGrover部分探索に組み込み,初期状態と1つのマーク付き状態を並列に比較した。 提案したBDGSアルゴリズムは、最先端のDepth-First Grover's Search (DFGS) とジェネリックGrover's Search (GS) の実装を2〜20ドルでベンチマークする。
  論文  参考訳（メタデータ） (2024-04-24T03:11:10Z)
• Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
  Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2023-02-07T22:58:12Z)
• A Nearly Tight Analysis of Greedy k-means++ [1.452875650827562]
  k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。 我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
  論文  参考訳（メタデータ） (2022-07-16T13:49:07Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• 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)
• Grover's search algorithm for $n$ qubits with optimal number of iterations [0.0]
  グローバーの探索アルゴリズムは、グローバーの拡散操作に続くオラクルの合成操作の繰り返し数に依存する。 1leq M leq N$ターゲット状態を持つ$n$-qubit Groverの探索アルゴリズムを構築するための一般的なスキームを示す。
  論文  参考訳（メタデータ） (2020-11-08T18:46:50Z)

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

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