Volume Hypothesis or Algorithmic Bias: Margin can Separate Gradient Descent from Random Search

Over-parameterized neural networks often generalize despite having the capacity to overfit their training data. Two proposed explanations are the inductive bias of optimization algorithms and the volume hypothesis, which posits that most interpolating solutions, measured under a fixed prior, generalize well. We investigate these explanations jointly by comparing Guess-and-Check (G&C), which fits the data through rejection sampling, and stochastic gradient descent (SGD). We focus on favorable settings under the margin assumption, where generalizing interpolators indeed carry significant volume, and optimization algorithms can utilize the structure through their respective bias. For our investigation, we first provide a novel sample-dependent generalization bound for G&C. We then prove a sharp statistical separation between G&C and GD in a Gaussian model, and finally: We show empirically, on common datasets, that G&C generalizes by effectively searching a finite hypothesis class but achieves little margin, whereas SGD attains markedly larger input-space margins and better generalization. Our theory and experiments challenge the apparent equivalence of G&C and SGD: even when random sampling generalizes, optimization can exploit the landscape’s margin structure to generalize better.