論文の概要: Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms

• arxiv url: http://arxiv.org/abs/2004.02635v4
• Date: Tue, 26 Jul 2022 11:21:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-17 04:09:32.210429
• Title: Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
• Title（参考訳）: 二元化、分割、ランダム化:高速非スムース最適化アルゴリズムに向けて
• Authors: Adil Salim, Laurent Condat, Konstantin Mishchenko, Peter Richt\'arik
• Abstract要約: 第一のFが滑らかで第二のFが非滑らかで近似可能な3つの凸函数の和を考える。 このテンプレート問題には、画像処理や機械学習など、多くの応用がある。 この問題に対して PDDY と呼ぶ新しい原始双対アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 21.904012114713428
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider minimizing the sum of three convex functions, where the first one F is smooth, the second one is nonsmooth and proximable and the third one is the composition of a nonsmooth proximable function with a linear operator L. This template problem has many applications, for instance, in image processing and machine learning. First, we propose a new primal-dual algorithm, which we call PDDY, for this problem. It is constructed by applying Davis-Yin splitting to a monotone inclusion in a primal-dual product space, where the operators are monotone under a specific metric depending on L. We show that three existing algorithms (the two forms of the Condat-Vu algorithm and the PD3O algorithm) have the same structure, so that PDDY is the fourth missing link in this self-consistent class of primal-dual algorithms. This representation eases the convergence analysis: it allows us to derive sublinear convergence rates in general, and linear convergence results in presence of strong convexity. Moreover, within our broad and flexible analysis framework, we propose new stochastic generalizations of the algorithms, in which a variance-reduced random estimate of the gradient of F is used, instead of the true gradient. Furthermore, we obtain, as a special case of PDDY, a linearly converging algorithm for the minimization of a strongly convex function F under a linear constraint; we discuss its important application to decentralized optimization.
• Abstract（参考訳）: 第一のFが滑らかで第二のFが滑らかで、第二のFが非滑らかで、第三のFが線形作用素 L を持つ非滑らかな確率関数の構成であるような3つの凸関数の和を最小化することを考える。 まず,この問題に対して PDDY と呼ぶ新しい原始双対アルゴリズムを提案する。 3つの既存のアルゴリズム(condat-vuアルゴリズムとpd3oアルゴリズムの2つの形式)が同じ構造を持っていることを示し、pddyがこの自己整合クラスにおける4番目の欠落リンクであることを示す。 この表現は収束解析を緩和し、一般の線型収束率を導出することができ、線形収束は強い凸性の存在をもたらす。 さらに, 広範かつ柔軟な解析フレームワークにおいて, 真の勾配ではなく, F の勾配の分散還元確率推定を用いたアルゴリズムの確率的一般化を提案する。 さらに,線形制約下での強凸関数Fの最小化のための線形収束アルゴリズムであるPDDYの特別な場合として,分散最適化への重要な応用について論じる。

関連論文リスト

• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  本研究では,RPMアルゴリズムの最小化目的関数を用いて要求を満たす手法を提案する。 分岐とバウンド(BnB)アルゴリズムが考案され、パラメータのみに分岐し、収束率を高める。 実験による評価は,非剛性変形,位置雑音,外れ値に対する提案手法の高剛性を示す。
  論文  参考訳（メタデータ） (2024-05-14T13:28:57Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming [5.126924253766052]
  提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。 また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
  論文  参考訳（メタデータ） (2021-11-10T04:56:38Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates [16.54912614895861]
  我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。 我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。 その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
  論文  参考訳（メタデータ） (2020-03-03T03:59:26Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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