Estimating Euclidean Distance to Linearity

Given oracle access to a real-valued function on the n-dimensional Boolean cube, how many queries does it take to estimate the squared Euclidean distance to its closest linear function within ϵ? Our main result is that O(log3(1/ϵ) · 1/ϵ2) queries suffice. Not only is the query complexity independent of n but it is optimal up to the polylogarithmic factor. Our estimator evaluates f on pairs correlated by noise rates chosen to cancel out the low-degree contributions to f while leaving the linear part intact. The query complexity is optimized when the noise rates are multiples of Chebyshev nodes. In contrast, we show that the dependence on n is unavoidable in two closely related settings. For estimation from random samples, Θ(√n/ϵ + 1/ϵ2) samples are necessary and sufficient. For agnostically learning a linear approximation with ϵ mean-square regret under the uniform distribution, Ω(n/√ϵ) nonadaptively chosen queries are necessary, while O(n/ϵ) random samples are known to be sufficient (Linial, Mansour, and Nisan). Our upper bounds apply to functions with bounded 4-norm. Our lower bounds apply even to ±1-valued functions.