New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains limited even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, little progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art.Submission Number: 3416
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing …
Divergence Frontiers for Generative Models: Sample Complexity, Quantization Effects, and Frontier Integrals
The spectacular success of deep generative models calls for quantitative tools to measure their statistical performance. Divergence frontiers have recently been proposed as an evaluation framework for generative models, …
DiversityQuantizationOutlier detection in default logics: the tractability/intractability frontier
In default theories, outliers denote sets of literals featuring unexpected properties. In previous papers, we have defined outliers in default logics and investigated their formal properties. Specifically, we have looked…
LEMMAOutlier DetectionParameterized Complexity Results for Plan Reuse
Planning is a notoriously difficult computational problem of high worst-case complexity. Researchers have been investing significant efforts to develop heuristics or restrictions to make planning practically feasible. Ca…
Theoretical Hardness and Tractability of POMDPs in RL with Partial Online State Information
Partially observable Markov decision processes (POMDPs) have been widely applied in various real-world applications. However, existing theoretical results have shown that learning in POMDPs is intractable in the worst ca…