Fugu-MT 論文翻訳(概要): On the Complexity of a Practical Primal-Dual Coordinate Method

論文の概要: On the Complexity of a Practical Primal-Dual Coordinate Method

arxiv url: http://arxiv.org/abs/2201.07684v1
Date: Wed, 19 Jan 2022 16:14:27 GMT
ステータス: 処理完了
システム内更新日: 2022-01-20 14:00:31.135800
Title: On the Complexity of a Practical Primal-Dual Coordinate Method
Title（参考訳）: 実用的2次元座標法の複雑さについて
Authors: Ahmet Alacaoglu, Volkan Cevher, Stephen J. Wright
Abstract要約: ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。バイマックス性能問題を解くための優れた外挿が得られることが示されている。
参考スコア（独自算出の注目度）: 63.899427212054995
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain good practical performance for solving convex-concave min-max problems with bilinear coupling. Our complexity bounds either match or improve the best-known results in the literature for both dense and sparse (strongly)-convex-(strongly)-concave problems.
Abstract（参考訳）: 両線形カップリングによる凸凹最小値問題の解法として, ランダムな外挿・座標降下法(PURE-CD)を応用した原始双対アルゴリズムの複雑性境界を証明した。我々の複雑性は、密度と疎度(強く)凸-(強く)凹凸問題の両方の文献において最もよく知られた結果に一致するか改善される。

関連論文リスト

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文参考訳（メタデータ） (2024-11-21T22:06:25Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文参考訳（メタデータ） (2023-06-21T17:03:22Z)
Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems [5.787117733071416]
min-max問題を解くための固定時間収束サドル点力学系を開発した。提案手法は他のどの状態法と比較しても高速に実現できる。
論文参考訳（メタデータ） (2022-07-26T12:25:05Z)
First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
min-maxアルゴリズムはユークリッド設定で解析されている。指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
論文参考訳（メタデータ） (2022-06-04T18:53:44Z)
Efficient Algorithms for High-Dimensional Convex Subspace Optimization via Strict Complementarity [19.24470467199451]
目的が$realsn$, $k$の部分空間を見つけることにある最適化問題を考慮し、凸の滑らかな損失を最小限に抑える。この問題は高次元のレジームでは高いが、大域的最適解を見つけることは困難である。本稿では自然について述べる。収束する最適な次元緩和を決定するのですグローバルは単純です
論文参考訳（メタデータ） (2022-02-08T17:36:43Z)
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文参考訳（メタデータ） (2020-10-31T21:35:42Z)
A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。我々は,新しい数値スケール問題の有効性を実証する。
論文参考訳（メタデータ） (2020-10-23T05:24:05Z)

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