論文の概要: A Batch Sequential Halving Algorithm without Performance Degradation
- arxiv url: http://arxiv.org/abs/2406.00424v1
- Date: Sat, 1 Jun 2024 12:41:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 07:05:16.106773
- Title: A Batch Sequential Halving Algorithm without Performance Degradation
- Title(参考訳): 性能劣化のないバッチ逐次Halvingアルゴリズム
- Authors: Sotetsu Koyamada, Soichiro Nishimori, Shin Ishii,
- Abstract要約: 簡単な逐次バッチアルゴリズムでは,実運用環境での性能が劣化しないことを示す。
実験により,固定サイズバッチ設定におけるアルゴリズムの頑健な性質を実証し,我々の主張を実証的に検証する。
- 参考スコア(独自算出の注目度): 0.8283940114367677
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we investigate the problem of pure exploration in the context of multi-armed bandits, with a specific focus on scenarios where arms are pulled in fixed-size batches. Batching has been shown to enhance computational efficiency, but it can potentially lead to a degradation compared to the original sequential algorithm's performance due to delayed feedback and reduced adaptability. We introduce a simple batch version of the Sequential Halving (SH) algorithm (Karnin et al., 2013) and provide theoretical evidence that batching does not degrade the performance of the original algorithm under practical conditions. Furthermore, we empirically validate our claim through experiments, demonstrating the robust nature of the SH algorithm in fixed-size batch settings.
- Abstract(参考訳): 本稿では,固定サイズのバッチでアームを引っ張るシナリオに着目し,マルチアームバンディットの文脈における純粋探索の問題について検討する。
バッチは計算効率を向上させることが示されているが、遅延したフィードバックと適応性の低下により、元のシーケンシャルアルゴリズムの性能よりも劣化する可能性がある。
本稿では,Sequential Halving (SH) アルゴリズムの簡単なバッチ版 (Karnin et al , 2013) を導入し,バッチ処理が実際の条件下でのアルゴリズムの性能を劣化させないという理論的証拠を提供する。
さらに, 実験により, SHアルゴリズムのロバストな特性を定サイズバッチ設定で実証し, 実験により検証した。
関連論文リスト
- Sparse is Enough in Fine-tuning Pre-trained Large Language Models [98.46493578509039]
我々はSparse Increment Fine-Tuning (SIFT) という勾配に基づくスパース微調整アルゴリズムを提案する。
GLUE Benchmark や Instruction-tuning などのタスクで有効性を検証する。
論文 参考訳(メタデータ) (2023-12-19T06:06:30Z) - Provably Efficient Learning in Partially Observable Contextual Bandit [4.910658441596583]
古典的帯域幅アルゴリズムの改善に因果境界をどのように適用できるかを示す。
本研究は,実世界の応用における文脈的包括的エージェントの性能を高める可能性を秘めている。
論文 参考訳(メタデータ) (2023-08-07T13:24:50Z) - Anti-Exploration by Random Network Distillation [63.04360288089277]
ランダムネットワーク蒸留 (RND) の条件付けは, 不確実性推定器として用いるのに十分な識別性がないことを示す。
この制限は、FiLM(Feature-wise Linear Modulation)に基づく条件付けによって回避できることを示す。
D4RLベンチマークで評価したところ、アンサンブルベースの手法に匹敵する性能を達成でき、アンサンブルのない手法よりも広いマージンで性能を向上できることがわかった。
論文 参考訳(メタデータ) (2023-01-31T13:18:33Z) - Batch Bayesian optimisation via density-ratio estimation with guarantees [26.052368583196426]
本稿では,BOREの後悔を理論的に分析し,不確実性の推定を改良したアルゴリズムの拡張について述べる。
また,BOREを近似ベイズ推論として再キャストすることにより,バッチ最適化設定に自然に拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-09-22T00:42:18Z) - Regret Bounds for Expected Improvement Algorithms in Gaussian Process
Bandit Optimization [63.8557841188626]
期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。
本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。
我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
論文 参考訳(メタデータ) (2022-03-15T13:17:53Z) - Extreme Bandits using Robust Statistics [12.6543086847761]
我々は,古典的バンディット設定における期待値とは対照的に,極端な値のみが関心を持つ状況に動機づけられたマルチアームバンディット問題を考える。
本研究では,ロバストな統計量を用いた分布自由アルゴリズムを提案し,統計特性を特徴付ける。
論文 参考訳(メタデータ) (2021-09-09T17:24:15Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳(メタデータ) (2021-04-14T09:22:42Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Provable Training of a ReLU Gate with an Iterative Non-Gradient
Algorithm [0.7614628596146599]
我々は,未調査体制下での1つのReLUゲートのトレーニングについて,証明可能な保証を示す。
我々は,真のラベルに対する(オンライン)データポゾン攻撃の下で,真のラベル生成パラメータを近似的に復元することを示す。
我々の保証は最悪の場合ほぼ最適であることが示され、真の重量回復の精度は攻撃の確率と大きさの増大とともに優雅に低下する。
論文 参考訳(メタデータ) (2020-05-08T17:59:23Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。