  Many machine learning applications require learning a function with a small
worst-case error over the entire input domain, that is, the $L_\infty$-error,
whereas most existing theoretical works only guarantee recovery in average
errors such as the $L_2$-error. $L_\infty$-recovery from polynomial samples is
even impossible for seemingly simple function classes such as constant-norm
infinite-width two-layer neural nets. This paper makes some initial steps
beyond the impossibility results by leveraging the randomness in the
ground-truth functions. We prove a polynomial sample complexity bound for
random ground-truth functions drawn from Gaussian random fields. Our key
technical novelty is to prove that the degree-$k$ spherical harmonics
components of a function from Gaussian random field cannot be spiky in that
their $L_\infty$/$L_2$ ratios are upperbounded by $O(d \sqrt{\ln k})$ with high
probability. In contrast, the worst-case $L_\infty$/$L_2$ ratio for degree-$k$
spherical harmonics is on the order of $\Omega(\min\{d^{k/2},k^{d/2}\})$.
