Fugu-MT 論文翻訳(概要): Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal

論文の概要: Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal

arxiv url: http://arxiv.org/abs/2606.13344v1
Date: Thu, 11 Jun 2026 13:34:03 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-12 15:55:27.819263
Title: Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal
Title（参考訳）: BinVal上の$(μ+ 1)$ EAのランタイム境界の改善
Authors: Joris Belder, Johannes Lengler, Raghu Raman Ravi,
Abstract要約: 我々は、$(+1)$ EAが、OneMaxよりもBinValの方が少なくとも$O(log cdot log n)$遅いことを示しています。
参考スコア（独自算出の注目度）: 0.9298078773213346
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the $(μ+1)$ EA on the Binary Value function BinVal. We show that it needs at most $O(μ\log μ\cdot n \log n)$ function evaluations to find the optimum when $μ= o(n/\log n)$. This substantially improves upon the recent upper bound of $O(μ^5 n \log(n/μ^4))$ by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the $(μ+1)$ EA is at most a factor $O(\log μ\cdot \log n)$ slower on BinVal than on OneMax.
Abstract（参考訳）: 結合値関数 BinVal 上の$(μ+1)$ EA について検討する。我々は、少なくとも$O(μ\log μ\cdot n \log n)$関数の評価が必要であり、$μ= o(n/\log n)$ のときの最適値を求める。これは、Krejca, Neumann and Witt による最近の$O(μ^5 n \log(n/μ^4))$の上限を大幅に改善する。我々の結果は、標準的なビット突然変異を含むいくつかの突然変異演算子に対して成り立つ。特に、我々の有界性は、$(μ+1)$ EA が少なくとも$O(\log μ\cdot \log n)$ BinVal において OneMax よりも遅くなることを意味する。

関連論文リスト

Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。 f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
論文参考訳（メタデータ） (2026-05-13T17:34:24Z)
Anytime Analysis on BinVal: Adaptive Parameters Help [0.0]
我々は、BinValをフィットネス機能として利用して、様々なアルゴリズムの固定目標実行時間を分析する。固定目標実行時間は o(n)$ で、定数 $varepsilon > 0$ が 0 に近いのは、このアルゴリズムに対して $mathcalOleft(k1+varepsilonright)$ である。
論文参考訳（メタデータ） (2026-04-08T11:47:10Z)
Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
論文参考訳（メタデータ） (2026-03-09T22:27:00Z)
Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions [9.044970217182117]
分解に基づく多目的進化アルゴリズム(MOEA/D)は、与えられた多目的関数$f$を直接最適化するのではなく、共進化的に$f$の単目的サブプロブレム$N + 1$を最適化する。我々は、標準突然変異演算子のみを持つMOEA/Dが、OneMinMaxベンチマークのPareto全体を計算する方法について、初めて分析する。パワーローに対する我々の全体的な境界は、MOEA/D が$N = O(nbeta - 1)$ に対して最も良く、結果として$O(n) となることを示唆している。
論文参考訳（メタデータ） (2024-05-02T05:32:19Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone Functions [7.111443975103329]
突然変異率$c/n$ for $cle 1$で、1:s+1)$-successルールで集団サイズを適応的に制御する。この$c=1$のセットアップは1maxで$s1$で効率的であるが、$s ge 18$で非効率的であることを示す。
論文参考訳（メタデータ） (2022-04-01T15:46:12Z)
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。我々はこの$d$への依存が対数的要因まで最適であることを示す。また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文参考訳（メタデータ） (2021-11-09T00:20:01Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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