論文の概要: Incremental Updates of Generalized Hypertree Decompositions

• arxiv url: http://arxiv.org/abs/2209.10375v1
• Date: Wed, 21 Sep 2022 14:12:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-22 17:03:56.044521
• Title: Incremental Updates of Generalized Hypertree Decompositions
• Title（参考訳）: 一般化ハイパーツリー分解のインクリメンタルアップデート
• Authors: Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus
• Abstract要約: 我々は、CSP$P'$の分解を更新することで、CSP$P'$のいくつかの変更によって生成される新しいCSP$P'$の有効な分解になるよう、最初のステップを作成する。 この問題は理論上は難しいが,GHDを効果的に更新するためのフレームワークを提案し,実装する。
• 参考スコア（独自算出の注目度）: 7.082768797784365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Structural decomposition methods, such as generalized hypertree decompositions, have been successfully used for solving constraint satisfaction problems (CSPs). As decompositions can be reused to solve CSPs with the same constraint scopes, investing resources in computing good decompositions is beneficial, even though the computation itself is hard. Unfortunately, current methods need to compute a completely new decomposition even if the scopes change only slightly. In this paper, we make the first steps toward solving the problem of updating the decomposition of a CSP $P$ so that it becomes a valid decomposition of a new CSP $P'$ produced by some modification of $P$. Even though the problem is hard in theory, we propose and implement a framework for effectively updating GHDs. The experimental evaluation of our algorithm strongly suggests practical applicability.
• Abstract（参考訳）: 一般化された高木分解のような構造分解法は、制約満足度問題(CSP)の解決に成功している。 分解は、同じ制約スコープでCSPを解くために再利用できるため、計算自体が困難であるにもかかわらず、優れた分解にリソースを投資することは有益である。 残念ながら、現在の方法はスコープがわずかに変化しても完全に新しい分解を計算する必要がある。 本稿では、CSP$P$の分解を更新することで、CSP$P’$のいくつかの変更によって生成される新しいCSP$P’$の有効な分解となるように、最初のステップを作成する。 この問題は理論上は難しいが,GHDを効果的に更新するためのフレームワークを提案し,実装する。 本アルゴリズムの実験的評価は実用的適用可能性を強く示唆する。

関連論文リスト

• Global Convergence of Decentralized Retraction-Free Optimization on the Stiefel Manifold [12.414718831844041]
  そこで, DRFGT は, 対応する DRFGT 法に基づいて, 勾配のリトラクションを行うことを示す。 また、DRFGTはエージェントのネットワーク上でリトラクションを行うことができる。
  論文  参考訳（メタデータ） (2024-05-19T15:50:57Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Cooperative Coevolution for Non-Separable Large-Scale Black-Box Optimization: Convergence Analyses and Distributed Accelerations [13.750841199401613]
  我々は、よく知られた協調的共進化(CC)の大規模バージョンを非分離関数で解析し、拡張する。 本研究では,分解に基づく手法が好まれるかどうかを,非分離性な大規模問題に対して実証的に明らかにする。 私たちは、最近のマルチレベル学習フレームワークの下で、強力な分散コンピューティングを使用してそれを加速します。
  論文  参考訳（メタデータ） (2023-04-11T07:15:37Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• A Screening Strategy for Structured Optimization Involving Nonconvex $\ell_{q,p}$ Regularization [5.522202658637732]
  我々は、noll_qp$正規化を含む構造化最適化の解法において、計算効率を改善するためのルール戦略を開発する。 我々は、IRL1法の有限個の繰り返しにおいて、我々の規則がすべての不活性変数を除去できることを証明した。 数値実験は、いくつかの最先端アルゴリズムと比較して、スクリーニングルール戦略の効率を例示する。
  論文  参考訳（メタデータ） (2022-08-02T10:01:49Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• NeCPD: An Online Tensor Decomposition with Optimal Stochastic Gradient Descent [1.0953917735844645]
  マルチウェイオンラインデータに基づく$(N)Nにおける非効率的な問題に対して,NeCPDという新しい効率的な分解アルゴリズムを提案する。 さらに,本手法を構造的データセットを用いた実生活モニタリングの分野に適用する。
  論文  参考訳（メタデータ） (2020-03-18T04:44:05Z)
• Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor Products [0.8528384027684192]
  本稿では, テンソル分解法を用いて, 効率よく並列に不満足性の証明を計算する方法を示す。 1つの分解は、品質を犠牲にすることなく、半分の時間で不満足な証明をもたらす。 この方法は、任意のCSPからバイナリCSPへの、よく知られた双対および隠れ変数変換を用いて、任意のCSPに適用できる。
  論文  参考訳（メタデータ） (2020-01-31T18:06:52Z)

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

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