The Exact Online Threshold for the Asymmetric Binary Perceptron

1 Introduction

• The model requires each sign to be fixed irrevocably after its Gaussian column arrives and before later columns are revealed.The feasibility question is the supremal constraint density achievable under this sequential information pattern.Source: §1 · p. 1
• The Brownian control problem gives the exact online threshold: a deterministic algorithm succeeds below it, while above it no online algorithm succeeds with probability tending to one.The threshold is an exact characterization, not only an upper bound or an analysis of one algorithm.Source: §1 · p. 2
• At zero margin, the online algorithm surpasses by more than a factor of three the best previously proved polynomial-time density, α ≤ 0.1.That prior guarantee is due to Li, Schramm, and Zhou.Source: §1 · p. 3
• As κ → +∞, the online threshold and offline storage capacity agree to first order.The comparison follows from matching leading-order bounds for the offline construction and storage capacity [Sto13].Source: §1 · p. 3
• As κ → −∞, the online threshold has scale 1/(κ^2Φ(κ)), matching the best known offline polynomial-time guarantee, while storage capacity is larger by order κ^2.Here Φ is the standard normal distribution function.Source: §1 · p. 3
• Half-line monotonicity lets feasible Brownian controls be approximated without optimizer regularity, and a final correction block enforces all M constraints simultaneously.The construction addresses the gap between a Brownian limit for a typical coordinate and simultaneous feasibility across M = Θ(N) rows.Source: §1 · pp. 4–5

2.1 Online algorithms and the constraint density

• Signs are chosen irrevocably as Gaussian columns arrive, and α is the paper’s constraint-density parameter.The online model commits to each sign before the next column is revealed.Source: §2.1 · p. 5

2.2 The Brownian control problem

• The Brownian control value E⋆(κ) concerns progressively measurable controls adapted to Brownian motion, with feasibility requiring compensation when B1 falls below κ.On {B1 < κ}, feasibility requires accumulated control at least κ − B1.Source: §2.2 · pp. 6–7

2.3 Admissible drifts for one Gaussian column

• A signed Gaussian column’s conditional drift lies in a Euclidean ball, and every predictable drift in that ball can be realized while retaining a fresh Gaussian innovation.This one-column constraint supplies the discrete mechanism for implementing coordinatewise Brownian controls.Source: §2.3 · pp. 8–9

3 Upper bound on the online threshold

• A uniformly selected row and a Brownian scaling limit turn successful online signs into a feasible limiting control with terminal value at least κ.The proof combines the one-column drift constraint with a compactness argument.Source: §3 · pp. 9–10
• Projecting the limiting drift onto Brownian’s natural filtration preserves the half-line terminal constraint and can only reduce its second moment.This projection places the control in the filtration used to define E⋆(κ).Source: §3 · pp. 10–11
• α_on(κ) ≤ 2/(πE⋆(κ)) for every online-achievable constraint density.This is the resulting upper bound on the online threshold.Source: §3 · p. 11

4 Achievability and the online algorithm

• The section establishes α_on(κ) ≥ 2πE⋆(κ) and gives a corresponding online algorithm.Source: §4 · p. 11

4.1 Approximation by simple predictable controls

• Half-line monotonicity lets the proof approximate arbitrary feasible Brownian controls without optimizer regularity, using simple predictable controls with bounded Lipschitz history-based coefficients.Source: §4.1 · pp. 12–13

4.2 The Föllmer drift on the final block

• A short final block uses deterministic drift to compensate coordinate shortfalls and a Föllmer drift to confine Gaussian fluctuations, with failure probability o(1) when M = O(N).Source: §4.2 · pp. 13–14

4.3 The online algorithm

• Both stages choose and project each control before the next column arrives; the algorithm uses O(MN) arithmetic operations and has a polynomial-bit-complexity implementation.Source: §4.3 · p. 14

4.4 Analysis of the online algorithm

• Under its control-budget conditions, the analysis shows both stages’ projections are inactive with probability 1−o(1), and the terminal Brownian comparison has minimum above r with probability tending to one.Source: §4.4 · pp. 17–18
• With probability 1−o(1), the projection is inactive and the Brownian comparison matches the ideal process, giving conditional expected ℓ∞ coupling error o(1) and proving (26).The stated coupling error is O(N^-1/4+1/(2p)).Source: §4.4 · p. 18
• A Brownian control with L2 norm strictly below the available drift budget can be instantiated with fixed Algorithm 1 parameters to meet the proposition’s hypotheses.The construction selects a simple predictable control and a positive slack ρ.Source: §4.4 · pp. 18–19
• Combining Corollary 3.3 and Proposition 4.8 completes the proof of the threshold identity; the implementation has polynomial bit complexity.The polynomial-bit-complexity proof is given in Appendix D.Source: §4.4 · p. 19

5.1 Zero margin

• At zero margin, 0.3274793 < α_on(0) < 0.3666340.The lower and upper bounds are obtained by independent computer-assisted arguments: a weighted L2 relaxation with a one-dimensional dynamic-programming recursion, and a self-similar diffusion construction.Source: §5 · p. 19, §5.1 · p. 25

5.2 Large positive margin

• As κ → +∞, α_on(κ) and Stojnic’s rigorous offline upper bound have the same first-order asymptotic, 2/(πκ^2) [Sto13].Source: §5.2 · p. 26

5.3 Large negative margin

• In particular, α_on(κ) = Θ(1/(κ^2Φ(κ))) as κ → −∞; the upper bound prescribes a compactly supported terminal distribution through a Föllmer drift, while the lower bound uses time scale 1 − t ≍ K^−2.Source: §5.3 · p. 26
• Mills bounds provide an integrable dominating function, allowing dominated convergence to establish the large-K limit.The proof also derives a uniform bound using Mills bounds before applying dominated convergence.Source: §5.3 · p. 29
• Replacing a feasible u at level −K by max{u, 0} preserves feasibility and does not increase E[u^2].Taking the infimum over feasible u then proves the stated bound.Source: §5.3 · pp. 29–30
• The large-negative-margin asymptotic has the form K^2(I0 + o(1)), with I0 = 5.06296006456….The coefficient is obtained by one-dimensional numerical integration and used only for display.Source: §5.3 · pp. 28, 30

AI Usage Disclosure

• GPT-5.6 Sol assisted with exploratory proof discussions and drafting and revising the manuscript; the authors take full responsibility for its contents and correctness.Source: AI Usage Disclosure · p. 30

A Proof of the Brownian limit

• The proof adapts the Doob-decomposition and compactness method to the Gaussian perceptron, a uniformly chosen row, and the normalization g_k/√N on [0, 1].The argument reduces to deterministic online algorithms by a seed-fixing argument.Source: A Proof of the Brownian limit · p. 31

A.1 Tightness and the drift bound

• Tightness follows from bounded-in-probability H1 norms for A_N, tightness of W_N, and lower-semicontinuity arguments that yield an adapted absolutely continuous limiting process with a progressively measurable derivative.The passage bounds the joint laws of (A_N, W_N) in C([0, 1])².Source: §A.1 · pp. 31–32

A.2 Identification of the Brownian motion

• The limiting process B is identified as Brownian motion in the completed filtration generated by (A, B), by passing the Brownian martingale problem to the limit.The proof first establishes the martingale identities on countable determining classes and extends them by approximation.Source: §A.2 · pp. 32–33

A.3 The terminal constraint

• Combining the terminal constraint with (79) and the Brownian identification proves Proposition 3.1.Source: §A.3 · p. 33

B Gaussian coupling for prescribed drifts

• The prescribed-drift coupling uses an invertible Gaussian steering map, matching discrete-time filtrations, and a conditional ℓ∞ coupling-error bound uniform in M and N.The construction is conditioned on an initial sigma-field when started after an initial block.Source: B Gaussian coupling for prescribed… · p. 34

• The constructed vectors Z1, . . . , ZN are independent N(0, IM/N) vectors.Their cumulative information through time k agrees with that in the Brownian mesh through time k.Source: §B.1 · p. 34
• At each mesh time k, adjoining Z1, . . . , Zk or the Brownian values Bt0, . . . , Btk to H0 generates the same sigma-field.Source: §B.1 · p. 34
• The result is restricted to controls based on Brownian mesh values; Brownian-bridge information inside intervals need not be reconstructible from the observed Gaussian inputs.Algorithm 1 uses only mesh values.Source: §B.1 · p. 34

B.2 The one-step coupling error

• Lemma B.2 gives a p-dependent conditional moment bound for the one-step coupling error for every p > 2.Source: §B.2 · p. 35

B.3 The conditional ℓ∞estimate

• The conditional ℓ∞ estimate uses martingale differences and the conditional Marcinkiewicz–Zygmund inequality to complete the proof of Proposition 4.6.Source: §B.3 · pp. 36–37

C Föllmer drifts and Euler discretization

• The appendix constructs the final-block feedback and proves Lemma 4.5’s confinement estimate, while also supplying the Föllmer drift for Proposition 5.14.The general drift statement is broader than Algorithm 1’s specialization.Source: C Föllmer drifts and Euler… · p. 37

C.1 Föllmer drift for a compactly supported terminal law

• For a compactly supported terminal density, the Föllmer construction yields a process whose endpoint has law f dγh and whose drift is adapted to the Brownian filtration.Source: §C.1 · p. 37

C.2 A shrinking-support terminal law

• For sufficiently small h, Lemma C.2 constructs an even, log-concave, compactly supported piecewise-polynomial density and a Föllmer drift with support radius rh tending to zero.Source: §C.2 · p. 39

C.3 Derivative bounds for the feedback

• Log-concavity gives a nondecreasing, 1-Lipschitz Euler map when h − t ≥ 1/N.Source: §C.3 · p. 41

C.4 Euler discretization

• The Euler discretization estimates complete the proof of the confinement estimate in Lemma 4.5.Source: §C.4 · pp. 42, 44

• The implementation handles switching-threshold ambiguity using Gaussian anti-concentration and evaluates final-stage feedback to inverse-polynomial accuracy with polynomially many bits.Source: D Finite-precision implementation · p. 44
• For fixed κ and α < αon(κ), the algorithm has a dyadic implementation with polynomially many bit operations that satisfies the stated terminal-margin guarantee.The input model accesses each exact Gaussian coordinate through an oracle returning dyadic approximations.Source: D Finite-precision implementation · p. 44

D.1 Numerical implementation

• The numerical implementation rounds stored states and feedback evaluations, guards small control norms, and uses interval computations to resolve the signing-rule branch.Source: §D.1 · p. 45

D.2 Polynomial bounds on the numerical state

• On AN, the exact and stored states and unprojected controls are bounded by N4, while the accumulated Brownian state is O(N2) in ℓ∞.Source: §D.2 · p. 46

D.3 Threshold comparisons and rounding stability

• On AN, required final-stage feedback values can be evaluated to absolute error εN with polynomially many bits and bit operations.Threshold ambiguity has conditional probability O(εN) per step, so a union bound over N arrivals controls the chance of any ambiguity.Source: §D.2 · p. 46, §D.3 · p. 47

D.4 Proof of the finite-precision theorem

• On the analyzed event, each numerical update is coupled to the exact Gaussian signing map using its actual dyadic control vector.The remaining difference from the exact analysis is the quantified deterministic numerical error.Source: §D.4 · p. 49
• Strict gaps absorb the numerical perturbation; with high probability, the guarded projection is inactive and the Brownian comparison and final-stage estimates remain valid.The lower norm cutoff changes accumulated predictable drift by at most O(τ_N).Source: §D.4 · p. 49
• With probability tending to one, the numerical signs meet the target margin κ because the exact terminal margin r exceeds κ by a fixed gap.The stored normalized margin's error is eventually smaller than (r − κ)/2.Source: §D.4 · p. 49
• A fixed polynomial budget bounds bit complexity on every input, while the capped implementation agrees with the analyzed execution with probability 1 − o(1).There are O(MN) scalar updates and feedback evaluations; the cap is not reached on the high-probability event.Source: §D.4 · p. 50

E Computer-assisted verification at zero margin

• The upper- and lower-bound verifiers are logically independent, and their fixed certificate data—not the search that found them—form the trusted computational argument.The proof combines the verifiers' soundness statements with acceptance of the supplied certificates.Source: E Computer-assisted verification at… · p. 50

E.1 Verification of the zero-margin upper bound

• Exact Bernstein-form checks with rational subdivision certify the spline inequalities over each full interval, rather than only at sampled points.The verifier also reduces tail signs to rational polynomial estimates over the half-lines.Source: §E.1 · p. 51
• The integral checks use rational lower bounds on a partition, avoiding floating-point quadrature.The verifier bounds the transformed integral by summing certified lower bounds across the partition.Source: §E.1 · p. 52
• Acceptance of the upper-bound certificate verifies every assertion of Lemma 5.7, from which Proposition 5.8 yields the upper-bound conclusion.The certificate uses a rational piecewise-polynomial spline with matching values and first derivatives at interfaces.Source: §E.1 · pp. 50, 52

E.2 Verification of the zero-margin lower bound

• The lower-bound verifier extends grid-node bounds between nodes before heat convolution, using global piecewise-affine bounds and upward-rounded nonnegative convolution contributions.Directed rounding preserves the upper-bound direction throughout the induction.Source: §E.2 · pp. 52, 54
• Acceptance of the lower-bound certificate gives stagewise upper bounds for the recursion and, with Lemma 5.1 and Theorem 5.3, proves the claimed lower bound for E*(0).The certificate includes rational interval lengths and increasing rational weights; the optimization that found them is not part of the proof.Source: §E.2 · pp. 52, 54

E.3 Artifact and reproducibility

• A single available script runs both verifiers; acceptance, together with Propositions E.1 and E.3, establishes the two bounds in (3).Source: §E.3 · p. 55