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