H₁-SR
A variant algorithm obtained by mathematically optimizing the phase schedule of the Successive Rejects algorithm. Under the constraint of a deterministic equal-count plan it achieves the optimal schedule, significantly improving best-arm identification efficiency.
Timeline (last 90 days)
A recent study formalized the design of SR's stage schedule as an optimization problem over the normalized error exponent, and proposed a new variant, H₁-Balanced Successive Rejects (H₁-SR).
H₁-SR's optimized schedule is optimal among SR-type algorithms with deterministic equal-counting schedules.
For Gaussian arms with a common variance, H₁-SR achieves at least 11/12 of the optimal normalized rate among all adaptive algorithms, and this ratio holds for any K≥2.
As the number of candidate arms K tends to infinity, H₁-SR's approximation ratio converges to 1 at a rate of 1-O(1/log K).
The study conducted experiments on ten synthetic instances and two dataset-based Gaussian benchmarks, comparing the optimized schedule with the original SR over a finite time horizon.
The experiments found that on most test instances the optimized schedule brought substantial performance gains, but in certain problem environments, an overly aggressive early elimination strategy instead incurred higher cost.
The computational overhead of H₁-SR is almost comparable to that of the original SR.
All Facts (7)
As the number of candidate arms K tends to infinity, H₁-SR's approximation ratio converges to 1 at a rate of 1-O(1/log K).
50%UnverifiedH₁-SR's optimized schedule is optimal among SR-type algorithms with deterministic equal-counting schedules.
50%UnverifiedFor Gaussian arms with a common variance, H₁-SR achieves at least 11/12 of the optimal normalized rate among all adaptive algorithms, and this ratio holds for any K≥2.
50%UnverifiedThe experiments found that on most test instances the optimized schedule brought substantial performance gains, but in certain problem environments, an overly aggressive early elimination strategy instead incurred higher cost.
50%UnverifiedThe computational overhead of H₁-SR is almost comparable to that of the original SR.
50%UnverifiedA recent study formalized the design of SR's stage schedule as an optimization problem over the normalized error exponent, and proposed a new variant, H₁-Balanced Successive Rejects (H₁-SR).
50%UnverifiedThe study conducted experiments on ten synthetic instances and two dataset-based Gaussian benchmarks, comparing the optimized schedule with the original SR over a finite time horizon.
50%