A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics

1 Introduction

• For general initializations with both layers updated, gradient descent reaches a global minimum exponentially fast regardless of label quality.The resulting network functions remain uniformly close to those of an associated kernel method.Source: §1 · p. 2
• For RKHS target functions, early stopping can make generalization error small, with sharp empirical- and population-risk estimates beyond the over-parametrized setting.The paper contrasts these results with earlier bounds for online SGD [10], classification [20], offline SGD [8], and GD [1].Source: §1 · p. 2, §1.1 · p. 2
• Over-parametrized networks can fit random labels, but generalization requires target functions in the appropriate RKHS, making their behavior resemble kernel methods.The paper also establishes uniform closeness to an associated kernel method whose kernel is defined by initialization.Source: §1 · p. 2

1.1 Related work

• The paper's optimization result removes the input-data non-degeneracy assumption by using target-function smoothness and significantly relaxes the required network width.Earlier results established global-minimum convergence for sufficiently over-parametrized two-layer networks [12].Source: §1.1 · p. 2
• Earlier data-dependent-norm bounds [4] were not strong enough to rule out curse-of-dimensionality behavior, which the paper's results suggest occurs in that setting.Source: §1.1 · p. 2
• The paper proves a non-asymptotic neural-tangent-kernel approximation for two-layer networks under weaker conditions than the earlier heuristic for infinitely wide networks [14].Source: §1.1 · p. 3

2.1 Problem setup

• The paper studies regression from i.i.d. samples drawn from a fixed distribution, assuming unit-norm inputs and labels bounded in magnitude by one.Source: §2.1 · p. 3
• The two-layer network uses ReLU activation, while the bias is omitted for notational simplicity and can be incorporated by augmenting the input.Source: §2.1 · p. 3
• The setup distinguishes population risk, the ultimate objective, from empirical risk, the quantity available from the training data.Source: §2.1 · p. 3
• The analysis uses continuous gradient-descent dynamics, with parameters updated by the gradient of empirical risk and a learning rate.Source: §2.1 · p. 3

2.2 Assumption on the input data

• The input-data assumption requires both defined kernel matrices to have positive smallest eigenvalues.Source: §2.2 · p. 4

2.3 The random feature model

• The random-feature reference model fixes its input-layer weights at the neural network's initial values, leaving linear dynamics for comparison.Source: §2.3 · p. 4

3.1 Properties of the initialization

• At initialization, the Gram matrices approach limiting kernels as network width m grows.The passage states G(a)(Θ0) → K(a) and G(b)(Θ0) → β²K(b).Source: §3.1 · p. 5

3.2 Gradient descent near the initialization

• A high-probability bound applies to gradient descent only through the exit time t0 from the initialization neighborhood.The bound is stated for t ∈ [0,t0], with t0 defined as the exit time of that neighborhood.Source: §3.2 · pp. 5–6

3.3 Global convergence for arbitrary labels

• The result of Du et al. [12] is extended to update both layers and to avoid a specific initialization-scale requirement.The cited result established exponential convergence to global minima; this analysis allows both layers to be updated and does not require β ∼ 1/√m.Source: §3.3 · p. 10

3.4 Characterization of the whole GD trajectory

• For highly over-parameterized networks, the gradient-descent solution stays uniformly close to the random-feature solution throughout the trajectory.Theorem 3.3 assumes β ≤ 1; the cited remark notes that the bound vanishes with width when β = o(m^-1/6).Source: §3.4 · p. 10

3.5 Curse of dimensionality of the implicit regularization

• For sufficiently small β, the curse of dimensionality also holds for network gradient-descent solutions at every time, so early stopping cannot remove it.The passage gives β = o(m^-1/6) as an example condition.Source: §3.5 · p. 14
• The comparison between bounds (40) and (41) quantifies how random-feature models fall short of explaining neural-network generalization behavior..Source: §3.5 · p. 14

4 Analysis of the general case

• The analysis relaxes the width requirement and assumes the target function admits an integral representation.It develops approximation and random-feature generalization bounds under this setting.Source: §4 · pp. 15–16

4.1 Optimization results

• The optimization analysis bounds gradient descent's empirical risk and parameter changes under stated width and target-function conditions.The paper also notes that empirical risk is non-increasing along the dynamics.Source: §4.1 · pp. 16, 20

4.2 Generalization results

• A population-error upper bound supports early stopping to reach optimal error without requiring over-parameterization.For target functions in the specified RKHS, the results apply with high probability in a mildly over-parameterized regime and over a short time.Source: §4.2 · pp. 20–21
• Corollary 4.4 studies how width, sample size, and stopping time balance to achieve best rates for population risk.It considers widths of the form m = n^p.Source: §4.2 · p. 21

5.1 Fitting random labels

• Gradient descent converges exponentially fast for every tested initialization on randomly labeled data, including β = m.The experiment uses n = 50, d = 50, and m = 10,000.Source: §5.1 · pp. 22–23, Figure 1 · p. 23

5.2 Learning the one-neuron function

• At m = 4, the random-feature model does not converge, while the neural network converges and generalizes; at m = 1000, their behavior is almost the same.At m = 50, both converge, with faster convergence and slightly better test accuracy for the neural network.Source: §5.2 · p. 23, Figure 2 · p. 24
• At very large widths, the unregularized neural network has poor test error relative to the small-width setting, and implicit regularization fails.The comparison is against the regularized model with λ = 0.01.Source: §5.2 · p. 24, Figure 3 · p. 24
• The one-neuron results illustrate the stated curse of dimensionality for gradient-descent learning of Barron-space functions.The target depends on one direction, whereas uniformly sampled features are nearly orthogonal to that direction in high dimension.Source: §5.2 · p. 24

6 Conclusion

• Regularized models with a suitably crafted penalty have optimal generalization error estimates for all Barron-space targets.The estimates are comparable to Monte Carlo rates [13].Source: §6 · p. 25
• Dimension-independent generalization requires the target function to lie in the RKHS defined by initialization; without knowing that kernel, the paper expects a curse of dimensionality for general Barron-space targets.The paper contrasts this requirement with optimal generalization estimates for suitably regularized models on the Barron space [13].Source: §6 · p. 25
• For general network widths, early stopping is needed for good generalization bounds, while some scaling regimes may still let gradient descent outperform the related kernel method.The analysis does not rule out that possibility.Source: §6 · p. 25
• The analysis covers only a particular initialization distribution π0 and the special input domain S^{d−1}.The authors say extensions are possible, but characterize their main message as negative: without explicit regularization, generalization is likely no better than for the kernel method.Source: §6 · p. 25
• The analysis relies on the b parameters evolving more slowly than the a parameters because β is small, effectively freezing b during gradient descent.Adding an explicit scaling factor for β could remove this time-scale separation; the effect on implicit regularization in that setting has no results yet.Source: §6 · p. 25

A Proof of Lemma 6

• The proof considers B̃0 differing from B0 at only one b0.The passage does not give further context for this comparison.Source: A Proof of Lemma 6 · p. 28
• McDiarmid’s inequality is then used to obtain a probability bound for any δ > 0.The stated probability is at least 1 − δ.Source: A Proof of Lemma 6 · p. 28
• Assumption 2 supplies the bound ∥a*∥ ≤ γ√m..Source: A Proof of Lemma 6 · p. 28

B Proof of Lemma 7

• For FQ, the class of functions f(·; a, B0) with ∥a∥ ≤ Q, the proof sets up a Rademacher-complexity bound.Source: B Proof of Lemma 7 · p. 28
• For HQ, the class of squared errors (f(·; a, B0) − f*)², the proof uses |f(x; a, B0)| ≤ √mQ, given |f*(x)| ≤ 1.It then bounds the class’s Rademacher complexity.Source: B Proof of Lemma 7 · p. 28
• Because the squared-error functions are Lipschitz with constant bounded by 2√mQ + 1, the proof obtains a high-probability bound.The stated probability exceeds 1 − δ.Source: B Proof of Lemma 7 · p. 29
• Dyadic choices Qk = 2^k and δk = 2^−|k|δ extend the bound to every Qk, and each a can be covered by a choice with Qk ≤ 2∥a∥.Source: B Proof of Lemma 7 · p. 29

C Proof of Lemma 1

• The proof defines h(a, b) = aσ(bᵀx) for ∥x∥ ≤ 1 and applies a standard Rademacher-complexity bound.It cites Theorem 26.5 of.Source: C Proof of Lemma 1 · p. 29
• Since φk(·) = akσ(·) is β-Lipschitz, the proof applies the contraction property of Rademacher complexity.It cites Lemma 26.9 of.Source: C Proof of Lemma 1 · p. 29
• The resulting bound holds for any ∥x∥ = 1 with probability 1 − δ.The proof also invokes Lemma 26.10 of.Source: C Proof of Lemma 1 · p. 29

• The proof invokes Hoeffding’s inequality.Source: D Proof of Lemma 2 · p. 30
• The proof also invokes Weyl’s Theorem.Source: D Proof of Lemma 2 · p. 30