Research map / Optimization / Implicit bias and generalization
Learning High-Degree Parities: The Crucial Role of the Initialization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that GD/SGD on two-layer ReLU nets learns the full parity with Rademacher initialization (up to sigma=O(1/d) perturbation), while Gaussian or large-sigma perturbed initialization provably fails, via a new loss-dependent initial gradient alignment measure.
Problem
Whether gradient descent on standard neural networks can learn high-degree (almost-full and full) parities, which remained unsettled, and how the weight initialization affects learnability.
Approach
Learnability of full parity by noisy GD depends on the initial weight distribution: Rademacher init yields linearly separable hidden embeddings enabling learning, while Gaussian or large-sigma perturbed init is blocked by a small initial gradient alignment (GAL), a new loss-dependent measure of initialization-target alignment.</120>
Key results
- Rademacher-initialized two-layer ReLU network with n=poly(d) neurons learns the full parity with perfect accuracy in one GD step (correlation loss) or poly(d) SGD steps.
- With Gaussian initialization, noisy GD on two-layer ReLU nets fails: accuracy at most 1/2 + exp(-Omega(d)) for any polynomial/subexponential parameters.
- For sigma-perturbed Rademacher, the positive result holds up to sigma=O(d^{-1}) for hinge loss, and the negative result holds for large constant sigma; experiments show accuracy decreases as sigma grows (learning at sigma in {0.1,0.2} for d=50).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace Rademacher initialization with Gaussian initialization (ablation) | Two-layer fully connected ReLU network trained with noisy-GD and correlation loss · Full parity, uniform inputs | accuracy: perfect accuracy -> ≤ 1/2+exp(-Ω(d)) | Hurt |
| Add Gaussian perturbation with σ=O(d^{-1}) to Rademacher initialization (ablation) | Two-layer fully connected ReLU network trained with GD or SGD · Full parity, uniform inputs | accuracy: perfect accuracy -> perfect accuracy | No clear effect |
| Add a sufficiently large constant Gaussian perturbation to Rademacher initialization (ablation) | Two-layer fully connected ReLU network trained with noisy-GD and correlation loss · Full parity, uniform inputs | accuracy: perfect accuracy -> ≤ 1/2+exp(-Ω(d)) | Hurt |
| Use Gaussian initialization instead of Rademacher initialization (ablation) | Two-layer fully connected ReLU network trained with noisy-GD and correlation loss · Almost-full parity, k≥d/2, uniform inputs | accuracy: ≤ 1/2+exp(-Ω(d)) | Hurt |
| Use clipped ReLU instead of ReLU (ablation) | Two-layer network with Rademacher initialization · Full parity, uniform inputs | hidden neurons sufficient for strong learning in one GD step: Ω(d^4) -> Ω(d^2) | Helped |
| Use a mixture of continuous uniform perturbations with σ=0.1 (ablation) | Four-layer MLP trained with SGD and hinge loss · Full parity, d=50 | test accuracy | No clear effect |
| Increase continuous-uniform perturbation magnitude (ablation) | Four-layer MLP trained with SGD and hinge loss · Full parity, d=50 | test accuracy | Hurt |
| Sparsify the Rademacher initialization by setting a fraction of weights to zero (ablation) | Four-layer MLP trained with SGD and hinge loss · Full parity | test accuracy | Hurt |
| Use symmetric discrete weights from {-2, -1, 1, 2} instead of Rademacher weights (ablation) | Four-layer MLP trained with SGD and hinge loss · Full parity | test accuracy | Hurt |
| Train a one-neuron ReLU network on random labels for a few steps | Gradient alignment under hinge loss · Full parity | gradient alignment | No clear effect |
Surprising findings
- Sparsifying the Rademacher initialization does not help learning the full parity, unlike the sparse-initialization benefit seen for k-parities.
- Discrete initializations other than Rademacher (e.g., uniform on {-2,-1,1,2}, sparsified Rademacher) fail to enable learning, suggesting Rademacher is a special case.
Limitations
- Negative result for perturbed Rademacher is proven only for large constant sigma; the threshold between O(1/d) and constant sigma is left open.
- Negative result for hinge loss and deeper networks is not proven; only correlation loss is covered theoretically.
- Empirical gradient alignment results cover only one-neuron networks and small input dimensions up to d=40.
Experimental setup
Datasets: uniform Boolean inputs on {±1}^d (synthetic parity data)
Benchmarks: full parity learning (synthetic, d=50 and up to d=40 for gradient alignment)
Metrics: test accuracy gradient alignment GAL
Baselines: Gaussian initialization sigma-perturbed Rademacher initialization sparsified Rademacher initialization symmetric discrete initialization
Builds on: LGA (label-gradient-alignment) Rademacher initialization analysis for almost-full parities cross-predictability INAL
Closest papers by meaning
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.87)
- Algorithm Development in Neural Networks: Insights from the Streaming Parity Task (ICML 2025 · similarity 0.87)
- Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.86)
- Deep linear networks for regression are implicitly regularized towards flat minima (NeurIPS 2024 · similarity 0.86)
- Feature emergence via margin maximization: case studies in algebraic tasks (ICLR 2024 · similarity 0.86)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.