論文の概要: 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が対戦する新しいアルゴリズムを提案する。 我々のアルゴリズムは、単調な進行(極限周期を持たないため)を保証し、多項式数反復において適切な「定常点」を求める。 本フレームワークでは,複数ステップの確率勾配を加味したスムーズなアルゴリズムとその高速化版について検討する。 さらに,理論的な結果を確認し,提案手法の有効性を実証する補完実験を行った。

関連論文リスト

• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• 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)

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

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