Product Distribution Learning with Imperfect Advice

Given i.i.d. samples from an unknown distribution P , the goal of distribution learning is to recover the parameters of a distribution that is close to P . When P belongs to the class of product distributions on the Boolean hypercube 0, 1 d , it is known that Ω(d/ε 2 ) samples are necessary to learn P within total variation (TV) distance ϵ. We revisit this problem when the learner is also given as advice the parameters of a product distribution Q. We show that there is an efficient algorithm to learn P within TV distance ε that has sample complexity Õ(d 1-η /ε 2 ), if ∥p -q∥1 < εd 0.5-Ω(η) . Here, p and q are the mean vectors of P and Q respectively, and no bound on ∥p -q∥1 is known to the algorithm a priori.