REVIEW 4 cited by
Discrepancy Algorithms for the Binary Perceptron
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with intercept $-\kappa$. We analyze the performance of the canonical discrepancy minimization algorithms of Lovett-Meka and Rothvoss/Eldan-Singh for the asymmetric binary perceptron problem. We obtain new algorithmic results in the $\kappa = 0$ case and in the large-$|\kappa|$ case. In the $\kappa\to-\infty$ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound.
Forward citations
Cited by 4 Pith papers
-
Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
For random order-p tensors with large p, the largest average k×...×k subtensor concentrates around sqrt(2p log(N choose k)/k^p), a greedy algorithm achieves a 2√p/(p+1) fraction of it, and an overlap gap property bloc...
-
Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
For the asymmetric binary perceptron, the worst-case local entropy breaks down for constraint density alpha in (0.77, 0.78), matching replica predictions and the range where fast algorithms stop working.
-
Fully lifted \emph{blirp} interpolation -- a large deviation view
A large-deviation upgrade of fully lifted blirp interpolation is derived, yielding explicit derivative identities that the author links to local entropy and computational gaps in perceptron models.
-
A large deviation view of \emph{stationarized} fully lifted blirp interpolation
The paper derives new derivative identities for a stationarized fully lifted bilinearly indexed random process interpolator and states an equality between large deviation limits at the opposite ends of an interpolation path.
Discussion (0). Continue with ORCID to comment.