論文の概要: A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games
- arxiv url: http://arxiv.org/abs/2503.18224v1
- Date: Sun, 23 Mar 2025 21:57:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-25 14:33:37.035283
- Title: A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games
- Title（参考訳）: 2プレイヤーゼロサムブラックボックスゲームにおける局所的サドル点探索フレームワーク
- Authors: Shubhankar Agarwal, Hamzah I. Khan, Sandeep P. Chinchali, David Fridovich-Keil,
- Abstract要約: サドルポイント最適化は、ポートフォリオ最適化、生成的敵ネットワーク、ロボット工学など、多くの現実世界のアプリケーションにおいて重要な問題である。
本稿では,未知の(潜在的にノンコンケーブな)目的関数をモデル化するプロセスを利用するベイズ最適化に着想を得たフレームワークを提案する。
ブラックボックスの非コンケーブ設定において,これらのアルゴリズムを合成的および現実的なデータセット上で実演する。
- 参考スコア（独自算出の注目度）: 10.826775895390881
- License:
- Abstract: Saddle point optimization is a critical problem employed in numerous real-world applications, including portfolio optimization, generative adversarial networks, and robotics. It has been extensively studied in cases where the objective function is known and differentiable. Existing work in black-box settings with unknown objectives that can only be sampled either assumes convexity-concavity in the objective to simplify the problem or operates with noisy gradient estimators. In contrast, we introduce a framework inspired by Bayesian optimization which utilizes Gaussian processes to model the unknown (potentially nonconvex-nonconcave) objective and requires only zeroth-order samples. Our approach frames the saddle point optimization problem as a two-level process which can flexibly integrate existing and novel approaches to this problem. The upper level of our framework produces a model of the objective function by sampling in promising locations, and the lower level of our framework uses the existing model to frame and solve a general-sum game to identify locations to sample. This lower level procedure can be designed in complementary ways, and we demonstrate the flexibility of our approach by introducing variants which appropriately trade off between factors like runtime, the cost of function evaluations, and the number of available initial samples. We experimentally demonstrate these algorithms on synthetic and realistic datasets in black-box nonconvex-nonconcave settings, showcasing their ability to efficiently locate local saddle points in these contexts.
- Abstract（参考訳）: サドルポイント最適化は、ポートフォリオ最適化、生成的敵ネットワーク、ロボット工学など、多くの現実世界のアプリケーションで採用されている重要な問題である。
目的関数が知られ、微分可能な場合に広く研究されている。
未知の目的しかサンプリングできないブラックボックス設定での既存の作業は、問題を単純化するための目的において凸凸凸性を仮定するか、ノイズの多い勾配推定器で操作するかのいずれかである。
対照的に、ベイズ最適化にインスパイアされたフレームワークを導入し、ガウス過程を利用して未知(潜在的には非凸-非凹面)の目的をモデル化し、ゼロ階のサンプルのみを必要とする。
提案手法では,サドル点最適化問題を2段階のプロセスとして,既存の手法と新しい手法を柔軟に統合する。
フレームワークの上層部は,有望な位置をサンプリングすることによって目的関数のモデルを生成し,下層部は既存のモデルを用いて,汎用ゲームを用いてサンプリング対象の場所を特定する。
この低レベルの手順は相補的な方法で設計することができ、ランタイムや関数評価のコスト、利用可能な初期サンプルの数といった要因を適切に交換するバリエーションを導入することで、我々のアプローチの柔軟性を実証することができる。
我々はこれらのアルゴリズムをブラックボックスの非凸非凹面設定における合成および現実的なデータセット上で実験的に実証し、これらの文脈における局所的なサドル点を効率的に見つける能力を示す。
関連論文リスト
- Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。
本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。
2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文 参考訳（メタデータ） (2024-09-24T04:39:47Z) - Pareto Set Prediction Assisted Bilevel Multi-objective Optimization [2.3293561091456283]
両レベルにおいて複数目的(BLMOP)の問題に対処する。
提案されたアプローチは、欺くことと非欺くことの両方を含む、さまざまな問題で競合する。
論文 参考訳（メタデータ） (2024-09-05T08:04:11Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Differentiable Multi-Target Causal Bayesian Experimental Design [43.76697029708785]
本稿では,ベイズ最適設計問題に対する勾配に基づくアプローチを導入し,バッチ環境で因果モデルを学習する。
既存の手法は、一連の実験を構築するためにグリーディ近似に依存している。
そこで本稿では,最適介入対象ペアの集合を取得するための,概念的にシンプルな勾配に基づく最適化手法を提案する。
論文 参考訳（メタデータ） (2023-02-21T11:32:59Z) - Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
本稿では,線形制約付き混合変数問題の解法として,新しいサロゲートに基づく大域的最適化アルゴリズムを提案する。
提案手法は, 目的関数の断片的なアフィンサロゲートを, 実現可能なサンプル上に構築することに基づいている。
この2つのアルゴリズムは、制約なしおよび制約付き混合変数ベンチマーク問題に対して評価される。
論文 参考訳（メタデータ） (2023-02-09T15:04:35Z) - Unsupervised Learning for Combinatorial Optimization with Principled
Objective Relaxation [19.582494782591386]
本研究は,最適化(CO)問題に対する教師なし学習フレームワークを提案する。
我々の重要な貢献は、緩和された目的がエントリーワイドな凹凸を満たすならば、低い最適化損失は最終積分解の品質を保証するという観察である。
特に、この観察は、対象が明示的に与えられていないアプリケーションにおいて、事前にモデル化される必要がある場合に、対象モデルの設計を導くことができる。
論文 参考訳（メタデータ） (2022-07-13T06:44:17Z) - Non-smooth Bayesian Optimization in Tuning Problems [5.768843113172494]
代理モデルの構築は、未知のブラックボックス関数を学習しようとする場合の一般的なアプローチである。
クラスター化ガウス過程 (cGP) と呼ばれる新しい加法的ガウス過程モデルを提案し, 加法的成分はクラスタリングによって誘導される。
調査した例では、反復実験で最大90%の性能向上が可能である。
論文 参考訳（メタデータ） (2021-09-15T20:22:09Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
本稿では,高密度点雲を生成するためのエンドツーエンド学習ベースのフレームワークを提案する。
まずこの問題を明示的に定式化し、重みと高次近似誤差を判定する。
そこで我々は,高次改良とともに,統一重みとソート重みを適応的に学習する軽量ニューラルネットワークを設計する。
論文 参考訳（メタデータ） (2020-11-25T14:00:18Z) - A Flexible Framework for Designing Trainable Priors with Adaptive
Smoothing and Game Encoding [57.1077544780653]
我々は、前方通過を非滑らかな凸最適化問題として解釈できるニューラルネットワーク層の設計とトレーニングのための一般的なフレームワークを紹介する。
グラフのノードに代表されるローカルエージェントによって解決され、正規化関数を介して相互作用する凸ゲームに焦点を当てる。
このアプローチは、訓練可能なエンドツーエンドのディープモデル内で、古典的な画像の事前使用を可能にするため、画像の問題を解決するために魅力的である。
論文 参考訳（メタデータ） (2020-06-26T08:34:54Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。