在高维高斯空间中学习与测试光滑凸函数，突破了传统离散方法的局限。
Learning and Testing Convex Functions
- 基于样本和Lipschitz光滑性假设，设计可容忍噪声的凸函数学习算法。
- 学习误差ε需样本量为n^{O(1/ε²)}，且存在n^{poly(1/ε)}的下界。
- 首次在高维连续空间实现凸性容忍测试，适合统计学习与优化研究者。
我们研究高维高斯空间中实值凸函数的学习与测试问题。尽管凸性在数学、统计学和计算机科学中被广泛研究，但其可学习性和可测试性此前主要局限于离散或受限设置——通常以汉明距离为度量，而该度量不适用于实值函数。本文在标准高斯测度下，假设对函数有样本访问权，并引入温和的光滑性条件（即Lipschitz连续性）。该假设在单维情况下是必要且自然的：无此条件，无法从有限样本推断凸性。主要结果包括：1）提出一种抗噪的适当学习算法，用于Lipschitz凸函数，以n^{O(1/ε²)}个样本达到ε误差，并在相关统计查询（CSQ）模型中给出n^{poly(1/ε)}的样本下界；2）基于学习结果，构造出具有相同样本复杂度的容忍型（双侧）凸性测试器，以及一个单侧测试器（永不错判凸函数），其样本复杂度为O(√n/ε)^n。
原文摘要 · Abstract (English)
We consider the problems of \emph{learning} and \emph{testing} real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematics, statistics, and computer science, its learnability and testability have largely been examined only in discrete or restricted settings -- typically with respect to the Hamming distance, which is ill-suited for real-valued functions. In contrast, we study these problems in high dimensions under the standard Gaussian measure, assuming sample access to the function and a mild smoothness condition, namely Lipschitzness. A smoothness assumption is natural and, in fact, necessary even in one dimension: without it, convexity cannot be inferred from finitely many samples. As our main results, we give: - Learning Convex Functions: An agnostic proper learning algorithm for Lipschitz convex functions that achieves error $\varepsilon$ using $n^{O(1/\varepsilon^2)}$ samples, together with a complementary lower bound of $n^{\mathrm{poly}(1/\varepsilon)}$ samples in the \emph{correlational statistical query (CSQ)} model. - Testing Convex Functions: A tolerant (two-sided) tester for convexity of Lipschitz functions with the same sample complexity (as a corollary of our learning result), and a one-sided tester (which never rejects convex functions) using $O(\sqrt{n}/\varepsilon)^n$ samples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。