Toward $L_\infty$-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields
This addresses the challenge of L∞-recovery in machine learning for applications requiring worst-case guarantees, though it is incremental as it relies on randomness in ground-truth functions.
The paper tackles the problem of learning functions with small worst-case (L∞) error from polynomial samples, which is impossible for some simple classes, by proving a polynomial sample complexity bound for random ground-truth functions drawn from Gaussian random fields. The result shows that the L∞/L2 ratio for degree-k spherical harmonics is upper-bounded by O(d √ln k) with high probability, compared to a worst-case ratio of Ω(min{d^{k/2}, k^{d/2}}).
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 $Ω(\min\{d^{k/2},k^{d/2}\})$.