論文の概要: A first-order primal-dual method with adaptivity to local smoothness
- arxiv url: http://arxiv.org/abs/2110.15148v1
- Date: Thu, 28 Oct 2021 14:19:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-29 16:23:29.802828
- Title: A first-order primal-dual method with adaptivity to local smoothness
- Title（参考訳）: 局所的滑らか性への適応性を持つ1次原始双対法
- Authors: Maria-Luiza Vladarean, Yura Malitsky, Volkan Cevher
- Abstract要約: 凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
- 参考スコア（独自算出の注目度）: 64.62056765216386
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding a saddle point for the convex-concave
objective $\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)$, where $f$ is a
convex function with locally Lipschitz gradient and $g$ is convex and possibly
non-smooth. We propose an adaptive version of the Condat-V\~u algorithm, which
alternates between primal gradient steps and dual proximal steps. The method
achieves stepsize adaptivity through a simple rule involving $\|A\|$ and the
norm of recently computed gradients of $f$. Under standard assumptions, we
prove an $\mathcal{O}(k^{-1})$ ergodic convergence rate. Furthermore, when $f$
is also locally strongly convex and $A$ has full row rank we show that our
method converges with a linear rate. Numerical experiments are provided for
illustrating the practical performance of the algorithm.
- Abstract（参考訳）: 我々は、凸対対象 $\min_x \max_y f の鞍点を求める問題を考える。
(x) + \langle ax, y\rangle - g^*
(y)$、ただし$f$ は局所リプシッツ勾配を持つ凸函数であり、$g$ は凸であり、おそらく非スムースである。
主勾配ステップと二重近位ステップを交互に行うCondat-V\~uアルゴリズムの適応バージョンを提案する。
この方法は、$\|a\|$ と最近計算された$f$ の勾配のノルムを含む単純な規則によって順応性を実現する。
標準的な仮定の下では、$\mathcal{o}(k^{-1})$ エルゴード収束率を証明できる。
さらに、$f$ が局所的に強凸であり、$A$ が全行ランクを持つとき、我々の方法が線形レートで収束することを示す。
本アルゴリズムの実用性能を示すための数値実験を行った。
関連論文リスト
- Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文 参考訳（メタデータ） (2023-05-23T15:26:36Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Perseus: A Simple and Optimal High-Order Method for Variational
Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。
そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文 参考訳（メタデータ） (2022-05-06T13:29:14Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
この楽観的な手法は凸凹点問題の解法として人気が高まっている。
我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
論文 参考訳（メタデータ） (2022-02-19T20:31:05Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
論文 参考訳（メタデータ） (2021-12-30T20:31:46Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳（メタデータ） (2021-03-29T23:03:24Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。