A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
Pith reviewed 2026-05-14 21:03 UTC · model grok-4.3
The pith
L¹ polynomial regression achieves Õ(n^{O(log(1/ε)/σ)}) runtime for smoothed agnostic halfspace learning, nearly matched by an SQ lower bound of n^{Ω(log(1+σ/ε²)/σ)}.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In the smoothed agnostic learning model for Boolean halfspaces on {±1}^n under uniform marginals, where each input coordinate is flipped independently with probability σ, L¹ polynomial regression attains runtime and sample complexity Õ(n^{O(log(1/ε)/σ)}), and any statistical query algorithm requires n^{Ω(log(1 + σ/ε²)/σ)} queries.
What carries the argument
L¹ polynomial regression, which finds a low-degree polynomial minimizing L¹ distance to the labels under the smoothed distribution, paired with a statistical query lower-bound construction that forces many queries to distinguish hard halfspaces.
Load-bearing premise
Inputs are drawn from the uniform hypercube distribution smoothed by independent coordinate flips of probability σ.
What would settle it
An SQ algorithm that learns halfspaces to accuracy 1-ε using only n^{o(log(1+σ/ε²)/σ)} queries on the smoothed distribution, or an algorithm improving the upper bound exponent below O(log(1/ε)/σ).
read the original abstract
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 $\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 of~\cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the complexity of smoothed agnostic learning of halfspaces over the hypercube under the coordinate-flip model of KM25. It shows that L¹ polynomial regression yields runtime and sample complexity Õ(n^{O(log(1/ε)/σ)}), and establishes a nearly matching SQ lower bound of n^{Ω(log(1+σ/ε²)/σ)} by reducing to low-degree approximation under the induced product distribution and constructing a suitable planted hard instance.
Significance. If the bounds hold, the work gives a near-optimal characterization of SQ complexity for this problem, with explicit dependence on the smoothing parameter σ. It complements the Gaussian results of DK26 and supplies both a concrete algorithmic upper bound via L¹ regression and a matching lower-bound construction whose exponent gap is only a constant factor in the leading log term for fixed σ.
minor comments (2)
- [§1] §1: The reduction to low-degree polynomial approximation under the σ-flip product distribution is central to both bounds; a short paragraph explicitly stating the degree threshold and the resulting correlation bound would improve readability.
- [Lower bound section] The lower-bound construction via the planted distribution controls correlation with low-degree polynomials; adding an explicit reference to the relevant lemma or equation number that bounds this correlation would make the SQ-hardness argument easier to follow.
Simulated Author's Rebuttal
We thank the referee for the positive assessment, the recognition that the work gives a near-optimal SQ characterization with explicit σ-dependence, and the recommendation for minor revision. No specific major comments were raised in the report.
Circularity Check
No significant circularity; derivation is self-contained
full rationale
The upper bound is obtained by reducing L1 polynomial regression to low-degree approximation under the product distribution induced by coordinate flips (standard technique, no self-definition). The SQ lower bound is obtained by constructing a planted distribution whose low-degree correlations are controlled by the smoothing parameter σ; this construction is presented as new and does not reduce to any fitted parameter or prior result by the same authors. Citations to KM25 (model definition) and DK26 (continuous analogue) are external and non-load-bearing for the claimed exponents. No step equates a prediction to its own input by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The statistical query model as standard in learning theory
Reference graph
Works this paper leans on
-
[1]
Ryan O'Donnell , title =
- [2]
- [3]
- [4]
- [5]
-
[6]
Gregory Valiant and Paul Valiant , title =. Journal of the ACM , volume =
-
[7]
The Annals of Statistics , volume =
Yihong Wu and Pengkun Yang , title =. The Annals of Statistics , volume =
-
[8]
Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC) , pages =
Mark Bun and Robin Kothari and Justin Thaler , title =. Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC) , pages =
- [9]
-
[10]
Mark Bun and Justin Thaler , title =. Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP) , series =
-
[11]
Information and Computation , volume =
David Haussler , title =. Information and Computation , volume =
-
[12]
Michael J. Kearns and Robert E. Schapire and Linda M. Sellie , title =. Machine Learning , volume =
- [13]
-
[14]
Vempala and Ying Xiao , title =
Vitaly Feldman and Elena Grigorescu and Lev Reyzin and Santosh S. Vempala and Ying Xiao , title =. Journal of the ACM , volume =
-
[15]
Proceedings of the 30th Annual Conference on Learning Theory (COLT) , volume =
Vitaly Feldman , title =. Proceedings of the 30th Annual Conference on Learning Theory (COLT) , volume =
- [16]
-
[17]
Adam T. Kalai and Adam R. Klivans and Yishay Mansour and Rocco A. Servedio , title =. SIAM Journal on Computing , volume =
-
[18]
Klivans and Ryan O'Donnell and Rocco A
Adam R. Klivans and Ryan O'Donnell and Rocco A. Servedio , title =. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =
-
[19]
Servedio and Emanuele Viola , title =
Ilias Diakonikolas and Parikshit Gopalan and Ragesh Jaiswal and Rocco A. Servedio and Emanuele Viola , title =. 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =
-
[20]
Kane and Jelani Nelson , title =
Ilias Diakonikolas and Daniel M. Kane and Jelani Nelson , title =. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =
-
[21]
Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis , title =
Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis , title =. Proceedings of the 34th Annual Conference on Learning Theory (COLT) , volume =
-
[22]
SIAM Journal on Computing , volume =
Vitaly Feldman and Parikshit Gopalan and Subhash Khot and Ashok Kumar Ponnuswami , title =. SIAM Journal on Computing , volume =
-
[23]
SIAM Journal on Computing , volume =
Venkatesan Guruswami and Prasad Raghavendra , title =. SIAM Journal on Computing , volume =
-
[24]
Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) , pages =
Amit Daniely , title =. Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) , pages =
-
[25]
Klivans and Pravesh Kothari , title =
Adam R. Klivans and Pravesh Kothari , title =. Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM) , volume =
-
[26]
Kane and Pasin Manurangsi and Lisheng Ren , title =
Ilias Diakonikolas and Daniel M. Kane and Pasin Manurangsi and Lisheng Ren , title =. Advances in Neural Information Processing Systems 35 (NeurIPS) , pages =
-
[27]
Kane and Lisheng Ren , title =
Ilias Diakonikolas and Daniel M. Kane and Lisheng Ren , title =. Proceedings of the 40th International Conference on Machine Learning (ICML) , volume =
-
[28]
Proceedings of the 36th Annual Conference on Learning Theory (COLT) , volume =
Stefan Tiegel , title =. Proceedings of the 36th Annual Conference on Learning Theory (COLT) , volume =
-
[29]
Kane and Alistair Stewart , title =
Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart , title =. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =
-
[30]
Kane and Nikos Zarifis , title =
Ilias Diakonikolas and Daniel M. Kane and Nikos Zarifis , title =. Advances in Neural Information Processing Systems 33 (NeurIPS) , year =
-
[31]
Surbhi Goel and Aravind Gollakota and Adam R. Klivans , title =. Advances in Neural Information Processing Systems 33 (NeurIPS) , year =
-
[32]
Kane and Ankit Pensia and Thanasis Pittas and Alistair Stewart , title =
Ilias Diakonikolas and Daniel M. Kane and Ankit Pensia and Thanasis Pittas and Alistair Stewart , title =. Advances in Neural Information Processing Systems 34 (NeurIPS) , year =
-
[33]
Kane and Thanasis Pittas and Nikos Zarifis , title =
Ilias Diakonikolas and Daniel M. Kane and Thanasis Pittas and Nikos Zarifis , title =. Proceedings of the 34th Annual Conference on Learning Theory (COLT) , volume =
-
[34]
Ilias Diakonikolas and Daniel M. Kane , title =. Proceedings of the 35th Annual Conference on Learning Theory (COLT) , volume =
-
[35]
Ilias Diakonikolas and Daniel M. Kane and Yuxin Sun , title =. Proceedings of the 35th Annual Conference on Learning Theory (COLT) , volume =
-
[36]
Daniel Hsu and Clayton Sanford and Rocco A. Servedio and Emmanouil V. Vlatakis-Gkaragkounis , title =. Proceedings of the 35th Annual Conference on Learning Theory (COLT) , volume =
-
[37]
Kane and Nikos Zarifis , title =
Ilias Diakonikolas and Giannis Iakovidis and Daniel M. Kane and Nikos Zarifis , title =. 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =
-
[38]
Kane and Lisheng Ren , title =
Ilias Diakonikolas and Giannis Iakovidis and Daniel M. Kane and Lisheng Ren , title =. Advances in Neural Information Processing Systems 38 (NeurIPS) , year =
-
[39]
Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =
Dana Dachman-Soled and Vitaly Feldman and Li-Yang Tan and Andrew Wan and Karl Wimmer , title =. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =
-
[40]
Spielman and Shang-Hua Teng , title =
Daniel A. Spielman and Shang-Hua Teng , title =. Journal of the ACM , volume =
-
[41]
Klivans and Vasilis Kontonis and Raghu Meka and Konstantinos Stavropoulos , title =
Gautam Chandrasekaran and Adam R. Klivans and Vasilis Kontonis and Raghu Meka and Konstantinos Stavropoulos , title =. Proceedings of the 37th Annual Conference on Learning Theory (COLT) , volume =
- [42]
-
[43]
Advances in Neural Information Processing Systems 38 (NeurIPS) , year =
Yiwen Kou and Raghu Meka , title =. Advances in Neural Information Processing Systems 38 (NeurIPS) , year =
- [44]
-
[45]
Psychological Review , volume =
Frank Rosenblatt , title =. Psychological Review , volume =
-
[46]
Anselm Blumer and Andrzej Ehrenfeucht and David Haussler and Manfred K. Warmuth , title =. Journal of the ACM , volume =
-
[47]
Avrim Blum and Alan Frieze and Ravi Kannan and Santosh Vempala , title =. Algorithmica , volume =
-
[48]
The Power of Localization for Efficiently Learning Linear Separators with Noise , journal =
Pranjal Awasthi and Maria. The Power of Localization for Efficiently Learning Linear Separators with Noise , journal =
-
[49]
Proceedings of the 28th Conference on Learning Theory (
Amit Daniely , title =. Proceedings of the 28th Conference on Learning Theory (. 2015 , publisher =
work page 2015
- [50]
- [51]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.