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