論文の概要: Minimax Optimization with Smooth Algorithmic Adversaries

• arxiv url: http://arxiv.org/abs/2106.01488v1
• Date: Wed, 2 Jun 2021 22:03:36 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-04 15:58:33.244356
• Title: Minimax Optimization with Smooth Algorithmic Adversaries
• Title（参考訳）: 滑らかなアルゴリズムによるミニマックス最適化
• Authors: Tanner Fiez, Chi Jin, Praneeth Netrapalli, Lillian J. Ratliff
• Abstract要約: 対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
• 参考スコア（独自算出の注目度）: 59.47122537182611
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers minimax optimization $\min_x \max_y f(x, y)$ in the challenging setting where $f$ can be both nonconvex in $x$ and nonconcave in $y$. Though such optimization problems arise in many machine learning paradigms including training generative adversarial networks (GANs) and adversarially robust models, many fundamental issues remain in theory, such as the absence of efficiently computable optimality notions, and cyclic or diverging behavior of existing algorithms. Our framework sprouts from the practical consideration that under a computational budget, the max-player can not fully maximize $f(x,\cdot)$ since nonconcave maximization is NP-hard in general. So, we propose a new algorithm for the min-player to play against smooth algorithms deployed by the adversary (i.e., the max-player) instead of against full maximization. Our algorithm is guaranteed to make monotonic progress (thus having no limit cycles), and to find an appropriate "stationary point" in a polynomial number of iterations. Our framework covers practical settings where the smooth algorithms deployed by the adversary are multi-step stochastic gradient ascent, and its accelerated version. We further provide complementing experiments that confirm our theoretical findings and demonstrate the effectiveness of the proposed approach in practice.
• Abstract（参考訳）: 本稿では,$f$ が$x$ の非凸と$y$の非凸の両方になるような困難な設定において,minimax 最適化 $\min_x \max_y f(x, y)$ を考える。 このような最適化問題は、GAN(generative adversarial network)のトレーニングを含む多くの機械学習パラダイムに生じるが、効率的な計算可能な最適性の概念の欠如や、既存のアルゴリズムの循環的・変動的挙動など、理論上の基本的問題は残っている。 我々のフレームワークは、計算予算の下では、非凹型最大化が一般にnpハードであるため、max-playerが$f(x,\cdot)$を完全に最大化することはできないという実践的考察から生まれたものです。 そこで,本研究では,対戦相手が展開するスムーズなアルゴリズム(すなわち,最大最大化ではなく最大化)に対して,Min-playerが対戦する新しいアルゴリズムを提案する。 我々のアルゴリズムは、単調な進行(極限周期を持たないため)を保証し、多項式数反復において適切な「定常点」を求める。 本フレームワークでは,複数ステップの確率勾配を加味したスムーズなアルゴリズムとその高速化版について検討する。 さらに,理論的な結果を確認し,提案手法の有効性を実証する補完実験を行った。

関連論文リスト

• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions [0.0]
  我々は,このアルゴリズムがリプシッツ連続函数の地平線に対して平均的後悔O(LstnT-frac1n)$を達成することを示す。
  論文  参考訳（メタデータ） (2022-06-06T06:28:38Z)
• Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning [12.069630105460766]
  AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。 本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-22T04:33:27Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Retrospective Approximation for Smooth Stochastic Optimization [1.0323063834827415]
  我々は,普遍近似問題サイズパラダイムとしてふりかえり近似(ra)を提案する。 線形探索準探索によるRAの性能について,不条件最小二乗問題と深部畳み込みニューラルネットを用いた画像分類問題について述べる。
  論文  参考訳（メタデータ） (2021-03-07T16:29:36Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint [14.077478685398379]
  我々は5.83ドルの近似を達成し、O(n log n)$ time, 少なくとも$n$を他の最先端アルゴリズムよりも高速に実行するグリーディアルゴリズムを提案する。 提案アルゴリズムの実験的評価は,実データおよび合成データ上での性能向上を示す。
  論文  参考訳（メタデータ） (2020-07-09T18:15:01Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。 また、単一または2つのミニバッチ誘導体でも機能する。
  論文  参考訳（メタデータ） (2020-06-27T03:05:18Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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