論文の概要: Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems

• arxiv url: http://arxiv.org/abs/2408.15969v1
• Date: Wed, 28 Aug 2024 17:43:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-29 14:59:16.357769
• Title: Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems
• Title（参考訳）: 多重ブロック凸最適化問題に対する一次2次元勾配流れのダイナミクスの安定性
• Authors: Ibrahim K. Ozaslan, Panagiotis Patrinos, Mihailo R. Jovanović,
• Abstract要約: 提案された力学はラグランジアンの近位拡大に基づいている。 我々は、グローバル(指数)収束保証を確立するために、様々な構造的特性を利用する。 我々の仮定は、様々な原始双対力学の(指数的な)安定性を証明するために必要なものよりもはるかに弱い。
• 参考スコア（独自算出の注目度）: 2.66854711376491
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We examine stability properties of primal-dual gradient flow dynamics for composite convex optimization problems with multiple, possibly nonsmooth, terms in the objective function under the generalized consensus constraint. The proposed dynamics are based on the proximal augmented Lagrangian and they provide a viable alternative to ADMM which faces significant challenges from both analysis and implementation viewpoints in large-scale multi-block scenarios. In contrast to customized algorithms with individualized convergence guarantees, we provide a systematic approach for solving a broad class of challenging composite optimization problems. We leverage various structural properties to establish global (exponential) convergence guarantees for the proposed dynamics. Our assumptions are much weaker than those required to prove (exponential) stability of various primal-dual dynamics as well as (linear) convergence of discrete-time methods, e.g., standard two-block and multi-block ADMM and EXTRA algorithms. Finally, we show necessity of some of our structural assumptions for exponential stability and provide computational experiments to demonstrate the convenience of the proposed dynamics for parallel and distributed computing applications.
• Abstract（参考訳）: 一般化されたコンセンサス制約の下での目的関数における複数の、おそらくは非滑らかな項を含む複合凸最適化問題に対する原始-双対勾配流の安定性特性について検討する。 提案手法はラグランジアンを近似的に拡張し,大規模マルチブロックシナリオにおける解析と実装の両面から大きな課題に直面するADMMに代わる実現可能な代替手段を提供する。 個別収束保証を伴うカスタマイズアルゴリズムとは対照的に、我々は幅広い難解な合成最適化問題を解くための体系的なアプローチを提供する。 我々は、様々な構造的特性を利用して、提案された力学に対する大域的(指数的)収束保証を確立する。 我々の仮定は、離散時間法、例えば標準2ブロック法、マルチブロックADMM法、EXTRAアルゴリズムの(線形)収束と同様に、様々な原始双対力学の(指数)安定性を証明するために必要なものよりもはるかに弱い。 最後に,指数的安定性を前提とした構造的仮定のいくつかの必要性を示し,並列・分散コンピューティングアプリケーションにおいて提案した動的手法の利便性を実証するための計算実験を行う。

関連論文リスト

• Consistent Submodular Maximization [27.266085572522847]
  定性制約下での単調部分モジュラ関数の最大化は、データマイニングや機械学習におけるいくつかの応用において古典的な最適化課題である。 本稿では, 安定解を持ちながら, ストリーミング方式で要素が到着し, 最適解に対する定数近似が維持されるという, 一貫性の制約のある動的環境において, この問題を考察する。 この設定では、一貫性と近似品質のトレードオフが異なるアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2024-05-30T11:59:58Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization [5.319361976450982]
  本稿では,特定の種類のEMアルゴリズムの収束を保証する一連の条件を紹介する。 本研究では,混合整数非線形最適化問題の解法として,反復アルゴリズムの新しい解析手法を提案する。
  論文  参考訳（メタデータ） (2024-01-31T11:42:46Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。 広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。 本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
  論文  参考訳（メタデータ） (2023-09-05T13:42:11Z)
• Multi-Symmetry Ensembles: Improving Diversity and Generalization via Opposing Symmetries [14.219011458423363]
  我々は,対称性軸に沿った仮説の多重性を捉えることで,多様なアンサンブルを構築するためのフレームワークであるマルチサイメトリ・アンサンブル(MSE)を提案する。 MSEは、ImageNetのような大規模で多様なデータセットでしばしば必要とされる矛盾する仮説の多重性を効果的にキャプチャする。 その固有の多様性の結果、MSEは分類性能、不確実な定量化、一連の伝達タスクの一般化を改善している。
  論文  参考訳（メタデータ） (2023-03-04T19:11:54Z)
• Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows [4.817429789586127]
  本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
  論文  参考訳（メタデータ） (2021-12-02T16:04:40Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Jointly Modeling and Clustering Tensors in High Dimensions [6.072664839782975]
  テンソルの合同ベンチマークとクラスタリングの問題を考察する。 本稿では,統計的精度の高い近傍に幾何的に収束する効率的な高速最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-15T21:06:16Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  この論文は、運動量に基づく最適化アルゴリズムにおいてシンプレクティックな離散化スキームが重要であることを厳格に証明している。 これは加速収束を示すアルゴリズムの特性を提供する。
  論文  参考訳（メタデータ） (2020-02-28T00:32:47Z)

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

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