On the power of small-depth threshold circuits

By J. Håstad, Mikael Goldmann. 1990

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

Training Very Deep Networks (2015, background): “Related observations hold for Boolean circuits [8, 9] and modern neural networks [10, 11, 12].”
Better Mixing via Deep Representations (2012, background): “specific function families have shown that choosing a sufficient depth of representation can yield exponential benefits, in terms of size of the model, to represent some functions (H̊astad, 1986; H̊astad and Goldmann, 1991; Bengio et al., 2006; Bengio and LeCun, 2007; Bengio and Delalleau, 2011).”
Deep Networks with Stochastic Depth (2016, background): “Network depth is a major determinant of model expressiveness, both in theory [9, 10] and in practice [5, 7, 8].”
Practical Recommendations for Gradient-Based Training of Deep Architectures (2012, background): “Complexity theory of circuits, e.g. (H˚astad, 1986; H˚astad and Goldmann, 1991), (which include neural networks as special cases) has much preceded the recent research on deep learning.”
On building ensembles of stacked denoising auto-encoding classifiers and their further improvement (2018, background): “The analyses in [23,24] show that by adding layers to a network, it is possible to reduce the effort to establish input-output correspondences.”
Unsupervised Feature Learning and Deep Learning: A Review and New Perspectives (2012, background): “Theoretical results clearly show families of functions where a deep representation can be exponentially more efﬁcient than one that is insufﬁciently deep (H˚astad, 1986; H˚astad and Goldmann, 1991; Bengio et al. , 2006a; Bengio and LeCun, 2007; Bengio and Delalleau, 2011).”
Stacked Denoising Autoencoders: Learning Useful Representations in a Deep Network with a Local Denoising Criterion (2010, background): “of the layered architecture of regions of the human brain such as the visual cortex, and in part by a body of theoretical arguments in its favor (Håstad, 1986; Håstad and Goldmann, 1991; Bengio and LeCun, 2007; Bengio, 2009).”
On the Expressive Power of Deep Learning: A Tensor Analysis (2015, unknown): “Such scenarios of exponential penalty for trimming down a single layer were discussed in Bengio (2009), but only in the context of speciﬁc functions realized by networks that do not resemble ones used in practice (see H˚astad and Goldmann (1991) for an example of such result).”
A review of convolutional neural network architectures and their optimizations (2022, background): “Theoretical research has demonstrated that when the function represented by deeper network architecture is expressed through shallow network architecture, its computing unit increases exponentially (Håstad and Goldmann 1991).”
Curriculum learning (2009, background): “A theoretical motivation for deep architectures comes from complexity theory: some functions can be represented compactly with an architecture of depth k, but require an exponential size architecture when the depth is restricted to be less than k (H°astad & Goldmann, 1991; Bengio, 2009).”
Learning Strict Identity Mappings in Deep Residual Networks (2018, background): “Another key contributing factor is the depth, which has been proven to be extremely beneficial in model expressiveness [12, 29, 38].”
Why Does Unsupervised Pre-training Help Deep Learning? (2010, result): “Theoretical results (Yao, 1985; H̊astad, 1986; H̊astad and Goldmann, 1991; Bengio et al., 2006), reviewed”
Automated Melanoma Recognition in Dermoscopy Images via Very Deep Residual Networks (2017, background): “depth is a key factor of model expressiveness for a long time [27], [28].”
SV-RCNet: Workflow Recognition From Surgical Videos Using Recurrent Convolutional Network (2018, background): “The importance of network depth for extracting discriminative features has been manifested by both computational theories [22], [23] and practical applications [24]–[26].”
Learning Deep Architectures for AI (2007, background): “A monotone weighted threshold circuit of depth k − 1 computing a function fk ∈ Fk,N has size at least 2cN for some constant c > 0 and N > N0 [63].”