論文の概要: Submodular Minimax Optimization: Finding Effective Sets
- arxiv url: http://arxiv.org/abs/2305.16903v1
- Date: Fri, 26 May 2023 13:17:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 14:54:42.467183
- Title: Submodular Minimax Optimization: Finding Effective Sets
- Title(参考訳): Submodular Minimax Optimization: Finding Effective Sets
- Authors: Loay Mualem, Ethan R. Elenberg, Moran Feldman, Amin Karbasi
- Abstract要約: 本稿では,全ての応答に対して有効となる集合を求める問題である,部分モジュラー最小最適化の特性について述べる。
また、ダウンストリーム機械学習アプリケーションに対して、minimaxサブモジュール最適化が堅牢なソリューションを提供する方法を実証する。
- 参考スコア(独自算出の注目度): 37.77367453380923
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite the rich existing literature about minimax optimization in continuous
settings, only very partial results of this kind have been obtained for
combinatorial settings. In this paper, we fill this gap by providing a
characterization of submodular minimax optimization, the problem of finding a
set (for either the min or the max player) that is effective against every
possible response. We show when and under what conditions we can find such
sets. We also demonstrate how minimax submodular optimization provides robust
solutions for downstream machine learning applications such as (i) efficient
prompt engineering for question answering, (ii) prompt engineering for dialog
state tracking, (iii) identifying robust waiting locations for ride-sharing,
(iv) ride-share difficulty kernelization, and (v) finding adversarial images.
Our experiments demonstrate that our proposed algorithms consistently
outperform other baselines.
- Abstract(参考訳): 連続設定におけるミニマックス最適化に関する豊富な文献にもかかわらず、コンビネータ設定で得られるのはこの種の部分的な結果のみである。
本稿では,各応答に対して有効となる集合(minまたはmaxプレーヤ)を見つけることの問題点である,部分モジュラー極小最適化の特性を提供することで,このギャップを埋める。
どのような条件でそのような集合が見つかるかを示す。
また,minimaxサブモジュール最適化が下流の機械学習アプリケーションに対して堅牢なソリューションを提供する方法を示す。
(i)質問応答のための効率的なプロンプトエンジニアリング
(ii)ダイアログ状態追跡のためのプロンプトエンジニアリング
(iii)ライドシェアリングのロバストな待機場所を特定すること。
(iv)ライドシェアリングの難しさ、及び
(v) 敵画像の発見。
我々の実験は,提案アルゴリズムが他のベースラインより一貫して優れていることを示した。
関連論文リスト
- Pareto Optimization with Robust Evaluation for Noisy Subset Selection [34.83487850400559]
サブセット選択は最適化の基本的な問題であり、影響やスパース回帰といった幅広い応用がある。
欲求アルゴリズムや進化進化的POSSを含む従来のアルゴリズムは、ノイズの多い環境で苦労するか、過剰な計算資源を消費する。
本稿では,頑健な評価関数を最大化し,同時にサブセットサイズを最小化する,雑音性サブセット選択(PORE)のためのロバスト評価を用いたパレート最適化に基づく新しい手法を提案する。
論文 参考訳(メタデータ) (2025-01-12T14:04:20Z) - Indirect Query Bayesian Optimization with Integrated Feedback [17.66813850517961]
我々は,未知関数の条件付き期待値$f$を最適化することで,統合されたフィードバックが与えられるような,ベイズ最適化の新たなクラスを開発する。
目的は、条件分布によって変換された空間を適応的にクエリし、観察することで、$f$のグローバルな最適値を見つけることである。
これは、プライバシ、ハードウェア、計算上の制約による直接的なフィードバックにアクセスできない現実世界のアプリケーションによって動機付けられている。
論文 参考訳(メタデータ) (2024-12-18T07:20:33Z) - Faster Stochastic Variance Reduction Methods for Compositional MiniMax
Optimization [50.10952609321302]
合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。
構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。
本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
論文 参考訳(メタデータ) (2023-08-18T14:57:21Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
凸最適化における総和係数法に着想を得て,広範な分岐関数を持つネットワーク上での検証クエリを解析するための新しい手法を提案する。
標準ケース分析に基づく完全探索手順の拡張は、各検索状態で実行される凸手順をDeepSoIに置き換えることによって達成できる。
論文 参考訳(メタデータ) (2022-03-19T15:05:09Z) - Bayesian Optimization for auto-tuning GPU kernels [0.0]
GPUカーネルの最適パラメータ設定を見つけることは、たとえ自動化されても、大規模な検索スペースにとって簡単な作業ではない。
拡張性を改善した新しい文脈探索機能と,情報機能選択機構を併用した新しい獲得機能を導入する。
論文 参考訳(メタデータ) (2021-11-26T11:26:26Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳(メタデータ) (2021-11-01T21:06:35Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。