On the complexity of loading shallow neural networks
type: Item
instance of: scholarly article
title: On the complexity of loading shallow neural networks
zbMATH Open document ID: 0648.68086
DOI: 10.1016/0885-064X(88)90019-2
published in: Journal of Complexity
publication date: 1988-01-01T00:00:00Z
review text: We formalize a notion of loading information into connectionist networks that characterizes the training of feed-forward neural networks. This problem is NP-complete, so we look for tractable subcases of the problem by placing constraints on the network architecture. The focus of these constraints is on various families of ``shallow'' architectures which are defined to have bounded depth and unbounded width. We introduce a perspective on shallow networks, called the support cone interaction (SCI) graph, which is helpful in distinguishing tractable from intractable subcases: When the SCI graph is a tree or if of limited bandwidth, loading can be accomplished in polynomial time; when its bandwidth is not limited we find the problem NP-complete even if the SCI graph is a simple 2-dimensional planar grid.
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 4058894
zbMATH Keywords: support cone interaction graph
zbMATH Keywords: loading
zbMATH Keywords: connectionist networks
zbMATH Keywords: neural networks
zbMATH Keywords: NP-complete
zbMATH Keywords: shallow networks
author: Stephen L. Judd
MaRDI profile type: Publication
cites work: Complexity Results for Bandwidth Minimization
cites work: Q4198056
cites work: Planar Formulae and Their Uses
cites work: Q3725545
description: scientific article; zbMATH DE number 4058894