Generalizability of Memorization Neural Networks

Lijia Yu, Xiao-Shan Gao, Lijun Zhang, Yibo Miao · 2024

Read Generalizability of Memorization Neural Networks by Lijia Yu, Xiao-Shan Gao, Lijun Zhang, Yibo Miao (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00372.txt.

Description

Abstract The neural network memorization problem is to study the expressive power of neural networks to interpolate a finite dataset. Although memorization is widely believed to have a close relationship with the strong generalizability of deep learning when using over-parameterized models, to the best of our knowledge, there exists no theoretical study on the generalizability of memorization neural networks.

Catalog record

CREATORLijia Yu, Xiao-Shan Gao, Lijun Zhang, Yibo Miao
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE158 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-00372

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generalizability of Memorization Neural Networks Lijia Yu, Xiao-Shan Gao, Lijun Zhang, Yibo Miao Abstract The neural network memorization problem is to study the expressive power of neural networks to interpolate a finite dataset. Although memorization is widely believed to have a close relationship with the strong generalizability of deep learning when using over-parameterized models, to the best of our knowledge, there exists no theoretical study on the generalizability of memorization neural networks. In this paper, we give the first theoretical analysis of this topic. Since using i.i.d. training data is a necessary condition for a learning algorithm to be generalizable, memorization and its generalization theory for i.i.d. datasets are developed under mild conditions on the data distribution. First, algorithms are given to construct memorization networks for an i.i.d. dataset, which have the smallest number of parameters and even a constant number of parameters. Second, we show that, in order for the memorization networks to be generalizable, the width of the network must be at least equal to the dimension of the data, which implies that the existing memorization networks with an optimal number of parameters are not generalizable. Third, a lower bound for the sample complexity of general memorization algorithms and the exact sample complexity for memorization algorithms with constant number of parameters are given. It is also shown that there exist data distributions such that, to be generalizable for them, the memorization network must have an exponential number of parameters in the data dimension. Finally, an efficient and generalizable memorization algorithm is given when the number of training samples is greater than the efficient memorization sample complexity of the data distribution. 1 Introduction Memorization is to study the expressive power of neural networks to interpolate a finite dataset [ 9 ] . The main focus of the existing work is to study how many parameters are needed to memorize. For any dataset {\mathcal{D}}_{tr} of size N and neural networks of the form {\mathcal{F}}:{\mathbb{R}}^{n}\to{\mathbb{R}} , memorization networks with \overline{O}(N) parameters have been given with various model structures and activation functions [ 31 , 50 , 30 , 29 , 26 , 47 , 56 , 11 , 65 ] . On the other hand, it is shown that in order to memorize an arbitrary dataset of size N [ 64 , 56 ] , the network must have at least \overline{\Omega}(N) parameters, so the above algorithms are approximately optimal. Under certain assumptions, it is shown that sublinear \overline{O}(N^{2/3}) parameters are sufficient to memorize {\mathcal{D}}_{tr} [ 49 ] . Furthermore, Vardi et al. [55] give a memorization network with optimal number of parameters: \overline{O}(\sqrt{N}) . Recently, it is shown that memorization is closely related to one of the most surprising properties of deep learning, that is, over-parameterized neural networks are trained to nearly memorize noisy data and yet can still achieve a very nice generalization on the test data [ 45 , 7 , 4 ] . More precisely, the double descent phenomenon [ 45 ] indicates that when the networks reach the interpolation threshold, larger networks tend to have more generalizability [ 41 , 10 ] . It is also noted that memorizing helps generalization in complex learning tasks, because data with the same label have quite diversified features and need to be nearly memorized [ 19 , 20 ] . A line of research to harvest the help of memorization to generalization is interpolation learning . Most of recent work in interpolation learning shows generalizability of memorization models in linear regimes [ 7 , 12 , 38 , 53 , 59 , 66 ] . As far as we know, the generazability of memorization neural networks has not been studied theoretically, which is more challenging compared to the linear models, and this paper provides a systematic study of this topic. In this paper, we consider datasets that are sampled i.i.d. from a data distribution, because i.i.d. training dataset is a necessary condition for learning algorithms to have generalizability [ 54 , 44 ] . More precisely, we consider binary data distributions {\mathcal{D}} over {\mathbb{R}}^{n}\times\{-1,1\} and use {\mathcal{D}}_{\rm{tr}}\sim{\mathcal{D}}^{N} to mean that {\mathcal{D}}_{tr} is sampled i.i.d. from {\mathcal{D}} and |{\mathcal{D}}_{tr}|=N . All neural networks are of the form {\mathcal{F}}:{\mathbb{R}}^{n}\to{\mathbb{R}} . The main contributions of this paper include four aspects. First, we give the smallest number of parameters required for a network to memorize an i.i.d. dataset. Theorem 1.1 (Informal. Refer to Section 4 ) . Under mild conditions on {\mathcal{D}} , if {\mathcal{D}}_{tr}\sim{\mathcal{D}}^{N} , it holds (1) There exists an algorithm to obtain a memorization network of {\mathcal{D}}_{tr} with width 6 and depth \overline{O}(\sqrt{N}) . (2) There exists a constant N_{\mathcal{D}}\in{\mathbb{Z}}_{+} depending on {\mathcal{D}} only, such that a memorization network of {\mathcal{D}}_{tr} with at most N_{\mathcal{D}} parameters can be obtained algorithmically. N_{\mathcal{D}} is named as the memorization parameter complexity of {\mathcal{D}} , which measures the complexity of {\mathcal{D}} under which a memorization network with \leq N_{\mathcal{D}} parameters exists for almost all D_{\rm{tr}}\sim{\mathcal{D}}^{N} . Theorem 1.1 allows us to give the memorization network for i.i.d dataset with the optimal number of parameters. When N is small so that \sqrt{N}\ll N_{\mathcal{D}} , the memorization network needs at least \overline{\Omega}(\sqrt{N}) parameters as proved in [ 6 ] and (1) of Theorem 1.1 gives the optimal construction. When N is large, (2) of Theorem 1.1 shows that a constant number of parameters is enough to memorize. Second, we give a necessary condition for the structure of the memorization networks to be generalizable, and shows that even if there is enough data, memorization network may not have generalizability. Theorem 1.2 (Informal. Refer to Section 5 ) . Under mild conditions on {\mathcal{D}} , if {\mathcal{D}}_{tr}\sim{\mathcal{D}}^{N} , it holds (1) Let {\mathbf{H}} be a set of neural networks with width w . Then, there exist an integer n>w and a data distribution {\mathcal{D}} over {\mathbb{R}}^{n}\times\{-1,1\} such that, any memorization network of {\mathcal{D}}_{tr} in {\mathbf{H}} is not generalizable. (2) For almost any {\mathcal{D}} , there exists a memorization network of {\mathcal{D}}_{tr} , which has \overline{O}(\sqrt{N}) parameters and is not generalizable. Theorem 1.2 indicates that memorization networks with the optimal number of parameters \overline{O}(\sqrt{N}) may have poor generalizability, and commonly used algorithms for constructing fixed-width memorization networks have poor generalization for some distributions. These conclusions demonstrate that the commonly used network structures for memorization is not generalizable and new network structures are needed to achieve generalization. Third, we give a lower bound for the sample complexity of general memorization networks and the exact sample complexity for certain memorization networks. Theorem 1.3 (Informal. Refer to Section 6 ) . Let N_{\mathcal{D}} be the memorization parameter complexity defined in Theorem 1.1 . Under mild conditions on {\mathcal{D}} , we have (1) Lower bound . In order for a memorization network of any {\mathcal{D}}_{\rm{tr}}\sim{\mathcal{D}}^{N} to be generalizable, N must be \geq\overline{\Omega}(\frac{N^{2}_{\mathcal{D}}}{\ln^{2}(N_{\mathcal{D}})}) 1 1 1 Here, \overline{\Omega} and \overline{O} mean that certain small quantities are omitted. Also, we keep the logarithm factor of N_{\mathcal{D}} for comparison with the upper bound . (2) Upper bound . For any memorization network with at most N_{{\mathcal{D}}} parameters for {\mathcal{D}}_{\rm{tr}}\sim{\mathcal{D}}^{N} , if N=\overline{O}(N_{{\mathcal{D}}}^{2}\ln N_{\mathcal{D}}) , then the network is generalizable. Notice that the lower bound is for general memorization networks and the upper bound is for memorization

Read the complete text