論文の概要: Trajectory-based Algorithm Selection with Warm-starting
- arxiv url: http://arxiv.org/abs/2204.06397v2
- Date: Tue, 7 Jun 2022 11:45:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 02:55:15.729697
- Title: Trajectory-based Algorithm Selection with Warm-starting
- Title（参考訳）: ウォームスタートによる軌道に基づくアルゴリズム選択
- Authors: Anja Jankovic, Diederick Vermetten, Ana Kostovska, Jacob de Nobel,
Tome Eftimov, Carola Doerr
- Abstract要約: 本研究では,アルゴリズムの性能予測シナリオにおいて,性能回帰モデルとアルゴリズム選択モデルの品質と精度について検討する。
ウォームスタートを用いたトラジェクトリベースラン毎のアルゴリズム選択の有望な性能を示す。
- 参考スコア（独自算出の注目度）: 2.3823600586675724
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Landscape-aware algorithm selection approaches have so far mostly been
relying on landscape feature extraction as a preprocessing step, independent of
the execution of optimization algorithms in the portfolio. This introduces a
significant overhead in computational cost for many practical applications, as
features are extracted and computed via sampling and evaluating the problem
instance at hand, similarly to what the optimization algorithm would perform
anyway within its search trajectory. As suggested in Jankovic et al. (EvoAPPs
2021), trajectory-based algorithm selection circumvents the problem of costly
feature extraction by computing landscape features from points that a solver
sampled and evaluated during the optimization process. Features computed in
this manner are used to train algorithm performance regression models, upon
which a per-run algorithm selector is then built.
In this work, we apply the trajectory-based approach onto a portfolio of five
algorithms. We study the quality and accuracy of performance regression and
algorithm selection models in the scenario of predicting different algorithm
performances after a fixed budget of function evaluations. We rely on landscape
features of the problem instance computed using one portion of the
aforementioned budget of the same function evaluations. Moreover, we consider
the possibility of switching between the solvers once, which requires them to
be warm-started, i.e. when we switch, the second solver continues the
optimization process already being initialized appropriately by making use of
the information collected by the first solver. In this new context, we show
promising performance of the trajectory-based per-run algorithm selection with
warm-starting.
- Abstract（参考訳）: ランドスケープアウェアなアルゴリズム選択アプローチは、ポートフォリオでの最適化アルゴリズムの実行とは無関係に、前処理ステップとしてランドスケープ機能抽出に依存している。
これは、最適化アルゴリズムが探索軌道内でどのような処理を行うかと同様に、目の前の問題事例をサンプリングし評価することで特徴を抽出し、計算することで、多くの実用的なアプリケーションにおいて計算コストの大幅なオーバーヘッドをもたらす。
Jankovic et al. (EvoAPPs 2021) で示唆されているように、軌道に基づくアルゴリズム選択は、最適化プロセス中にソルバがサンプリングし評価した点からランドスケープの特徴を計算することによってコストの高い特徴抽出の問題を回避する。
この方法で計算された機能はアルゴリズムのパフォーマンス回帰モデルのトレーニングに使用され、実行毎のアルゴリズムセレクタが構築される。
本研究では,軌跡に基づくアプローチを5つのアルゴリズムのポートフォリオに適用する。
本研究では,関数評価の固定予算後の異なるアルゴリズム性能を予測するシナリオにおいて,性能回帰モデルとアルゴリズム選択モデルの品質と精度について検討する。
我々は、上記の機能評価の予算の一部を用いて計算された問題インスタンスのランドスケープ特性に依存している。
また、第1のソルバが収集した情報を利用して、第2のソルバが既に初期化されている最適化プロセスを継続するなど、ウォームスタートを必要とするソルバを一度切り替える可能性についても検討する。
この新しい文脈では、ウォームスタートによる軌道ベースの実行毎アルゴリズム選択の有望な性能を示す。
関連論文リスト
- On Constructing Algorithm Portfolios in Algorithm Selection for Computationally Expensive Black-box Optimization in the Fixed-budget Setting [0.0]
本稿では,アルゴリズムポートフォリオ構築におけるサンプリングフェーズにおける関数評価の回数を考慮することの重要性を論じる。
その結果,提案手法により構築されたアルゴリズムのポートフォリオは,従来の手法よりも大幅に向上していることがわかった。
論文 参考訳（メタデータ） (2024-05-13T03:31:13Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Per-run Algorithm Selection with Warm-starting using Trajectory-based
Features [5.073358743426584]
インスタンスごとのアルゴリズム選択は、与えられた問題の場合、1つまたは複数の適切なアルゴリズムを推奨する。
提案手法は,実行毎のアルゴリズム選択を行うオンラインアルゴリズム選択方式を提案する。
提案手法は静的なインスタンスごとのアルゴリズム選択よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-04-20T14:30:42Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - 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) - 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) - Landscape-Aware Fixed-Budget Performance Regression and Algorithm
Selection for Modular CMA-ES Variants [1.0965065178451106]
市販の教師あり学習手法を用いて,高品質な性能予測が可能であることを示す。
このアプローチを,モジュール型CMA-ESアルゴリズム群から選択した,非常に類似したアルゴリズムのポートフォリオ上でテストする。
論文 参考訳（メタデータ） (2020-06-17T13:34:57Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。