論文の概要: Black-Box Min--Max Continuous Optimization Using CMA-ES with Worst-case
Ranking Approximation
- arxiv url: http://arxiv.org/abs/2204.02646v1
- Date: Wed, 6 Apr 2022 08:03:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-18 03:01:11.703307
- Title: Black-Box Min--Max Continuous Optimization Using CMA-ES with Worst-case
Ranking Approximation
- Title（参考訳）: CMA-ESを用いたブラックボックス最小値連続最適化
- Authors: Atsuhiro Miyagi, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto
- Abstract要約: 一般的なアプローチでは、$x$と$y$を同時に、あるいは交互に更新する。
既存のアプローチは、$f$がリプシッツの滑らかで、最適解を囲む凸凸が強い場合失敗する。
本稿では、共分散行列適応進化戦略を用いて、最悪の対象関数 $F(x)=max_yf(x,y)$ を最小化することを提案する。
- 参考スコア（独自算出の注目度）: 22.576922942465142
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this study, we investigate the problem of min-max continuous optimization
in a black-box setting $\min_{x} \max_{y}f(x,y)$. A popular approach updates
$x$ and $y$ simultaneously or alternatingly. However, two major limitations
have been reported in existing approaches. (I) As the influence of the
interaction term between $x$ and $y$ (e.g., $x^\mathrm{T} B y$) on the
Lipschitz smooth and strongly convex-concave function $f$ increases, the
approaches converge to an optimal solution at a slower rate. (II) The
approaches fail to converge if $f$ is not Lipschitz smooth and strongly
convex-concave around the optimal solution. To address these difficulties, we
propose minimizing the worst-case objective function $F(x)=\max_{y}f(x,y)$
directly using the covariance matrix adaptation evolution strategy, in which
the rankings of solution candidates are approximated by our proposed worst-case
ranking approximation (WRA) mechanism. Compared with existing approaches,
numerical experiments show two important findings regarding our proposed
method. (1) The proposed approach is efficient in terms of $f$-calls on a
Lipschitz smooth and strongly convex-concave function with a large interaction
term. (2) The proposed approach can converge on functions that are not
Lipschitz smooth and strongly convex-concave around the optimal solution,
whereas existing approaches fail.
- Abstract（参考訳）: 本研究では, black-box set $\min_{x} \max_{y}f(x,y)$ におけるmin-max連続最適化の問題を検討する。
一般的なアプローチは、同時に$x$と$y$を更新する。
しかし、既存のアプローチでは2つの大きな制限が報告されている。
(I)$x$と$y$の間の相互作用項(例えば、$x^\mathrm{T} B y$)がリプシッツの滑らかで強凸凸凸函数 $f$ に与える影響を考えると、アプローチはより遅い速度で最適解に収束する。
(II)
このアプローチは、$f$がリプシッツ滑らかで、最適解を囲む凸凸が強い場合、収束しない。
これらの問題に対処するために,提案手法を用いて解候補のランキングを近似する共分散行列適応進化戦略を用いて,最悪の目的関数 $f(x)=\max_{y}f(x,y)$ の最小化を提案する。
既存の手法と比較して,数値実験では提案手法について2つの重要な知見が得られた。
1) 提案手法は, 相互作用項が大きいリプシッツ滑らかかつ強い凸凸凸関数上の$f$-callsの点で効率的である。
2) 提案手法は, リプシッツ滑らかでない関数と, 最適解の周りに強い凸凹を持つ関数に収束するが, 既存のアプローチは失敗する。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。
本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
論文 参考訳（メタデータ） (2024-05-28T20:52:46Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。
解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
論文 参考訳（メタデータ） (2024-02-07T18:22:41Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Covariance Matrix Adaptation Evolutionary Strategy with Worst-Case
Ranking Approximation for Min--Max Optimization and its Application to
Berthing Control Tasks [19.263468901608785]
我々は mathbbX max_y in mathbbYf(x,y)$ の連続 min-max 最適化問題 $min_x を考える。
最悪の対象関数である$F(x) = max_y f(x,y)$を直接最小化する新しい手法を提案する。
論文 参考訳（メタデータ） (2023-03-28T15:50:56Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
論文 参考訳（メタデータ） (2021-12-30T20:31:46Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳（メタデータ） (2021-03-29T23:03:24Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。