\emph{Lifted} RDT based capacity analysis of the 1-hidden layer treelike \emph{sign} perceptrons neural networks

• URL: http://arxiv.org/abs/2312.08257v1
• Date: Wed, 13 Dec 2023 16:19:58 GMT
• Title: \emph{Lifted} RDT based capacity analysis of the 1-hidden layer treelike \emph{sign} perceptrons neural networks
• Abstract summary: We consider the capabilities of multilayered emphsign perceptrons neural networks (SPNNs) A recent rigorous capacity characterization, obtained in citeStojnictcmspnncaprdt23, demonstrated that adding neurons in a network configuration may indeed be very beneficial.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the memorization capabilities of multilayered \emph{sign} perceptrons neural networks (SPNNs). A recent rigorous upper-bounding capacity characterization, obtained in \cite{Stojnictcmspnncaprdt23} utilizing the Random Duality Theory (RDT), demonstrated that adding neurons in a network configuration may indeed be very beneficial. Moreover, for particular \emph{treelike committee machines} (TCM) architectures with $d\leq 5$ neurons in the hidden layer, \cite{Stojnictcmspnncaprdt23} made a very first mathematically rigorous progress in over 30 years by lowering the previously best known capacity bounds of \cite{MitchDurb89}. Here, we first establish that the RDT bounds from \cite{Stojnictcmspnncaprdt23} scale as $\sim \sqrt{d}$ and can not on their own \emph{universally} (over the entire range of $d$) beat the best known $\sim \log(d)$ scaling of the bounds from \cite{MitchDurb89}. After recognizing that the progress from \cite{Stojnictcmspnncaprdt23} is therefore promising, but yet without a complete concretization, we then proceed by considering the recently developed fully lifted RDT (fl RDT) as an alternative. While the fl RDT is indeed a powerful juggernaut, it typically relies on heavy numerical evaluations. To avoid such heavy numerics, we here focus on a simplified, \emph{partially lifted}, variant and show that it allows for very neat, closed form, analytical capacity characterizations. Moreover, we obtain the concrete capacity bounds that \emph{universally} improve for \emph{any} $d$ over the best known ones of \cite{MitchDurb89}.

Related papers

• Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limit [66.20349460098275]
  We study the gradient descent learning of a general Gaussian Multi-index model $f(boldsymbolx)=g(boldsymbolUboldsymbolx)$ with hidden subspace $boldsymbolUin mathbbRrtimes d$.<n>We prove that under generic non-degenerate assumptions on the link function, a standard two-layer neural network trained via layer-wise gradient descent can agnostically learn the target with $o_d(1)$ test error.
  arXiv  Detail & Related papers  (2025-11-19T04:46:47Z)
• Sparse by Rule: Probability-Based N:M Pruning for Spiking Neural Networks [66.61171793101872]
  Spiking neural networks (SNNs) promise energy-efficient intelligence via event-driven, sparse computation, but deeper architectures inflate parameters and computational cost, hindering their edge deployment.<n>Recent progress in SNN pruning helps alleviate this burden, yet existing efforts fall into only two families: emphunstructured pruning, which attains high sparsity but is difficult to accelerate on general hardware, and emphstructured pruning, which eases deployment but lack flexibility and often degrades accuracy at matched sparsity.<n>We introduce bfSpikeNM, the first SNN
  arXiv  Detail & Related papers  (2025-11-15T08:23:20Z)
• Simple Convergence Proof of Adam From a Sign-like Descent Perspective [58.89890024903816]
  We show that Adam achieves the optimal rate of $cal O(frac1Ts14)$ rather than the previous $cal O(fracln TTs14)$.<n>Our theoretical analysis provides new insights into the role of momentum as a key factor ensuring convergence.
  arXiv  Detail & Related papers  (2025-07-08T13:19:26Z)
• Emergence and scaling laws in SGD learning of shallow neural networks [64.48316762675141]
  We study the complexity of online gradient descent (SGD) for learning a two-layer neural network with $P$ neurons on isotropic Gaussian data.<n>We provide a precise analysis of SGD dynamics for the training of a student two-layer network to minimize the mean squared error (MSE) objective.
  arXiv  Detail & Related papers  (2025-04-28T16:58:55Z)
• Capacity of the Hebbian-Hopfield network associative memory [0.0]
  In citeHop82, Hopfield introduced a emphHebbian learning rule based neural network model and suggested how it can efficiently operate as an associative memory. We study two famous pattern's basins of attraction: textbfemph(i) The AGS one from citeAmiGutSom85; and textbfemph(ii) The NLT one from citeNewman88,Louk94,Louk94a,Louk97,Tal
  arXiv  Detail & Related papers  (2024-03-04T10:10:23Z)
• Exact capacity of the \emph{wide} hidden layer treelike neural networks with generic activations [0.0]
  Random Duality Theory (RDT) and its a emphpartially lifted(pl RDT) variant are powerful tools that can be used for very precise networks capacity analysis. Here, we consider emphwide hidden layer networks and uncover that certain aspects of numerical difficulties faced in citeStojnictcmspnncapdiffactrdt23 miraculously disappear.
  arXiv  Detail & Related papers  (2024-02-08T14:50:07Z)
• Fixed width treelike neural networks capacity analysis -- generic activations [0.0]
  We consider the capacity of emphtreelike committee machines (TCM) neural networks. We show that the frameworks of citeStojnictcmspnncaprdt23,Stojnictcmspnncapliftedrdt23 are sufficiently powerful to enable handling of such scenarios as well.
  arXiv  Detail & Related papers  (2024-02-08T14:19:29Z)
• Fl RDT based ultimate lowering of the negative spherical perceptron capacity [0.0]
  We consider the classical emphspherical perceptrons and study their capacities. We first show that the emphnegative spherical perceptrons can be fitted into the frame of the fl RDT and then employ the whole fl RDT machinery to characterize the capacity.
  arXiv  Detail & Related papers  (2023-12-27T11:23:40Z)
• Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper bounds [0.0]
  We study the capacity of emphsign perceptrons neural networks (SPNN) We focus on 1-hidden layer emphtreelike committee machine (TCM) architectures.
  arXiv  Detail & Related papers  (2023-12-13T16:06:18Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories. We propose a novel GNN architecture whereby the emphforward pass explicitly depends on emphboth positive (as is typical) and negative (unique to our approach) edges. This is achieved by recasting the embeddings themselves as minimizers of a forward-pass-specific energy function that favors separation of positive and negative samples.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work [59.29606307518154]
  We show that as long as the width $m geq 2n/d$ (where $d$ is the input dimension), its expressivity is strong, i.e., there exists at least one global minimizer with zero training loss. We also consider a constrained optimization formulation where the feasible region is the nice local region, and prove that every KKT point is a nearly global minimizer.
  arXiv  Detail & Related papers  (2022-10-21T14:41:26Z)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  We study the first gradient descent step on the first-layer parameters $boldsymbolW$ in a two-layer network. Our results demonstrate that even one step can lead to a considerable advantage over random features.
  arXiv  Detail & Related papers  (2022-05-03T12:09:59Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  We show that feedforward ReLU neural networks can memorization any $N$ points that satisfy a mild separability assumption. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.
  arXiv  Detail & Related papers  (2021-10-07T05:25:23Z)
• An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks [40.489350374378645]
  We prove that $widetildemathcalO(e1/delta2+sqrtn)$ neurons and $widetildemathcalO(fracddelta+n)$ weights are sufficient. We also prove new lower bounds by connecting in neural networks to the purely geometric problem of separating $n$ points on a sphere using hyperplanes.
  arXiv  Detail & Related papers  (2021-06-14T19:42:32Z)
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
  We analyze the properties of adversarial learning adversarially robust halfspaces in the presence of label noise. To the best of our knowledge, this is the first work to show that adversarial training prov yields classifiers in noise.
  arXiv  Detail & Related papers  (2021-04-19T16:35:38Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
  arXiv  Detail & Related papers  (2020-10-22T19:14:37Z)
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
  We consider the dynamic of descent for learning a two-layer neural network. We show that an over-parametrized two-layer neural network can provably learn with gradient loss at most ground with Tangent samples.
  arXiv  Detail & Related papers  (2020-07-09T07:09:28Z)

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.