{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T12:00:21Z","timestamp":1761393621329,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540428756"},{"type":"electronic","value":"9783540455837"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45583-3_9","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:37:04Z","timestamp":1192783024000},"page":"92-105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Minimizing the Quadratic Training Error of a Sigmoid Neuron Is Hard"],"prefix":"10.1007","author":[{"given":"Ji\u0159\u00ed","family":"\u0160\u00edma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,10,31]]},"reference":[{"key":"9_CR1","unstructured":"E. Amaldi: On the complexity of training perceptrons. In T. Kohonen, K. M\u00e4kisara, O. Simula, and J. Kangas (eds.), Proceedings of the ICANN\u201991 First International Conference on Artificial Neural Networks, 55\u201360, North-Holland, Amsterdam: Elsevier Science Publisher, 1991."},{"key":"9_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511624216","volume-title":"Neural Network Learning: Theoretical Foundations","author":"M. Anthony","year":"1999","unstructured":"M. Anthony and P. L. Bartlett: Neural Network Learning: Theoretical Foundations. Cambridge, UK: Cambridge University Press, 1999."},{"issue":"2","key":"9_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk: The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences54(2):317\u2013331, 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR4","unstructured":"P. L. Bartlett and S. Ben-David: Hardness results for neural network approximation problems. In P. Fischer and H.-U. Simon (eds.), Proceedings of the EuroCOLT\u201999 Fourth European Conference on Computational Learning Theory, LNAI 1572, 50\u201362, Berlin: Springer-Verlag, 1999."},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0893-6080(05)80010-3","volume":"5","author":"A. L. Blum","year":"1992","unstructured":"A. L. Blum and R. L. Rivest: Training a 3-node neural network is NP-complete. Neural Networks5(1):117\u2013127, 1992.","journal-title":"Neural Networks"},{"issue":"4","key":"9_CR6","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth: Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM36(4):929\u2013965, 1989.","journal-title":"Journal of the ACM"},{"key":"9_CR7","unstructured":"B. DasGupta and B. Hammer: On approximate learning by multi-layered feedforward circuits. In H. Arimura, S. Jain, and A. Sharma (eds.), Proceedings of the ALT\u20192000 Eleventh International Conference on Algorithmic Learning Theory, LNAI 1968, 264\u2013278, Berlin: Springer-Verlag, 2000."},{"issue":"6","key":"9_CR8","doi-asserted-by":"publisher","first-page":"1490","DOI":"10.1109\/72.471360","volume":"6","author":"B. DasGupta","year":"1995","unstructured":"B. DasGupta, H. T. Siegelmann, and E. D. Sontag: On the complexity of training neural networks with continuous activation functions. IEEE Transactions on Neural Networks6(6):1490\u20131504, 1995.","journal-title":"IEEE Transactions on Neural Networks"},{"key":"9_CR9","first-page":"524","volume-title":"Advances in Neural Information Processing Systems (NIPS\u201989)","author":"S. E. Fahlman","year":"1990","unstructured":"S. E. Fahlman and C. Lebiere: The cascade-correlation learning architecture. In D. S. Touretzky (ed.), Advances in Neural Information Processing Systems (NIPS\u201989), Vol. 2, 524\u2013532, San Mateo: Morgan Kaufmann, 1990."},{"key":"9_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman, 1979."},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"B. Hammer: Some complexity results for perceptron networks. In L. Niklasson, M. Boden, and T. Ziemke (eds.), Proceedings of the ICANN\u201998 Eight International Conference on Artificial Neural Networks, 639\u2013644, Berlin: Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4471-1599-1_97"},{"key":"9_CR12","unstructured":"B. Hammer: Training a sigmoidal network is difficult. In M. Verleysen (ed.) Proceedings of the ESANN\u201998 Sixth European Symposium on Artificial Neural Networks, 255\u2013260, D-Facto Publications, 1998."},{"key":"9_CR13","volume-title":"Neural Networks: A Comprehensive Foundation","author":"S. Haykin","year":"1999","unstructured":"S. Haykin: Neural Networks: A Comprehensive Foundation. Upper Saddle River, NJ: Prentice-Hall, 2nd edition, 1999.","edition":"2nd edition"},{"issue":"3","key":"9_CR14","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0166-218X(94)00161-6","volume":"66","author":"T. Heged\u00fcs","year":"1996","unstructured":"T. Heged\u00fcs and N. Megiddo: On the geometric separability of Boolean functions, Discrete Applied Mathematics66(3):205\u2013218, 1996.","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"9_CR15","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(93)90064-G","volume":"46","author":"K.-U. H\u00f6ffgen","year":"1993","unstructured":"K.-U. H\u00f6ffgen: Computational limitations on training sigmoid neural networks. Information Processing Letters46(6):269\u2013274, 1993.","journal-title":"Information Processing Letters"},{"issue":"1","key":"9_CR16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1006\/jcss.1995.1011","volume":"50","author":"K.-U. H\u00f6ffgen","year":"1995","unstructured":"K.-U. H\u00f6ffgen, H.-U. Simon, and K. S. Van Horn: Robust trainability of single neurons. Journal of Computer and System Sciences50(1):114\u2013125, 1995.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"9_CR17","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1162\/089976699300016449","volume":"11","author":"D. R. Hush","year":"1999","unstructured":"D. R. Hush: Training a sigmoidal node is hard. Neural Computation11(5):1249\u20131260, 1999.","journal-title":"Neural Computation"},{"issue":"1","key":"9_CR18","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","volume":"6","author":"D. S. Johnson","year":"1978","unstructured":"D. S. Johnson and F. P. Preparata: The densest hemisphere problem. Theoretical Computer Science6(1):93\u2013107, 1978.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1109\/18.567673","volume":"43","author":"L. K. Jones","year":"1997","unstructured":"L. K. Jones: The computational intractability of training sigmoidal neural networks. IEEE Transactions on Information Theory43(1):167\u2013173, 1997.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"9_CR20","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0885-064X(88)90019-2","volume":"4","author":"J. S. Judd","year":"1988","unstructured":"J. S. Judd: On the complexity of loading shallow networks. Journal of Complexity4(3):177\u2013192, 1988.","journal-title":"Journal of Complexity"},{"key":"9_CR21","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4932.001.0001","volume-title":"Neural Network Design and the Complexity of Learning","author":"J. S. Judd","year":"1990","unstructured":"J. S. Judd: Neural Network Design and the Complexity of Learning. Cambridge, MA: The MIT Press, 1990."},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp: Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, 85\u2013103, New York: Plenum Press, 1972."},{"key":"9_CR23","unstructured":"Ch. Kuhlmann: Hardness results for general two-layer neural networks. In N. Cesa-Bianchi and S. A. Goldman (eds.), Proceedings of the COLT 2000 Thirteenth Annual Conference on Computational Learning Theory, 275\u2013285, 2000."},{"key":"9_CR24","first-page":"211","volume":"6","author":"J.-H. Lin","year":"1991","unstructured":"J.-H. Lin and J. S. Vitter: Complexity results on learning by neural nets. Machine Learning6:211\u2013230, 1991.","journal-title":"Machine Learning"},{"key":"9_CR25","unstructured":"A. Macintyre and E. D. Sontag: Finiteness results for sigmoidal \u201cneural\u201d networks. In Proceedings of the STOC\u201993 Twenty-Fifth Annual ACM Symposium on the Theory of Computing, 325\u2013334, New York: ACM Press, 1993."},{"key":"9_CR26","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02187916","volume":"3","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo: On the complexity of polyhedral separability. Discrete Computational Geometry3:325\u2013337, 1988.","journal-title":"Discrete Computational Geometry"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"I. Parberry: On the complexity of learning with a small number of nodes. In Proceedings of the International Joint Conference on Neural Networks, Vol. 3, 893\u2013898, 1992.","DOI":"10.1109\/IJCNN.1992.227086"},{"issue":"4","key":"9_CR28","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"L. Pitt and L. G. Valiant: Computational limitations on learning from examples. Journal of the ACM35(4):965\u2013984, 1988.","journal-title":"Journal of the ACM"},{"issue":"2","key":"9_CR29","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1109\/72.363468","volume":"6","author":"V. P. Roychowdhury","year":"1995","unstructured":"V. P. Roychowdhury, K.-Y. Siu, and T. Kailath: Classification of linearly nonseparable patterns by linear threshold elements. IEEE Transactions on Neural Networks6(2):318\u2013331, 1995.","journal-title":"IEEE Transactions on Neural Networks"},{"volume-title":"Theoretical Advances in Neural Computation and Learning","year":"1994","key":"9_CR30","unstructured":"V. P. Roychowdhury, K.-Y. Siu, and A. Orlitsky (eds.): Theoretical Advances in Neural Computation and Learning. Boston: Kluwer Academic Publishers, 1994."},{"key":"9_CR31","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1038\/323533a0","volume":"323","author":"D. E. Rumelhart","year":"1986","unstructured":"D. E. Rumelhart, G. E. Hinton, and R. J. Williams: Learning representations by back-propagating errors. Nature323:533\u2013536, 1986.","journal-title":"Nature"},{"issue":"5","key":"9_CR32","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1162\/neco.1994.6.5.842","volume":"6","author":"J. \u0160\u00edma","year":"1994","unstructured":"J. \u0160\u00edma: Loading deep networks is hard. Neural Computation6(5):842\u2013850, 1994.","journal-title":"Neural Computation"},{"issue":"6","key":"9_CR33","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/0893-6080(95)00135-2","volume":"9","author":"J. \u0160\u00edma","year":"1996","unstructured":"J. \u0160\u00edma: Back-propagation is not efficient. Neural Networks9(6):1017\u20131023, 1996.","journal-title":"Neural Networks"},{"issue":"1","key":"9_CR34","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0022-0000(92)90039-L","volume":"45","author":"E. D. Sontag","year":"1992","unstructured":"E. D. Sontag: Feedforward networks for interpolation and classification. Journal of Computer and System Sciences45(1):20\u201348, 1992.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"9_CR35","first-page":"367","volume":"1","author":"G. Tesauro","year":"1987","unstructured":"G. Tesauro: Scaling relationships in back-propagation learning: dependence on training set size. Complex Systems1(2):367\u2013372, 1987.","journal-title":"Complex Systems"},{"issue":"1","key":"9_CR36","first-page":"39","volume":"2","author":"G. Tesauro","year":"1988","unstructured":"G. Tesauro and B. Janssens: Scaling relationships in back-propagation learning. Complex Systems2(1):39\u201344, 1988.","journal-title":"Complex Systems"},{"key":"9_CR37","unstructured":"V. H. Vu: On the infeasibility of training neural networks with small squared errors. In M. I. Jordan, M. J. Kearns, and S. A. Solla (eds.), Advances in Neural Information Processing Systems (NIPS\u201997), Vol. 10, 371\u2013377, The MIT Press,1998."},{"key":"9_CR38","volume-title":"A Theory of Learning and Generalization","author":"M. Vidyasagar","year":"1997","unstructured":"M. Vidyasagar: A Theory of Learning and Generalization. London: Springer-Verlag, 1997."},{"key":"9_CR39","unstructured":"H. Wiklicky: The neural network loading problem is undecidable. In J. Shawe-Taylor and M. Anthony (eds.), Proceedings of the EuroCOLT\u201993 First Conference on Computational Learning Theory, 183\u2013192, Oxford: Clarendon Press, 1994."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45583-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T19:11:35Z","timestamp":1737486695000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45583-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540428756","9783540455837"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/3-540-45583-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"31 October 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}