論文の概要: Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicity
- arxiv url: http://arxiv.org/abs/2312.06540v2
- Date: Tue, 9 Jul 2024 14:51:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-11 00:11:18.104314
- Title: Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicity
- Title（参考訳）: 単調性欠如におけるシャンブル・ポックアルゴリズムの収束性
- Authors: Brecht Evens, Puya Latafat, Panagiotis Patrinos,
- Abstract要約: Chambolle-Pockアルゴリズム(CPA)は、大規模な凸構造問題の解法の成功により、過去10年間で人気を博している。
この研究は、関連する原始双対作用素上のいわゆる弱ミント条件によって定量化される、(非)単調性の異なる問題に対する収束解析を拡張した。
- 参考スコア（独自算出の注目度）: 4.307128674848627
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Chambolle-Pock algorithm (CPA), also known as the primal-dual hybrid gradient method, has gained popularity over the last decade due to its success in solving large-scale convex structured problems. This work extends its convergence analysis 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, 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, we build upon the recently introduced class of semimonotone operators, providing sufficient convergence conditions for CPA when the individual operators are semimonotone. Since this class of operators encompasses traditional operator classes including (hypo)- and co(hypo)-monotone operators, this analysis recovers and extends existing results for CPA. Tightness of the proposed stepsize ranges is demonstrated through several examples.
- Abstract（参考訳）: シャンブル・ポックアルゴリズム(英: Chambolle-Pock algorithm, CPA)は、大規模凸構造問題の解法の成功により、過去10年間で人気を博したアルゴリズムである。
この研究は、関連する原始双対作用素上のいわゆる斜め弱ミント条件によって定量化される、(非)単調性の異なる問題に対する収束解析を拡張した。
この結果から,線形写像のノルムに依存せず,他の特異値にも依存する新たなステップサイズと緩和パラメータの範囲が明らかとなった。
特に、非単調な設定では、古典的なステップサイズ条件に加えて、ステップサイズと緩和パラメータの余分な境界が必要である。
一方、強い単調な設定では、緩和パラメータは古典的な2つの上限を超えることが許される。
さらに、最近導入されたセミモノトン作用素のクラスを構築し、個々の作用素がセミモノトンである場合、CPAに対して十分な収束条件を提供する。
この演算子のクラスは(hypo)-およびco(hypo)-モノトン演算子を含む従来の演算子クラスを含むため、この分析はCPAの既存の結果を回復し拡張する。
提案した段差範囲の厚さは、いくつかの例を通して示される。
関連論文リスト
- 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) - 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) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - 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) - A Generalized Nachtmann Theorem in CFT [0.0]
ユニタリ量子場理論の相関子は、ある解析性と正の性質に従う。
2次元以上のユニタリ CFT の相互作用について、これらの性質が極小ツイスト作用素の族に一般の制約を与えることを示す。
論文 参考訳（メタデータ） (2020-02-27T19:05:44Z) - On operator growth and emergent Poincar\'e symmetries [0.0]
有限温度での一般大Nゲージ理論に対する作用素成長を考察する。
これらのモードの代数は、初期作用素が時間とともに混合する作用素の簡単な解析を可能にする。
これらのアプローチはすべて、ゲルファント・ナイマルク・セガル(GNS)の構成の観点から自然な定式化を持つことを示す。
論文 参考訳（メタデータ） (2020-02-10T15:29:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。