What Gradient Descent Can See

The Boolean queries computed by DLOGTIME-uniform, polynomial-size, bounded-depth threshold networks are definable in first-order logic with majority quantifiers, the logic of uniform constant-depth threshold circuits. Expressibility is not learnability: polynomial-tolerance correlational queries cannot efficiently learn some targets that these networks represent, with sparse parity the standard witness. We show that this gap is itself logical. We introduce the correlationally visible fragment of that logic, in which a step may introduce new coordinates only when they carry a correlation with the residual of the target given what is already present. In the correlational statistical query model, this fragment is exactly the class learnable to any inverse-polynomial error in polynomial time, for definable targets of logarithmic arity, inverse-polynomial Fourier coefficients, and definable relevant sets. The lower half of the characterization is a leap lower bound proved in the model itself, with absolute constants, for arbitrary Boolean shapes of logarithmic arity. The arity bound cannot be dropped: we exhibit a sparse query with no small coefficient that introduces one coordinate per step, lies in the fragment, and is not learnable. The separation from the full logic is unconditional, witnessed by parity.