論文の概要: Evidence for Long-Tails in SLS Algorithms

• arxiv url: http://arxiv.org/abs/2107.00378v1
• Date: Thu, 1 Jul 2021 11:31:39 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-02 19:05:54.161839
• Title: Evidence for Long-Tails in SLS Algorithms
• Title（参考訳）: SLSアルゴリズムにおけるLong-Tailsのエビデンス
• Authors: Florian W\"orz and Jan-Hendrik Lorenz
• Abstract要約: 局所探索(SLS)は命題論理の満足度問題を解くためのパラダイムとして成功している。 この領域における最近の開発には、オリジナルのインスタンスではなく、修正されたが論理的に等価なインスタンスを解くことが含まれる。 本稿では,この手法がSLSソルバのランタイムに与える影響について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic local search (SLS) is a successful paradigm for solving the satisfiability problem of propositional logic. A recent development in this area involves solving not the original instance, but a modified, yet logically equivalent one. Empirically, this technique was found to be promising as it improves the performance of state-of-the-art SLS solvers. Currently, there is only a shallow understanding of how this modification technique affects the runtimes of SLS solvers. Thus, we model this modification process and conduct an empirical analysis of the hardness of logically equivalent formulas. Our results are twofold. First, if the modification process is treated as a random process, a lognormal distribution perfectly characterizes the hardness; implying that the hardness is long-tailed. This means that the modification technique can be further improved by implementing an additional restart mechanism. Thus, as a second contribution, we theoretically prove that all algorithms exhibiting this long-tail property can be further improved by restarts. Consequently, all SAT solvers employing this modification technique can be enhanced.
• Abstract（参考訳）: 確率的局所探索(SLS)は命題論理の満足度問題を解くために成功したパラダイムである。 この領域における最近の開発は、元のインスタンスではなく、修正されながら論理的に等価なインスタンスを解決することである。 この技術は,最先端のSLS解法の性能向上に有効であることが実証された。 現在、この修正手法がSLSソルバのランタイムにどのように影響するかは理解されていない。 したがって、この修正過程をモデル化し、論理的に等価な公式の硬さを実証的に分析する。 私たちの結果は2倍です。 まず、修正プロセスがランダムなプロセスとして扱われる場合、対数正規分布は、硬さを完全に特徴づけ、硬さが長いことを暗示する。 これにより、追加の再起動機構を実装することにより、修正技術をさらに改善することができる。 したがって、この長尾特性を示す全てのアルゴリズムが再起動によってさらに改善できることを理論的に証明する。 これにより、この改良技術を用いたSATソルバを全て強化することができる。

関連論文リスト

• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Directed Acyclic Graphs With Tears [8.774590352292932]
  DAGs with Tearsはmix-integerプログラミングに基づく新しいタイプの構造学習である。 本研究では,課題1の理由を理論的に分析し,混合整数計画法に基づくDAGs with Tears法という新しい手法を提案する。 さらに, 先行知識を新たな手法に取り入れることで, 産業プロセスにおいて構造学習をより実用的で有用なものにすることができる。
  論文  参考訳（メタデータ） (2023-02-04T13:00:52Z)
• Towards an Understanding of Long-Tailed Runtimes of SLS Algorithms [0.0]
  GapSATソルバは、SLSソルバの性能を平均的に向上させる方法として、追加情報を学習した。 本稿では論理的に等価な問題定式化を生成する方法を提案する。 シュオニングのランダムウォークアルゴリズムのランタイムは約 Johnson SB であることを示す。
  論文  参考訳（メタデータ） (2022-10-24T12:22:25Z)
• Linear Temporal Logic Modulo Theories over Finite Traces (Extended Version) [72.38188258853155]
  有限トレース(LTLf)上の線形時間論理について検討する。 命題の文字は任意の理論で解釈された一階述語式に置き換えられる。 Satisfiability Modulo Theories (LTLfMT) と呼ばれる結果の論理は半決定可能である。
  論文  参考訳（メタデータ） (2022-04-28T17:57:33Z)
• Bolstering Stochastic Gradient Descent with Model Building [0.0]
  勾配降下法とその変種は、優れた収束率を達成するためのコア最適化アルゴリズムを構成する。 本稿では,前方ステップモデル構築に基づく新しいアルゴリズムを用いて,線探索の代替手法を提案する。 提案アルゴリズムは、よく知られたテスト問題において、より高速な収束とより優れた一般化を実現する。
  論文  参考訳（メタデータ） (2021-11-13T06:54:36Z)
• Learning to solve TV regularized problems with unrolled algorithms [18.241062505073234]
  トータル・バージョニング(Total Variation、TV)は、一方向定値信号を促進する一般的な正規化戦略である。 そこで我々は,2つのアプローチを開発し,そのメリットと限界を記述し,反復的な手順よりも実際に改善できる体制について議論する。
  論文  参考訳（メタデータ） (2020-10-19T14:19:02Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。 このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。 また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
  論文  参考訳（メタデータ） (2020-10-13T08:02:38Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)

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

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