We study the complexity of smoothed agnostic learning, recently introduced by~\cite{CKKMS24}, 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 the smoothed model. The best known upper bound for this problem relies on L1-polynomial regression and has complexity dO~(1/σ2)log(1/ε), where σ is the smoothing parameter and ε is the excess error. Our main result is a Statistical Query (SQ) lower bound providing formal evidence that this upper bound is close to best possible. In more detail, we show that (even for Gaussian marginals) any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity dΩ(1/σ2+log(1/ε)). This is the first non-trivial lower bound on the complexity of this task and nearly matches the known upper bound. Roughly speaking, we show that applying L1-polynomial regression to a smoothed version of the function is essentially best possible. Our techniques involve finding a moment-matching hard distribution by way of linear programming duality. This dual program corresponds exactly to finding a low-degree approximating polynomial to the smoothed version of the target function (which turns out to be the same condition required for the L1-polynomial regression to work). Our explicit SQ lower bound then comes from proving lower bounds on this approximation degree for the class of halfspaces.
We study the complexity of smoothed agnostic learning of halfspaces on {±1}n under uniform marginals in the model of~\cite{KM25}, where each input coordinate is independently flipped with probability σ∈(0,1/2). We show that L1 polynomial regression achieves runtime and sample complexity O~(nO(log(1/ε)/σ)), and prove a nearly matching Statistical Query complexity lower bound of nΩ(log(1+σ/ε2)/σ). This complements the recent work of~\cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.
The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its L1-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most Γ, Klivans et al. (2008) show that degree d=O(Γ2/ε4) suffices to achieve an ε-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree d=O~(Γ2/ε2) is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered L1-approximation on the Boolean hypercube.
We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over Rd×{±1} whose marginal on Rd is Gaussian, the goal is to output a hypothesis from a target class F whose 0-1 loss is within ε of that of the best classifier in F. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of K halfspaces under Gaussian marginals. Our algorithm runs in time dO(K2log(1/ε)/ε2)+(K/ε)O(K3/ε2.5). Prior to our work, the only known algorithm for K≥2 was brute-force search, with run-time exponential in d. Moreover, the dependence of our run-time on the dimension d matches that of the best known improper learning algorithm, namely dO(K2/ε2). For the special case of a single halfspace (K=1), the best previous run-time was dO(1/ε4)+(1/ε)O(1/ε6). Our algorithm improves this to dO(1/ε2)+(1/ε)O(1/ε2.5). Once again, the dependence on d matches that of the best known improper algorithm, namely dO(1/ε2). Furthermore, the dependence of our run-time on the dimension d is essentially optimal in the statistical query model.