論文の概要: Signed Sensitivity of Expected Hitting Time to Mutation Rate in the (1+1) EA: Per-State Sign Theorems and Verifiable Certificates for Non-Lumpable Families
- arxiv url: http://arxiv.org/abs/2609.12510v1
- Date: Fri, 11 Sep 2026 07:14:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-15 07:38:31.652011
- Title: Signed Sensitivity of Expected Hitting Time to Mutation Rate in the (1+1) EA: Per-State Sign Theorems and Verifiable Certificates for Non-Lumpable Families
- Title（参考訳）: 1+1)EAにおけるハッティング時間と突然変異率の有意な感度:状態ごとのサイン理論と非言語家族に対する検証可能な証明書
- Abstract要約: 本研究は, 予測打撃時間$H_p=mathbbE_x T$の変異率に対する感度について検討した。
2つのフィットネス関数は1ステップの成功率曲線全体を共有するが、期待されるヒット時間は2つの正確な有理数である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For the (1+1) evolutionary algorithm with standard bit mutation, we study the sensitivity of the expected hitting time $H_p=\mathbb{E}_x T$ to the mutation rate. We first point out an easily overlooked formalization pitfall: the improvement event is not monotone in the mutation mask, so the unsigned (total-influence) form of the Margulis-Russo formula does not apply; the correct object is the signed endpoint difference. Second, we give an exact three-dimensional separation: two fitness functions share the entire one-step success-rate curve, yet their expected hitting times are two different exact rational numbers; hence one-step success-rate quantities do not determine the expected hitting time. Building on the runtime derivative $H'_p=(I-Q_p)^{-1}Q'_p H_p$, we construct computable double-residual sign certificates, prove a per-initial-state sign theorem on OneMax (for every non-optimal initial state, $\partial_c H<0$ on $0<c<1$, where $p=c/n$; at $c=1$ only the distance-one state is stationary), and extend the framework to non-lumpable positive linear families: an explicit non-lumpability witness, a block-interval double-residual certificate that covers all states without enumerating them, a uniform sign bound $\partial_c\mathbb{E}T\le -9n/16$ over the whole interval $c\in[1/4,1/2]$ for an explicit family at all even scales $n\ge 8$, and a heterogeneous instance certificate $H'_x\le -1/6$ on 57 of 63 states across $c=1$. All finite verifications use exact rational arithmetic. A bounded systematic literature search did not uncover this exact combination, although the underlying tools are well established; we therefore make no novelty claim beyond the stated combination.
- Abstract（参考訳）: 標準ビット突然変異を持つ(1+1)進化的アルゴリズムについて、予測ヒット時間$H_p=\mathbb{E}_x T$の突然変異率に対する感度について検討する。
改善事象は突然変異マスクにおいて単調ではないので、マルグリス・ルッソの公式の符号なし(トータル影響)形式は適用されない。
第二に、2つのフィットネス関数は1ステップの成功率曲線全体を共有するが、それらの期待されるヒット時間は2つの正確な有理数である。
実行時微分 $H'_p=(I-Q_p)^{-1}Q'_p H_p$ の上に、計算可能な二重残留符号証明を構築し、OneMax 上の初期状態当たりの符号定理(すべての非最適初期状態に対して$\partial_c H<0$ on $0<c<1$, where $p=c/n$; at $c=1$ 距離1は定常である)を証明し、フレームワークを非可換な正の線形族に拡張する。
すべての有限検証は完全有理算術を使用する。
体系的な体系的な文献検索は、基礎となるツールが十分に確立されているにもかかわらず、この正確な組み合わせを明らかにしなかった。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - One Inverse Step is a Convex Program: Bayes-Limit Calibration of Diffusion Inversion [0.0]
1つの暗黙のDDIM反転ステップは、事前訓練された拡散モデルが局所多様体幾何学を符号化するかどうかの最も安価なプローブである。
フェルミ窓はモデルのトレーニングサポートと3.6$-$5.6times$で対立し、ヘッセン=リプシッツ定数は法が読み取る曲率の2-$12%である。
最後の条件付き天井 $_t_max(mathrmsym,J)le1$, from $mathrmCov(x_0mid x_t)succeq0$
論文 参考訳（メタデータ） (2026-08-24T11:01:54Z) - The Physical Cutoff Does Not Restore Homogenization: Phase-Dependent Burning in the Strain G-Equation [2.538209532048867]
C2$非圧縮性周期フローに対して、すべての$varepsilon$-ward barrier certificateが半径を少なくとも2dvarepsilon$でカバーしていることを証明している。
論文 参考訳（メタデータ） (2026-08-15T17:41:14Z) - An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。
私たちの指導原則は、最大値が丸みを帯びた候補であることです。
論文 参考訳（メタデータ） (2026-08-03T17:58:00Z) - The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳（メタデータ） (2026-08-03T17:57:01Z) - Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Random Parameter Noise Does Not Make Exact ReLU Verification Easy [14.270378035741404]
逆スムースドモデルにおけるReLUネットワークの正確な検証について検討する。
標準的な仮定である$mathrmNPnotsubseteqmathrmBPP$ では,ネットワークサイズ,ビット複雑性,各ベースインスタンスの逆ノイズレベルにランニングタイムを埋め込むような,健全かつ完全検証器が存在しないことを示す。
論文 参考訳（メタデータ） (2026-07-15T21:26:20Z) - Nonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat It [46.80389197344682]
位相遷移機構を一般非線形TTSAに拡張する局所移動定理を証明した。
証明は漸近的ではなく、2つのアベル変換のキャンセルに依存している。
論文 参考訳（メタデータ） (2026-06-12T14:24:28Z) - Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
2026年のエルツの単位距離予想とサウィンの量的洗練の反証は、固定正の$varepsilon$に対して、n$平面点の間の単位距離の最大値$u(n)$が$n1+varepsilon$を超えることを示す。
本稿では、Sawinのパラメータ選択を非線形整数最適化問題として扱い、素集合$T$と$S_Q$を含む証明書のためのオープンソースのPythonパイプラインを開発する。
論文 参考訳（メタデータ） (2026-06-02T10:05:23Z) - 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) - Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
時間差分学習(TD(0))は強化学習の基本である。
マルコフデータを混合したバニラTD(0)の最初の高確率有限サンプル解析を行う。
論文 参考訳（メタデータ） (2025-02-08T22:01:02Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。