論文の概要: Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection
- arxiv url: http://arxiv.org/abs/2405.11349v2
- Date: Mon, 3 Jun 2024 12:55:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-04 14:29:15.599752
- Title: Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection
- Title（参考訳）: アルゴリズムの特徴を解き放つ:アルゴリズム選択のための一般化解析
- Authors: Xingyu Wu, Yan Zhong, Jibin Wu, Yuxiao Huang, Sheng-hao Wu, Kay Chen Tan,
- Abstract要約: 本稿では,アルゴリズムの特徴に基づくアルゴリズム選択の証明可能な最初の保証を提案する。
アルゴリズムの特徴に関連する利点とコストを分析し、一般化誤差が様々な要因にどのように影響するかを考察する。
- 参考スコア（独自算出の注目度）: 25.29451529910051
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the algorithm selection research, the discussion surrounding algorithm features has been significantly overshadowed by the emphasis on problem features. Although a few empirical studies have yielded evidence regarding the effectiveness of algorithm features, the potential benefits of incorporating algorithm features into algorithm selection models and their suitability for different scenarios remain unclear. In this paper, we address this gap by proposing the first provable guarantee for algorithm selection based on algorithm features, taking a generalization perspective. We analyze the benefits and costs associated with algorithm features and investigate how the generalization error is affected by different factors. Specifically, we examine adaptive and predefined algorithm features under transductive and inductive learning paradigms, respectively, and derive upper bounds for the generalization error based on their model's Rademacher complexity. Our theoretical findings not only provide tight upper bounds, but also offer analytical insights into the impact of various factors, such as the training scale of problem instances and candidate algorithms, model parameters, feature values, and distributional differences between the training and test data. Notably, we demonstrate how models will benefit from algorithm features in complex scenarios involving many algorithms, and proves the positive correlation between generalization error bound and $\chi^2$-divergence of distributions.
- Abstract（参考訳）: アルゴリズム選択研究において,アルゴリズムの特徴を取り巻く議論は,問題特徴の強調によって著しく過小評価されている。
アルゴリズム特徴の有効性に関する実証的研究はいくつかあるが、アルゴリズム選択モデルにアルゴリズム特徴を組み込むことの潜在的な利点は明らかでない。
本稿では,アルゴリズムの特徴に基づくアルゴリズム選択の証明可能な最初の保証を提案し,一般化の観点から,このギャップに対処する。
アルゴリズムの特徴に関連する利点とコストを分析し、一般化誤差が様々な要因にどのように影響するかを考察する。
具体的には、帰納的学習パラダイムと帰納的学習パラダイムに基づく適応的および事前定義されたアルゴリズム機能について検討し、モデルのRadecher複雑性に基づく一般化誤差の上限を導出する。
我々の理論的な知見は、厳密な上限を提供するだけでなく、問題インスタンスと候補アルゴリズムのトレーニングスケール、モデルパラメータ、特徴値、トレーニングデータとテストデータの分布差など、様々な要因の影響に関する分析的な洞察も提供する。
特に、多くのアルゴリズムを含む複雑なシナリオにおいて、モデルがアルゴリズムの特徴の恩恵を受けることを示し、一般化誤差境界と分布の$\chi^2$-divergenceとの正の相関を証明した。
関連論文リスト
- A Survey of Meta-features Used for Automated Selection of Algorithms for Black-box Single-objective Continuous Optimization [4.173197621837912]
単目的連続ブラックボックス最適化の分野におけるアルゴリズム選択への重要な貢献について概説する。
自動アルゴリズム選択、構成、性能予測のための機械学習モデルについて検討する。
論文 参考訳（メタデータ） (2024-06-08T11:11:14Z) - Quantized Hierarchical Federated Learning: A Robust Approach to
Statistical Heterogeneity [3.8798345704175534]
本稿では,コミュニケーション効率に量子化を組み込んだ新しい階層型フェデレーション学習アルゴリズムを提案する。
最適性ギャップと収束率を評価するための包括的な分析フレームワークを提供する。
この結果から,本アルゴリズムはパラメータの範囲で常に高い学習精度を達成できることが判明した。
論文 参考訳（メタデータ） (2024-03-03T15:40:24Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Multivariate Systemic Risk Measures and Computation by Deep Learning
Algorithms [63.03966552670014]
本稿では,主観的最適度と関連するリスク割り当ての公平性に着目し,重要な理論的側面について論じる。
私たちが提供しているアルゴリズムは、予備項の学習、二重表現の最適化、およびそれに対応する公正なリスク割り当てを可能にします。
論文 参考訳（メタデータ） (2023-02-02T22:16:49Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。
新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。
反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
論文 参考訳（メタデータ） (2022-12-06T12:42:11Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z) - Identifying Co-Adaptation of Algorithmic and Implementational
Innovations in Deep Reinforcement Learning: A Taxonomy and Case Study of
Inference-based Algorithms [15.338931971492288]
我々は、アルゴリズムの革新と実装決定を分離するために、一連の推論に基づくアクター批判アルゴリズムに焦点を当てる。
実装の詳細がアルゴリズムの選択に一致すると、パフォーマンスが大幅に低下します。
結果は、どの実装の詳細がアルゴリズムと共適応され、共進化しているかを示す。
論文 参考訳（メタデータ） (2021-03-31T17:55:20Z) - Algorithmic Stability and Generalization of an Unsupervised Feature
Selection Algorithm [20.564573628659918]
アルゴリズム安定性は、入力サンプルの摂動に対する感度に関するアルゴリズムの重要な特徴である。
本稿では,この安定性を保証可能な保証で実現した,革新的な教師なし特徴選択アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-19T12:25:39Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。