Optimistic Estimate Uncovers the Potential of Nonlinear Models
This work addresses the challenge of understanding the potential of nonlinear models in fitting at overparameterization, which is incremental as it builds on existing theoretical frameworks to provide new insights for architecture design in deep learning.
The authors tackled the problem of evaluating the best possible fitting performance of nonlinear models by proposing an optimistic estimate that yields an optimistic sample size, quantifying the smallest sample size needed to fit a target function, and they confirmed predictions for models like DNNs through experiments, revealing properties such as free expressiveness in width and costly expressiveness in connection.
We propose an optimistic estimate to evaluate the best possible fitting performance of nonlinear models. It yields an optimistic sample size that quantifies the smallest possible sample size to fit/recover a target function using a nonlinear model. We estimate the optimistic sample sizes for matrix factorization models, deep models, and deep neural networks (DNNs) with fully-connected or convolutional architecture. For each nonlinear model, our estimates predict a specific subset of targets that can be fitted at overparameterization, which are confirmed by our experiments. Our optimistic estimate reveals two special properties of the DNN models -- free expressiveness in width and costly expressiveness in connection. These properties suggest the following architecture design principles of DNNs: (i) feel free to add neurons/kernels; (ii) restrain from connecting neurons. Overall, our optimistic estimate theoretically unveils the vast potential of nonlinear models in fitting at overparameterization. Based on this framework, we anticipate gaining a deeper understanding of how and why numerous nonlinear models such as DNNs can effectively realize their potential in practice in the near future.