論文の概要: Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms

• arxiv url: http://arxiv.org/abs/2211.14722v2
• Date: Tue, 29 Nov 2022 01:49:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-30 12:08:04.570922
• Title: Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms
• Title（参考訳）: 最適計算予算割当アルゴリズムの収束率解析
• Authors: Yanwen Li, Siyang Gao
• Abstract要約: オーディナル最適化(Ordinal Optimization, OO)は、離散イベント動的システムを最適化するための広く研究されている手法である。 OOのよく知られた方法は、最適計算予算配分(OCBA)である。 本稿では,2つのOCBAアルゴリズムについて検討する。
• 参考スコア（独自算出の注目度）: 1.713291434132985
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ordinal optimization (OO) is a widely-studied technique for optimizing discrete-event dynamic systems (DEDS). It evaluates the performance of the system designs in a finite set by sampling and aims to correctly make ordinal comparison of the designs. A well-known method in OO is the optimal computing budget allocation (OCBA). It builds the optimality conditions for the number of samples allocated to each design, and the sample allocation that satisfies the optimality conditions is shown to asymptotically maximize the probability of correct selection for the best design. In this paper, we investigate two popular OCBA algorithms. With known variances for samples of each design, we characterize their convergence rates with respect to different performance measures. We first demonstrate that the two OCBA algorithms achieve the optimal convergence rate under measures of probability of correct selection and expected opportunity cost. It fills the void of convergence analysis for OCBA algorithms. Next, we extend our analysis to the measure of cumulative regret, a main measure studied in the field of machine learning. We show that with minor modification, the two OCBA algorithms can reach the optimal convergence rate under cumulative regret. It indicates the potential of broader use of algorithms designed based on the OCBA optimality conditions.
• Abstract（参考訳）: 順序最適化 (ordinal optimization, oo) は離散事象動的システム (deds) を最適化するための広く研究された手法である。 有限集合におけるシステム設計の性能をサンプリングにより評価し、設計の順序的比較を正しく行うことを目的とする。 OOのよく知られた方法は、最適計算予算配分(OCBA)である。 各設計に割り当てられたサンプル数に対する最適性条件を構築し、最適性条件を満たすサンプル割り当ては、最適な設計のための正しい選択の確率を漸近的に最大化する。 本稿では,2つのOCBAアルゴリズムについて検討する。 各設計のサンプルに対する既知の分散により、それぞれの収束率を異なる性能指標で特徴付ける。 まず2つのOCBAアルゴリズムが正しい選択の確率と期待される機会コストで最適収束率を達成することを実証した。 これはocbaアルゴリズムの収束解析の空白を埋める。 次に、機械学習の分野で研究されている主要な尺度である累積後悔の尺度に分析を拡張する。 2つのOCBAアルゴリズムは,小さな修正を加えれば,累積後悔の下で最適収束率に達することを示す。 これはOCBA最適条件に基づいて設計されたアルゴリズムの幅広い利用の可能性を示している。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• 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)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Selection of the Most Probable Best [2.1095005405219815]
  予測値ランキングと選択(R&S)問題では,すべてのk解のシミュレーション出力が,分布によって不確実性をモデル化可能な共通パラメータに依存する。 我々は、最も確率の高い最適解 (MPB) を、分布に関して最適である確率が最も大きい解と定義する。 最適化条件における未知の手段をその推定値に置き換えるアルゴリズムを考案し,シミュレーション予算が増加するにつれて,アルゴリズムのサンプリング比が条件を満たすことを証明した。
  論文  参考訳（メタデータ） (2022-07-15T15:27:27Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• A unified surrogate-based scheme for black-box and preference-based optimization [2.561649173827544]
  ブラックボックスと嗜好に基づく最適化問題は密接に関連しており、同じアプローチのファミリを用いて解決可能であることを示す。 一般的なMSRSフレームワークを一般化した最適化手法である一般化されたメトリック応答面(gMRS)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-03T08:47:54Z)
• An Efficient Batch Constrained Bayesian Optimization Approach for Analog Circuit Synthesis via Multi-objective Acquisition Ensemble [11.64233949999656]
  MACE(Multi-objective Acquisition Function Ensemble)を用いた並列化可能なベイズ最適化アルゴリズムを提案する。 提案アルゴリズムは,バッチサイズが15のときの非制約最適化問題に対する微分進化(DE)と比較して,シミュレーション全体の時間を最大74倍削減することができる。 制約付き最適化問題に対して,提案アルゴリズムは,バッチサイズが15の場合に,重み付き改善に基づくベイズ最適化(WEIBO)アプローチと比較して最大15倍の高速化を実現することができる。
  論文  参考訳（メタデータ） (2021-06-28T13:21:28Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• 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)

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

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