Research map / Optimization / Implicit bias and generalization
Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time
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 the Gaussian (randomly sampled hyperplane arrangement) convex relaxation of regularized two-layer ReLU training is within an O(√log n) factor of the original non-convex optimum for random data, yielding a polynomial-time approximation algorithm and guarantees for local gradient methods.
Problem
Training two-layer ReLU networks with weight decay is NP-hard, and the optimality gap between the randomized convex relaxation (Gaussian sampling of hyperplane arrangement patterns) and the original non-convex problem was unknown.
Approach
Under i.i.d. Gaussian data with n/d constant, bounds the relative optimality gap of the Gaussian-sampled convex relaxation by O(√log n) via a duality analysis for unconstrained group-l1 problems plus a Gordon-comparison bound on cone sharpness; combined with a coupling lemma, this extends to local gradient methods converging to stationary points with low loss.
Key results
- Gaussian relaxation with O(max{m*, log n}) sampled patterns satisfies p* <= p~* <= C sqrt(log 2n) p* with high probability for random data.
- Cone sharpness bounded by 2 + 200c sqrt(c log 2n), giving O(sqrt(log n)) relative gap.
- Local gradient methods converge to stationary points with loss within C sqrt(log 2n) of the global optimum under assumptions (A1), (A2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the full set of hyperplane arrangement patterns with randomly sampled patterns | Two-layer ReLU network convex reformulation · Gaussian random training data (A1) | relative optimality approximation factor: C\sqrt{\log 2n} | Helped |
| Solve the randomly relaxed convex problem using the polynomial-time algorithm | Two-layer ReLU network with weight decay · Gaussian random training data (A1) | relative optimality bound: O(\sqrt{\log n}) | Helped |
| Use random initialization with a local gradient method under (A1) and (A2) | Two-layer ReLU network with weight decay · Gaussian random training data (A1) | relative training loss: C\sqrt{\log 2n} | Helped |
| Use group l1 regularization rather than l2 regularization in the unconstrained relaxation | Unconstrained Gaussian relaxation · Gaussian random training data (A1) | relative optimality approximation factor: \frac{\sqrt{2\kappa}}{G} | Helped |
Limitations
- Guarantees hold only under i.i.d. Gaussian data assumption (A1) with n/d constant and large d.
- Relative gap is logarithmic rather than constant; authors list removing the log factor as open.
- Assumption (A2) on hyperplane pattern stability is only verified empirically for gradient descent.
Experimental setup
Datasets: synthetic i.i.d. Gaussian data MNIST
Metrics: relative optimality gap optimal value ratio
Baselines: exact convex reformulation (Pilanci & Ergen 2020) Gaussian relaxation (Ergen & Pilanci) l2-regularized convex approximation
Builds on: convex reformulation of ReLU networks Gaussian relaxation of hyperplane arrangements Gordon's comparison matrix Chernoff
Closest papers by meaning
- Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions (ICML 2022 · similarity 0.93)
- Convex Formulations for Training Two-Layer ReLU Neural Networks (ICLR 2025 · 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.90)
- Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.89)
- ReLU Network with Width $d+\mathcal{O}(1)$ Can Achieve Optimal Approximation Rate (ICML 2024 · similarity 0.89)
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.