Provably Consistent Partial-Label Learning: Supplementary Material A Proofs of Data Generation Process A.1 Proof of Theorem 1

A.3 Proof of Lemma 1 Let us first consider the case where the correct label y is a specific label i ( i [ k ]), then we have p(y Y,y = i | x) = p( y Y | y = i, x)p (y = i | x) = null Our proof of the estimation error bound is based on Rademacher complexity [1]. Before proving Theorem 4, we introduce the following lemmas. The same proof has been provided in [20]. Then we have the following lemma. Since this proof is somewhat similar to the proof of Theorem 4, we briefly sketch the key points.