論文の概要: Run Time Bounds for Integer-Valued OneMax Functions
- arxiv url: http://arxiv.org/abs/2307.11855v2
- Date: Mon, 9 Oct 2023 08:49:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-13 05:31:31.544610
- Title: Run Time Bounds for Integer-Valued OneMax Functions
- Title（参考訳）: 整数値OneMax関数の時間境界の実行
- Authors: Jonathan Gadea Harder, Timo K\"otzing, Xiaoyue Li, Aishwarya
Radhakrishnan
- Abstract要約: 探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。
ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。
本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
- 参考スコア（独自算出の注目度）: 0.9012198585960443
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While most theoretical run time analyses of discrete randomized search
heuristics focused on finite search spaces, we consider the search space
$\mathbb{Z}^n$. This is a further generalization of the search space of
multi-valued decision variables $\{0,\ldots,r-1\}^n$.
We consider as fitness functions the distance to the (unique) non-zero
optimum $a$ (based on the $L_1$-metric) and the \ooea which mutates by applying
a step-operator on each component that is determined to be varied. For changing
by $\pm 1$, we show that the expected optimization time is $\Theta(n \cdot
(|a|_{\infty} + \log(|a|_H)))$. In particular, the time is linear in the
maximum value of the optimum $a$. Employing a different step operator which
chooses a step size from a distribution so heavy-tailed that the expectation is
infinite, we get an optimization time of $O(n \cdot \log^2 (|a|_1) \cdot
\left(\log (\log (|a|_1))\right)^{1 + \epsilon})$.
Furthermore, we show that RLS with step size adaptation achieves an
optimization time of $\Theta(n \cdot \log(|a|_1))$.
We conclude with an empirical analysis, comparing the above algorithms also
with a variant of CMA-ES for discrete search spaces.
- Abstract（参考訳）: 離散ランダム化探索ヒューリスティックのほとんどの理論的実行時間解析は有限探索空間に焦点を当てているが、探索空間 $\mathbb{z}^n$ を考える。
これは、多値決定変数 $\{0,\ldots,r-1\}^n$ の探索空間のさらなる一般化である。
フィットネス関数として、(単調な)非ゼロの最適な$a$($l_1$-metricに基づく)と、変化が決定される各コンポーネントにステップ操作を適用することによって変化する \ooea までの距離を考える。
$\pm 1$ で変更する場合、期待される最適化時間は$\theta(n \cdot (|a|_{\infty} + \log(|a|_h))$である。
特に、時間は最適な$a$の最大値において線形である。
期待値が無限であるような分布からステップサイズを選択する異なるステップ演算子を用いて、最適化時間は$O(n \cdot \log^2 (|a|_1) \cdot \left(\log (\log (|a|_1))\right)^{1 + \epsilon})$である。
さらに、ステップサイズ適応を持つrlsは$\theta(n \cdot \log(|a|_1))$の最適化時間を達成する。
本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
関連論文リスト
- Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Convergence Rates for Non-Log-Concave Sampling and Log-Partition
Estimation [0.0]
m$timesの微分可能関数が$d$の場合、$n$(m/d)のアルゴリズムの最適レートは$n(m/d)であることが知られている。
サンプリングと計算に類似したレートが可能であり、独立レートが$d$の時間で実現可能であることを示す。
論文 参考訳（メタデータ） (2023-03-06T15:53:44Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - A Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump
Functions [8.34061303235504]
我々は,このアルゴリズムの最初の実行時解析を,ジャンプ関数ベンチマークであるマルチモーダル問題クラス上で実施する。
ジャンプ関数の局所最適性を残すという孤立した問題に対して、$(n/k)k/2 eTheta(k)$のランタイムにつながる証明可能な最適パラメータを決定する。
論文 参考訳（メタデータ） (2020-04-14T17:54:12Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。