Home / Curated / Algorithms / Successive Halving

Successive Halving

Algorithms AIMech:SuccessiveHalving DRAFT

Aliases: SHA, Sequential Halving

A staged best-candidate selection algorithm that divides a resource budget across elimination rounds, evaluates surviving candidates with comparable within-round effort, removes approximately the poorer-performing half, and allocates more effort per remaining candidate in later rounds.

Identity Notes & Concept Scope This record retains the common staged-halving algorithm with explicitly separated stochastic and non-stochastic realizations. Jamieson and Talwalkar identify their Successive Halving as the algorithm of Karnin et al., whose source calls it Sequential Halving. That attribution supports a shared identity, not equality of every printed rounding or score formula. One fixed-cohort halving run differs from Hyperband’s bracket hedge, ASHA’s growing asynchronous cohort, BOHB’s learned proposals and PBT’s cross-model weight inheritance. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 259 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in both worktree and main checkout, returning 26 lines in each checkout. These were prior candidate leads, source references and neighboring-method mentions, not existing records for these identities. Nine exact AIO CLASS nodes with synonyms and outgoing edges and six neighboring native mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.

Claims & Grounded Evidence

1 Claim

Mechanism #method

Start with a finite candidate set and a total allocation budget, divide effort across elimination rounds, evaluate the current survivors, retain their better-performing subset, and repeat with fewer candidates and more effort per survivor. The original stochastic Sequential Halving allocates floor(T/(|S|*ceil(log2(n)))) samples per surviving arm in a round, ranks stage empirical reward averages, and keeps ceil(|S|/2) arms with the highest averages. The non-stochastic hyperparameter formulation instead allocates additional training pulls and compares current validation losses at cumulative training progress; it minimizes these losses rather than averaging raw observations as if they were i.i.d. rewards. Its analysis assumes fixed loss sequences with limits but does not require the convergence envelopes as inputs. Randomly sampled or prespecified configurations can supply the finite cohort. Resume within a candidate’s own training trajectory; the mechanism does not copy weights between candidates.

supports Source: Non-stochastic Best Arm Identification and Hyperparameter Optimization · Locator: Sections 2–4, PDF pp.2–6 (printed 241–245), especially Figure 3 and Section 3 on PDF p.4/printed 243; relation to the original algorithm in Section 2.1 on PDF p.3
supports Source: Almost Optimal Exploration in Multi-Armed Bandits · Locator: Section 4 and Algorithm 2, PDF pp.5–6; background assumptions on PDF pp.1–2

⚠️ Curated Limitations & Negative Results

The 2016 Figure 3 prints a floor-half threshold and a fixed ceil(log2(n)) round count. Literal application to non-power-of-two counts can reach an empty set; ties at its non-strict threshold can retain more than half. The 2013 cardinality rule uses a ceiling instead. These are source conventions requiring explicit implementation choices, not silently equivalent formulas or an author-issued erratum.
The non-stochastic guarantees assume convergent, action-independent loss sequences and sufficient problem-dependent budget. Unknown convergence envelopes prevent a finite observed ranking alone from certifying the eventual best candidate. No universal speedup or finite-budget optimum is asserted.
The budget, cohort and evaluation statistic must be specified. The paper’s doubling construction can remove a prespecified horizon, but does not eliminate all modeling or resource choices. The 2016 PDF footer says volume 41; bibliographic metadata follows the publisher’s volume 51.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:TrainingStrategy` TrainingStrategy	related_match	The hyperparameter-optimization use of this procedure selects training settings or allocates resources to candidate models. This relates it to AIO’s training-strategy concept without making the algorithm a preprocessing subclass or equating broader best-candidate selection with a machine-learning task.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Non-stochastic Best Arm Identification and Hyperparameter Optimization Kevin Jamieson, Ameet Talwalkar	primary paper full_text	sha256:97a2ce248041…
`original-halving`	Almost Optimal Exploration in Multi-Armed Bandits Zohar Karnin, Tomer Koren, Oren Somekh	primary paper full_text	sha256:a1aa3ba680f3…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T11:42:59Z

Updated: 2026-10-11T11:42:59Z

Source File: data/curated/SuccessiveHalving.yaml