Cryptographic Hardness for Learning Intersections of Halfspaces

By Adam R. Klivans, Alexander A. Sherstov. 2006

197 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

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 [13, 15, 23, 32, 37, 38, 51].”
On the Computational Efficiency of Training Neural Networks (2014, methodology): “In particular, [15] and [12] have shown this in the case of learning intersections of halfspaces, using cryptographic and average case complexity assumptions.”
In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning (2014, background): “More broadly, any O ( T ) time computable function can be captured by an O ( T 2 ) sized network, and so the expressive power of such networks is indeed great (Sipser, 2006, Theorem 9.25).”
Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity (2016, background): “to depth two networks with very few hidden units, it is hard to predict even marginally better than random [29, 30, 17, 18, 16].”
Provable Bounds for Learning Some Deep Representations (2013, neutral): “1”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Unfortunately, this approach it is probably doomed to fail, as implied by various computational hardness results [8, 19, 7, 20, 21, 22, 12, 11].”
ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time (2015, methodology): “tween 0 and 2π. (c) a black and white image was used as the background for the digit image; (d) the background perturbation and the rotation perturbation are combined. Theorem 2 (Klivans and Sherstov [14]). If T= dρ for some constant ρ>0, then under a certain cryptographic assumption, HT is not e”
Learning Halfspaces and Neural Networks with Random Initialization (2015, methodology): “Klivans et al. (2006) show that if T = Θ( d ρ ) then H T is not eﬃciently learnable under a certain cryptographic assumption.”
Complexity Theoretic Limitations on Learning DNF's (2014, background): “Also, DNFq(n) is the class of functions that are realized by DNF formulas with ≤ q(n) clauses.”
Convergence Results for Neural Networks via Electrodynamics (2017, background): “However, for arbitrary distributions, there are hardness results for PAC-learning halfspaces [KS06].”
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.”
Learning Kernel-Based Halfspaces with the 0-1 Loss (2011, methodology): “Klivans and Sherstov [18] (see also similar arguments in [13]).”
Distribution-Specific Agnostic Boosting (2009, methodology): “ delicate argument. In Section 3.2 we use our boosting algorithm to extend the observation that agnostic learning of a class C implies PAC learning of low-weight linear thresholds of functions from C [25, 9, 28] to a distribution speciﬁc setting. For a set of functions Cand integer W denote by TH(W,”
Reliably Learning the ReLU in Polynomial Time (2016, background): “ple polynomial-time solutions, all extensively used in practice [30]. In contrast, Problem 1.2 is thought to be computationally intractable due to the many existing hardness results in the literature [7,11,19,21]. The ReLU is a hybrid function that lies “in-between” a linear function and a threshold”