論文の概要: A Finite Markov Chain Analysis of the Simplified Swarm Optimisation Update Rule
- arxiv url: http://arxiv.org/abs/2611.16541v1
- Date: Thu, 12 Nov 2026 09:35:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.415666
- Title: A Finite Markov Chain Analysis of the Simplified Swarm Optimisation Update Rule
- Title(参考訳): 簡易Swarm最適化更新規則の有限マルコフ連鎖解析
- Abstract要約: SSO(Simplified Swarm optimisation)は、グローバルまたはパーソナルのベストをコピーする1つのドローによって各変数を更新する。
ブランチのロギングとチェックポイントの再生は、テストされたOneMaxとLeadingOnesの実行を慣性で遅くする。
速度調整突然変異や一様交叉をもつ$(+1)の遺伝的アルゴリズムに対して一貫した優位性は確立されなかった。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Simplified swarm optimisation (SSO) updates each variable by one draw that copies the global or personal best, keeps the current value or redraws uniformly, with probabilities $c_g$, $c_p$, $c_w$ and $c_r$. As a finite Markov chain under frozen memory, its coordinate kernel $c_w I + (1 - c_w)Π$ has an explicit stationary law and exact convergence rate $c_w^t$. The elitist chain has a geometric hitting-time bound, from a non-optimal start a fixed $c_r$ needs at least $\exp(nc_r/2)$ expected evaluations to reach a unique optimum, and a coupling under changing memories gives $O(n\log n)$ and $O(n^2)$ expected generations on OneMax and LeadingOnes for every population size with redraw share of order $1/n$ and no inertia, and within a $\log n$ factor for fixed inertia. With a frozen memory, inertia cannot speed up first entry into any set from stationary positions, though it can from others. Where the three reference values agree, only $c_r$ acts; where they disagree, copy branches recombine the memories, forcing a redraw only where no active branch holds the target value. Branch logging and checkpoint replay show inertia slowed the tested OneMax and LeadingOnes runs and suggest memory-mediated gains on wider gaps. On Jump functions SSO needed 3.8--8.9 times fewer evaluations than the (1+1) evolutionary algorithm with rate $1/n$, but no consistent advantage over rate-adjusted mutation or a $(μ+1)$ genetic algorithm with uniform crossover was established. The analytical redraw rule improved six of eight benchmark--setting pairs and redundancy allocation, but was slower than $c_r = 0.1$ on Jump$_2$.
- Abstract(参考訳): SSO(Simplified Swarm optimisation)は、グローバルまたはパーソナルベストをコピーする1つのドローによって各変数を更新し、現在の値または再描画を均一に保持し、確率$c_g$, $c_p$, $c_w$, $c_r$とする。
凍結メモリ下の有限マルコフ連鎖として、その座標核 $c_w I + (1 - c_w) = は明示的な定常法則と正確な収束率 $c_w^t$ を持つ。
非最適開始から、固定された$c_r$を少なくとも$\exp(nc_r/2)$期待評価して、一意の最適値に到達し、変化するメモリの下で結合すると、OneMaxおよびLeadingOnes上の期待世代が1/n$で、慣性を持たない全ての集団サイズに対して$O(n\log n)$と$O(n^2)$を与えられる。
凍結したメモリでは、慣性は静止位置からの任意のセットへの最初のエントリをスピードアップすることはできないが、他のものからでも可能である。
3つの参照値が一致する場合は、$c_r$しか動作しないが、それらが一致しない場合は、コピーブランチがメモリを再結合し、アクティブブランチがターゲット値を保持しない場合にのみ、redrawを強制する。
ブランチロギングとチェックポイントのリプレイでは,テスト対象のOneMaxとLeadingOnesの実行が遅くなった。
ジャンプ関数では、SSOは1/n$の(1+1)進化アルゴリズムよりも3.8~8.9倍低い評価を必要としたが、速度調整突然変異や一様交叉をもつ$(μ+1)の遺伝的アルゴリズムに対して一貫した優位性は確立されなかった。
解析的再帰則は,8つのベンチマークセットペアと冗長性アロケーションのうち6つを改善したが,Jump$_2$では$c_r = 0.1$よりも遅かった。
関連論文リスト
- Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback [7.858819231575403]
1次支配(FSD)の単調性は、オンライン最適化(SOO)学習の一般的な削減を可能にする
アルゴリズムは最適ポリシーの動的プログラムを実行し、各期待値を最も楽観的な値に置き換える。
一定のレベルセットの複素数に対して、後悔は連続分布に対しても$tildeO(sqrtnT)$である。
論文 参考訳(メタデータ) (2026-11-02T08:27:17Z) - A Convergence Framework for Deep $V$-Learning: Error Propagation and Sharp Action-Gap Bounds [0.0]
更新エラーを、フィッティング、遷移再利用、ターゲット構築、リプレイ、アクション選択、探索の6つの残差に分解する。
次数$n-$の統計的誤差境界に対して、最適連続割り当てと、制約された最適値の係数2$以内の整数割り当てを導出する。
これらの結果から, FIFO/インターリーブされたSGDに対して, 厳密な動作スコアを有する固定水平生成-リセット近似-ERM法に対して, 期待されるポリシ-ロス一貫性が得られた。
論文 参考訳(メタデータ) (2026-09-16T15:03:46Z) - 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) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳(メタデータ) (2025-06-30T13:27:39Z) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳(メタデータ) (2025-04-06T18:39:45Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳(メタデータ) (2021-06-22T15:50:45Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳(メタデータ) (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。