Supplementary Material for " Training Over-parameterized Models with Non-decomposable Objectives " Algorithm 2 Reductions-based Algorithm for Constraining Coverage (2)

These algorithms additionally incorporate the "two dataset" trick suggested by Cotter et al. We will find the following standard result to be useful in our proofs. We reproduce the proof from Narasimhan et al. We provide a proof for Proposition 4 . The proof follows by setting D = G and applying Proposition 4 .