  While many classical notions of learnability (e.g., PAC learnability) are
distribution-free, utilizing the specific structures of an input distribution
may improve learning performance. For example, a product distribution on a
multi-dimensional input space has a much simpler structure than a correlated
distribution. A recent paper [GHTZ21] shows that the sample complexity of a
general learning problem on product distributions is polynomial in the input
dimension, which is exponentially smaller than that on correlated
distributions. However, the learning algorithm they use is not the standard
Empirical Risk Minimization (ERM) algorithm. In this note, we characterize the
sample complexity of ERM in a general learning problem on product
distributions. We show that, even though product distributions are simpler than
correlated distributions, ERM still needs an exponential number of samples to
learn on product distributions, instead of a polynomial. This leads to the
conclusion that a product distribution by itself does not make a learning
problem easier -- an algorithm designed specifically for product distributions
is needed.
