Fugu-MT 論文翻訳(概要): Rethinking Successive Rejects Algorithms

論文の概要: Rethinking Successive Rejects Algorithms

arxiv url: http://arxiv.org/abs/2610.22051v1
Date: Thu, 15 Oct 2026 15:19:12 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-17 06:09:33.145604
Title: Rethinking Successive Rejects Algorithms
Title（参考訳）: 逐次リジェクトアルゴリズムの再考
Abstract要約: Successive Rejects (SR) は、単純な固定予算のベストアーム識別アルゴリズムである。本稿では,位相長のスケジュールを最適化することで,SRの枠組みを拡張する。 10の合成インスタンスと2つのデータセット由来のガウスベンチマークの実験は、最適化されたスケジュールと元のSRを比較した。
参考スコア（独自算出の注目度）: 6.573084871282377
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the best-arm identification problem, an algorithm adaptively selects arms to find the arm of the largest mean reward. Successive Rejects (SR) is a simple fixed-budget best-arm identification algorithm that eliminates one candidate arm at each phase. At first glance, SR seems to have limited adaptivity, since it follows predetermined phase lengths. However, for Gaussian arms with common variance, SR's worst-instance error exponent normalized by the popular complexity measure $H_1(P)$ is optimal up to a constant factor, which partly explains why SR's performance is competitive compared with state-of-the-art adaptive sampling algorithms. In this paper, we extend the framework of SR by optimizing its predefined schedule of phase lengths. We formulate phase-schedule design as an optimization problem for the normalized error exponent. Then, we introduce a version of SR with the optimized schedule, which we call $H_1$-balanced Successive Rejects ($H_1$-SR). This schedule is optimal within the class of SR-type algorithms with deterministic equal-count schedules. For Gaussian arms with common variance, $H_1$-SR achieves at least $11/12$ of the optimal normalized rate over all adaptive algorithms for every $K\ge2$, and this approximation ratio converges to one as $1-O(1/\log K)$ as $K\to\infty$. This is a significant improvement over original SR, whose corresponding fraction of the optimal normalized rate converges to $1/4$. Finally, experiments on ten synthetic instances and two dataset-derived Gaussian benchmarks compare the optimized schedule with original SR at finite horizons. They show substantial gains on many instances while also exposing a regime in which more aggressive early elimination is costly.
Abstract（参考訳）: ベストアーム識別問題において、アルゴリズムは、最大の平均報酬の腕を見つけるために、適応的にアームを選択する。逐次リジェクト (SR) は、各フェーズで1つの候補アームを除去する単純な固定予算のベストアーム識別アルゴリズムである。一見すると、SRは所定の位相長に従うため、適応性に制限があるようである。しかし、共通分散を持つガウスの腕では、一般的な複雑性尺度である$H_1(P)$が正規化される最悪の確率誤差指数は定数係数まで最適であり、SRの性能が最先端適応サンプリングアルゴリズムと比較して競合する理由を部分的に説明できる。本稿では、予め定義された位相長のスケジュールを最適化することにより、SRの枠組みを拡張する。正規化誤差指数の最適化問題として位相スケジュール設計を定式化する。次に、最適化されたスケジュールを持つSRのバージョンを紹介し、これを$H_1$- balanced Successive Rejects(H_1$-SR)と呼ぶ。このスケジュールは、決定論的等数スケジュールを持つSR型アルゴリズムのクラス内で最適である。共通の分散を持つガウスの腕に対して、$H_1$-SRは、すべての適応アルゴリズムに対して、任意の$K\ge2$に対して最適な正規化率の少なくとも11/12$を達成し、この近似比は$K\to\infty$として1-O(1/\log K)$に収束する。これは、最適正規化率の対応する割合が1/4$に収束する元のSRよりも大きな改善である。最後に、10の合成インスタンスと2つのデータセット由来のガウスベンチマークの実験は、最適化されたスケジュールと有限地平線における元のSRを比較する。それらは多くのケースでかなりの増加を示しながら、より攻撃的な早期排除がコストがかかる体制を明らかにしている。

関連論文リスト

Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文参考訳（メタデータ） (2026-04-09T16:38:14Z)
Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文参考訳（メタデータ） (2025-12-01T02:52:33Z)
Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。本稿では,ZPDVR法とZPDVR法を提案する。
論文参考訳（メタデータ） (2024-05-28T02:27:53Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文参考訳（メタデータ） (2022-06-14T08:14:14Z)
A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization [7.014966911550542]
スパースサブ構造を検索するために,非滑らかな正規化を伴うディープニューラルネットワークをトレーニングする問題を考察する。我々は、収束と最悪のケースの複雑さが勾配のリプシッツ定数の知識や近似なしで確立されるSR2と呼ばれる新しい解法を導出する。 CIFAR-10とCIFAR-100で訓練されたネットワークインスタンスの実験により、SR2はProxGENやProxSGDのような関連する手法よりも常に高い空間性と精度を達成することが示された。
論文参考訳（メタデータ） (2022-06-14T00:28:44Z)
Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文参考訳（メタデータ） (2021-11-14T21:49:58Z)
A Retrospective Approximation Approach for Smooth Stochastic Optimization [0.2867517731896504]
グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
論文参考訳（メタデータ） (2021-03-07T16:29:36Z)
Proximal and Federated Random Reshuffling [11.83842808044211]
ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。 ProxRR と FedRR は複合凸有限和最小化問題を解く。 ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
論文参考訳（メタデータ） (2021-02-12T18:59:24Z)

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

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