論文の概要: Decentralized gradient descent maximization method for composite
nonconvex strongly-concave minimax problems
- arxiv url: http://arxiv.org/abs/2304.02441v1
- Date: Wed, 5 Apr 2023 13:54:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-06 12:35:42.234588
- Title: Decentralized gradient descent maximization method for composite
nonconvex strongly-concave minimax problems
- Title（参考訳）: 複合非凸強凹極小問題に対する分散勾配勾配最大化法
- Authors: Yangyang Xu
- Abstract要約: 定常的非平滑項の両方にフォーカスできるNCSCミニマックス問題を解くための最初の試みを行う。
提案アルゴリズムは,ミニマックス問題の新たな再構成に基づいて設計されている。
- 参考スコア（独自算出の注目度）: 7.5573375809946395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Minimax problems have recently attracted a lot of research interests. A few
efforts have been made to solve decentralized nonconvex strongly-concave (NCSC)
minimax-structured optimization; however, all of them focus on smooth problems
with at most a constraint on the maximization variable. In this paper, we make
the first attempt on solving composite NCSC minimax problems that can have
convex nonsmooth terms on both minimization and maximization variables. Our
algorithm is designed based on a novel reformulation of the decentralized
minimax problem that introduces a multiplier to absorb the dual consensus
constraint. The removal of dual consensus constraint enables the most
aggressive (i.e., local maximization instead of a gradient ascent step) dual
update that leads to the benefit of taking a larger primal stepsize and better
complexity results. In addition, the decoupling of the nonsmoothness and
consensus on the dual variable eases the analysis of a decentralized algorithm;
thus our reformulation creates a new way for interested researchers to design
new (and possibly more efficient) decentralized methods on solving NCSC minimax
problems. We show a global convergence result of the proposed algorithm and an
iteration complexity result to produce a (near) stationary point of the
reformulation. Moreover, a relation is established between the (near)
stationarities of the reformulation and the original formulation. With this
relation, we show that when the dual regularizer is smooth, our algorithm can
have lower complexity results (with reduced dependence on a condition number)
than existing ones to produce a near-stationary point of the original
formulation. Numerical experiments are conducted on a distributionally robust
logistic regression to demonstrate the performance of the proposed algorithm.
- Abstract（参考訳）: ミニマックス問題は最近多くの研究の関心を集めている。
分散化された非凸強対流(NCSC)の最小構成最適化を解く試みがいくつかなされているが、いずれも最大化変数に制約を課すスムーズな問題に焦点を当てている。
本稿では、最小化変数と最大化変数の両方に対して凸非滑らか項を持つ合成NCSCミニマックス問題を解くための最初の試みを行う。
本アルゴリズムは,二元コンセンサス制約を吸収する乗算器を導入する分散ミニマックス問題の新しい再構成法に基づいて設計する。
二重コンセンサス制約の除去は、最も攻撃的な(すなわち、勾配上昇ステップの代わりに局所的な最大化)二重更新を可能にする。
さらに、二変数に対する非平滑性とコンセンサスの分離は、分散化アルゴリズムの解析を容易にするため、我々の改革は、NCSCのミニマックス問題を解決するための新しい(そしておそらくより効率的な)分散化手法を設計する新しい方法を生み出す。
本研究では,提案アルゴリズムによる大域的な収束結果と反復複雑性の結果を示し,再構成の(ほぼ)定常点を生成する。
また、改革の(近辺の)定常性と元の定式化との間に関係が確立される。
この関係により、双対正則化器が滑らかな場合、アルゴリズムは既存のものよりも複雑さの少ない結果(条件数への依存性が小さくなる)を持つことを示し、元の定式化のほぼ定常点を生成する。
提案アルゴリズムの性能を示すために, 分散ロジスティック回帰法を用いて数値実験を行った。
関連論文リスト
- Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T02:19:39Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - A Variance-Reduced Stochastic Gradient Tracking Algorithm for
Decentralized Optimization with Orthogonality Constraints [7.028225540638832]
直交制約付き分散最適化のための新しいアルゴリズムを提案する。
VRSGTは、サンプリングと通信の複雑さを同時に低減する直交制約付き分散最適化のための最初のアルゴリズムである。
数値実験では、VRGTSは現実の自律的なサンプルにおいて有望な性能を持つ。
論文 参考訳（メタデータ） (2022-08-29T14:46:44Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳（メタデータ） (2021-11-01T21:06:35Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - An efficient nonconvex reformulation of stagewise convex optimization
problems [21.61123565780424]
我々は、段階的構造問題を活用するために設計された非改革を開発する。
ニューラルネットワーク検証のアプローチでは、わずか数ステップで急激な局所的なギャップが得られます。
棚から取り出した問題や特殊な解法よりも早く解決できる。
論文 参考訳（メタデータ） (2020-10-27T14:30:32Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳（メタデータ） (2020-10-23T05:24:05Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Stochastic gradient algorithms from ODE splitting perspective [0.0]
我々は、ODEの近似解の分割スキームに遡る最適化に関する異なる見解を示す。
そこで本研究では, ODE の勾配一階分割方式と降下アプローチの関連性について述べる。
我々は、機械学習アプリケーションにインスパイアされた分割の特殊なケースを考察し、それに対するグローバルスプリッティングエラーに新たな上限を導出する。
論文 参考訳（メタデータ） (2020-04-19T22:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。