Complexity theoretic limitations on learning halfspaces

By Amit Daniely. 2015

160 citations recorded by the source corpus.

We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution D on Q^n X {-1,1}. We define Err_H(D) as the least error of a halfspace classifier for D. A learner who can access D has to return a hypothesis whose error is small compared to Err_H(D). Using the recently developed method of Daniely, Linial and Shalev-Shwartz we prove hardness of learning results assuming that random K-XOR formulas are hard to (strongly) refute. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that Err_H(D) <= eta for arbitrarily small constant eta>0, and that D is supported in the Boolean cube. Namely, even under these favorable conditions, and for every c>0, it is hard to return a hypothesis with error <= 1/2-n^{-c}. In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where K can be poly-logarithmic in n), we can take eta = 2^{-log^{1-nu}(n)} for arbitrarily small nu>0. These results substantially improve on previously known results, that only show hardness of exact learning.

Subfields: Artificial Intelligence, Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Stronger hardness results have been proved over the last decade (Daniely, 2016; Daniely & Shalev-Shwartz, 2016; Goel et al., 2017; Klivans & Sherstov, 2009; Livni et al., 2014; Manurangsi & Reichman, 2018; Song et al., 2017).”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “th polynomially large weights agnostically is equivalent to agnostically learning a half space to a polynomially small error, which has no polynomial time algorithms under the random K-XOR assumption [19]. 5 Algorithm 1 SGD for two-layer networks Input: Data set Z, initialization W(0), step size 1:”
Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity (2016, background): “oretical results suggests that when going slightly deeper beyond single layer networks, e.g. to depth two networks with very few hidden units, it is hard to predict even marginally better than random [29,30,17,18,16]. Finally, we note that the recent empirical successes of NNs have prompted a surge ”
Complexity Theoretic Limitations on Learning DNF's (2014, methodology): “, 2006; Kearns and Valiant, 1989), and also assuming that randomK-XOR is hard (Daniely, 2016).”
Learning Non-Discriminatory Predictors (2017, methodology): “We will show that such an algorithm can be used to improperly weakly learn Halfspace which, subject to the complexity assumption that refuting random K-XOR formulas is hard, was shown to be computationally hard by Daniely [2015].”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “, [52], [58], [40], [59], [20], [19] for the problems of learning halfspaces and learning intersections thereof.”
Reliably Learning the ReLU in Polynomial Time (2016, background): “2 is thought to be computationally intractable due to the many existing hardness results in the literature [7, 11,19,21].”
Learning geometric concepts with nasty noise (2017, methodology): “Improving on this bound has remained a challenge for a long time, and it was recently shown [7] that this holds for a reason: under plausible complexity assumptions, no efficient algorithm can achieve error at most 1/2−1/nc , for some constant c > 0, even if ε is an arbitrarily small constant.”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, background): “ dimension. For learning intersections of polynomially many halfspaces, there are known hardness results based on cryptographic assumptions [KS09b] or the hardness of constraint satisfaction problems [Dan16]. A source of angst in machine learning theory is that these hardness results do not square w”