論文の概要: Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor Products

• arxiv url: http://arxiv.org/abs/2002.03766v1
• Date: Fri, 31 Jan 2020 18:06:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-05 06:40:27.484974
• Title: Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor Products
• Title（参考訳）: テンソル製品による制約満足度問題の不適合性試験
• Authors: Daya Gaur and Muhammad Khan
• Abstract要約: 本稿では, テンソル分解法を用いて, 効率よく並列に不満足性の証明を計算する方法を示す。 1つの分解は、品質を犠牲にすることなく、半分の時間で不満足な証明をもたらす。 この方法は、任意のCSPからバイナリCSPへの、よく知られた双対および隠れ変数変換を用いて、任意のCSPに適用できる。
• 参考スコア（独自算出の注目度）: 0.8528384027684192
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the design of stochastic local search methods to prove unsatisfiability of a constraint satisfaction problem (CSP). For a binary CSP, such methods have been designed using the microstructure of the CSP. Here, we develop a method to decompose the microstructure into graph tensors. We show how to use the tensor decomposition to compute a proof of unsatisfiability efficiently and in parallel. We also offer substantial empirical evidence that our approach improves the praxis. For instance, one decomposition yields proofs of unsatisfiability in half the time without sacrificing the quality. Another decomposition is twenty times faster and effective three-tenths of the times compared to the prior method. Our method is applicable to arbitrary CSPs using the well known dual and hidden variable transformations from an arbitrary CSP to a binary CSP.
• Abstract（参考訳）: 制約満足度問題(csp)の満足度を証明する確率的局所探索法の設計について検討した。 バイナリCSPでは、これらの手法はCSPのマイクロ構造を用いて設計されている。 本稿では,微細構造をグラフテンソルに分解する方法を開発した。 テンソル分解を用いて, 効率的に並列に不満足性の証明を計算する方法を示す。 また、我々のアプローチがPraxisを改善するという実証的な証拠も提供します。 例えば、ある分解は品質を犠牲にすることなく半分の時間で満足できない証明を得る。 もう1つの分解は、従来の方法に比べて20倍速く、有効な3倍の時間である。 本手法は任意の csp からバイナリ csp へのよく知られた双対および隠れ変数変換を用いて任意の csp に適用できる。

関連論文リスト

• Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
  政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。 本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
  論文  参考訳（メタデータ） (2023-11-15T12:36:45Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization [26.218670461973705]
  非漸近勾配ノルム保証を協調する問題の解法を提案する。 本研究は,ニューラルネットの深部学習における循環還元方式の有効性を実証するものである。
  論文  参考訳（メタデータ） (2022-12-09T19:17:39Z)
• Incremental Updates of Generalized Hypertree Decompositions [7.082768797784365]
  我々は、CSP$P'$の分解を更新することで、CSP$P'$のいくつかの変更によって生成される新しいCSP$P'$の有効な分解になるよう、最初のステップを作成する。 この問題は理論上は難しいが,GHDを効果的に更新するためのフレームワークを提案し,実装する。
  論文  参考訳（メタデータ） (2022-09-21T14:12:16Z)
• Finite-rate sparse quantum codes aplenty [1.1279808969568252]
  本稿では、ランダムな二部グラフ上の制約満足度問題(CSP)を解決するために、ランダムなマルチキュービット安定化器符号を生成する手法を提案する。 現状のCSPソルバを用いて、満足度しきい値の存在を証明できる証拠を得る。 良好な位相にあるスパース符号は、消去ノイズのチャネル容量を実質的に達成する。
  論文  参考訳（メタデータ） (2022-07-07T20:39:39Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  本稿では,潜伏変数と選択バイアスの存在下での観測データからシステムの因果MAGを学習する問題を考察する。 本稿では,音と完全性を備えた計算効率のよい制約ベースの新しい手法を提案する。 提案手法と人工と実世界の両方の構造に関する技術の現状を比較した実験結果を提供する。
  論文  参考訳（メタデータ） (2021-10-22T19:49:59Z)
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs [84.7328507118758]
  構造学習のためのBregman近位勾配法を開発した。 高い非線形反復に対する曲率の影響を計測する。 様々な合成および実集合上で本手法をテストする。
  論文  参考訳（メタデータ） (2020-11-05T11:37:44Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)

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

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