Logarithmic Width Suffices for Robust Memorization

2025/02/16 by Amitsour Egosi, Gilad Yehudai, Egosi, Amitsour +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2502.11162

openalex publication_date 2025/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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).

Related

• On the Optimal Memorization Power of ReLU Neural Networks
• Network size and weights size for memorization with two-layers neural networks
• The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets
• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
• Memorization Capacity for Additive Fine-Tuning with Small ReLU Networks