Binary perceptrons capacity via fully lifted random duality theory

• URL: http://arxiv.org/abs/2312.00073v1
• Date: Wed, 29 Nov 2023 22:22:32 GMT
• Title: Binary perceptrons capacity via fully lifted random duality theory
• Abstract summary: We study the statistical capacity of the classical binary perceptrons with general thresholds $kappa$. We rely on emphfully lifted random duality theory (fl RDT) established in citeStojnicflrdt23 to create a general framework for studying the perceptrons' capacities.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the statistical capacity of the classical binary perceptrons with general thresholds $\kappa$. After recognizing the connection between the capacity and the bilinearly indexed (bli) random processes, we utilize a recent progress in studying such processes to characterize the capacity. In particular, we rely on \emph{fully lifted} random duality theory (fl RDT) established in \cite{Stojnicflrdt23} to create a general framework for studying the perceptrons' capacities. Successful underlying numerical evaluations are required for the framework (and ultimately the entire fl RDT machinery) to become fully practically operational. We present results obtained in that directions and uncover that the capacity characterizations are achieved on the second (first non-trivial) level of \emph{stationarized} full lifting. The obtained results \emph{exactly} match the replica symmetry breaking predictions obtained through statistical physics replica methods in \cite{KraMez89}. Most notably, for the famous zero-threshold scenario, $\kappa=0$, we uncover the well known $\alpha\approx0.8330786$ scaled capacity.

Related papers

• Learn from your own latents and not from tokens: A sample-complexity theory [53.5821824211418]
  We study networks trained to predict their emphown latent representations of related views or masked regions.<n>We show that latent prediction achieves this with a number of samples emphconstant in $L$, up to logarithmic factors.<n>This suggests that explicit stacking such as H-JEPA is largely redundant.
  arXiv  Detail & Related papers  (2026-05-26T22:16:42Z)
• A Relative-Budget Theory for Reinforcement Learning with Verifiable Rewards in Large Language Model Reasoning [48.70183357021465]
  Reinforcement learning (RL) is a dominant paradigm for improving the reasoning abilities of large language models.<n>We propose a emphrelative-budget theory explaining this variation through a single quantity called relative budget $:= H/mathbbE[T]$.<n>We show that $$ determines sample efficiency by controlling reward variance and the likelihood of informative trajectories.
  arXiv  Detail & Related papers  (2026-02-02T01:31:52Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  We provide the first convergence guarantee for Optimistic Multiplicative Weights Update ($mathtOMWU$) in NLHF.<n>Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values.
  arXiv  Detail & Related papers  (2025-12-31T12:08:29Z)
• Injectivity capacity of ReLU gates [0.0]
  We consider the injectivity property of the ReLU networks layers. We develop a powerful program to handle the $ell_0$ spherical perceptron and implicitly the ReLU layers injectivity. The obtained results are also shown to fairly closely match the replica predictions from [40]
  arXiv  Detail & Related papers  (2024-10-28T00:57:10Z)
• Stochastic Gradient Succeeds for Bandits [64.17904367852563]
  We show that the emphstochastic gradient bandit algorithm converges to a emphglobally optimal policy at an $O (1/t)$ rate. Remarkably, global convergence of the gradient bandit algorithm has not been previously established.
  arXiv  Detail & Related papers  (2024-02-27T06:05:01Z)
• 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)
• Spectral chaos bounds from scaling theory of maximally efficient quantum-dynamical scrambling [49.1574468325115]
  A key conjecture about the evolution of complex quantum systems towards an ergodic steady state, known as scrambling, is that this process acquires universal features when it is most efficient. We develop a single- parameter scaling theory for the spectral statistics in this scenario, which embodies exact self-similarity of the spectral correlations along the complete scrambling dynamics. We establish that scaling predictions are matched by a privileged process, and serve as bounds for other dynamical scrambling scenarios, allowing one to quantify inefficient or incomplete scrambling on all timescales.
  arXiv  Detail & Related papers  (2023-10-17T15:41:50Z)
• On the Stability and Generalization of Triplet Learning [55.75784102837832]
  Triplet learning, i.e. learning from triplet data, has attracted much attention in computer vision tasks. This paper investigates the generalization guarantees of triplet learning by leveraging the stability analysis.
  arXiv  Detail & Related papers  (2023-02-20T07:32:50Z)
• Scalable Lipschitz Residual Networks with Convex Potential Flows [120.27516256281359]
  We show that using convex potentials in a residual network gradient flow provides a built-in $1$-Lipschitz transformation. A comprehensive set of experiments on CIFAR-10 demonstrates the scalability of our architecture and the benefit of our approach for $ell$ provable defenses.
  arXiv  Detail & Related papers  (2021-10-25T07:12:53Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  Modern machine learning models often employ a huge number of parameters and are typically optimized to have zero training loss. We examine how these benign overfitting phenomena occur in a two-layer neural network setting. We show that it is possible for the two-layer ReLU network interpolator to achieve a near minimax-optimal learning rate.
  arXiv  Detail & Related papers  (2021-06-06T19:08:53Z)
• Robustness, Privacy, and Generalization of Adversarial Training [84.38148845727446]
  This paper establishes and quantifies the privacy-robustness trade-off and generalization-robustness trade-off in adversarial training. We show that adversarial training is $(varepsilon, delta)$-differentially private, where the magnitude of the differential privacy has a positive correlation with the robustified intensity. Our generalization bounds do not explicitly rely on the parameter size which would be large in deep learning.
  arXiv  Detail & Related papers  (2020-12-25T13:35:02Z)

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.