論文の概要: Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator

• arxiv url: http://arxiv.org/abs/2506.01107v1
• Date: Sun, 01 Jun 2025 18:16:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:33.933784
• Title: Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator
• Title（参考訳）: Markov-Chain Operator Selection と Only-Worsening Acceptance Operator によるハイパーヒューリスティクスの高速化
• Authors: Abderrahim Bendahi, Benjamin Doerr, Adrien Fradin, Johannes F. Lutzeyer,
• Abstract要約: 古典的なCliff$_d$とJump$_m$関数クラスを含む、多数のベンチマーククラスで印象的なパフォーマンスを示す。 我々は、全ての動きの受け入れ演算子を、悪化を受け入れるのみの演算子に置き換える。 我々はマルコフ移動受容超ヒューリスティックに対して$O(nk+1 log n)$の驚くほど良いランタイムを証明した。
• 参考スコア（独自算出の注目度）: 10.404614698222058
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The move-acceptance hyper-heuristic was recently shown to be able to leave local optima with astonishing efficiency (Lissovoi et al., Artificial Intelligence (2023)). In this work, we propose two modifications to this algorithm that demonstrate impressive performances on a large class of benchmarks including the classic Cliff$_d$ and Jump$_m$ function classes. (i) Instead of randomly choosing between the only-improving and any-move acceptance operator, we take this choice via a simple two-state Markov chain. This modification alone reduces the runtime on Jump$_m$ functions with gap parameter $m$ from $\Omega(n^{2m-1})$ to $O(n^{m+1})$. (ii) We then replace the all-moves acceptance operator with the operator that only accepts worsenings. Such a, counter-intuitive, operator has not been used before in the literature. However, our proofs show that our only-worsening operator can greatly help in leaving local optima, reducing, e.g., the runtime on Jump functions to $O(n^3 \log n)$ independent of the gap size. In general, we prove a remarkably good runtime of $O(n^{k+1} \log n)$ for our Markov move-acceptance hyper-heuristic on all members of a new benchmark class SEQOPT$_k$, which contains a large number of functions having $k$ successive local optima, and which contains the commonly studied Jump$_m$ and Cliff$_d$ functions for $k=2$.
• Abstract（参考訳）: 移動受容超ヒューリスティックは、最近、驚くべき効率で局所的なオプティマを離れることができた(Lissovoi et al , Artificial Intelligence (2023))。 本研究では,古典的なCliff$_d$とJump$_m$関数クラスを含む,大規模なベンチマーククラスにおける印象的な性能を示すアルゴリズムを2つの修正して提案する。 (i) 唯一の改善演算子と任意の受け入れ演算子をランダムに選択するのではなく、単純な2状態マルコフ連鎖によって選択する。 この変更だけでJump$_m$関数のランタイムを、ギャップパラメータ$m$で$\Omega(n^{2m-1})$から$O(n^{m+1})$に削減できる。 (ii) より悪くなる演算子のみを受け入れる演算子に全移動許容演算子を置き換える。 このような直感に反する演算子は、文献ではこれまで使われていない。 しかしながら、我々の証明は、唯一の保留演算子が局所最適化を残して、例えば、Jump関数のランタイムをギャップサイズに依存しない$O(n^3 \log n)$に減らすのに大いに役立つことを示している。 一般に、新しいベンチマーククラスSEQOPT$_k$は、$k$逐次局所最適化を持つ多数の関数を含み、よく研究されているJump$_m$とCliff$_d$関数を$k=2$で含む。

関連論文リスト

• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Hyper-Heuristics Can Profit From Global Variation Operators [12.774575491521926]
  モーブアクセプタンス・ハイパーヒューリスティック(MAHH)は,マルチモーダルCLIFFベンチマークの局所的最適化を極めて効率よく残していることを示す。 また、MAHHの局所的な1ビット突然変異演算子を、EAで一般的に使用されるグローバルビットワイズ演算子に置き換えると、JUMP関数上の$min1, O(fraceln(n)m)m, O(nm)$のランタイムが得られることを示す。
  論文  参考訳（メタデータ） (2024-07-19T12:10:05Z)
• 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)
• How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs [6.793248433673384]
  我々は, マルチモーダル崖ベンチマークの局所的最適度を, 高い効率で保ち, モブアクセプタンスハイパーヒューリスティック (MAHH) が最適であることを示す。 また、局所的な1ビット演算子の代わりにグローバルビットワイズ演算子を持つMAHHがジャンプ関数を時間内に最適化することを示した。 これは、いくつかの方法で局所最適に対処する方法を組み合わせることは、実りあるアプローチであることを示している。
  論文  参考訳（メタデータ） (2023-04-20T15:57:33Z)
• 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)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization [133.53164856723782]
  そこで我々は,関数値のみが得られるブラックボックス最小最適化のための新しいアクセラレーションゼロ階運動量 (AccZOM) 法を提案する。 一方,ブラックボックス最小値最適化のためのアクセラレーションゼロ階運動量降下法(Acc-MDA)を提案する。 特に、Acc-MDAは、$tildeO(kappa_y2.5epsilon-3)$の低い勾配の複雑さを、バッチサイズ$O(kappa_y4)$で得ることができる。
  論文  参考訳（メタデータ） (2020-08-18T22:19:29Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Runtime Analysis of a Heavy-Tailed $(1+(\lambda,\lambda))$ Genetic Algorithm on Jump Functions [9.853329403413701]
  ジャンプ関数は、n(k + 1)/2k-k/2eO(k)$フィットネス評価のみの期待実行時に、ジャンプサイズ$k$で最適化できる。 ジャンプサイズが最大$n/4$のすべてのジャンプ関数上の分布パラメータを自然に選択したこのアルゴリズムは、前回の作業で得られる最良のインスタンス固有パラメータに近い性能を持つことを示す。
  論文  参考訳（メタデータ） (2020-06-05T15:57:55Z)
• 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)
• On the Modularity of Hypernetworks [103.1147622394852]
  構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T22:51:52Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。