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.
翻译:虽然许多典型的可学习性概念(如PAC可学习性)是无分配的,但利用投入分配的具体结构可以提高学习绩效。例如,多维输入空间的产品分配结构比相关分布结构简单得多。最近的一份论文[GHTZ21]表明,产品分销一般学习问题的抽样复杂性在投入层面是多式的,其指数小于相关分布。然而,他们使用的学习算法并不是标准的经验风险最小化(ERM)算法。在本说明中,我们将机构风险管理的样本复杂性描述为产品分销的一般学习问题。我们表明,尽管产品分配比相关分布简单得多,但机构机构仍然需要指数数量的样本来学习产品分销,而不是多式的。这导致这样的结论,即产品分销本身不会使学习问题变得容易一些 -- -- 需要专门为产品分销设计的算法。