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

関連論文リスト

• Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint [18.290666675596984]
  非単調制約部分モジュラー・サブアニメーションは、様々な機械学習応用において重要な役割を果たす。 既存のアルゴリズムは、近似保証と実用効率のトレードオフにしばしば苦労する。 我々は,$0.385$-approximationの保証と$O(n+k2)$の低い,実用的なクエリ複雑性を組み合わせた新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-22T20:56:57Z)
• Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
  様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。 我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。 また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
  論文  参考訳（メタデータ） (2023-08-02T07:20:37Z)
• Target-based Surrogates for Stochastic Optimization [26.35752393302125]
  我々は(おそらく)勾配を計算するのに費用がかかる関数の最小化を考える。 このような機能は、計算強化学習、模倣学習、および敵の訓練で広く用いられている。 我々のフレームワークは、最適化アルゴリズムを用いて、効率的に最小化できるサロゲートを構築することができる。
  論文  参考訳（メタデータ） (2023-02-06T08:08:34Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• 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 [13.357957711519134]
  制約されたサブモジュール問題には、パーソナライズされたレコメンデーション、チーム形成、バイラルマーケティングによる収益化など、さまざまな応用が含まれている。 我々は5.83のランダム化近似を達成し、O(n log n)$禁断時間、すなわち少なくとも$n$を他の最先端アルゴリズムよりも高速に実行する単純なグリーディアルゴリズムを提案する。 そこで我々は,非単調な目的に対する最初の定数近似である9-近似を求め,実データと合成データに改良された性能を示すアルゴリズムの実験評価を行った。
  論文  参考訳（メタデータ） (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)

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

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