A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1\}^n$ under uniform marginals in the model of~\cite{KM25}, where each input coordinate is independently flipped with probability $σ\in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\tilde{O}(n^{O(\log(1/\varepsilon)/σ)})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{Ω(\log(1+σ/\varepsilon^2)/σ)}$. This complements the recent work of~\cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Statistical Query Lower Bounds for Smoothed Agnostic Learning
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. Sp…
A Smoothed Approximate Linear Program
We present a novel linear program for the approximation of the dynamic programming cost-to-go function in high-dimensional stochastic control problems. LP approaches to approximate DP naturally restrict attention to appr…
Agnostic Smoothed Online Learning
Classical results in statistical learning typically consider two extreme data-generating models: i.i.d. instances from an unknown distribution, or fully adversarial instances, often much more challenging statistically. T…
PAC learningThe Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP duality. For Boolean-valued concept classes, w…
regressionNear-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
We consider the well-studied problem of learning intersections of halfspaces under the Gaussian distribution in the challenging \emph{agnostic learning} model. Recent work of Diakonikolas et al. (2021) shows that any Sta…