Testing Distributional Assumptions of Learning Algorithms
Testing Distributional Assumptions of Learning Algorithms
复制标题
DOI：
10.1145/3564246.3585117
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
R. Rubinfeld;A. Vasilyan
中科院分区：
文献类型：
--
作者：
R. Rubinfeld;A. Vasilyan
有许多重要的高维函数类具有快速的不可知学习算法，当可以对样本的分布进行强假设时，例如高斯性或域上的均匀性。但是，人们如何能够充分确信数据确实满足分布假设，从而可以信任不可知学习算法的输出质量？我们提出了一个模型，通过它系统地研究测试者-学习者对（A，T）的设计，这样，如果数据中的例子的分布通过测试者T，那么人们可以安全地信任数据上的不可知学习者A的输出。为了证明该模型的强大功能，我们将其应用于标准高斯分布下的半空间不可知学习的经典问题，并提出了一个测试-学习器对，其组合运行时间为nums（1/nums 4）。这在定性上与用于此任务的最知名的普通不可知学习算法相匹配。相比之下，有限样本高斯分布测试不存在的L1和EMD距离测量。以前，人们知道半空间是很好的近似与低次多项式相对于高斯分布。在我们的分析中的一个关键步骤是表明，即使相对于其低阶矩近似匹配高斯分布的分布，情况也是如此。我们还超越了球对称分布，并给出了一个测试者-学习者对下的半空间均匀分布在{0，1}n与组合运行时间的number 2（1/number 4）。这是使用多项式近似理论和临界指数机制[Diakonikolas，Gopalan，Jaiswal，Servedio和Viola 2009]实现的。人们能否在分布式假设下设计不可知的学习算法，并指望未来的技术工作产生，当然，测试者-学习者对具有相似的运行时间？我们的回答是一个响亮的否定，因为我们表明存在一些经过充分研究的设置，其中2n Ω（n）运行时不可知学习算法是可用的，但测试者-学习者对的组合运行时间必须高达2Ω（n）。因此，测试者-学习者对的设计本身就是一个独立于标准不可知学习的研究方向。具体地说，我们的下界适用于高斯分布下的不可知学习凸集和单调布尔函数在{0，1}n上的均匀分布下的问题。
There are many important high dimensional function classes that have fast agnostic learning algorithms when strong assumptions on the distribution of examples can be made, such as Gaussianity or uniformity over the domain. But how can one be sufficiently confident that the data indeed satisfies the distributional assumption, so that one can trust in the output quality of the agnostic learning algorithm? We propose a model by which to systematically study the design of tester-learner pairs (A,T), such that if the distribution on examples in the data passes the tester T then one can safely trust the output of the agnostic learner A on the data. To demonstrate the power of the model, we apply it to the classical problem of agnostically learning halfspaces under the standard Gaussian distribution and present a tester-learner pair with a combined run-time of nÕ(1/є4). This qualitatively matches that of the best known ordinary agnostic learning algorithms for this task. In contrast, finite sample Gaussian distribution testers do not exist for the L1 and EMD distance measures. Previously it was known that half-spaces are well-approximated with low-degree polynomials relative to the Gaussian distribution. A key step in our analysis is showing that this is the case even relative to distributions whose low-degree moments approximately match those of a Gaussian. We also go beyond spherically-symmetric distributions, and give a tester-learner pair for halfspaces under the uniform distribution on {0,1}n with combined run-time of nÕ(1/є4). This is achieved using polynomial approximation theory and critical index machinery of [Diakonikolas, Gopalan, Jaiswal, Servedio, and Viola 2009]. Can one design agnostic learning algorithms under distributional assumptions and count on future technical work to produce, as a matter of course, tester-learner pairs with similar run-time? Our answer is a resounding no, as we show there exist some well-studied settings for which 2Õ(√n) run-time agnostic learning algorithms are available, yet the combined run-times of tester-learner pairs must be as high as 2Ω(n). On that account, the design of tester-learner pairs is a research direction in its own right independent of standard agnostic learning. To be specific, our lower bounds apply to the problems of agnostically learning convex sets under the Gaussian distribution and for monotone Boolean functions under the uniform distribution over {0,1}n.