Optimistic Estimate Uncovers the Potential of Nonlinear Models
Yaoyu Zhang Zhongwang Zhang Leyang Zhang Zhiwei Bai Tao Luo Zhi-Qin John Xu
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.