Research map / Optimization / Implicit bias and generalization
Convex Formulations for Training Two-Layer ReLU Neural Networks
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.
Reformulates training of wide and infinite-width two-layer ReLU networks as a convex completely positive program, then relaxes it to an SDP (doubly non-negative) solved with CVXPY plus a TOS rounding heuristic.
Problem
Training two-layer ReLU networks is non-convex and NP-hard; prior convex formulations for ReLU training rely on sign-pattern enumeration or special data assumptions, and exact copositive/completely positive formulations are intractable.
Approach
Lifts the ReLU training problem via positive/negative decomposition of pre-activations into a PSD matrix variable with a completely positive constraint whose size is independent of width (finite critical width bounded by max{p, 2n^2+n-1}); relaxes the CP cone to the doubly non-negative cone to obtain a polynomial-time SDP, then rounds with three-operator splitting.
Key results
- On synthetic Random and Spiral datasets, the SDP-NN approximation ratio was 89.93% (gamma=0.1) and 76.90% or higher (gamma=0.01) relative to SGD with 300 neurons.
- On real datasets, SDP-NN test accuracy is competitive on Iris (0.987) and Ionosphere (0.920 at gamma=0.1) but drops on MNIST (0.794 vs NTK 0.863) and Bank Notes at gamma=0.01 (0.767).
- The SDP relaxation with rounding is run with rank R=300 (below the theoretical critical width), and runtime grows to over 100,000 seconds on Bank Notes and MNIST.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a first-layer bias term (ablation) | SDP-NN · Iris test (γ = 0.01) | weighted average F1 score: 0.987 -> 1.000 | Helped |
| add a first-layer bias term (ablation) | SDP-NN · Iris test (γ = 0.1) | weighted average F1 score: 0.987 -> 0.946 | Hurt |
| add a first-layer bias term (ablation) | SDP-NN · Ionosphere test (γ = 0.1) | weighted average F1 score: 0.924 -> 0.912 | Hurt |
| add a first-layer bias term (ablation) | SDP-NN · Pima Indians test (γ = 0.01) | weighted average F1 score: 0.703 -> 0.744 | Helped |
| add a first-layer bias term (ablation) | SDP-NN · Bank Notes test (γ = 0.1) | weighted average F1 score: 0.930 -> 0.991 | Helped |
| add a first-layer bias term (ablation) | SDP-NN · MNIST test (γ = 0.01) | weighted average F1 score: 0.849 -> 0.838 | Hurt |
Surprising findings
- Approximation ratio is a lower bound because SGD (300 neurons) is itself non-global, and the SDP loss is a relaxation lower bound, so it is not directly a performance comparison.
- SDP-NN-bias improves test accuracy on Pima Indians and Ionosphere relative to SDP-NN without bias, yet SDP-NN is worse than NTK and NNGP on MNIST.
Limitations
- Problem size scales quadratically with the number of data points, limiting scalability to real datasets.
- Rounding via three-operator splitting has no known convergence guarantees in this setting; the rounding rank 300 is below the theoretical critical width.
- Experiments use small datasets (up to 1000 samples, PCA-reduced MNIST) and the SDP relaxation is not tight by construction, with the approximation ratio only a lower bound.
Experimental setup
Datasets: Random (synthetic) Spiral (synthetic) Iris Ionosphere Pima Indians Diabetes Bank Notes Authentication MNIST (PCA-reduced to 20 features)
Benchmarks: Random Spiral Iris Ionosphere Pima Indians Diabetes Bank Notes Authentication MNIST (PCA-20)
Metrics: SGD training loss approximation ratio runtime (sec) weighted average F1 score test accuracy
Baselines: SGD NNGP NTK SGD with 5/10/100/200/300 hidden neurons
Builds on: Sum-of-squares hierarchy Burer-Monteiro factorization NNGP Neural Tangent Kernel
Closest papers by meaning
- The Hidden Convex Optimization Landscape of Regularized Two-Layer ReLU Networks: an Exact Characterization of Optimal Solutions (ICLR 2022 · similarity 0.92)
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time (ICML 2024 · similarity 0.92)
- Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions (ICML 2022 · similarity 0.92)
- Expressivity of ReLU-Networks under Convex Relaxations (ICLR 2024 · similarity 0.90)
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.88)
- Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.88)
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.