論文の概要: Convergence of the Chambolle-Pock Algorithm in the Absence of
Monotonicity
- arxiv url: http://arxiv.org/abs/2312.06540v1
- Date: Mon, 11 Dec 2023 17:20:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-13 18:56:21.074219
- Title: Convergence of the Chambolle-Pock Algorithm in the Absence of
Monotonicity
- Title（参考訳）: 単調性の欠如によるchambolle-pockアルゴリズムの収束
- Authors: Brecht Evens and Puya Latafat and Panagiotis Patrinos
- Abstract要約: シャンブル・ポックアルゴリズム(CPA)は、凸・単トン構造問題の解法の成功により、過去10年間に人気が高まっている。
この研究は、関連する原始双対作用素上のいわゆる弱ミント条件によって定量化される、(非)単調性の異なる問題に対する収束結果を提供する。
- 参考スコア（独自算出の注目度）: 4.8407809921878915
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Chambolle-Pock algorithm (CPA), also known as the primal-dual hybrid
gradient method (PDHG), has surged in popularity in the last decade due to its
success in solving convex/monotone structured problems. This work provides
convergence results for problems with varying degrees of (non)monotonicity,
quantified through a so-called oblique weak Minty condition on the associated
primal-dual operator. Our results reveal novel stepsize and relaxation
parameter ranges which do not only depend on the norm of the linear mapping,
but also on its other singular values. In particular, in nonmonotone settings,
in addition to the classical stepsize conditions for CPA, extra bounds on the
stepsizes and relaxation parameters are required. On the other hand, in the
strongly monotone setting, the relaxation parameter is allowed to exceed the
classical upper bound of two. Moreover, sufficient convergence conditions are
obtained when the individual operators belong to the recently introduced class
of semimonotone operators. Since this class of operators encompasses many
traditional operator classes including (hypo)- and co(hypo)monotone operators,
this analysis recovers and extends existing results for CPA. Several examples
are provided for the aforementioned problem classes to demonstrate and
establish tightness of the proposed stepsize ranges.
- Abstract（参考訳）: Chambolle-Pockアルゴリズム(CPA)は、原始双対ハイブリッド勾配法(PDHG)としても知られ、凸・単トン構造問題の解法の成功により、過去10年間に人気が高まっている。
この研究は、関連する原始双対作用素上のいわゆる斜め弱ミント条件によって定量化される、(非)単調性の異なる問題に対する収束結果を提供する。
この結果から,線形写像のノルムに依存せず,他の特異値にも依存する新たなステップサイズと緩和パラメータの範囲が明らかになった。
特に、モノトーン以外の設定では、cpaの古典的なステップ化条件に加えて、ステップ化と緩和パラメータの余分な境界が必要である。
一方、強い単調な設定では、緩和パラメータは古典的な2つの上限を超えることが許される。
さらに、個々の作用素が最近導入された半単調作用素のクラスに属する場合に十分な収束条件が得られる。
この演算子のクラスは(hypo)-やco(hypo)monotone演算子を含む多くの従来の演算子クラスを含んでいるので、この分析はCPAの既存の結果を回復し拡張する。
上記の問題クラスに対して、提案した段差範囲の厳密性を実証し、確立するためのいくつかの例を提供する。
関連論文リスト
- On the Hypomonotone Class of Variational Inequalities [4.204990010424083]
本研究では,低単調な演算子に適用した場合の過次アルゴリズムの挙動について検討する。
次数次アルゴリズムが収束しない条件を特定するための評価定理を提供する。
論文 参考訳（メタデータ） (2024-10-11T18:35:48Z) - Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。
我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。
我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
論文 参考訳（メタデータ） (2023-10-04T17:24:45Z) - Single-Call Stochastic Extragradient Methods for Structured Non-monotone
Variational Inequalities: Improved Analysis under Weaker Conditions [21.681130192954583]
シングルコール・エクストラグラディエント法は、大規模なmin-max最適化問題を解くための最も効率的なアルゴリズムの1つである。
i)準強単調問題(強単調問題の一般化)と(ii)弱ミンティ変分不等式(単調とミニティVIPの一般化)の2つのクラスに対して収束保証を提供する。
我々の収束分析は、重要なサンプリングと様々なミニバッチ戦略を特別な場合として含む任意のサンプリングパラダイムの下で成り立っている。
論文 参考訳（メタデータ） (2023-02-27T18:53:28Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文 参考訳（メタデータ） (2022-10-27T17:59:09Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - 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) - Lipschitz Bounded Equilibrium Networks [3.2872586139884623]
本稿では、平衡ニューラルネットワーク、すなわち暗黙の方程式で定義されるネットワークの新しいパラメータ化を提案する。
新しいパラメータ化は、制約のない最適化を通じてトレーニング中にリプシッツ境界を許容する。
画像分類実験では、リプシッツ境界は非常に正確であり、敵攻撃に対する堅牢性を向上させることが示されている。
論文 参考訳（メタデータ） (2020-10-05T01:00:40Z) - Models of zero-range interaction for the bosonic trimer at unitarity [91.3755431537592]
ゼロ範囲の2体相互作用によって相互に結合された同一ボソンからなる3体系に対する量子ハミルトニアンの構成について述べる。
プレゼンテーションの大部分では、無限の散乱長が考慮される。
論文 参考訳（メタデータ） (2020-06-03T17:54:43Z) - On operator growth and emergent Poincar\'e symmetries [0.0]
有限温度での一般大Nゲージ理論に対する作用素成長を考察する。
これらのモードの代数は、初期作用素が時間とともに混合する作用素の簡単な解析を可能にする。
これらのアプローチはすべて、ゲルファント・ナイマルク・セガル(GNS)の構成の観点から自然な定式化を持つことを示す。
論文 参考訳（メタデータ） (2020-02-10T15:29:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。