Algorithms learn complex shapes with better efficiency under Gaussian noise

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs

Machine LearningData Structures and Algorithms

Summary

This work tackles the problem of learning complicated decision shapes made by combining multiple curved boundaries called degree-2 polynomial threshold functions. The authors develop a new algorithm that can learn these shapes more efficiently from data that follows a bell curve distribution. They improve on previous methods by reducing how much the running time depends on the accuracy we want. Their approach uses advanced mathematics to identify key directions within the high-dimensional data where the shape’s boundaries matter most. This allows building a model that closely approximates the original shape using fewer resources.

What this means in practice

  • For machine learning engineers: Improve learning efficiency of models that classify complex data structures under Gaussian noise, especially where multiple quadratic boundaries interact.
  • For data scientists in finance: Enable more accurate modeling of financial risk factors that combine quadratic relationships with noisy Gaussian data distributions.

Authors

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma, Lisheng Ren, Trung Tran

Abstract

We give an algorithm for PAC learning intersections of $k$ degree-2 polynomial threshold functions over $R^d$ under a Gaussian distribution. Our algorithm achieves classification error $ε$ using $d^{O(k)}2^{O_k(\log^3(1/ε))}$ time and samples, improving over the $d^{O(k^2/ε^2)}$ running time of the polynomial regression approach. To our knowledge, our result is the first to obtain a dimension exponent independent of the accuracy parameter, even for $k=2$. We complement our algorithmic result with an SQ lower bound showing that the complexity dependence of $d^{Ω(k)}$ is unavoidable. Lifting the input to polynomial features turns the target into an intersection of $k$ halfspaces. This suggests using the first two labeled moments for subspace recovery. In the lifted space, however, these moments can reveal nothing. Our starting point is a Gaussian comparison theorem showing that, for sufficiently regular defining quadratics, the labeled moments needed for subspace recovery are approximately preserved. To handle arbitrary defining quadratics, we establish a new structural result showing that every direction with significant resampling influence can be detected through degree-$O(k)$ moments. These results yield an initial $d^{O(k)}2^{\mathrm{poly}_k(1/ε)}$-time learner using adaptive restrictions. To improve the exponential dependence on $1/ε$, we develop a two-stage dimension-reduction approach that avoids the costly adaptive partitioning. After identifying a subspace containing all directions with large influence, we use generalized regularity and Gaussian comparison to recover the remaining relevant quadratic features through a new derivative-based moment operator. The recovered features support an intersection close to the target. Combining them with robust hinge-loss minimization gives our quasipolynomial-time learner.