Logarithmic Width Suffices for Robust Memorization
The memorization capacity of neural networks with a given architecture has been thoroughly studied in many works. Specifically, it is well-known that memorizing $N$ samples can be done using a network of constant width, independent of $N$. However, the required constructions are often quite delicate. In this paper, we consider the natural question of how well feedforward ReLU neural networks can memorize robustly, namely while being able to withstand adversarial perturbations of a given radius. We establish both upper and lower bounds on the possible radius for general $l_p$ norms, implying (among other things) that width logarithmic in the number of input samples is necessary and sufficient to achieve robust memorization (with robustness radius independent of $N$).
Code (0)
등록된 구현이 없습니다.
Tasks
MemorizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Memorization capacity of deep ReLU neural networks characterized by width and depth
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 sep…
Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
Recent theoretical work has guaranteed that overparameterized networks trained by gradient descent achieve arbitrarily low training error, and sometimes even low test error. The required width, however, is always polynom…
How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
A recent line of research on deep learning focuses on the extremely over-parameterized setting, and shows that when the network width is larger than a high degree polynomial of the training sample size and the inverse o…
Open-Ended Question AnsweringHow Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
A recent line of research on deep learning focuses on the extremely over-parameterized setting, and shows that when the network width is larger than a high degree polynomial of the training sample size $n$ and the invers…
Open-Ended Question AnsweringOptimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks
Kolmogorov--Arnold Networks (KANs) have recently emerged as a structured alternative to standard MLPs, yet a principled theory for their training dynamics, generalization, and privacy properties remains limited. In this …