論文の概要: Mirror Natural Evolution Strategies
- arxiv url: http://arxiv.org/abs/2308.00469v1
- Date: Tue, 1 Aug 2023 11:45:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-02 14:21:55.536839
- Title: Mirror Natural Evolution Strategies
- Title(参考訳): 鏡の自然進化戦略
- Authors: Haishan Ye
- Abstract要約: 我々は、ゼロ階探索で近似された一階情報と二階情報の両方を利用するゼロ階最適化理論に焦点をあてる。
我々は、textttMiNES の推定共分散行列が、目的関数のヘッセン行列の逆行列に収束することを示す。
- 参考スコア(独自算出の注目度): 10.495496415022064
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The zeroth-order optimization has been widely used in machine learning
applications. However, the theoretical study of the zeroth-order optimization
focus on the algorithms which approximate (first-order) gradients using
(zeroth-order) function value difference at a random direction. The theory of
algorithms which approximate the gradient and Hessian information by
zeroth-order queries is much less studied. In this paper, we focus on the
theory of zeroth-order optimization which utilizes both the first-order and
second-order information approximated by the zeroth-order queries. We first
propose a novel reparameterized objective function with parameters $(\mu,
\Sigma)$. This reparameterized objective function achieves its optimum at the
minimizer and the Hessian inverse of the original objective function
respectively, but with small perturbations. Accordingly, we propose a new
algorithm to minimize our proposed reparameterized objective, which we call
\texttt{MiNES} (mirror descent natural evolution strategy). We show that the
estimated covariance matrix of \texttt{MiNES} converges to the inverse of
Hessian matrix of the objective function with a convergence rate
$\widetilde{\mathcal{O}}(1/k)$, where $k$ is the iteration number and
$\widetilde{\mathcal{O}}(\cdot)$ hides the constant and $\log$ terms. We also
provide the explicit convergence rate of \texttt{MiNES} and how the covariance
matrix promotes the convergence rate.
- Abstract(参考訳): zeroth-order optimizationは機械学習アプリケーションで広く使われている。
しかし、ゼロ次最適化の理論的研究は、ランダム方向の(ゼロ次)関数値差を用いて(一階)勾配を近似するアルゴリズムに焦点を当てている。
勾配とヘッセン情報をゼロ次クエリで近似するアルゴリズムの理論はあまり研究されていない。
本稿では,ゼロ階探索で近似された一階情報と二階情報の両方を利用するゼロ階最適化理論に焦点をあてる。
まずパラメータ $(\mu, \sigma)$ を持つ新しい再パラメータ付き目的関数を提案する。
この再パラメータ化された対象関数は、元の目的関数の最小値とヘッセン逆値でそれぞれ最適となるが、摂動は小さい。
そこで我々は,提案する再パラメータ化目標を最小化するための新しいアルゴリズムを提案し,その手法を<textt{mines} (mirror descent natural evolution strategy) と呼ぶ。
ここで、 \texttt{MiNES} の推定共分散行列は、収束率 $\widetilde{\mathcal{O}}(1/k)$ で対象関数のヘッセン行列の逆数に収束し、$k$ は反復数、$\widetilde{\mathcal{O}}(\cdot)$ は定数と $\log$ 項を隠す。
また、 texttt{MiNES} の明示的な収束率と共分散行列が収束率を促進する方法も提供する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth
Nonconvex Stochastic Optimization [44.065130483176944]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
我々の分析は、最近の進歩を活用できる単純だが強力な集合に基づいている。
論文 参考訳(メタデータ) (2023-07-10T11:56:04Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳(メタデータ) (2022-11-03T14:12:51Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳(メタデータ) (2022-10-25T11:37:11Z) - Majorization-minimization for Sparse Nonnegative Matrix Factorization
with the $\beta$-divergence [2.3787352248749376]
他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。
標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。
我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
論文 参考訳(メタデータ) (2022-07-13T16:09:29Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-10T13:07:44Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse
Gradients and Adaptive Sampling [29.600975900977343]
我々はZOROと呼ばれる新しい$textbfZ$eroth-$textbfO$rder $textbfR$egularized $textbfO$ptimization法を提案する。
基礎となる勾配がイテレートでほぼスパースである場合、ZOROは目的関数を減少させる新しいイテレートを得るために、非常に少数の客観的関数評価を必要とする。
論文 参考訳(メタデータ) (2020-03-29T11:01:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。