Supplementary Material for Submission ID8000: Learnability with Indirect Supervision Signals

T H is weak VC-major with dimension d < . Then, H is T -learnable. We need several intermediate results to prove this. The first lemma bounds the empirical risk via the averaged Rademacher complexity. Work done while at the Allen Institute for AI and at the University of Illinois at Urbana-Champaign.