論文の概要: EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization

• arxiv url: http://arxiv.org/abs/2508.12479v1
• Date: Sun, 17 Aug 2025 19:39:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-19 14:49:10.79169
• Title: EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization
• Title（参考訳）: EXOTIC: Min-Max最適化のためのエクササイズ,最適化,ツリーベースアルゴリズム
• Authors: Chinmay Maheshwari, Chinmay Pimpalkhare, Debasish Chatterjee,
• Abstract要約: ミニマックス最適化は、ゲーム理論、機械対向学習などの分野において、勾配に基づく手法を典型的なツールとして現れる。 本稿では,凸型手法におけるグローバル最適解をアルゴリズムで計算する手法を提案する。 次に,EXOTIC Exactを紹介する。 反復的に内部楽観的な木に基づく解法で外楽観的な領域を(ほぼ)解決する クラスの呼び出し数の内部への呼び出し数。
• 参考スコア（独自算出の注目度）: 3.249853429482705
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Min-max optimization arises in many domains such as game theory, adversarial machine learning, etc., with gradient-based methods as a typical computational tool. Beyond convex-concave min-max optimization, the solutions found by gradient-based methods may be arbitrarily far from global optima. In this work, we present an algorithmic apparatus for computing globally optimal solutions in convex-non-concave and non-convex-concave min-max optimization. For former, we employ a reformulation that transforms it into a non-concave-convex max-min optimization problem with suitably defined feasible sets and objective function. The new form can be viewed as a generalization of Sion's minimax theorem. Next, we introduce EXOTIC-an Exact, Optimistic, Tree-based algorithm for solving the reformulated max-min problem. EXOTIC employs an iterative convex optimization solver to (approximately) solve the inner minimization and a hierarchical tree search for the outer maximization to optimistically select promising regions to search based on the approximate solution returned by convex optimization solver. We establish an upper bound on its optimality gap as a function of the number of calls to the inner solver, the solver's convergence rate, and additional problem-dependent parameters. Both our algorithmic apparatus along with its accompanying theoretical analysis can also be applied for non-convex-concave min-max optimization. In addition, we propose a class of benchmark convex-non-concave min-max problems along with their analytical global solutions, providing a testbed for evaluating algorithms for min-max optimization. Empirically, EXOTIC outperforms gradient-based methods on this benchmark as well as on existing numerical benchmark problems from the literature. Finally, we demonstrate the utility of EXOTIC by computing security strategies in multi-player games with three or more players.
• Abstract（参考訳）: 最小限の最適化はゲーム理論、逆機械学習など多くの領域で発生し、勾配に基づく手法が典型的な計算ツールである。 凸凹 min-max 最適化の他に、勾配法で見つかる解は、大域的最適値から任意に遠いかもしれない。 本研究では,凸非凹面および凸非凹面 min-max 最適化における大域的最適解を計算するアルゴリズムを提案する。 前者に対しては、適切な定義可能な集合と目的関数を持つ非凸凸最大分最適化問題に変換する再構成を用いる。 新しい形式は、シオンのミニマックス定理の一般化と見なすことができる。 次に、修正された最大ミン問題を解くために、ExoTIC-an Exact, Optimistic, Tree-based algorithmを導入する。 EXOTICは、反復凸最適化解法を用いて、内部の最小化を(ほぼ)解決し、外側の最大化を求める階層木探索を行い、凸最適化解法によって返される近似解に基づいて、期待する領域を楽観的に選択する。 我々は、内部解法への呼び出し数、解法収束率、および追加の問題依存パラメータの関数として、その最適性ギャップに上限を定めている。 我々のアルゴリズム装置とそれに伴う理論解析は、ともに非凸凸min-max最適化にも適用できる。 さらに,その解析的大域的解法とともに,ベンチマーク凸のないmin-max問題のクラスを提案し,min-max最適化のためのアルゴリズムを評価するためのテストベッドを提供する。 経験的に、EXOTICは、このベンチマークの勾配に基づく手法と、文献からの既存の数値ベンチマークの問題を上回ります。 最後に,3人以上のプレイヤーを持つマルチプレイヤーゲームにおいて,セキュリティ戦略の計算によるEXOTICの有用性を実証する。

関連論文リスト

• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  拡張ラグランジアンに基づくmin-max問題のスムーズな変種を提案する。 提案アルゴリズムは, 段階的戦略よりも目的数で拡張性が高い。
  論文  参考訳（メタデータ） (2025-03-16T11:05:51Z)
• Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion [9.551565016483833]
  非コンケーブなmin-max最適化問題の構造化クラスであるコモノトンmin-max最適化について検討する。 最初のコントリビューションでは、extra Anchored Gradient (EAG)アルゴリズムを制約付きコモノトン min-max 最適化に拡張する。 第2のコントリビューションでは、FEG(Fast Extra Gradient)アルゴリズムを制約のないmin-max最適化に拡張する。
  論文  参考訳（メタデータ） (2022-06-10T17:44:06Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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