論文の概要: When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection

• arxiv url: http://arxiv.org/abs/2604.07473v1
• Date: Wed, 08 Apr 2026 18:11:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-10 18:34:05.49973
• Title: When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection
• Title（参考訳）: アルゴリズムの切り替えが役に立つ:オンラインアルゴリズム選択の理論的研究
• Authors: Denis Antipov, Carola Doerr,
• Abstract要約: オンラインセレクション(OAS)は、フィットネスのランドスケープの変化に最適化プロセスを適用することを目的としており、特定のポートフォリオから任意のアルゴリズムを上回ることが期待されている。 現在、OASがスピードアップを達成できるという理論的な結果は得られていない。 本稿では,2つのアルゴリズムの切り換えが,それぞれのアルゴリズムの分離よりも問題的に高速であることを示す最初の理論的例を示す。
• 参考スコア（独自算出の注目度）: 0.15469452301122175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups (apart from some artificial examples for hyper-heuristics). Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing. In this paper, we present the first theoretical example in which switching between two algorithms -- the $(1+λ)$ EA and the $(1+(λ,λ))$ GA -- solves the OneMax problem asymptotically faster than either algorithm used in isolation. We show that an appropriate choice of population sizes for the two algorithms allows the optimum to be reached in $O(n\log\log n)$ expected time, faster than the $Θ(n\sqrt{\frac{\log n \log\log\log n}{\log\log n}})$ runtime of the best of these two algorithms with optimally tuned parameters. We first establish this bound under an idealized switching rule that changes from the $(1+λ)$ to the $(1+(λ,λ))$ GA at the optimal time. We then propose a realistic switching strategy that achieves the same performance. Our analysis combines fixed-start and fixed-target perspectives, illustrating how different algorithms dominate at different stages of the optimization process. This approach offers a promising path toward a deeper theoretical understanding of OAS.
• Abstract（参考訳）: オンラインアルゴリズム選択(OAS)は、フィットネスのランドスケープの変化に最適化プロセスを適用することを目的としており、特定のポートフォリオから任意のアルゴリズムを上回ることが期待されている。 この予想は多くの経験的な研究によって支持されているが、OASが漸近的なスピードアップをもたらすことを示す理論的結果は今のところない(超ヒューリスティックスのいくつかの人工的な例は別として)。 さらに、アルゴリズムを切り替えるタイミングと方法に関する理論に基づくガイドラインは、ほとんど失われている。 本稿では, 1+λ) = EA と 1+(λ,λ) = GA の 2 つのアルゴリズムの切り換えが, いずれのアルゴリズムよりも漸近的に高速であることを示す最初の理論的例を示す。 この2つのアルゴリズムの集団サイズを適切に選択することで、最適なパラメータを最適に調整した2つのアルゴリズムのうちの最高の実行の実行時間を、$O(n\log\log n)$期待時間で、$O(n\sqrt{\frac{\log n \log\log n}{\log n}})$より高速に達成できることが示される。 1+λ)$ から 1+(λ,λ)$ GA に最適なタイミングで変化する理想的なスイッチング規則の下で、まずこの境界を定めます。 次に,同じ性能を実現する現実的なスイッチング戦略を提案する。 我々の分析は、最適化プロセスの異なる段階において、異なるアルゴリズムがどのように支配されているかを示す固定開始視点と固定目標視点を組み合わせる。 このアプローチは、OASのより深い理論的理解に向けた有望な道を提供する。

関連論文リスト

• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。 その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
  論文  参考訳（メタデータ） (2023-12-14T17:31:38Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
  本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。 そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。 我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
  論文  参考訳（メタデータ） (2023-01-23T19:13:25Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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