論文の概要: Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems

• arxiv url: http://arxiv.org/abs/2209.04604v1
• Date: Sat, 10 Sep 2022 05:56:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-13 14:00:56.117409
• Title: Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems
• Title（参考訳）: 凸強凸サドル点問題の加速原始双対法
• Authors: Mohammad Khalafi, Digvijay Boob
• Abstract要約: オラクル・コンカブ・サドル点問題に対するPrimal-Dual (PD)法について検討した。 本稿では,不正確な主成分のみの2次勾配勾配法を提案する。
• 参考スコア（独自算出の注目度）: 3.04585143845864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we aim to investigate Primal-Dual (PD) methods for convex-strongly-concave saddle point problems (SPP). In many cases, the computation of the proximal oracle over the primal-only function is inefficient. Hence, we use its first-order linear approximation in the proximal step resulting in a Linearized PD (LPD) method. Even when the coupling term is bilinear, we observe that LPD has a suboptimal dependence on the Lipschitz constant of the primal-only function. In contrast, LPD has optimal convergence for the strongly-convex concave case. This observation induces us to present our accelerated linearized primal-dual (ALPD) algorithm to solve convex strongly-concave SPP. ALPD is a single-loop algorithm that combines features of Nesterov's accelerated gradient descent (AGD) and LPD. We show that when the coupling term is semi-linear (which contains bilinear as a specific case), ALPD obtains the optimal dependence on the Lipschitz constant of primal-only function. Hence, it is an optimal algorithm. When the coupling term has a general nonlinear form, the ALPD algorithm has suboptimal dependence on the Lipschitz constant of the primal part of the coupling term. To improve this dependence, we present an inexact APD algorithm. This algorithm performs AGD iterations in the inner loop to find an approximate solution to a proximal subproblem of APD. We show that inexact APD maintains optimal number of gradients evaluations (gradient complexity) of primal-only and dual parts of the problem. It also significantly improves the gradient-complexity of the primal coupling term.
• Abstract（参考訳）: 本研究では,差動点問題(SPP)に対するPrimal-Dual(PD)法について検討する。 多くの場合、素数のみの関数上の近似オラクルの計算は非効率である。 したがって,線形化pd法(lpd法)による近位ステップでは,その一階線形近似を用いる。 カップリング項が双線型である場合でも、LPDは原始関数のリプシッツ定数に最適値に依存することが観察される。 対照的に lpd は強凸凸の場合の最適収束を持つ。 この観測により, 凸凸型SPPを解くために, 加速線形化原始双対 (ALPD) アルゴリズムを提案する。 ALPDは、ネステロフの加速勾配降下(AGD)とLPDの特徴を組み合わせた単一ループアルゴリズムである。 結合項が半線型(特定の場合として双線型を含む)であるとき、alpdは原始関数のリプシッツ定数の最適依存性を得る。 したがって、最適なアルゴリズムである。 結合項が一般的な非線形形式を持つとき、alpdアルゴリズムは結合項の原始部分のリプシッツ定数に準最適依存性を持つ。 この依存性を改善するために,不正確なAPDアルゴリズムを提案する。 このアルゴリズムは、adpの近位部分問題に対する近似解を見つけるために内側ループでagd反復を実行する。 我々は,不正確なAPDが,問題の主成分と双対部分の勾配評価(漸進的複雑性)を最適に維持していることを示す。 また、主結合項の勾配複雑度を著しく改善する。

関連論文リスト

• A Natural Primal-Dual Hybrid Gradient Method for Adversarial Neural Network Training on Solving Partial Differential Equations [9.588717577573684]
  偏微分方程式(PDE)を解くためのスケーラブルな事前条件付き原始ハイブリッド勾配アルゴリズムを提案する。 本稿では,提案手法の性能を,一般的なディープラーニングアルゴリズムと比較する。 その結果,提案手法は効率的かつ堅牢に動作し,安定に収束することが示唆された。
  論文  参考訳（メタデータ） (2024-11-09T20:39:10Z)
• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
  我々は,非漸近収束を伴う最適決定主義政策を求めるための決定主義的政策勾配原始双対法を開発した。 D-PGPDの一次-双対反復は、最適正則化原始-双対にサブ線形速度で収束することが証明された。 我々の知る限り、これは連続空間制約型MDPに対する決定論的ポリシー探索法を提案する最初の研究であると思われる。
  論文  参考訳（メタデータ） (2024-08-19T14:11:04Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Adaptive Proximal Gradient Method for Convex Optimization [18.681222155879656]
  凸最適化における2つの基本的な一階法、すなわち勾配降下法(GD)と近位勾配法(ProxGD)について検討する。 我々の焦点は、スムーズな関数の局所曲率情報を活用することによって、これらのアルゴリズムを完全に適応させることである。 本稿では,GD と ProxGD の適応バージョンを提案する。
  論文  参考訳（メタデータ） (2023-08-04T11:37:08Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。 両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
  論文  参考訳（メタデータ） (2022-10-04T06:17:52Z)
• Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity [40.73281056650241]
  本稿では,真の勾配時間差学習アルゴリズムを設計・解析する原理的な方法として,近位勾配時間差学習を導入する。 本研究では, 従来の目的関数からではなく, 主目的関数から始めることによって, 勾配性TD強化学習法を公式に導出する方法を示す。
  論文  参考訳（メタデータ） (2020-06-06T21:04:21Z)
• Complexity Guarantees for Polyak Steps with Momentum [76.97851351276165]
  そこでは,この知識を最適な値である$f_*$で置き換える。 まず、Polyak ステップによる単純な勾配勾配の古典的な場合よりも若干改善された収束境界を示し、その後、収束保証とともに、Polyak ステップと運動量を持つ加速勾配法を導出する。
  論文  参考訳（メタデータ） (2020-02-03T17:50:28Z)

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

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