acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning theory
Keywords:
volume hypothesis, implicit bias, margin, generalization

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_RbTJOpenReview ↗
Rating
4(+2)
Confidence
4
Informativeness
3(+1)
Presentation
3
Soundness
3(+2)
Read review
Paper summary

The paper studies the difference in generalization between SGD and guess & check (G&C), an algorithm where random interpolating solutions are chosen from a fixed prior. The goal is to use this analysis to better understand generalization in over-parameterized models. The paper first produces sample complexity results for both algorithms in a linear model setting. Then, the paper experimentally shows that the margin of SGD models is larger than G&C, and moreover SGD achieves better generalization.

Critical strengths
  1. The paper studies a very important problem, namely what is the source of good generalization in over-parameterized neural networks. The empirical approach of comparing SGD with G&C directly is promising as well and yields insights into the behavior of SGD.
Critical weaknesses
  1. l’m primarily concerned that “volume hypothesis” and “algorithmic bias” are not really two separate hypotheses, but they are significantly overlapping, and G&C is not experimentally set up in a way that helps meaningfully separate these hypotheses. Specifically, it’s not clear whether there exists a prior for G&C such that it’s solutions are the same (or nearly the same) as SGD. If so, then the results really compare two different priors for G&C and don’t really answer the question of whether algorithmic bias or volume hypothesis is more important for generalization. Put another way, perhaps the generalization benefits of SGD can be viewed as the volume hypothesis under a specific prior. Another way to state this is, how do we know that the prior chosen for G&C is the right one (maybe it wasn’t chosen to yield a fair comparison with SGD).
Questions for authors
  1. Does there exist a prior for G&C that matches the distribution of solutions for SGD?
Reviewer_p2eCOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether the abundance of generalizing interpolators can explain the performance of gradient based optimization by comparing Guess-and-Check (G&C) with gradient descent and SGD. It introduces a generalization bound based on the number of distinct prediction patterns encountered during random search and establishes a statistical separation in a Gaussian mixture model, where gradient descent achieves exponentially smaller error than G&C under the stated assumptions. Experiments on binary image classification tasks further show that SGD generally attains larger margins, while G&C performance closely correlates with the number of prediction patterns explored.

Critical strengths
  1. The paper offers a useful perspective on how solution volume and optimization bias can jointly contribute to generalization.
  2. The Gaussian analysis establishes a clear statistical separation, supported by matching bounds for G&C and a guarantee for gradient descent after finitely many iterations.
  3. Counting distinct prediction patterns provides a meaningful refinement of bounds based on interpolation probability, especially when the prior frequently produces similar predictors.
  4. The experiments examine accuracy, margins, and search behavior across several settings, with repeated runs and uncertainty estimates supporting the comparisons.
Critical weaknesses
  1. The Gaussian theory and neural network experiments use substantially different models and priors, leaving their connection somewhat indirect.
  2. The explicit bound involving N(S)N(S) remains vacuous at the experimental sample sizes, limiting its quantitative explanatory value.
  3. The comparisons retain only samples where G&C succeeds within its budget. Reporting success rates and results on excluded samples would clarify the resulting selection effect.
  4. The observed correlations support the proposed interpretation but do not establish distinct generalization mechanisms. Comparisons controlling for task difficulty would strengthen this claim.
Questions for authors

Please refer to weaknesses.

Reviewer_VV6LOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper shows a separation between the generalization performance in the overparametrized regime of Guess & Check (interpolating to 100% accuracy) and SGD/max-margin classifiers, both theoretically (in a mixture of Gaussians) and empirically (in several of the feasibly-small settings like MNIST).

Critical strengths

The use of N(S) to come up with a generalization bound seems interesting (and I think separate from Bayesian treatments already, e.g., Mingard et. al https://jmlr.org/papers/v22/20-676.html) The exposition in the appendix looks well done too, though I only skimmed it.

The experimental setup also seems solid, using LOO and noting the influence of learning rate on SGD's performance, adding to the story seen in Chieng and then contrasted in Peleg.

Critical weaknesses

The biggest issue to me is that the loss function may be a confounder. Guess & Check in Chiang et al. (2023) not only seeks interpolation, but restricts to parameter draws "with train loss below a certain threshold" (§3.2). Intuitively, that breathing room in parameter space might be some breathing room in data space, i.e., margin. Of course, restricting ourselves to the interior of a basin makes it much less likely to draw from G&C, but that's beside the point for talking about generalization gap. The volume hypothesis claim (vs. implicit bias of SGD) works just as well when the universe of points is those getting low-loss (since we achieve that with SGD too), rather than just interpolating. I don't think the theorems on the GMM are apples-to-apples in this way, as the SGD theorem just gives an iteration condition for the exponential separation?

§4 (except §4.10) does account for this mostly in the experiments, by having SGD stop as soon as it interpolates as well. As an aside, it'd probably be worth commenting on (maybe just in the appendix) the use of Kaiming initialization, since that was what Peleg & Hein pointed to as a spurious cause of the results in Chiang et al. (though some of their non-main results did use more standard initialization schemes).

I also am not sure the theoretical result has any bearing on the empirical results (of here, Chieng or Peleg), given it is closely tied to the guarantee of producing max-margin in this setting.

Questions for authors

Do the theorems readily accommodate defining interpolation using the cross-entropy loss rather than 0–1? What about the experiments (i.e., let both algorithms run until a solution is found with a certain loss)?

Is the role of learning rate more nuanced in this setting than just being a hyperparameter, like does a large learning rate create a bigger margin (since the trajectory will be deeper into the basin when it makes the interpolating step and is stopped)?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.