Statistical Query Lower Bounds for Smoothed Agnostic Learning

We study the complexity of smoothed agnostic learning, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspaces under subgaussian distributions in this model. The best known upper bound for this problem is based on $L_1$-polynomial regression and has complexity $d^{\tilde O(1/\sigma^2)\log(1/\epsilon)}$, where $\sigma$ is the smoothing parameter and $\epsilon$ is the excess error. Our main result is a Statistical Query (SQ) lower bound showing that this upper bound is close to best possible. In particular, we prove that, even for Gaussian marginals, any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity $d^{\Omega(1/\sigma^2+\log(1/\epsilon))}$. This is the first non-trivial computational lower bound for this task, and it nearly matches the known upper bound. At a conceptual level, we show that the complexity of the problem is governed by the low-degree $L_1$ approximation of the smoothed target $T_\sigma f$, so that applying $L_1$-polynomial regression to the smoothed function is essentially optimal in the SQ model. Our proof proceeds by constructing a moment-matching hard distribution via linear programming duality; the dual program corresponds exactly to finding a low-degree approximating polynomial for $T_\sigma f$, which is the same approximation-theoretic condition underlying the upper bound. To instantiate this framework for halfspaces, we prove explicit lower bounds on the approximation degree of the smoothed sign function. A key ingredient is a new structural result: we construct a distribution that matches moments with a Gaussian while exhibiting periodic structure. This result underlies our $1/\sigma^2$-degree lower bound and may be of independent interest.