論文の概要: Diffusion Stochastic Optimization for Min-Max Problems

• arxiv url: http://arxiv.org/abs/2401.14585v1
• Date: Fri, 26 Jan 2024 01:16:59 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-29 16:14:16.780493
• Title: Diffusion Stochastic Optimization for Min-Max Problems
• Title（参考訳）: min-max問題に対する拡散確率最適化
• Authors: Haoyuan Cai, Sulaiman A. Alghunaim, Ali H. Sayed
• Abstract要約: 楽観的勾配法はミニマックス最適化問題に対処するのに有用である。 従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
• 参考スコア（独自算出の注目度）: 33.73046548872663
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The optimistic gradient method is useful in addressing minimax optimization problems. Motivated by the observation that the conventional stochastic version suffers from the need for a large batch size on the order of $\mathcal{O}(\varepsilon^{-2})$ to achieve an $\varepsilon$-stationary solution, we introduce and analyze a new formulation termed Diffusion Stochastic Same-Sample Optimistic Gradient (DSS-OG). We prove its convergence and resolve the large batch issue by establishing a tighter upper bound, under the more general setting of nonconvex Polyak-Lojasiewicz (PL) risk functions. We also extend the applicability of the proposed method to the distributed scenario, where agents communicate with their neighbors via a left-stochastic protocol. To implement DSS-OG, we can query the stochastic gradient oracles in parallel with some extra memory overhead, resulting in a complexity comparable to its conventional counterpart. To demonstrate the efficacy of the proposed algorithm, we conduct tests by training generative adversarial networks.
• Abstract（参考訳）: 楽観的勾配法はミニマックス最適化問題に対処するのに有用である。 従来の確率的バージョンは$\mathcal{o}(\varepsilon^{-2})$で$\varepsilon$定常解を達成するために大きなバッチサイズを必要とするという観測に動機づけられ、新しい定式化である拡散確率的同値楽観的勾配 (dss-og) を導入し分析した。 非凸ポリak-lojasiewicz (pl) のリスク関数のより一般的な設定の下で、より厳密な上界を確立することにより、その収束を証明し、大きなバッチ問題を解く。 また,提案手法の適用性を分散シナリオに拡張し,エージェントが左派プロトコルを介して隣人と通信する。 DSS-OGを実装するために,確率勾配オーラクルとメモリオーバーヘッドの増大を並列にクエリすることで,従来のものと同等の複雑性を実現する。 提案アルゴリズムの有効性を示すために,生成逆ネットワークを訓練してテストを行う。

関連論文リスト

• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
  非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
  論文  参考訳（メタデータ） (2024-06-27T18:38:42Z)
• On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization [10.36447258513813]
  我々は、強化学習(RL)における既存の問題の多くを網羅する非文献設定における正規化期待報酬最適化問題を考える。 特に、標準条件下では、$O(epsilon-4)$サンプルを$epsilon$-stationaryポイントに含めることが示されている。 分析の結果,サンプルの複雑さは,追加条件下では$O(epsilon-4)$から$O(epsilon-3)$に改善できることがわかった。
  論文  参考訳（メタデータ） (2024-01-23T06:01:29Z)
• Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems [39.197569803430646]
  最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。 近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
  論文  参考訳（メタデータ） (2023-04-21T11:38:41Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。 MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
  論文  参考訳（メタデータ） (2022-02-02T20:10:40Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• On Distributed Non-convex Optimization: Projected Subgradient Method For Weakly Convex Problems in Networks [13.385373310554327]
  Moreau subgradient 法は、機械学習における線形シャープネス問題を収束させる。 理論的保証を伴う下位段階法の分散実装を提案する。
  論文  参考訳（メタデータ） (2020-04-28T01:01:49Z)
• Better Theory for SGD in the Nonconvex World [2.6397379133308214]
  大規模な非最適化問題は、現代の機械学習ではユビキタスである。 我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
  論文  参考訳（メタデータ） (2020-02-09T09:56:06Z)

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

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