Learning Intersections of Two Margin Halfspaces under Factorizable Distributions

• URL: http://arxiv.org/abs/2511.09832v2
• Date: Sun, 16 Nov 2025 19:17:22 GMT
• Title: Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
• Authors: Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, Christos Tzamos,
• Abstract summary: Learning intersections of halfspaces is a central problem in Computational Learning Theory.<n>Even for just two halfspaces, it remains a major open question whether learning is possible in time.<n>We introduce a novel algorithm that provably circumvents the CSQ hardness barrier.
• Score: 56.51474048985742
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning intersections of halfspaces is a central problem in Computational Learning Theory. Even for just two halfspaces, it remains a major open question whether learning is possible in polynomial time with respect to the margin $γ$ of the data points and their dimensionality $d$. The best-known algorithms run in quasi-polynomial time $d^{O(\log(1/γ))}$, and it has been shown that this complexity is unavoidable for any algorithm relying solely on correlational statistical queries (CSQ). In this work, we introduce a novel algorithm that provably circumvents the CSQ hardness barrier. Our approach applies to a broad class of distributions satisfying a natural, previously studied, factorizability assumption. Factorizable distributions lie between distribution-specific and distribution-free settings, and significantly extend previously known tractable cases. Under these distributions, we show that CSQ-based methods still require quasipolynomial time even for weakly learning, whereas our algorithm achieves $poly(d,1/γ)$ time by leveraging more general statistical queries (SQ), establishing a strong separation between CSQ and SQ for this simple realizable PAC learning problem. Our result is grounded in a rigorous analysis utilizing a novel duality framework that characterizes the moment tensor structure induced by the marginal distributions. Building on these structural insights, we propose new, efficient learning algorithms. These algorithms combine a refined variant of Jennrich's Algorithm with PCA over random projections of the moment tensor, along with a gradient-descent-based non-convex optimization framework.

Related papers

• Smoothed Agnostic Learning of Halfspaces over the Hypercube [14.269955880630404]
  We introduce a new smoothed learning framework for Boolean inputs, where perturbations are modeled via random bit flips.<n>Under strictly subexponential assumptions on the input distribution, we give an efficient algorithm for learning halfspaces.
  arXiv  Detail & Related papers  (2025-11-21T20:59:11Z)
• New Statistical and Computational Results for Learning Junta Distributions [0.38073142980733]
  We show that learning $k$-junta distributions is emphcomputationally equivalent to learning $k$-parity functions with noise.<n>We design an algorithm for learning junta distributions whose statistical complexity is optimal.
  arXiv  Detail & Related papers  (2025-05-09T06:44:35Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
  We give a Gaussian-time algorithm for learning high-dimensional halfspaces with margins in $d$-dimensional space to within desired TV distance. Notably, our algorithm does not need labels and establishes unique (and efficient) identifiability of the hidden halfspace. We improve on this by providing polytime guarantees based on Total Variation (TV) distance, in place of existing moment-bound guarantees that can be super-polynomial.
  arXiv  Detail & Related papers  (2023-11-02T17:51:10Z)
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
  This paper presents two novel model-free algorithms, namely the distributionally robust Q-learning and its variance-reduced counterpart, that can effectively learn a robust policy despite distributional shifts. A series of numerical experiments confirm the theoretical findings and the efficiency of the algorithms in handling distributional shifts.
  arXiv  Detail & Related papers  (2023-05-28T19:40:46Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent PAC model. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem.
  arXiv  Detail & Related papers  (2020-07-30T04:18:51Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.