{"id":36521,"date":"2026-06-08T13:16:27","date_gmt":"2026-06-08T13:16:27","guid":{"rendered":"https:\/\/lamarr-institute.org\/publication\/a-near-optimal-sq-lower-bound-for-smoothed-agnostic-learning-of-boolean-halfspaces\/"},"modified":"2026-06-08T13:16:27","modified_gmt":"2026-06-08T13:16:27","slug":"a-near-optimal-sq-lower-bound-for-smoothed-agnostic-learning-of-boolean-halfspaces","status":"publish","type":"publication","link":"https:\/\/lamarr-institute.org\/de\/publication\/a-near-optimal-sq-lower-bound-for-smoothed-agnostic-learning-of-boolean-halfspaces\/","title":{"rendered":"A Near-optimal {SQ} Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces"},"content":{"rendered":"<p>We study the complexity of smoothed agnostic learning of halfspaces on ${\\pm 1}^n$ under uniform marginals, where each input coordinate is independently flipped with probability $\\sigma \\in (0, {1}\/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\\tilde{O}(n^{O(\\log(1\/\\varepsilon)\/\\sigma)})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{\\Omega(\\log(1+\\sigma\/\\varepsilon^2)\/\\sigma)}$. This complements the recent work, which established analogous bounds in the continuous setting under Gaussian marginals.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We study the complexity of smoothed agnostic learning of halfspaces on ${\\pm 1}^n$ under uniform marginals, where each input coordinate is independently flipped with probability $\\sigma \\in (0, {1}\/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\\tilde{O}(n^{O(\\log(1\/\\varepsilon)\/\\sigma)})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{\\Omega(\\log(1+\\sigma\/\\varepsilon^2)\/\\sigma)}$. This complements the recent work, which established analogous bounds in the continuous setting under Gaussian marginals.<\/p>\n","protected":false},"author":12,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[30],"class_list":["post-36521","publication","type-publication","status-publish","hentry","publication-type-article"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/36521","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/12"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/36521\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=36521"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=36521"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}