論文の概要: Fast instance-specific algorithm configuration with graph neural network
- arxiv url: http://arxiv.org/abs/2501.11240v1
- Date: Mon, 20 Jan 2025 03:01:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-22 14:21:30.089233
- Title: Fast instance-specific algorithm configuration with graph neural network
- Title（参考訳）: グラフニューラルネットワークを用いた高速インスタンス固有アルゴリズムの構成
- Authors: Shingo Aihara, Matthieu Parizy,
- Abstract要約: 本研究は,グラフニューラルネットワークを用いて特徴抽出とクラス決定を合理化することにより,ISAC実行段階の時間を大幅に短縮する手法を提案する。
実験の結果、最初のISAC方式で10秒かかる実行ステップで$T_tune$をサブ秒に減らすことができた。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Combinatorial optimization (CO) problems are pivotal across various industrial applications, where the speed of solving these problems is crucial. Improving the performance of CO solvers across diverse input instances requires fine-tuning solver parameters for each instance. However, this tuning process is time-consuming, and the time required increases with the number of instances. To address this, a method called instance-specific algorithm configuration (ISAC) has been devised. This approach involves two main steps: training and execution. During the training step, features are extracted from various instances and then grouped into clusters. For each cluster, parameters are fine-tuned. This cluster-specific tuning process results in a set of generalized parameters for instances belonging to each class. In the execution step, features are extracted from an unknown instance to determine its cluster, and the corresponding pre-tuned parameters are applied. Generally, the running time of a solver is evaluated by the time to solution ($TTS$). However, methods like ISAC require preprocessing. Therefore, the total execution time is $T_{tot}=TTS+T_{tune}$, where $T_{tune}$ represents the tuning time. While the goal is to minimize $T_{tot}$, it is important to note that extracting features in the ISAC method requires a certain amount of computational time. The extracting features include summary statistics of the solver execution logs, which takes several 10 seconds. This research presents a method to significantly reduce the time of the ISAC execution step by streamlining feature extraction and class determination with a graph neural network. Experimental results show that $T_{tune}$ in the execution step, which take several 10 seconds in the original ISAC manner, could be reduced to sub-seconds.
- Abstract（参考訳）: 組合せ最適化(CO)問題は、これらの問題を解決するスピードが不可欠である様々な産業アプリケーションにおいて重要な問題である。
多様な入力インスタンス間でCOソルバの性能を改善するには、各インスタンスの微調整ソルバパラメータが必要である。
しかし、このチューニングプロセスは時間がかかり、インスタンスの数に応じて必要な時間が増加する。
これを解決するために、ISAC ( instance-specific algorithm configuration) と呼ばれる手法が考案された。
このアプローチには、トレーニングと実行の2つの主要なステップがある。
トレーニングステップでは、さまざまなインスタンスから機能を抽出し、クラスタにグループ化する。
各クラスタについて、パラメータは微調整される。
このクラスタ固有のチューニングプロセスは、各クラスに属するインスタンスに対する一般化されたパラメータのセットをもたらす。
実行ステップでは、未知のインスタンスから特徴を抽出してクラスタを決定し、対応する事前調整されたパラメータを適用する。
一般に、解法器の実行時間は解法時間によって評価される(TTS$)。
しかし、ISACのような方法は前処理を必要とする。
したがって、総実行時間は$T_{tot}=TTS+T_{tune}$であり、$T_{tune}$はチューニング時間を表す。
目的は$T_{tot}$を最小化することであるが、ISAC法の特徴抽出にはある程度の計算時間が必要であることに注意する必要がある。
抽出機能には、ソルバの実行ログのサマリ統計が含まれている。
本研究は,グラフニューラルネットワークを用いて特徴抽出とクラス決定を合理化することにより,ISAC実行段階の時間を大幅に短縮する手法を提案する。
実験結果によると、実行ステップで$T_{tune}$は、元のISAC方式で10秒以上かかるので、サブ秒に短縮できる。
関連論文リスト
- Learning Algorithm Hyperparameters for Fast Parametric Convex Optimization [2.0403774954994858]
本稿では,一階法のハイパーパラメータ列を学習するための機械学習フレームワークを提案する。
いくつかのアルゴリズムのハイパーパラメータの学習方法を示す。
本稿では,制御,信号処理,機械学習など,多くの例を用いて本手法の有効性を示す。
論文 参考訳（メタデータ） (2024-11-24T04:58:36Z) - Scaling LLM Inference with Optimized Sample Compute Allocation [56.524278187351925]
我々は、異なる推論構成の最適な混合を見つけるアルゴリズムであるOSCAを提案する。
実験の結果,学習した混合アロケーションでは,最高の単一構成よりも精度がよいことがわかった。
OSCAはシングルターンタスク以外のエージェント処理にも有効であることが示されており、デフォルト設定よりも3倍少ない計算でSWE-Benchの精度が向上している。
論文 参考訳（メタデータ） (2024-10-29T19:17:55Z) - Distributed Collapsed Gibbs Sampler for Dirichlet Process Mixture Models
in Federated Learning [0.22499166814992444]
本稿では,DPMM (DisCGS) のための分散マルコフ連鎖モンテカルロ (MCMC) 推論手法を提案する。
我々のアプローチでは、崩壊したGibbsサンプルラーを使用し、独立マシンと異種マシンの分散データを扱うように設計されています。
例えば、100Kのデータポイントのデータセットでは、中央集権的なアルゴリズムは100回のイテレーションを完了するのに約12時間かかります。
論文 参考訳（メタデータ） (2023-12-18T13:16:18Z) - Sequential Gradient Coding For Straggler Mitigation [28.090458692750023]
分散コンピューティングでは、遅いノード(ストラグラー)がボトルネックとなる。
グラディエント符号化(GC)は、誤り訂正符号の原理を用いて、ストラグラーの存在下で勾配計算を分散する効率的な手法である。
本稿では,GCと比較して性能向上を示す2つのスキームを提案する。
論文 参考訳（メタデータ） (2022-11-24T21:12:49Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Active Sampling of Multiple Sources for Sequential Estimation [92.37271004438406]
本研究の目的は,パラメータを逐次推定するアクティブサンプリングアルゴリズムを設計し,信頼性の高い推定値を生成することである。
本稿では, エンフ条件推定コスト関数を導入し, 最近, トラクタブル解析を施した逐次推定手法を提案する。
論文 参考訳（メタデータ） (2022-08-10T15:58:05Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳（メタデータ） (2021-07-27T08:48:01Z) - Hyperparameter Transfer Learning with Adaptive Complexity [5.695163312473305]
ネストされたドロップアウトと自動関連性判定によって複雑性を高める順序付き非線形基底関数の集合を学習する新しいマルチタスクBO法を提案する。
論文 参考訳（メタデータ） (2021-02-25T12:26:52Z) - Fast Learning for Renewal Optimization in Online Task Scheduling [18.935043109084543]
本稿では,リニューアル・リワードシステムのオンライン最適化について考察する。
タスク型ベクトルの確率分布は未知である。
提案アルゴリズムは,古典的なRobins-Monroイテレーションに従って更新される補助変数を用いる。
論文 参考訳（メタデータ） (2020-07-18T22:44:13Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。