在噪声下学习布尔多项式，给出最优样本复杂度的精确刻画。
Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
- 用辅助范数控制无穷范数误差，突破传统傅里叶分析局限。
- 低次多项式需约n^(d+1)个样本，稀疏多项式需ns^2个样本。
- 结果适用于优化安全的代理模型，对黑箱优化有指导意义。
为优化有界二值黑箱函数，研究在布尔超立方体上学习多项式代理模型的问题。为确保代理模型优化能获得良好解，需满足统一的L_∞误差保证，而非通常的L_2型保证。本文刻画了在子高斯噪声下，两类有界多项式的极小最大样本复杂度：第一类是n变量上次数不超过d的多项式，样本复杂度为n^{d+1}；第二类是s-稀疏的傅里叶-沃尔什多项式（s ≤ n），样本复杂度为ns^2。这些速率与无噪声情形（分别对应n^d和ns）存在结构性差异。下界即使对任意自适应学习者也成立，表明额外因子是噪声情形的固有特性。标准的L_2范数傅里叶分析无法自然扩展至L_∞设置以获得统一保证。证明通过选用合适的辅助范数作为控制L_∞误差的代理来克服这一困难。结果共同提供了学习优化安全多项式代理模型的紧致样本复杂度刻画。
原文摘要 · Abstract (English)
Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform $L_\infty$-error guarantees rather than the usual $L_2$-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most $d$ on $n$ variables, the sample complexity scales as $n^{d+1}$. Second, for $s$-sparse Fourier-Walsh polynomials with $s \leq n$, it scales as $ns^2$. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as $n^d$ and $ns$, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the $L_2$-norm do not naturally extend to the $L_\infty$-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the $L_\infty$-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。