16 research outputs found
A Law of Data Reconstruction for Random Features (and Beyond)
No full textLarge-scale deep learning models are known to memorize parts of the training set. In machine learning theory, memorization is often framed as interpolation or label fitting, and classical results show that this can be achieved when the number of parameters in the model is larger than the number of training samples . In this work, we consider memorization from the perspective of data reconstruction, demonstrating that this can be achieved when is larger than , where is the dimensionality of the data. More specifically, we show that, in the random features model, when , the subspace spanned by the training samples in feature space gives sufficient information to identify the individual samples in input space. Our analysis suggests an optimization method to reconstruct the dataset from the model parameters, and we demonstrate that this method performs well on various architectures (random features, two-layer fully-connected and deep residual networks). Our results reveal a law of data reconstruction, according to which the entire training dataset can be recovered as exceeds the threshold
The dynamics of Stochastic Gradient Descent in the loss landscape of Deep Neural Networks
No full textThe deep learning optimization community has observed how the neural networks generalization ability is strongly related to the flatness of the loss landscape in the point the optimization algorithm converged to. Experiments show that SGD is more likely to converge to flat minima, unlike its deterministic counterpart, GD. In this work we try to build a mathematical model able to clarify this phenomenon, using a variation of the Eyring-Kramers law, a formula used in physics to describe the mean transition time of a Brownian particle between local minima in a potential landscape.
Later, we discuss the validity of the continuous approach for these purposes, showing how the SGD dynamics does not fulfill the necessary requirements for our architecture, since it is substantially a strongly discrete process. This result casts doubts on the validity of continuous-time approximation commonly used to analyze SGD dynamics through the theory of stochastic differential equations.
We finally try, with empirical experiments, to better investigate the loss landscape and the SGD trajectory of a real training process on a real neural network. We are therefore able to get an overview of the loss landscape topology, that we claim is in analogy with a tower of colanders. In particular, we find a natural constraint between the loss and the highest eigenvalue of its Hessian, meaning that we cannot achieve low values of the loss function, without entering in narrow areas of the landscape
Privacy for free in the overparameterized regime
No full textDifferentially private gradient descent (DP-GD) is a popular algorithm to train deep learning models with provable guarantees on the privacy of the training data. In the last decade, the problem of understanding its performance cost with respect to standard GD has received remarkable attention from the research community, which formally derived upper bounds on the excess population risk RP in different learning settings. However, existing bounds typically degrade with over-parameterization, i.e., as the number of parameters p gets larger than the number of training samples n -- a regime which is ubiquitous in current deep-learning practice. As a result, the lack of theoretical insights leaves practitioners without clear guidance, leading some to reduce the effective number of trainable parameters to improve performance, while others use larger models to achieve better results through scale. In this work, we show that in the popular random features model with quadratic loss, for any sufficiently large p , privacy can be obtained for free, i.e., |RP|=o(1) , not only when the privacy parameter ε has constant order, but also in the strongly private setting ε=o(1) . This challenges the common wisdom that over-parameterization inherently hinders performance in private learning
PMLR
No full textUnderstanding the reasons behind the exceptional success of transformers requires a better analysis of why attention layers are suitable for NLP tasks. In particular, such tasks require predictive models to capture contextual meaning which often depends on one or few words, even if the sentence is long. Our work studies this key property, dubbed word sensitivity (WS), in the prototypical setting of random features. We show that attention layers enjoy high WS, namely, there exists a vector in the space of embeddings that largely perturbs the random attention features map. The argument critically exploits the role of the softmax in the attention layer, highlighting its benefit compared to other activations (e.g., ReLU). In contrast, the WS of standard random features is of order 1/n−−√, n being the number of words in the textual sample, and thus it decays with the length of the context. We then translate these results on the word sensitivity into generalization bounds: due to their low WS, random features provably cannot learn to distinguish between two sentences that differ only in a single word; in contrast, due to their high WS, random attention features have higher generalization capabilities. We validate our theoretical results with experimental evidence over the BERT-Base word embeddings of the imdb review dataset
PMLR
No full textUnderstanding the reasons behind the exceptional success of transformers requires a better analysis of why attention layers are suitable for NLP tasks. In particular, such tasks require predictive models to capture contextual meaning which often depends on one or few words, even if the sentence is long. Our work studies this key property, dubbed word sensitivity (WS), in the prototypical setting of random features. We show that attention layers enjoy high WS, namely, there exists a vector in the space of embeddings that largely perturbs the random attention features map. The argument critically exploits the role of the softmax in the attention layer, highlighting its benefit compared to other activations (e.g., ReLU). In contrast, the WS of standard random features is of order 1/n−−√, n being the number of words in the textual sample, and thus it decays with the length of the context. We then translate these results on the word sensitivity into generalization bounds: due to their low WS, random features provably cannot learn to distinguish between two sentences that differ only in a single word; in contrast, due to their high WS, random attention features have higher generalization capabilities. We validate our theoretical results with experimental evidence over the BERT-Base word embeddings of the imdb review dataset
PMLR
No full textDeep learning models are known to overfit and memorize spurious features in the training dataset. While numerous empirical studies have aimed at understanding this phenomenon, a rigorous theoretical framework to quantify it is still missing. In this paper, we consider spurious features that are uncorrelated with the learning task, and we provide a precise characterization of how they are memorized via two separate terms: (i) the stability of the model with respect to individual training samples, and (ii) the feature alignment between the spurious pattern and the full sample. While the first term is well established in learning theory and it is connected to the generalization error in classical work, the second one is, to the best of our knowledge, novel. Our key technical result gives a precise characterization of the feature alignment for the two prototypical settings of random features (RF) and neural tangent kernel (NTK) regression. We prove that the memorization of spurious features weakens as the generalization capability increases and, through the analysis of the feature alignment, we unveil the role of the model and of its activation function. Numerical experiments show the predictive power of our theory on standard datasets (MNIST, CIFAR-10)
PMLR
No full textDeep learning models are known to overfit and memorize spurious features in the training dataset. While numerous empirical studies have aimed at understanding this phenomenon, a rigorous theoretical framework to quantify it is still missing. In this paper, we consider spurious features that are uncorrelated with the learning task, and we provide a precise characterization of how they are memorized via two separate terms: (i) the stability of the model with respect to individual training samples, and (ii) the feature alignment between the spurious pattern and the full sample. While the first term is well established in learning theory and it is connected to the generalization error in classical work, the second one is, to the best of our knowledge, novel. Our key technical result gives a precise characterization of the feature alignment for the two prototypical settings of random features (RF) and neural tangent kernel (NTK) regression. We prove that the memorization of spurious features weakens as the generalization capability increases and, through the analysis of the feature alignment, we unveil the role of the model and of its activation function. Numerical experiments show the predictive power of our theory on standard datasets (MNIST, CIFAR-10)
Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels
No full textMachine learning models are vulnerable to adversarial perturbations, and a
thought-provoking paper by Bubeck and Sellke has analyzed this phenomenon
through the lens of over-parameterization: interpolating smoothly the data
requires significantly more parameters than simply memorizing it. However, this
"universal" law provides only a necessary condition for robustness, and it is
unable to discriminate between models. In this paper, we address these gaps by
focusing on empirical risk minimization in two prototypical settings, namely,
random features and the neural tangent kernel (NTK). We prove that, for random
features, the model is not robust for any degree of over-parameterization, even
when the necessary condition coming from the universal law of robustness is
satisfied. In contrast, for even activations, the NTK model meets the universal
lower bound, and it is robust as soon as the necessary condition on
over-parameterization is fulfilled. This also addresses a conjecture in prior
work by Bubeck, Li and Nagaraj. Our analysis decouples the effect of the kernel
of the model from an "interaction matrix", which describes the interaction with
the test data and captures the effect of the activation. Our theoretical
results are corroborated by numerical evidence on both synthetic and standard
datasets (MNIST, CIFAR-10).Comment: Second arxiv version, updated to the icml23 version of the pape
Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization
No full textThe 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 neurons, 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: the number of parameters is roughly and,
hence, the number of neurons is as little as . To showcase
the applicability of our NTK bounds, we provide two results concerning
memorization capacity and optimization guarantees for gradient descent
training.Comment: Uniformed with the published NeurIPS 2022 versio
Advances in Neural Information Processing Systems
No full textThe 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 Ω(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: the number of parameters is roughly Ω(N) and, hence, the number of neurons is as little as Ω(N−−√). To showcase the applicability of our NTK bounds, we provide two results concerning memorization capacity and optimization guarantees for gradient descent training
