hyperopt_pruners/
successive_halving.rs

1use hyperopt_core::{Pruner, StudyState, Trial};
2
3/// ASHA-style (Asynchronous Successive Halving) pruner — the "advanced" option.
4///
5/// Trials are compared at a ladder of resource **rungs**
6/// `min_resource * reduction_factor^k` (starting at exponent
7/// `min_early_stopping_rate`). When a trial crosses a rung, only the top
8/// `1/reduction_factor` fraction of the trials that reached that rung are
9/// promoted to continue; the rest are pruned. Compared to [`MedianPruner`],
10/// this allocates a shrinking budget across rungs rather than a single
11/// median cut, and is asynchronous (each trial is judged against whichever
12/// peers have reached its rung so far), which suits parallel execution.
13///
14/// Implemented second and treated as the advanced choice; [`MedianPruner`] is
15/// the simpler default.
16#[derive(Debug, Clone)]
17pub struct SuccessiveHalvingPruner {
18    min_resource: usize,
19    reduction_factor: usize,
20    min_early_stopping_rate: u32,
21}
22
23impl Default for SuccessiveHalvingPruner {
24    fn default() -> Self {
25        SuccessiveHalvingPruner {
26            min_resource: 1,
27            reduction_factor: 4,
28            min_early_stopping_rate: 0,
29        }
30    }
31}
32
33impl SuccessiveHalvingPruner {
34    /// Defaults: `min_resource = 1`, `reduction_factor = 4`,
35    /// `min_early_stopping_rate = 0`.
36    pub fn new() -> Self {
37        Self::default()
38    }
39
40    /// Resource (step count) of the first rung.
41    pub fn min_resource(mut self, r: usize) -> Self {
42        self.min_resource = r.max(1);
43        self
44    }
45
46    /// `eta`: the fraction `1/eta` of trials promoted at each rung, and the
47    /// factor by which rung resources grow. Must be `>= 2`.
48    pub fn reduction_factor(mut self, eta: usize) -> Self {
49        self.reduction_factor = eta.max(2);
50        self
51    }
52
53    /// Starting rung exponent — skip the earliest, cheapest rungs.
54    pub fn min_early_stopping_rate(mut self, s: u32) -> Self {
55        self.min_early_stopping_rate = s;
56        self
57    }
58
59    /// The highest rung resource `<= step`, or `None` if `step` hasn't reached
60    /// the first rung yet.
61    fn rung_resource_for(&self, step: usize) -> Option<usize> {
62        let eta = self.reduction_factor as u64;
63        let first = (self.min_resource as u64) * eta.pow(self.min_early_stopping_rate);
64        if (step as u64) < first {
65            return None;
66        }
67        let mut rung = first;
68        loop {
69            let next = rung.saturating_mul(eta);
70            if next <= step as u64 {
71                rung = next;
72            } else {
73                break;
74            }
75        }
76        Some(rung as usize)
77    }
78}
79
80impl Pruner for SuccessiveHalvingPruner {
81    fn should_prune(&self, study_state: &StudyState, trial: &Trial) -> bool {
82        let Some((step, value)) = trial.last_intermediate() else {
83            return false;
84        };
85        let Some(rung) = self.rung_resource_for(step) else {
86            return false;
87        };
88
89        // Peers that have reached this rung (the current trial is not in the
90        // snapshot, so it is counted separately below).
91        let peers = study_state.values_at_or_after(rung);
92        let eta = self.reduction_factor;
93
94        // A rung must be "full enough" before anyone is promoted or cut.
95        if peers.len() + 1 < eta {
96            return false;
97        }
98
99        let direction = study_state.direction();
100        let better_than_current = peers
101            .iter()
102            .filter(|&&p| direction.is_better(p, value))
103            .count();
104
105        // Total trials at this rung including the current one.
106        let total = peers.len() + 1;
107        let top_k = (total / eta).max(1);
108
109        // Promote (keep) if the current trial ranks within the top 1/eta.
110        let rank = better_than_current; // number strictly better than current
111        rank >= top_k
112    }
113}
hyperopt_pruners/successive_halving.rs

hyperopt_pruners/
successive_halving.rs
