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: f_{i} ← ClassificationAlgorithm | ◃ Train a scoring function f_{i} on |

15: | ◃ Apply the scoring function f_{i} to to obtain a set of score threshold candidates |

16: {t_{i,(1)}, ⋯, t_{i,(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 f_{i} and the threshold |

19: Output: an ensemble NP classifier | ◃ By majority vote |