論文の概要: Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

• arxiv url: http://arxiv.org/abs/2606.28307v1
• Date: Fri, 26 Jun 2026 17:52:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-29 18:24:25.55254
• Title: Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization
• Title（参考訳）: 非凸および非Lipschitz最適化におけるBregman ADMMの2次KKT保証
• Abstract要約: 非線型制約問題に対するBregman ADMMを両側の相対的滑らかさの下で解析する。 分散最適化のためのマルチブロック星コンセンサス定式化に解析を拡張した。
• 参考スコア（独自算出の注目度）: 20.87701856262044
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor models for which a global Lipschitz-gradient constant need not exist. We show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal--dual fixed-point map whose strict-saddle KKT points are unstable fixed points; consequently, from random initialization the iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points. We extend the analysis to a multi-block star consensus formulation for distributed optimization. The technical novelty lies in a determinant reduction with a Bregman-specific symmetrization and scaling step in the two block spectral argument, together with a null space cancellation exploiting the star graph structure in the consensus case. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting idea beyond the separable consensus setting.
• Abstract（参考訳）: 我々は、標準的なリプシッツ勾配仮定をブレグマン核に対するヘシアン比較に置き換える条件である両側相対滑らか性の下で、非凸線形制約問題に対するブレグマンADMMを解析する。 この設定は、大域リプシッツの勾配定数が存在しない行列やテンソルモデルで生じる多項式の目的をカバーしている。 不変な開状態空間領域において、Bregman ADMMの1つの反復は、厳密なKKT点が不安定な不動点を持つ滑らかな原始双対不動点写像を定義することを示し、したがってランダム初期化から、イテレートは確率 0 の厳密なサドルに収束する。 既存の一階収束結果と組み合わせることで、KKT点を制限する2階定常性がほぼ確実に得られる。 分散最適化のためのマルチブロック星コンセンサス定式化に解析を拡張した。 技術的新奇性は、2ブロックのスペクトル論におけるブレグマン固有の対称性とスケーリングのステップによる決定的な還元と、コンセンサスの場合の星グラフ構造を利用したヌル空間の消去に関係している。 分散行列因数分解に関する数値実験は、この理論を示し、対称テンソル因数分解の例は、分離可能なコンセンサス設定を超えて、より広いブレグマン近位分裂の考えを示す。

関連論文リスト

• Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy [1.1907026010541673]
  本稿では,KKT定常点におけるラグランジュ乗算器の符号に基づく制約付き非制約最適化のための構造的分類法を提案する。 ベクトルのない4つの形は、この二重空間を非制約、リソース制限、飽和、強い結合、ハイブリッドの5つの運用体制に分割する。
  論文  参考訳（メタデータ） (2026-08-31T23:22:05Z)
• Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards [1.370633147306388]
  $text-mathrmNPTS_mathrmSG$はアンカーフリーの非パラメトリックトンプソンサンプリングアルゴリズムである。 我々は、$text-mathrmNPTS_mathrmSG$が、$log n$の先頭の順にインスタンス依存の下位境界と一致することを証明した。
  論文  参考訳（メタデータ） (2026-06-08T08:26:37Z)
• Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL [8.809468023364703]
  堅牢な強化学習アルゴリズムの設計は根本的な課題を生んでいる。 本稿では、関連するロバスト関数の1次展開に基づく近似DRRLフレームワークを提案する。 この近似方程式の定点を学習するために,平均変数近似(MVSA)を提案する。
  論文  参考訳（メタデータ） (2026-05-08T19:24:28Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms [18.425648833592312]
  tBMM は $O(epsilon-2)$ 内の $ilon$-定常点に収束することを示す。 軽度反復の下では、全最適性ギャップが有界である場合、各反復においてサブプロブレムが解かれるときの結果は依然として保たれる。
  論文  参考訳（メタデータ） (2024-05-05T22:53:14Z)
• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence [25.717501580080846]
  本稿では、現代の非最適化設定における勾配フォワードミラー(SMD)の収束を再考する。 トレーニングのために,線形ネットワーク問題に対する確率収束アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-27T17:56:49Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization [2.9112649816695204]
  実バナッハ空間上の凸凹サドル点問題の第一次原始双対解法について検討する。 我々のフレームワークは一般であり、アルゴリズムにおいてブレグマンの発散を誘導するエントロピーの強い凸性を必要としない。 数値的な応用としては、エントロピー的正則化ワッサーシュタイン・バリセンタ問題や、単純体上の正則化逆問題などが挙げられる。
  論文  参考訳（メタデータ） (2021-12-22T14:47:44Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• 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)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)

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

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