2011/03/03 by Constantinos Daskalakis, Ilias Diakonikolas, Daskalakis, Constantinos +3
Computer Science · Mathematics · #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1103.0598
openalex publication_date 2011/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of learning an unknown product distribution X over \0,1\n using samples f(X) where f is a known transformation function. Each choice of a transformation function f specifies a learning problem in this framework. Information-theoretic arguments show that for every transformation function f the corresponding learning problem can be solved to accuracy \eps, using O(n/\eps2) examples, by a generic algorithm whose running time may be exponential in n. We show that this learning problem can be computationally intractable even for constant \eps and rather simple transformation functions. Moreover, the above sample complexity bound is nearly optimal for the general problem, as we give a simple explicit linear transformation function f(x)=w ⋅ x with integer weights wi ≤ n and prove that the corresponding learning problem requires Ω(n) samples. As our main positive result we give a highly efficient algorithm for learning a sum of independent unknown Bernoulli random variables, corresponding to the transformation function f(x)= ∑i=1n xi. Our algorithm learns to \eps-accuracy in poly(n) time, using a surprising poly(1/\eps) number of samples that is independent of n. We also give an efficient algorithm that uses log n ⋅ \poly(1/\eps) samples but has running time that is only \poly(log n, 1/\eps).