論文の概要: Minimax Optimization: The Case of Convex-Submodular

• arxiv url: http://arxiv.org/abs/2111.01262v1
• Date: Mon, 1 Nov 2021 21:06:35 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-03 14:13:00.205977
• Title: Minimax Optimization: The Case of Convex-Submodular
• Title（参考訳）: Minimax Optimization: Convex-submodular の場合
• Authors: Arman Adibi, Aryan Mokhtari, Hamed Hassani
• Abstract要約: ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
• 参考スコア（独自算出の注目度）: 50.03984152441271
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minimax optimization has been central in addressing various applications in machine learning, game theory, and control theory. Prior literature has thus far mainly focused on studying such problems in the continuous domain, e.g., convex-concave minimax optimization is now understood to a significant extent. Nevertheless, minimax problems extend far beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains. In this paper, we study mixed continuous-discrete minimax problems where the minimization is over a continuous variable belonging to Euclidean space and the maximization is over subsets of a given ground set. We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable. Even though such problems appear frequently in machine learning applications, little is known about how to address them from algorithmic and theoretical perspectives. For such problems, we first show that obtaining saddle points are hard up to any approximation, and thus introduce new notions of (near-) optimality. We then provide several algorithmic procedures for solving convex and monotone-submodular minimax problems and characterize their convergence rates, computational complexity, and quality of the final solution according to our notions of optimally. Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization. Finally, we provide numerical experiments to showcase the effectiveness of our purposed methods.
• Abstract（参考訳）: ミニマックス最適化は、機械学習、ゲーム理論、制御理論における様々な応用に取り組んできた。 これまでの文献では、例えば凸凸ミニマックス最適化(convex-concave minimax optimization)など、連続領域におけるそのような問題の研究に重点を置いてきた。 それでも、ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 本稿では、ユークリッド空間に属する連続変数上の最小化が与えられた基底集合の部分集合上の最大化である混合連続離散ミニマックス問題について研究する。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 このような問題は機械学習アプリケーションに頻繁に現れるが、アルゴリズム的および理論的観点からそれらに対処する方法についてはほとんど分かっていない。 このような問題に対して、まず、サドル点の取得は任意の近似に対して困難であることを示し、従って(近傍)最適性の新たな概念を導入する。 次に, 凸および単調サブモジュラーミニマックス問題の解法と, その収束率, 計算複雑性, 最終解の質を最適解として特徴付けるアルゴリズム手法を提案する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。 最後に,本手法の有効性を示す数値実験を行った。

関連論文リスト

• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems [7.5573375809946395]
  定常的非平滑項の両方にフォーカスできるNCSCミニマックス問題を解くための最初の試みを行う。 提案アルゴリズムは,ミニマックス問題の新たな再構成に基づいて設計されている。
  論文  参考訳（メタデータ） (2023-04-05T13:54:43Z)
• Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems [46.71914490521821]
  本稿では,非コンケーブなミニマックス問題のクラスに対して,新たな漸進型アルゴリズムを提案する。 提案アルゴリズムは制約付き正規化問題に適用可能である。
  論文  参考訳（メタデータ） (2023-02-20T08:37:08Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems [9.653157073271021]
  我々は、min-max最適化問題を解決するために、分散適応運動量 (ADAM) 型アルゴリズムを開発した。 我々は、(確率的な)一階のナッシュ平衡点を求めるための提案アルゴリズムの非漸近収束率を求める。
  論文  参考訳（メタデータ） (2021-06-10T22:32:01Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances [58.54078318403909]
  min-max問題(英: min-max problem)またはサドル点問題(英: saddle point problem)は、サムゲームにおいても研究されるクラス逆問題である。
  論文  参考訳（メタデータ） (2020-06-15T05:33:42Z)
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities [14.848525762485872]
  非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。 これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
  論文  参考訳（メタデータ） (2020-02-20T17:12:49Z)

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

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