Algorithm 1. An NP umbrella algorithm 1: Input:  Training data: A mixed i.i.d. sample  , where  and  are class 0 and 1 samples, respectively  α: Type I error upper bound, 0 ≤ α ≤ 1; (default α = 0.05)  δ: A small tolerance level, 0 < δ < 1; (default δ = 0.05)  M: Number of random splits on  ; (default M = 1) 2: Function RankThreshold(n, α, δ) 3: For k in {1, ⋯, n} do ◃ For each rank threshold candidate k 4:  ◃ Calculate the violation rate upper bound 5: k* ← min{k ∈ {1, ⋯, n} : v(k) ≤ δ} ◃ Pick the rank threshold 6: Return k* 7: Procedure NPClassifier(  ) 8:  ◃ Denote half of the size of  as n 9: k* ← RankThreshold(n, α, δ) ◃ Find the rank threshold 10: For i in {1, ⋯, M} do ◃ Randomly split  for M times 11:  random split on  ◃ Each time randomly split  into two halves with equal sizes 12:  ◃ Combine  and  13:  ◃ Write  as a set of n data points 14: fi ← ClassificationAlgorithm  ◃ Train a scoring function fi on  15:  ◃ Apply the scoring function fi to  to obtain a set of score threshold candidates 16: {ti,(1), ⋯, ti,(n)} ← sort  ◃ Sort elements of  in an increasing order 17:  ◃ Find the score threshold corresponding to the rank threshold k* 18:  ◃ Construct an NP classifier based on the scoring function fi and the threshold  19: Output: an ensemble NP classifier  ◃ By majority vote