論文の概要: Super-Reparametrizations of Weighted CSPs: Properties and Optimization
Perspective
- arxiv url: http://arxiv.org/abs/2201.02018v1
- Date: Thu, 6 Jan 2022 11:49:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-07 15:13:31.461109
- 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の最適値に関する上限計算フレームワークを提案する。
- 参考スコア(独自算出の注目度): 0.0
- 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. Newly, 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)法を実装し,WCSPの他の強い局所成分と比較した。
その結果、SACから得られる境界は、多くの事例群よりも優れていることがわかった。
関連論文リスト
- 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) - Scalable Variational Gaussian Processes via Harmonic Kernel
Decomposition [54.07797071198249]
汎用性を維持しつつ高い忠実度近似を提供する,スケーラブルな変分ガウス過程近似を導入する。
様々な回帰問題や分類問題において,本手法は変換やリフレクションなどの入力空間対称性を活用できることを実証する。
提案手法は, 純粋なGPモデルのうち, CIFAR-10 の最先端化を実現する。
論文 参考訳(メタデータ) (2021-06-10T18:17:57Z) - Stochastic Optimization of Areas Under Precision-Recall Curves with
Provable Convergence [66.83161885378192]
ROC(AUROC)と精度リコール曲線(AUPRC)の下の領域は、不均衡問題に対する分類性能を評価するための一般的な指標である。
本稿では,深層学習のためのAUPRCの最適化手法を提案する。
論文 参考訳(メタデータ) (2021-04-18T06:22:21Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳(メタデータ) (2020-10-12T17:41:44Z) - Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
本稿では,MISDP(MISDP)とMISDP(MISDP)について述べる。
次に、それらの連続緩和値の理論的最適性ギャップを分析し、それらが最先端の値よりも強いことを証明する。
市販の解法は一般にMISDPを解くのが難しいため,MISDPと同等の大きさのMILP(mixed-integer linear program)を用いてSPCAを任意の精度で近似する。
論文 参考訳(メタデータ) (2020-08-28T02:07:08Z) - 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) - SIBRE: Self Improvement Based REwards for Adaptive Feedback in
Reinforcement Learning [5.868852957948178]
強化学習(RL)における収束率向上のための汎用的な報酬形成手法を提案する。
このアプローチは既存のRLアルゴリズムと併用して使用するために設計されており、エージェントの過去のパフォーマンスよりも報奨的な改善で構成されている。
我々は、SIBREが元のRLアルゴリズムと同じ条件下で期待に収束することを証明した。
論文 参考訳(メタデータ) (2020-04-21T09:22:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。