Fl RDT based ultimate lowering of the negative spherical perceptron capacity

• URL: http://arxiv.org/abs/2312.16531v1
• Date: Wed, 27 Dec 2023 11:23:40 GMT
• Title: Fl RDT based ultimate lowering of the negative spherical perceptron capacity
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the classical \emph{spherical} perceptrons and study their capacities. The famous zero-threshold case was solved in the sixties of the last century (see, \cite{Wendel62,Winder,Cover65}) through the high-dimensional combinatorial considerations. The general threshold, $\kappa$, case though turned out to be much harder and stayed out of reach for the following several decades. A substantial progress was then made in \cite{SchTir02} and \cite{StojnicGardGen13} where the \emph{positive} threshold ($\kappa\geq 0$) scenario was finally fully settled. While the negative counterpart ($\kappa\leq 0$) remained out of reach, \cite{StojnicGardGen13} did show that the random duality theory (RDT) is still powerful enough to provide excellent upper bounds. Moreover, in \cite{StojnicGardSphNeg13}, a \emph{partially lifted} RDT variant was considered and it was shown that the upper bounds of \cite{StojnicGardGen13} can be lowered. After recent breakthroughs in studying bilinearly indexed (bli) random processes in \cite{Stojnicsflgscompyx23,Stojnicnflgscompyx23}, \emph{fully lifted} random duality theory (fl RDT) was developed in \cite{Stojnicflrdt23}. We here first show that the \emph{negative spherical perceptrons} can be fitted into the frame of the fl RDT and then employ the whole fl RDT machinery to characterize the capacity. To be fully practically operational, the fl RDT requires a substantial numerical work. We, however, uncover remarkable closed form analytical relations among key lifting parameters. Such a discovery enables performing the needed numerical calculations to obtain concrete capacity values. We also observe that an excellent convergence (with the relative improvement $\sim 0.1\%$) is achieved already on the third (second non-trivial) level of the \emph{stationarized} full lifting.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging [54.172416732517156]
  Langevin dynamics can succeed with $n gtrsim d kstar/2 $ samples if one considers the average iterate, rather than the last.<n>We show that Langevin dynamics can succeed with $n gtrsim d kstar/2 $ samples if one considers the average iterate, rather than the last.
  arXiv  Detail & Related papers  (2026-03-06T08:23:24Z)
• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II) [51.320599504997745]
  We show that when the number $K$ of communities remains smaller than $sqrtn$, non-trivial community recovery is possible in time above the Kesten--Stigum threshold.<n>We also show that, in moderately sparse settings, the optimal algorithms appear to be fundamentally different from spectral methods.
  arXiv  Detail & Related papers  (2025-11-26T15:54:17Z)
• Binary perceptron computational gap -- a parametric fl RDT view [2.538209532048867]
  asymmetric binary perceptron (ABP) likely exhibits two phase transitioning constraint density thresholds.<n>We consider a particular parametric utilization of emphfully lifted random duality theory (fl RDT) [85] and study its potential ABP's algorithmic implications.
  arXiv  Detail & Related papers  (2025-11-02T18:23:49Z)
• 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)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  We show that SignSGD with Majority Voting can robustly work on the whole range of complexity with $kappakappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappa
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  We develop a emphBest-of-Both-Worlds (BoBW) algorithm with regret upper bounds in both adversarial regimes.<n>We show that the proposed algorithm achieves $Oleft(log(T)1+beta2+betaTfrac12+betaright)$ regret under the margin condition.
  arXiv  Detail & Related papers  (2024-03-05T18:59:47Z)
• 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)
• \emph{Lifted} RDT based capacity analysis of the 1-hidden layer treelike \emph{sign} perceptrons neural networks [0.0]
  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.
  arXiv  Detail & Related papers  (2023-12-13T16:19:58Z)
• Binary perceptrons capacity via fully lifted random duality theory [0.0]
  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.
  arXiv  Detail & Related papers  (2023-11-29T22:22:32Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59:30Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• 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)
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
  We propose a new framework of variance-reduced Hamiltonian Monte Carlo (HMC) methods for sampling from an $L$-smooth and $m$-strongly log-concave distribution. We show that the unbiased gradient estimators, including SAGA and SVRG, based HMC methods achieve highest gradient efficiency with small batch size. Experimental results on both synthetic and real-world benchmark data show that our new framework significantly outperforms the full gradient and gradient HMC approaches.
  arXiv  Detail & Related papers  (2021-02-09T02:44:24Z)
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins [92.7662890047311]
  We show that gradient descent finds halfspaces with classification error $tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
  arXiv  Detail & Related papers  (2020-10-01T16:48:33Z)

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.