Timezone: »

 
Poster
Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization
Simone Bombari · Mohammad Hossein Amani · Marco Mondelli

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #810
in Poster Session 6 »
The Neural Tangent Kernel (NTK) has emerged as a powerful tool to provide memorization, optimization and generalization guarantees in deep neural networks. A line of work has studied the NTK spectrum for two-layer and deep networks with at least a layer with $\Omega(N)$ neurons, $N$ being the number of training samples. Furthermore, there is increasing evidence suggesting that deep networks with sub-linear layer widths are powerful memorizers and optimizers, as long as the number of parameters exceeds the number of samples. Thus, a natural open question is whether the NTK is well conditioned in such a challenging sub-linear setup. In this paper, we answer this question in the affirmative. Our key technical contribution is a lower bound on the smallest NTK eigenvalue for deep networks with the minimum possible over-parameterization: up to logarithmic factors, the number of parameters is $\Omega(N)$ and, hence, the number of neurons is as little as $\Omega(\sqrt{N})$. To showcase the applicability of our NTK bounds, we provide two results concerning memorization capacity and optimization guarantees for gradient descent training.
Keywords: Deep Neural Networks · Neural Tangent Kernel · memorization capacity · minimum over-parameterization · gradient descent training
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Simone Bombari (IST Austria)
Mohammad Hossein Amani (Institute of Science and Technology Austria)
Marco Mondelli (IST Austria)

More from the Same Authors