論文の概要: Asymmetric Burer-Monteiro Factorization with Theoretically Sound Penalty for Semidefinite Programming

• arxiv url: http://arxiv.org/abs/1811.01198v9
• Date: Mon, 22 Sep 2025 12:31:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-05 15:45:20.862944
• Title: Asymmetric Burer-Monteiro Factorization with Theoretically Sound Penalty for Semidefinite Programming
• Title（参考訳）: 半有限計画法における理論的に不規則な不斉バーラ・モンティロ因子の非対称化
• Authors: En-Liang Hu,
• Abstract要約: 大規模半確定プログラム (SDP) の解法として, 対称なBurer-iro Factorization (BMF) を用いる。 結果、非対称BMFは多重凸$最適化であることを示す。
• 参考スコア（独自算出の注目度）: 0.7614628596146601
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the solving of large-scale semidefinite programs (SDPs), the symmetric Burer-Monteiro factorization (BMF) offers an economical low-rank solution of the form $XX^\top$. However, BMF turns a convex SDP into a more difficult nonconvex optimization problem in some cases, which limits the use of off-the-shelf convex optimization algorithms. To alleviate this problem, we convert symmetric BMF to its asymmetric counterpart involving $XY^\top$, and use a penalty with parameter $\gamma$ to encourage $X$ and $Y$ to be close. We show that the resultant asymmetric BMF is multi-convex, and thus convex optimization can again be used to solve the subproblems involving $X$ and $Y$ in an alternating manner. More importantly, to ensure that $X=Y$ on convergence, we derive theoretically sound conditions for exact $\gamma$ that are independent of both the application problem and underlying algorithm. Experiments demonstrate that the proposed method is more advantageous over existing related approaches.
• Abstract（参考訳）: 大規模半定値プログラム (SDP) の解法において、対称的ブルア・モンテイロ分解 (BMF) は$XX^\top$という形の経済的低ランクな解を提供する。 しかし、BMFは凸SDPをより難しい非凸最適化問題に変換するため、既製の凸最適化アルゴリズムの使用を制限している。 この問題を緩和するために、対称BMFを$XY^\top$を含む非対称に変換し、パラメータ$\gamma$でペナルティを使い、$X$と$Y$を閉じることを奨励する。 結果、非対称BMFは多重凸であり、したがって凸最適化は再び、$X$と$Y$を含むサブプロブレムを交互に解くために用いられる。 さらに重要なことは、収束において$X=Y$を保証するために、アプリケーション問題と基礎となるアルゴリズムの両方に依存しない正確な$\gamma$に対して理論的に健全な条件を導出する。 実験により,提案手法は既存手法よりも有利であることが示された。

関連論文リスト

• Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms [26.645423762494985]
  コンパクト凸可能領域$P$ 上の(滑らかな)凸関数の差を最小化する問題を考える。 Blended Pairwise Gradients (BPCG) アルゴリズムを用いて, 拘束された直流問題を効率的に解けることを示す。
  論文  参考訳（メタデータ） (2025-07-23T14:22:42Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Black-Box Min--Max Continuous Optimization Using CMA-ES with Worst-case Ranking Approximation [22.576922942465142]
  一般的なアプローチでは、$x$と$y$を同時に、あるいは交互に更新する。 既存のアプローチは、$f$がリプシッツの滑らかで、最適解を囲む凸凸が強い場合失敗する。 本稿では、共分散行列適応進化戦略を用いて、最悪の対象関数 $F(x)=max_yf(x,y)$ を最小化することを提案する。
  論文  参考訳（メタデータ） (2022-04-06T08:03:39Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization [8.386501595252]
  BMM(Block Majorization-minimativeization)は、制約付き非負のサロゲートに対する単純な反復アルゴリズムである。 BMMは,様々なアルゴリズムに対して,新しい一階最適度尺度を生成する。 また, BMM の収束率を向上させるために, 減衰半径の付加的利用が有効であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T07:53:09Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)

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

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