Halfspace Learning

Follow this topic Ask about this topic

Latest papers

13 papers1 paper in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Efficient Robust Learning at the Information-Theoretic Limit
Sep 15, 2026Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1Boolean Function Learning Learning with Noisy Labels
UT Austin · Institute for Advanced Study · Aarhus University
Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization
Jun 15, 2026Xiaoyu LiCorruption Robustness Noise Robustness
University of New South Wales
Efficiently Learning Drifting Halfspaces with Massart Noise
Jun 9, 2026Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1Noisy-Label Learning Low-Degree Polynomial Method
University of Wisconsin-Madison
Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals
May 26, 2026Sergei Tikhonov, Arsen VasilyanAgnostic Learning Boolean Function Learning
UT Austin
What is Learnable in Valiant's Theory of the Learnable?
May 13, 2026Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1Sample Compression Halfspace Learning
Purdue University · Stanford University · Google Research +1
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
May 7, 2026Adam R. Klivans, Shyamal Patel, Konstantinos Stavropoulos +1Halfspace Learning
UT Austin · Columbia University
A Fine-Grained Understanding of Uniform Convergence for Halfspaces
May 7, 2026Aryeh Kontorovich, Kasper Green LarsenHalfspace Learning Statistical Learning Theory
Ben-Gurion University · Aarhus University
A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
May 4, 2026Tim SinenBoolean Function Learning Statistical Learning Theory
University of Bonn, Germany
Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
Apr 29, 2026Jizhou Huang, Brendan JubaAgnostic Learning Statistical Learning Theory
Meta · Washington Universtiy in St. Louis
Tight Bounds for Learning Polyhedra with a Margin
Apr 16, 2026Shyamal Patel, Santosh VempalaMargin-Based Learning PAC Learning
Columbia University · Georgia Tech
Testable Learning of General Halfspaces under Massart Noise
Feb 25, 2026Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1Halfspace Learning Learning with Noisy Labels
UW Madison · UC San Diego
Statistical Query Lower Bounds for Smoothed Agnostic Learning
Feb 24, 2026Ilias Diakonikolas, Daniel M. KaneHalfspace Learning Statistical Learning Theory
University of Wisconsin-Madison · University of California, San Diego
Actively Learning Halfspaces without Synthetic Data
Sep 25, 2025Hadley Black, Kasper Green Larsen, Arya Mazumdar +2Query Complexity Boolean Function Learning
Baruch College, CUNY · Aarhus University · University of California, San Diego

Sep 15, 2026J/K move · Enter open · S save

Efficient Robust Learning at the Information-Theoretic Limit

Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan

UT Austin · Institute for Advanced Study · Aarhus University

Boolean Function Learning Learning with Noisy Labels Halfspace Learning Robust Classification

Open paper AskPDF arXiv

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of

η+ \varepsilon

where

η

is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than

2η+ \varepsilon.

Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error

η+ \varepsilon

for any constant

\varepsilon