Sharp threshold for the Ising perceptron model

2019/05/15 by Changji Xu, Xu, Changji · 4 citations
Computer Science · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1905.05978

openalex publication_date 2019/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider the discrete cube \-1,1\^N and a random collection of half spaces which includes each half space H(x) := \y ∈ \-1,1\^N: x ⋅ y ≥ κ√(N)\ for x ∈ \-1,1\^N independently with probability p. Is the intersection of these half spaces empty? This is called the Ising perceptron model under Bernoulli disorder. We prove that this event has a sharp threshold; that is, the probability that the intersection is empty increases quickly from ε to 1- ε when p increases only by a factor of 1 + o(1) as N → ∞.

Citations

• The influence of variables in product spaces
• Capacity lower bound for the Ising perceptron

Cited by

• Uniqueness of Replica-symmetric Saddle Point for Ising Perceptron
• Binary perceptron computational gap -- a parametric fl RDT view
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• A large deviation view of stationarized fully lifted blirp interpolation

Related

• Capacity lower bound for the Ising perceptron
• Sharp threshold sequence and universality for Ising perceptron models
• Gardner formula for Ising perceptron models at small densities
• Capacity threshold for the Ising perceptron
• Distribution of the threshold for the symmetric perceptron