Where Does Gradient Descent's Generalization Live? Separating Pattern Search from Convex Fitting in ReLU Networks

A two-layer ReLU network does two things during training. It decides which neurons switch on for which inputs, and it fits linear weights given those on/off choices. The second job alone is a convex problem: if the on/off choices (the "activation patterns") are held fixed, the training objective has no bad local minima and can be solved to global optimality. Kim and Pilanci showed that solving this convex problem over a random sample of patterns comes within a factor $O(\sqrt{\log n})$ of the true non-convex global optimum. They also observed that gradient descent barely changes its patterns after initialization (Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time). Their work bounds only training loss. This proposal uses the same split to study generalization. If gradient descent is mostly solving a convex program over nearly frozen patterns, then its test error should match that convex program's test error. That convex program's test error can be bounded independently of width. Any test-error advantage of the real network over the convex model must then come from the non-convex part: the movement of the patterns.

The result is an experimental and theoretical tool for both open problems in this file. On the optimization side, it asks whether the global convergence that theory guarantees is the same thing that practical training achieves. On the generalization side, it asks whether the global minimum of the fixed-pattern problem generalizes as well as what gradient descent actually finds. It may generalize better or worse, even when gradient descent ends at a higher training objective.

Core Claim

We claim that the test error of a trained two-layer ReLU network splits into two parts. The first is a convex-fit part, equal to the test error of the globally optimal model over the network's initial activation patterns. The second is a pattern-search part, equal to the further change obtained by re-solving that convex problem with the network's final patterns. We expect three results. The convex-fit part obeys a width-free bound. The pattern-search part is nearly zero exactly when patterns drift little, which is the regime where convergence proofs that keep the network close to its initialization apply. The pattern-search part is large on data where adaptive features are known to matter.

The convex model is the gated ReLU relaxation. Given a set of $P$ gate vectors $g_1,\dots,g_P$ and inputs $x$, it predicts

$$\hat y(x)=\sum_{i=1}^{P}\mathbb{1}[g_i^\top x\ge 0]\,w_i^\top x,\qquad \min_{w}\ \frac1n\sum_{j=1}^n \ell(\hat y(x_j),y_j)+\beta\sum_{i=1}^P\|w_i\|_2 .$$

Here $w_i$ is the weight vector attached to gate $i$, $\ell$ is the loss, and $\beta$ sets the strength of a group-norm penalty. This penalty is the convex counterpart of weight decay on the two-layer network. The function class with $\sum_i\|w_i\|\le B$ is the convex hull of single-gate linear units. For gates chosen independently of the training data, its Rademacher complexity is therefore at most roughly $BR\sqrt{\log P/n}$, where $R$ bounds $\|x\|$. The $\sqrt{\log P}$ factor comes from taking a maximum over $P$ fixed gates. The bound does not depend on width and grows only logarithmically in the number of patterns. When the gates are instead taken from a trained network, they depend on the data. In that case the bound holds only with sample splitting, and this gap is precisely what the pattern-search part measures.

Relation to Prior Work

Several papers motivate the question by showing that global convergence proofs say nothing about test error. Gradient Descent Finds Global Minima of Deep Neural Networks proves linear convergence to zero loss even on random labels. Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology and the piecewise-affine analysis in Convergence rates for gradient descent in the training of overparameterized artificial neural networks with piecewise affine activation explicitly leave generalization to future work. We do not add another convergence proof. Instead, we use a convex object that is provably globally solvable and ask how much of gradient descent's test behaviour it accounts for.

The method comes from Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time, which supplies the relaxation, the pattern sampling, and the coupling observation. That paper studies only the training optimality gap, under Gaussian inputs. We add a generalization bound, move to non-Gaussian data, and turn the coupling observation into a quantity we can measure and that predicts test error.

Two lines of work constrain the design. Disentangling Trainability and Generalization in Deep Neural Networks shows, in the infinite-width linearized regime, that perfect conditioning can coexist with generalization collapse. Easy optimization of a fixed-feature model is therefore no guarantee of good test error, so our convex-fit part could be poor on some inputs. Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks proves that kernel and linearized models are suboptimal for functions with uneven smoothness, while weight-decayed networks are minimax optimal. That result is a property of the global minimizer and says nothing about the training path. Our pattern-search part is the place where that advantage should appear if gradient descent actually realizes it.

Benign Underfitting of Stochastic Gradient Descent shows, in a convex setting, that good test error need not require reaching the training optimum. Our setting gives a non-convex test of that idea. Gradient descent and the convex program optimize closely related objectives, and the convex program reaches the global optimum. We can therefore check directly whether gradient descent's higher objective comes with equal or better test error.

Research Program

The theory component states and proves the bound above for the gated relaxation with data-independent gates, including the Gaussian-sampled gates of Kim and Pilanci. It then extends the bound to data-dependent gates through sample splitting: gates are learned on one half of the data and weights are fit on the other. Combining this with the existing $O(\sqrt{\log n})$ training-optimality result gives a statement of the form "near-global training optimality plus width-free generalization" for a polynomial-time learner. As far as the file shows, no such statement exists for any ReLU model.

The measurement component trains two-layer ReLU networks with gradient descent and stochastic gradient descent at practical widths, with and without weight decay. At checkpoints we record three quantities:

  1. Pattern drift, defined as the fraction of (neuron, training-input) pairs whose on/off state has flipped since initialization.
  2. The test error of the convex program re-solved to global optimality at the current patterns.
  3. The network's own test error and training objective.

The three re-solves that define the decomposition use the same group-norm $\beta$ as the network's weight decay:

  • Initial patterns: the convex-fit reference.
  • Final patterns: the pattern-search reference.
  • Random Gaussian patterns, matched in number: the Kim–Pilanci reference.

Baselines

The naive reference point is the trained network itself, reported with its training loss and test error. It shows what we are trying to explain, and its training objective is compared against the convex optimum to check for benign suboptimality.

The strongest existing method on this question is the Gaussian-sampled convex relaxation of Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time. It is the only polynomial-time near-global solver in the file. We run it with the same pattern budget $P$ and the same $\beta$ grid as the network's weight-decay grid, select by the same validation split, and use matched wall-clock time. That paper reports an optimality-gap guarantee but no test accuracy; no reported result found on Lacuna for its test accuracy on any benchmark here. We count a learner as beating it if it reduces test error beyond seed variance, which we will measure, at equal $P$.

A linearized-network baseline fits kernel regression with the network's tangent kernel at initialization (Six Lectures on Linearized Neural Networks). It uses the same data and the same ridge tuning budget. It is the standard explanation the reviewer will offer, and it fixes more than our convex model does, since it freezes both the patterns and the first-layer weights.

For reference only, we include a flatness-seeking optimizer, K-SAM (K-SAM: Sharpness-Aware Minimization at the Speed of SGD), applied to the same two-layer network. That paper reports 97.45% CIFAR-10 accuracy for a WideResNet-28-10. This number sets the scale of what deep networks reach and is not comparable to two-layer models; no reported result found on Lacuna for two-layer ReLU networks on CIFAR-10.

The ablation that isolates the key ingredient compares three re-solves: initial patterns, final patterns, and random patterns. Weights, $\beta$, and solver stay fixed, so the only thing that varies is which patterns are used.

Why not just…?

Why not just use the tangent-kernel (linearized) model as the explanation? In our setting this is a real threat. If kernel regression at initialization already matches the network's test error wherever pattern drift is small, then the convex surrogate adds only a different bound, not a better explanation. Two pieces of evidence argue against it. Disentangling Trainability and Generalization in Deep Neural Networks shows that linearized models can collapse at test time. Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks proves them suboptimal on uneven-smoothness targets. Our convex model differs in a concrete way: it learns a full weight vector per gate under a sparsity-inducing group norm, so it can select features from a fixed set of gates. The head-to-head experiment settles the question. We will report it even if the kernel ties.

Why not just measure distance from initialization or sharpness instead of pattern drift? Weight distance and top Hessian eigenvalue, as used by MoXCo: How I learned to stop exploring and love my local minima?, are cheaper or more familiar. Neither of them comes with a convex counterpart that can be solved to global optimality and bounded. We will still compute both and report how well each correlates with the pattern-search part across runs. If either predicts that part as well as drift does, we will say so. The re-solve decomposition would remain useful even then, because it is causal rather than correlational: it swaps the patterns while holding everything else fixed.

Why not just train longer, or with weight decay, and read off the test error? This tells us whether the network generalizes, but not why. It cannot separate the effect of selecting patterns from the effect of fitting weights. The decomposition can.

Proposed Experiments

We use four testbeds:

Every CIFAR-10 experiment is repeated with randomized labels. There the convex-fit bound should stay large and correctly predict failure, which gradient-descent convergence theory cannot do.

Three checks are decisive:

  1. The proposal fails if the final-pattern re-solve does not recover the network's test error to within seed variance. That would mean the split into "pattern search" and "convex fit" is not where generalization lives.
  2. The coupling-based story fails if the pattern-search part does not grow with measured drift across widths and learning rates.
  3. We test benign suboptimality by comparing gradient descent's final objective against the convex optimum computed on the same patterns. If gradient descent sits strictly above that optimum while matching or beating its test error, that is the first non-convex instance of the phenomenon Koren et al. proved only in convex settings.