論文の概要: Saddle Point Optimization with Approximate Minimization Oracle

• arxiv url: http://arxiv.org/abs/2103.15985v2
• Date: Wed, 31 Mar 2021 23:30:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-06 05:41:29.198209
• Title: Saddle Point Optimization with Approximate Minimization Oracle
• Title（参考訳）: 近似最小化オラクルによる鞍点最適化
• Authors: Youhei Akimoto
• Abstract要約: サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。 対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。 我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
• 参考スコア（独自算出の注目度）: 8.680676599607125
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A major approach to saddle point optimization $\min_x\max_y f(x, y)$ is a gradient based approach as is popularized by generative adversarial networks (GANs). In contrast, we analyze an alternative approach relying only on an oracle that solves a minimization problem approximately. Our approach locates approximate solutions $x'$ and $y'$ to $\min_{x'}f(x', y)$ and $\max_{y'}f(x, y')$ at a given point $(x, y)$ and updates $(x, y)$ toward these approximate solutions $(x', y')$ with a learning rate $\eta$. On locally strong convex--concave smooth functions, we derive conditions on $\eta$ to exhibit linear convergence to a local saddle point, which reveals a possible shortcoming of recently developed robust adversarial reinforcement learning algorithms. We develop a heuristic approach to adapt $\eta$ derivative-free and implement zero-order and first-order minimization algorithms. Numerical experiments are conducted to show the tightness of the theoretical results as well as the usefulness of the $\eta$ adaptation mechanism.
• Abstract（参考訳）: saddle point optimization $\min_x\max_y f(x, y)$ に対する主要なアプローチは、ジェネレイティブ・アドバーサリー・ネットワーク(gans)によって一般化された勾配に基づくアプローチである。 対照的に、私たちは、およそ最小化問題を解決するオラクルのみに依存する別のアプローチを分析します。 我々のアプローチは、近似解 $x'$ と $y'$ to $\min_{x'}f(x', y)$ and $\max_{y'}f(x, y')$ at a given point $(x, y)$ and update $(x, y)$ toこれらの近似解 $(x', y')$ with a learning rate $\eta$。 局所強凸-凹スムーズ関数では、局所的なサドル点への線形収束を示す$\eta$の条件が導出され、最近開発された強相関強化学習アルゴリズムの欠点が明らかになる。 我々は,$\eta$デリバティブフリーを適用し,ゼロ次および1次最小化アルゴリズムを実装したヒューリスティックな手法を開発した。 理論的結果の厳密さと$\eta$適応機構の有用性を示す数値実験を行った。

関連論文リスト

• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。 この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
  論文  参考訳（メタデータ） (2024-06-26T18:19:10Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
  上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。 我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
  論文  参考訳（メタデータ） (2022-08-07T20:53:42Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• The Complexity of Constrained Min-Max Optimization [29.57458485068705]
  十分大きな局所点 min-max が存在することが保証されていることを示す。 さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。 この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
  論文  参考訳（メタデータ） (2020-09-21T05:54:12Z)
• Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization [28.431572772564518]
  リプシッツの$varepsilon$-greedy逆数モデルは任意の出発点から$max_z f(x, z)$に収束することを示す。 また、リプシッツの$nabla_y f(x,y)$が$d$, $1/varepsilon$であり、$nabla2_y f(x,y)$上の境界は$nabla2_yであることを示す。
  論文  参考訳（メタデータ） (2020-06-22T16:03:41Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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