論文の概要: Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method

• arxiv url: http://arxiv.org/abs/2003.08093v1
• Date: Wed, 18 Mar 2020 08:38:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-22 09:50:48.910763
• Title: Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method
• Title（参考訳）: 近似勾配法による非凸非微分可能ミニマックスゲームの解法
• Authors: Babak Barazandeh and Meisam Razaviyayn
• Abstract要約: ミニマックスサドル点降下器は、機械の傾きと信号処理において幅広い用途に現れる。 単純な多段階LA-Ascentアルゴリズムは文献上の既存アルゴリズムよりも強いことを示す。
• 参考スコア（独自算出の注目度）: 10.819408603463426
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Min-max saddle point games appear in a wide range of applications in machine leaning and signal processing. Despite their wide applicability, theoretical studies are mostly limited to the special convex-concave structure. While some recent works generalized these results to special smooth non-convex cases, our understanding of non-smooth scenarios is still limited. In this work, we study special form of non-smooth min-max games when the objective function is (strongly) convex with respect to one of the player's decision variable. We show that a simple multi-step proximal gradient descent-ascent algorithm converges to $\epsilon$-first-order Nash equilibrium of the min-max game with the number of gradient evaluations being polynomial in $1/\epsilon$. We will also show that our notion of stationarity is stronger than existing ones in the literature. Finally, we evaluate the performance of the proposed algorithm through adversarial attack on a LASSO estimator.
• Abstract（参考訳）: min-max saddle pointゲームは、機械の傾きや信号処理における幅広い応用に現れる。 適用性は広いが、理論的な研究は主に特別な凸凹構造に限られる。 最近の研究では、これらの結果を特別な滑らかな非凸ケースに一般化したものの、非滑らかなシナリオに対する理解はまだ限られている。 本研究では,目的関数がプレイヤーの決定変数の1つに対して(強く)凸である場合,非滑らかなmin-maxゲームの特徴形式について検討する。 単純な多段階の近位勾配降下勾配アルゴリズムは、min-maxゲームの1次ナッシュ平衡に収束し、1/\epsilon$の多項式となる勾配評価の個数を示す。 また、文献上に存在するものよりも定常性の概念が強いことも示します。 最後に,LASSO推定器への逆攻撃による提案アルゴリズムの性能評価を行った。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  本稿では,離散潜在変数の生成に関わるパラメータの勾配を近似する新しい手法を提案する。 本稿では,Hunの手法とODEを解くための2次数値法を統合することで,2次精度を実現するReinMaxを提案する。
  論文  参考訳（メタデータ） (2023-04-17T20:59:49Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Alternating Mirror Descent for Constrained Min-Max Games [44.46086335474311]
  制約付き戦略空間を持つ2プレイヤー双線形ゼロサムゲームについて検討する。 我々は,各プレイヤーが交互に行動する交互ミラー降下アルゴリズムを,制約付き最適化のためのミラー降下アルゴリズムに従って解析する。
  論文  参考訳（メタデータ） (2022-06-08T20:48:16Z)
• Convex-Concave Min-Max Stackelberg Games [0.0]
  コンベックス・コンケーブ min-max Stackelberg ゲームのクラスを解く2つの一階法を導入する。 私たちは我々の方法が時間内に収束していることを示します。 フィッシャー市場での競争均衡の計算は、min-max Stackelbergゲームも含む。
  論文  参考訳（メタデータ） (2021-10-05T06:09:45Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Direct-Search for a Class of Stochastic Min-Max Problems [0.0]
  オラクルを通してのみ対象物にアクセスする導関数探索法について検討する。 この手法の収束性は軽微な仮定で証明する。 私達の分析は設定のminmax目的のための直接調査方法の収束に取り組む最初のものです。
  論文  参考訳（メタデータ） (2021-02-22T22:23:58Z)
• The Complexity of Constrained Min-Max Optimization [29.57458485068705]
  十分大きな局所点 min-max が存在することが保証されていることを示す。 さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。 この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
  論文  参考訳（メタデータ） (2020-09-21T05:54:12Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
  滑らかなゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。 スペクトル形状の変換として, 勾配法, 指数勾配法について述べる。 バイリニアゲームに最適なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-02T19:21:48Z)

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

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