Memorization capacity of deep ReLU neural networks characterized by width and depth
Xin Yang, Yunfei Yang
原文摘要
This paper studies the memorization capacity of deep neural networks with ReLU activation. Specifically, we investigate the minimal size of such networks to memorize any $N$ data points in the unit ball with pairwise separation distance $δ$ and labels from a finite set of size $C$. Most prior studies characterize the memorization capacity by the number of parameters or neurons. We extend these results by constructing ReLU networks with adjustable width $W$ and depth $L$ satisfying $W^2L^2\log W=\mathcal{O}(N(\log(δ^{-1})+\log C))$ that can memorize any such dataset. We also establish width-depth lower bounds that depend explicitly on $δ$ and $C$ for networks capable of memorizing all such datasets. When $\log(δ^{-1})\asymp\log N$, our construction achieves $W^2L^2\asymp N$ for suitable choices of width and depth. This order is optimal if $\log C\asymp\log N$, and optimal up to logarithmic factors if $\log C=o(\log N)$.
cs.LG · math.NA