Local Linear Recovery Guarantee of Deep Neural Networks at Overparameterization
This work addresses a critical theoretical issue in deep learning for researchers, providing foundational insights into recovery guarantees in overparameterized scenarios, though it is incremental as it builds on existing theory with a new analytical concept.
The paper tackles the problem of whether deep neural networks can reliably recover target functions when overparameterized by introducing 'local linear recovery' (LLR), a weaker form of recovery that simplifies analysis, and proves that functions expressible by narrower DNNs are recoverable from fewer samples than parameters, with upper bounds on sample sizes established and achieved for two-layer tanh networks.
Determining whether deep neural network (DNN) models can reliably recover target functions at overparameterization is a critical yet complex issue in the theory of deep learning. To advance understanding in this area, we introduce a concept we term "local linear recovery" (LLR), a weaker form of target function recovery that renders the problem more amenable to theoretical analysis. In the sense of LLR, we prove that functions expressible by narrower DNNs are guaranteed to be recoverable from fewer samples than model parameters. Specifically, we establish upper limits on the optimistic sample sizes, defined as the smallest sample size necessary to guarantee LLR, for functions in the space of a given DNN. Furthermore, we prove that these upper bounds are achieved in the case of two-layer tanh neural networks. Our research lays a solid groundwork for future investigations into the recovery capabilities of DNNs in overparameterized scenarios.