論文の概要: Local search for valued constraint satisfaction parameterized by treedepth

• arxiv url: http://arxiv.org/abs/2405.12410v1
• Date: Mon, 20 May 2024 23:28:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-22 14:47:55.555905
• Title: Local search for valued constraint satisfaction parameterized by treedepth
• Title（参考訳）: 木深度パラメータによる値制約満足度の局所探索
• Authors: Artem Kaznatcheev,
• Abstract要約: 局所探索アルゴリズムは局所ピークを効率的に見つけることができない。 重度制約満足度問題(VCSP)によるフィットネスランドスケープの上昇構造の検討 loglog treedepthではsuperpolynomial ascentsが存在し、polylog treedepthでは、すべてのAscentsがsuperpolynomialである初期割り当てがある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sometimes local search algorithms cannot efficiently find even local peaks. To understand why, I look at the structure of ascents in fitness landscapes from valued constraint satisfaction problems (VCSPs). Given a VCSP with a constraint graph of treedepth $d$, I prove that from any initial assignment there always exists an ascent of length $2^{d + 1} \cdot n$ to a local peak. This means that short ascents always exist in fitness landscapes from constraint graphs of logarithmic treedepth, and thus also for all VCSPs of bounded treewidth. But this does not mean that local search algorithms will always find and follow such short ascents in sparse VCSPs. I show that with loglog treedepth, superpolynomial ascents exist; and for polylog treedepth, there are initial assignments from which all ascents are superpolynomial. Together, these results suggest that the study of sparse VCSPs can help us better understand the barriers to efficient local search.
• Abstract（参考訳）: 時折、局所探索アルゴリズムは局所的なピークを効率的に見つけることができない。 その理由を理解するため、VCSP(価値制約満足度問題)からフィットネスランドスケープの上昇構造を考察する。 木深$d$の制約グラフを持つ VCSP が与えられたとき、任意の初期割り当てから、常に局所ピークまでの長さ 2^{d + 1} \cdot n$ の上昇が存在することを証明します。 これは、対数木深度の制約グラフから常にフィットネスランドスケープに存在することを意味し、したがって有界木幅のすべてのVCSPに対してもである。 しかし、これは、ローカルな検索アルゴリズムが、まばらなVCSPの短い上昇を常に見つけ、追跡するという意味ではない。 loglog treedepthではsuperpolynomial ascentsが存在し、polylog treedepthでは、すべてのAscentsがsuperpolynomialである初期割り当てがある。 これらの結果は、スパースVCSPの研究が、効率的な局所探索の障壁を理解するのに役立つことを示唆している。

関連論文リスト

• Pathfinding with Lazy Successor Generation [12.02023514105999]
  位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。 単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。 そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
  論文  参考訳（メタデータ） (2024-08-27T23:25:25Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• The Effect of Points Dispersion on the $k$-nn Search in Random Projection Forests [1.376408511310322]
  パーティショニングツリーは、$k$-nearest 隣のサーチのための効率的なデータ構造である。 $k$d-treesはベクトル量子化(VQ)誤差を減らすためにより多くの木レベルを必要とするため、高次元では非効率である。 木が多くなると、点の分散は$k$-nn 探索に非常に限定的な影響を及ぼす。
  論文  参考訳（メタデータ） (2023-02-25T20:57:06Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。 Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
  論文  参考訳（メタデータ） (2022-09-28T09:55:47Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks [70.0197695666261]
  Q*検索は,ノードの子どもの移動コストと値の和を利用するために,深いQ-networksを用いて探索をガイドする検索アルゴリズムである。 我々は1872のメタアクションを含む大きなアクション空間で定式化された場合、Q*探索を用いてルービックキューブを解く。 Q*検索は最大129倍速く、A*検索の最大1288倍のノードを生成する。
  論文  参考訳（メタデータ） (2021-02-08T20:36:41Z)
• Solving the Steiner Tree Problem with few Terminals [8.024778381207128]
  動的プログラミングによるスタイナーツリー問題の解法として、Dijkstra-Steinerアルゴリズムがある。 我々はDijkstra-Steinerアルゴリズムを強化し、DS*と呼ばれる再検討アルゴリズムを確立する。 そこで本研究では,DS* アルゴリズムの適合性は整合性よりも弱いことを示し,許容関数を用いた場合の正当性を確立する。
  論文  参考訳（メタデータ） (2020-11-09T17:46:02Z)
• Decision trees as partitioning machines to characterize their generalization properties [2.370481325034443]
  データの分割の観点から、実値の特徴について二分決定木を再検討する。 内部ノードが$N$である二分木構造のVC次元が$N log(Nell)$であることを示す。 我々は,これらの結果に基づいて,多数のデータセット上でのCARTアルゴリズムよりも優れたプルーニングアルゴリズムを詳述する。
  論文  参考訳（メタデータ） (2020-10-14T19:25:58Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。 低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
  論文  参考訳（メタデータ） (2020-10-13T17:26:09Z)

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

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