Fugu-MT 論文翻訳(概要): Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs

論文の概要: Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs

arxiv url: http://arxiv.org/abs/2411.03103v1
Date: Tue, 05 Nov 2024 13:47:07 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-06 14:59:09.620308
Title: Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs
Title（参考訳）: MaxCut型半定値プログラムのBurer-Monteiro分解に対するベニグアランドスケープ
Authors: Faniriana Rakoto Endor, Irène Waldspurger,
Abstract要約: 低階解を持つMaxCut数値半定プログラム(SDP)を考える。低階仮説を活用するために、標準的なアルゴリズム的アプローチはブラー・モンテイロ化係数である。
参考スコア（独自算出の注目度）: 0.9208007322096532
License:
Abstract: We consider MaxCut-type semidefinite programs (SDP) which admit a low rank solution. To numerically leverage the low rank hypothesis, a standard algorithmic approach is the Burer-Monteiro factorization, which allows to significantly reduce the dimensionality of the problem at the cost of its convexity. We give a sharp condition on the conditioning of the Laplacian matrix associated with the SDP under which any second-order critical point of the non-convex problem is a global minimizer. By applying our theorem, we improve on recent results about the correctness of the Burer-Monteiro approach on $\mathbb{Z}_2$-synchronization problems.
Abstract（参考訳）: 低階解を持つ MaxCut 型半定値プログラム (SDP) を考える。低階仮説を数値的に活用するために、標準的なアルゴリズム的アプローチは、その凸性のコストで問題の次元を著しく減少させることができるバー・モンティロ因子化である。我々は、非凸問題の2階臨界点が大域最小化器であるSDPに付随するラプラシア行列の条件付けに鋭い条件を与える。この定理を適用して、$\mathbb{Z}_2$-synchronization問題に対するBurer-Monteiroアプローチの正しさに関する最近の結果を改善する。

関連論文リスト

Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
論文参考訳（メタデータ） (2024-10-24T19:57:56Z)
Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
離散メモリレスソースに対するRDPF(Ralse-Distortion-Perception Function)の計算について検討した。最適パラメトリック解を特徴付ける。歪みと知覚制約について十分な条件を提供する。
論文参考訳（メタデータ） (2024-08-27T12:50:12Z)
Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文参考訳（メタデータ） (2024-06-28T02:56:22Z)
Covariance Matrix Adaptation Evolutionary Strategy with Worst-Case Ranking Approximation for Min--Max Optimization and its Application to Berthing Control Tasks [19.263468901608785]
我々は mathbbX max_y in mathbbYf(x,y)$ の連続 min-max 最適化問題 $min_x を考える。最悪の対象関数である$F(x) = max_y f(x,y)$を直接最小化する新しい手法を提案する。
論文参考訳（メタデータ） (2023-03-28T15:50:56Z)
Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems [46.71914490521821]
本稿では,非コンケーブなミニマックス問題のクラスに対して,新たな漸進型アルゴリズムを提案する。提案アルゴリズムは制約付き正規化問題に適用可能である。
論文参考訳（メタデータ） (2023-02-20T08:37:08Z)
Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文参考訳（メタデータ） (2022-02-26T19:10:48Z)
A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文参考訳（メタデータ） (2021-06-24T13:46:09Z)
Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文参考訳（メタデータ） (2021-02-27T19:28:39Z)
A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文参考訳（メタデータ） (2021-02-15T07:10:33Z)
Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文参考訳（メタデータ） (2020-10-12T17:41:44Z)
Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers [0.0]
核ノルムへの凸緩和を最小化することは、推奨システムと堅牢な主成分分析に重要である。本研究では, ブイロとルクシロによる核プログラムのランク因数分解のための効率的なアルゴリズムを開発した。
論文参考訳（メタデータ） (2020-06-13T19:04:37Z)

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