論文の概要: Anytime Analysis on BinVal: Adaptive Parameters Help
- arxiv url: http://arxiv.org/abs/2604.06976v1
- Date: Wed, 08 Apr 2026 11:47:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-09 17:30:51.502123
- Title: Anytime Analysis on BinVal: Adaptive Parameters Help
- Title（参考訳）: BinValの任意の解析: 適応パラメータが役に立つ
- Authors: Timo Kötzing, Jurek Sander,
- Abstract要約: 我々は、BinValをフィットネス機能として利用して、様々なアルゴリズムの固定目標実行時間を分析する。
固定目標実行時間は o(n)$ で、定数 $varepsilon > 0$ が 0 に近いのは、このアルゴリズムに対して $mathcalOleft(k1+varepsilonright)$ である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While most theoretical run time analyses of discrete randomized search heuristics provide bounds on the expected number of evaluations to find the global optimum, we consider the anytime performance of evolutionary and estimation-of-distribution algorithms. For this purpose, we analyze the fixed-target run time of various algorithms using BinVal as fitness function and bound the run time to optimize the most significant $k \in o(n)$ bits of a bit string with length $n$. We analyze the run times such that they hold not only for a fixed $k$, but simultaneously for all $k \in o(n)$. For the standard (1+1) EA with fixed mutation rate $1/n$, we show that the fixed-target run time for all $k \in o(n)$ is in $Θ(n \log k)$. Using an EDA instead, we get an expected number of evaluations of $Θ(k \log n)$ for the sig-cGA. Replacing in the standard (1+1) EA the fixed mutation rate with a self-adjusting rate, we show that the fixed-target run time for $k \in o(n)$ and a constant $\varepsilon >0$ arbitrarily close to zero is in $\mathcal{O}\left(k^{1+\varepsilon}\right)$ for this algorithm. In particular, this run time is independent of $n$, holds simultaneously for all $k \in o(n)$, and is close to the run time of $Θ(k \log k)$ for the (1+1) EA with the best fixed mutation rate if $k$ is known.
- Abstract（参考訳）: 離散的ランダム化探索ヒューリスティックスのほとんどの理論的実行時間解析は、大域的最適点を求めるために期待される評価数に限界を与えるが、進化的および分布推定アルゴリズムのいつでもの性能を考える。
この目的のために、BinValを適合関数として使用し、様々なアルゴリズムの固定ターゲット実行時間を分析し、最も重要な$k \in o(n)$ビット長$n$のビットを最適化するためにランタイムをバインドする。
固定された$k$だけでなく、すべての$k \in o(n)$に対して同時に保持するように実行時間を分析する。
固定突然変異率が 1/n$ の標準 (1+1) EA に対して、すべての$k \in o(n)$ に対する固定ターゲット実行時間は$(n \log k)$ であることを示す。
代わりに EDA を用いることで、sig-cGA に対して $(k \log n)$ の期待値が得られます。
1+1) EA の固定突然変異率を自己調整率で置き換えると、固定目標実行時間は $k \in o(n)$ で、定数 $\varepsilon > 0$ が 0 に任意に近づくと、このアルゴリズムは $\mathcal{O}\left(k^{1+\varepsilon}\right)$ となる。
特に、この実行時間は$n$とは独立であり、すべての$k \in o(n)$に対して同時に保持され、 (1+1) EA に対して $k$ が知られている場合、最も固定された突然変異率を持つ$(k \log k)$ のランニング時間に近い。
関連論文リスト
- Computational Hardness of Private Coreset [84.99100741615423]
与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。
no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。
$k$-means in the
論文 参考訳（メタデータ） (2026-02-19T15:58:49Z) - Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - Run Time Bounds for Integer-Valued OneMax Functions [0.9012198585960443]
探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。
ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。
本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
論文 参考訳（メタデータ） (2023-07-21T18:49:06Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。
すべての集団サイズを2i mid 0 le i le 18$で計算します。
我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
論文 参考訳（メタデータ） (2020-06-20T01:23:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。