論文の概要: Convergence Rate of the (1+1)-Evolution Strategy with Success-Based
Step-Size Adaptation on Convex Quadratic Functions
- arxiv url: http://arxiv.org/abs/2103.01578v2
- Date: Mon, 12 Apr 2021 14:16:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-09 12:22:21.220869
- Title: Convergence Rate of the (1+1)-Evolution Strategy with Success-Based
Step-Size Adaptation on Convex Quadratic Functions
- Title（参考訳）: 1+1)-進化戦略の収束速度と凸二次関数上のステップサイズ適応
- Authors: Daiki Morinaga, Kazuto Fukuchi, Jun Sakuma, and Youhei Akimoto
- Abstract要約: 1+1)-進化戦略(ES)と成功に基づくステップサイズ適応を一般凸二次関数で解析する。
1+1)-ES の収束速度は、一般凸二次函数上で明示的に厳密に導かれる。
- 参考スコア（独自算出の注目度）: 20.666734673282498
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The (1+1)-evolution strategy (ES) with success-based step-size adaptation is
analyzed on a general convex quadratic function and its monotone
transformation, that is, $f(x) = g((x - x^*)^\mathrm{T} H (x - x^*))$, where
$g:\mathbb{R}\to\mathbb{R}$ is a strictly increasing function, $H$ is a
positive-definite symmetric matrix, and $x^* \in \mathbb{R}^d$ is the optimal
solution of $f$. The convergence rate, that is, the decrease rate of the
distance from a search point $m_t$ to the optimal solution $x^*$, is proven to
be in $O(\exp( - L / \mathrm{Tr}(H) ))$, where $L$ is the smallest eigenvalue
of $H$ and $\mathrm{Tr}(H)$ is the trace of $H$. This result generalizes the
known rate of $O(\exp(- 1/d ))$ for the case of $H = I_{d}$ ($I_d$ is the
identity matrix of dimension $d$) and $O(\exp(- 1/ (d\cdot\xi) ))$ for the case
of $H = \mathrm{diag}(\xi \cdot I_{d/2}, I_{d/2})$. To the best of our
knowledge, this is the first study in which the convergence rate of the
(1+1)-ES is derived explicitly and rigorously on a general convex quadratic
function, which depicts the impact of the distribution of the eigenvalues in
the Hessian $H$ on the optimization and not only the impact of the condition
number of $H$.
- Abstract（参考訳）: 1+1)-進化戦略 (es) は、一般凸二次関数とその単調変換、すなわち、$f(x) = g((x - x^*)^\mathrm{t} h (x - x^*))$, ここで $g:\mathbb{r}\to\mathbb{r}$ は厳密に増加する関数であり、$h$ は正定値対称行列であり、$x^* \in \mathbb{r}^d$ は$f$の最適解である。
収束率、すなわち、探索点 $m_t$ から最適解 $x^*$ への距離の減少率は、$O(\exp( - L / \mathrm{Tr}(H) )$ で証明され、$L$ は$H$ の最小固有値であり、$\mathrm{Tr}(H)$ は$H$ のトレースである。
この結果は、$H = I_{d}$$$(\exp(- 1/d ))$(I_d$ is the identity matrix of dimension $d$)と$O(\exp(- 1/ (d\cdot\xi) )$ for the case of $H = \mathrm{diag}(\xi \cdot I_{d/2}, I_{d/2})$の既知レートを一般化する。
我々の知る限り、これは (1+1)-ES の収束速度が一般凸二次函数上で明示的に厳密に導出される最初の研究であり、これはHessian $H$ における固有値の分布が最適化に与える影響だけでなく、条件数$H$ の影響も表すものである。
関連論文リスト
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。
適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文 参考訳（メタデータ） (2024-11-08T17:10:38Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。