論文の概要: Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

• arxiv url: http://arxiv.org/abs/2201.02018v2
• Date: Wed, 17 May 2023 19:20:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-19 21:09:11.204089
• Title: Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective
• Title（参考訳）: 重み付きcspsのスーパーリパラメトリゼーション:特性と最適化の展望
• Authors: Tom\'a\v{s} Dlask, Tom\'a\v{s} Werner, Simon de Givry
• Abstract要約: スーパーレパラメトリゼーションの理論的性質をいくつか提示し、それをリパラメトリゼーションの理論特性と比較する。 超並列化を用いたWCSPの最適値に関する上限計算フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 1.933681537640272
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The notion of reparametrizations of Weighted CSPs (WCSPs) (also known as equivalence-preserving transformations of WCSPs) is well-known and finds its use in many algorithms to approximate or bound the optimal WCSP value. In contrast, the concept of super-reparametrizations (which are changes of the weights that keep or increase the WCSP objective for every assignment) was already proposed but never studied in detail. To fill this gap, we present a number of theoretical properties of super-reparametrizations and compare them to those of reparametrizations. Furthermore, we propose a framework for computing upper bounds on the optimal value of the (maximization version of) WCSP using super-reparametrizations. We show that it is in principle possible to employ arbitrary (under some technical conditions) constraint propagation rules to improve the bound. For arc consistency in particular, the method reduces to the known Virtual AC (VAC) algorithm. We implemented the method for singleton arc consistency (SAC) and compared it to other strong local consistencies in WCSPs on a public benchmark. The results show that the bounds obtained from SAC are superior for many instance groups.
• Abstract（参考訳）: 重み付きCSP(WCSP)の再パラメータ化の概念(WCSPの同値保存変換とも呼ばれる)はよく知られており、最適なWCSP値の近似や有界化に多くのアルゴリズムで用いられている。 対照的にスーパーリパラメトリゼーション(wcspの目標を各割り当てに維持または増やす重みの変化)の概念は既に提案されていたが、詳細は研究されなかった。 このギャップを埋めるために、超再パラメータ化の理論的性質をいくつか提示し、再パラメータ化の理論特性と比較する。 さらに,スーパーリパラメトリゼーションを用いたwcspの最適値の上限を計算するためのフレームワークを提案する。 任意の制約伝達ルール(技術的条件下では)を原則として適用して境界値を改善することは可能であることを示す。 特にアーク整合性については、この手法は既知の仮想AC(VAC)アルゴリズムに還元される。 我々はSAC(Singleton arc consistency)法を実装し,WCSPの他の強力な局所成分と比較した。 その結果、SACから得られる境界は、多くの事例群よりも優れていることがわかった。

関連論文リスト

• Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation [58.288682735160585]
  Low-Rank Adaptation (LoRA) は、ファインチューニングモデルの一般的なテクニックである。 LoRAは、フルパラメータの微調整と比較すると、しばしば実行されます。 本稿では,LoRA手法の適応率を厳密に分析するフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-10T18:51:53Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  ランダム機能(RF)は、機械学習においてカーネルメソッドをスケールアップする一般的なテクニックである。 ユークリッド空間と離散入力空間の両方で定義されるRFを改善するための結合を求める。 パラダイムとしての分散還元の利点と限界について、驚くほどの結論に達した。
  論文  参考訳（メタデータ） (2024-05-26T12:25:09Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Geometric Optimization of Restricted-Open and Complete Active Space Self-Consistent Field Wavefunctions [0.0]
  完全宇宙アクティブF問題の解法を提示し,検討する。 これらの手法を比較し,数値パラメータを伴わないロバストな手法を求める。 本研究は, ROHF と CHF の軌道特性の微調整としてのリーマン最適化がさらなる研究を保証していることを示唆している。
  論文  参考訳（メタデータ） (2024-04-23T01:31:41Z)
• 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)
• Multiplicative Updates for Online Convex Optimization over Symmetric Cones [28.815822236291392]
  任意の対称コーンのトレースワンスライスに対するオンライン最適化のためのプロジェクションフリーアルゴリズムであるSymmetric-Cone Multiplicative Weights Update (SCMWU)を導入する。 SCMWUは, 対称錐負エントロピーを正則化器とするFollow-the-Regularized-LeaderおよびOnline Mirror Descentと等価であることを示す。
  論文  参考訳（メタデータ） (2023-07-06T17:06:43Z)
• Deep Diversity-Enhanced Feature Representation of Hyperspectral Images [87.47202258194719]
  トポロジを改良して3次元畳み込みを補正し,上行階の高次化を図る。 また、要素間の独立性を最大化するために特徴マップに作用する新しい多様性対応正規化(DA-Reg)項を提案する。 提案したRe$3$-ConvSetとDA-Regの優位性を実証するために,様々なHS画像処理および解析タスクに適用する。
  論文  参考訳（メタデータ） (2023-01-15T16:19:18Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Optimal Posteriors for Chi-squared Divergence based PAC-Bayesian Bounds and Comparison with KL-divergence based Optimal Posteriors and Cross-Validation Procedure [0.0]
  カイ二乗発散に基づくPACBayesian境界の最適後部について,その分布,計算のスケーラビリティ,テストセットの性能について検討した。 チ二乗発散に基づく後肢は境界が弱く、試験誤差が悪くなるため、KL発散に基づく後肢による基礎的な正規化が示唆される。
  論文  参考訳（メタデータ） (2020-08-14T03:15:23Z)

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

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