Memory capacity of two layer neural networks with smooth activations

• URL: http://arxiv.org/abs/2308.02001v3
• Date: Wed, 1 May 2024 20:53:20 GMT
• Title: Memory capacity of two layer neural networks with smooth activations
• Authors: Liam Madden, Christos Thrampoulidis,
• Abstract summary: We determine the memory capacity of two layer neural networks with $m$ hidden neurons and input dimension $d$. We derive the precise generic rank of the network's Jacobian, which can be written in terms of Hadamard powers. Our approach differs from prior works on memory capacity and holds promise for extending to deeper models.
• Score: 27.33243506775655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Determining the memory capacity of two layer neural networks with $m$ hidden neurons and input dimension $d$ (i.e., $md+2m$ total trainable parameters), which refers to the largest size of general data the network can memorize, is a fundamental machine learning question. For activations that are real analytic at a point and, if restricting to a polynomial there, have sufficiently high degree, we establish a lower bound of $\lfloor md/2\rfloor$ and optimality up to a factor of approximately $2$. All practical activations, such as sigmoids, Heaviside, and the rectified linear unit (ReLU), are real analytic at a point. Furthermore, the degree condition is mild, requiring, for example, that $\binom{k+d-1}{d-1}\ge n$ if the activation is $x^k$. Analogous prior results were limited to Heaviside and ReLU activations -- our result covers almost everything else. In order to analyze general activations, we derive the precise generic rank of the network's Jacobian, which can be written in terms of Hadamard powers and the Khatri-Rao product. Our analysis extends classical linear algebraic facts about the rank of Hadamard powers. Overall, our approach differs from prior works on memory capacity and holds promise for extending to deeper models and other architectures.

Related papers

• Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression [21.849997443967705]
  Two-layer regression problem has been well-studied in prior works. First layer is activated by a ReLU unit, and the second layer is activated by a softmax unit. We prove that the loss function for the Hessian matrix is positive definite and Lipschitz continuous under certain assumptions.
  arXiv  Detail & Related papers  (2023-11-26T19:19:02Z)
• Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification [22.361338848134025]
  We present a fully connected two-layer neural network for shifted ReLU activation to enable activated neuron identification in sublinear time via geometric search. We also prove that our algorithm can converge in $O(M2/epsilon2)$ time with network size quadratic in the coefficient norm upper bound $M$ and error term $epsilon$.
  arXiv  Detail & Related papers  (2023-07-13T05:33:44Z)
• Polynomial Width is Sufficient for Set Representation with High-dimensional Features [69.65698500919869]
  DeepSets is the most widely used neural network architecture for set representation. We present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE)
  arXiv  Detail & Related papers  (2023-07-08T16:00:59Z)
• A Unified Algebraic Perspective on Lipschitz Neural Networks [88.14073994459586]
  This paper introduces a novel perspective unifying various types of 1-Lipschitz neural networks. We show that many existing techniques can be derived and generalized via finding analytical solutions of a common semidefinite programming (SDP) condition. Our approach, called SDP-based Lipschitz Layers (SLL), allows us to design non-trivial yet efficient generalization of convex potential layers.
  arXiv  Detail & Related papers  (2023-03-06T14:31:09Z)
• Improved Convergence Guarantees for Shallow Neural Networks [91.3755431537592]
  We prove convergence of depth 2 neural networks, trained via gradient descent, to a global minimum. Our model has the following features: regression with quadratic loss function, fully connected feedforward architecture, RelU activations, Gaussian data instances, adversarial labels. They strongly suggest that, at least in our model, the convergence phenomenon extends well beyond the NTK regime''
  arXiv  Detail & Related papers  (2022-12-05T14:47:52Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation [76.57464214864756]
  We study function approximation with two-layer neural networks. Our results significantly improve upon what can be attained with linear (or eluder dimension) methods.
  arXiv  Detail & Related papers  (2021-07-14T03:03:56Z)
• Towards Lower Bounds on the Depth of ReLU Neural Networks [7.355977594790584]
  We investigate whether the class of exactly representable functions strictly increases by adding more layers. We settle an old conjecture about piecewise linear functions by Wang and Sun (2005) in the affirmative. We present upper bounds on the sizes of neural networks required to represent functions with logarithmic depth.
  arXiv  Detail & Related papers  (2021-05-31T09:49:14Z)
• Deep neural network approximation of analytic functions [91.3755431537592]
  entropy bound for the spaces of neural networks with piecewise linear activation functions. We derive an oracle inequality for the expected error of the considered penalized deep neural network estimators.
  arXiv  Detail & Related papers  (2021-04-05T18:02:04Z)
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks [27.374589803147025]
  We prove that a single step of decent gradient over depth two network, with $q$ hidden neurons, can memorize $Omegaleft(fracdqlog4(d)right)$ independent and randomly labeled Gaussians in $mathbbRd$. The result is valid for a large class of activation functions, which includes the absolute value.
  arXiv  Detail & Related papers  (2020-03-28T21:45:42Z)
• On Approximation Capabilities of ReLU Activation and Softmax Output Layer in Neural Networks [6.852561400929072]
  We prove that a sufficiently large neural network using the ReLU activation function can approximate any function in $L1$ up to any arbitrary precision. We also show that a large enough neural network using a nonlinear softmax output layer can also approximate any indicator function in $L1$.
  arXiv  Detail & Related papers  (2020-02-10T19:48:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.