Bounded-Time Logistic SGD Requires Gaussian ReLU Kernel Correlation

Abstract

Feldman, Kamath, and Srebro ask whether a class that Gaussian-initialized logistic SGD on a ReLU network learns under every input distribution must have dimension complexity at most proportional to the number of parameters times the number of steps. We study their two-layer bias-free process on {−1, 1}ⁿ, in which both layers are trained by exact single-example updates and the prediction is the sign of the tail sum of scores. Write B = ηmT for the effective time. For B ≤ 12 and width and step count large relative to n and B, we show that the expected error on a target h under a marginal D is at least 1/2 − Δ − 9B A_D(h), where A_D(h) is the label correlation of the Gaussian ReLU features under D and Δ is an explicit error term. Let θ = 1/2 − ε for an error level ε < 1/2. Once width and step count are also large relative to 1/θ, learning to error ε under every marginal therefore forces correlation at least θ/(18B) under every marginal. Convex separation turns this into a margin for every target in one fixed kernel, which bounds the VC dimension by O(B²/θ²) and gives an exact deterministic representation of dimension O((B/θ)⁴ n). The margin is restrictive: adjacent cube points are within 2/√n of each other in this kernel, so once n > (18B/θ)² only constant targets can be learned under every marginal, and the dimension bound has content only below that threshold. We also prove a parity lower bound and, in a separate small-step regime, an exact fixed-gate representation with a probabilistic-dimension bound. The proofs of the risk bound, the margin theorem, and the fixed-gate theorem are formalized in Lean 4, apart from the final random-projection step.