論文の概要: Per-run Algorithm Selection with Warm-starting using Trajectory-based Features

• arxiv url: http://arxiv.org/abs/2204.09483v2
• Date: Wed, 7 Sep 2022 15:51:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-16 06:22:24.563184
• Title: Per-run Algorithm Selection with Warm-starting using Trajectory-based Features
• Title（参考訳）: トラジェクトリに基づく特徴量を用いたウォームスタート型アルゴリズム選択
• Authors: Ana Kostovska, Anja Jankovic, Diederick Vermetten, Jacob de Nobel, Hao Wang, Tome Eftimov, Carola Doerr
• Abstract要約: インスタンスごとのアルゴリズム選択は、与えられた問題の場合、1つまたは複数の適切なアルゴリズムを推奨する。 提案手法は,実行毎のアルゴリズム選択を行うオンラインアルゴリズム選択方式を提案する。 提案手法は静的なインスタンスごとのアルゴリズム選択よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 5.073358743426584
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Per-instance algorithm selection seeks to recommend, for a given problem instance and a given performance criterion, one or several suitable algorithms that are expected to perform well for the particular setting. The selection is classically done offline, using openly available information about the problem instance or features that are extracted from the instance during a dedicated feature extraction step. This ignores valuable information that the algorithms accumulate during the optimization process. In this work, we propose an alternative, online algorithm selection scheme which we coin per-run algorithm selection. In our approach, we start the optimization with a default algorithm, and, after a certain number of iterations, extract instance features from the observed trajectory of this initial optimizer to determine whether to switch to another optimizer. We test this approach using the CMA-ES as the default solver, and a portfolio of six different optimizers as potential algorithms to switch to. In contrast to other recent work on online per-run algorithm selection, we warm-start the second optimizer using information accumulated during the first optimization phase. We show that our approach outperforms static per-instance algorithm selection. We also compare two different feature extraction principles, based on exploratory landscape analysis and time series analysis of the internal state variables of the CMA-ES, respectively. We show that a combination of both feature sets provides the most accurate recommendations for our test cases, taken from the BBOB function suite from the COCO platform and the YABBOB suite from the Nevergrad platform.
• Abstract（参考訳）: インスタンスごとのアルゴリズム選択は、与えられた問題インスタンスと与えられたパフォーマンス基準に対して、特定の設定に対してうまく動作すると期待される1つまたは複数の適切なアルゴリズムを推奨しようとする。 選択は古典的にオフラインで行われ、専用の機能抽出ステップでインスタンスから抽出された問題インスタンスや機能に関する情報を公開している。 これは最適化プロセス中にアルゴリズムが蓄積する貴重な情報を無視する。 本研究では,実行毎のアルゴリズム選択を考案した,オンラインアルゴリズム選択方式を提案する。 提案手法では, 既定のアルゴリズムを用いて最適化を開始し, 一定回数の反復を繰り返して, この初期最適化器の観測軌道からインスタンス特徴を抽出し, 他の最適化器に切り替えるかどうかを決定する。 我々は、デフォルトの解法としてCMA-ESを用いてこのアプローチを検証し、6種類の最適化アルゴリズムのポートフォリオを切り替える。 オンライン実行毎のアルゴリズム選択に関する他の研究とは対照的に、第1の最適化フェーズで蓄積された情報を用いて第2のオプティマイザをウォームスタートする。 提案手法が静的per-instanceアルゴリズム選択よりも優れていることを示す。 また, cma-esの内部状態変数の探索的ランドスケープ解析と時系列解析に基づいて, 2つの異なる特徴抽出原理を比較した。 両機能セットを組み合わせることで,COCOプラットフォームのBBOB関数スイートとNevergradプラットフォームのYABBOBスイートから取得したテストケースに対して,最も正確なレコメンデーションが提供される。

関連論文リスト

• DynamoRep: Trajectory-Based Population Dynamics for Classification of Black-box Optimization Problems [0.755972004983746]
  簡単な統計量を用いて最適化アルゴリズムの軌道を記述する特徴抽出法を提案する。 提案するDynamoRep機能は,最適化アルゴリズムが動作している問題クラスを特定するのに十分な情報を取得する。
  論文  参考訳（メタデータ） (2023-06-08T06:57:07Z)
• Trajectory-based Algorithm Selection with Warm-starting [2.3823600586675724]
  本研究では,アルゴリズムの性能予測シナリオにおいて,性能回帰モデルとアルゴリズム選択モデルの品質と精度について検討する。 ウォームスタートを用いたトラジェクトリベースラン毎のアルゴリズム選択の有望な性能を示す。
  論文  参考訳（メタデータ） (2022-04-13T14:00:55Z)
• Benchmarking Feature-based Algorithm Selection Systems for Black-box Numerical Optimization [0.0]
  特徴に基づくアルゴリズムの選択は、目に見えない問題において最適化アルゴリズムのポートフォリオから最適なアルゴリズムを自動的に見つけることを目的としている。 本稿では,24個のノイズレスブラックボックス最適化ベンチマーク関数のアルゴリズム選択システムについて分析する。 アルゴリズム選択システムの性能は, 逐次最小二乗プログラミングをプリゾルバとして利用することにより, 大幅に向上できることを示す。
  論文  参考訳（メタデータ） (2021-09-17T07:17:40Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Leveraging Benchmarking Data for Informed One-Shot Dynamic Algorithm Selection [0.9281671380673306]
  進化的アルゴリズムの適用における重要な課題は、目の前の問題に最も適したアルゴリズムインスタンスの選択である。 本研究では, 疑似ブール最適化問題の解法として, このような先行性能データを用いて, 動的アルゴリズム選択スキームを推論する方法について分析する。
  論文  参考訳（メタデータ） (2021-02-12T12:27:02Z)
• Towards Feature-Based Performance Regression Using Trajectory Data [0.9281671380673306]
  ブラックボックス最適化は非常に活発な研究領域であり、毎年多くの新しいアルゴリズムが開発されている。 アルゴリズムの多様性はメタプロブレム(メタプロブレム):どのアルゴリズムが与えられた問題を選択するか? 過去の研究では、探索ランドスケープ分析に基づくインスタンスごとのアルゴリズム選択が、このメタプロブレムに取り組むための効率的な手段であることが示されている。
  論文  参考訳（メタデータ） (2021-02-10T10:19:13Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)
• Stepwise Model Selection for Sequence Prediction via Deep Kernel Learning [100.83444258562263]
  本稿では,モデル選択の課題を解決するために,新しいベイズ最適化(BO)アルゴリズムを提案する。 結果として得られる複数のブラックボックス関数の最適化問題を協調的かつ効率的に解くために,ブラックボックス関数間の潜在的な相関を利用する。 我々は、シーケンス予測のための段階的モデル選択(SMS)の問題を初めて定式化し、この目的のために効率的な共同学習アルゴリズムを設計し、実証する。
  論文  参考訳（メタデータ） (2020-01-12T09:42:19Z)

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

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