Source-linked AI summary
Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
Mert Pilanci, Tolga Ergen
TL;DR
Training finite-width two-layer ReLU networks is difficult because the objective is non-convex and globally optimizing it can require exponential combinatorial search. The paper develops exact finite-dimensional convex programs using duality and finite-support representations, showing equivalence with the neural-network optimum under a neuron-count condition. These results characterize ReLU networks through convex regularization while identifying scope boundaries related to non-uniqueness and the required support size.
Problem
Finite-width two-layer ReLU training is non-convex, and known global or approximate methods can have exponential complexity in the number of neurons.
Method
The paper uses semi-infinite duality, finite-support measure representations, and hyperplane-arrangement structure to construct exact finite-dimensional convex programs.
Results
The convex program and the non-convex two-layer ReLU problem have identical optimal values when m ≥ m*, and an optimal neural-network solution can be constructed from the convex solution.
Takeaways & Limitations
ReLU neural networks admit an equivalent convex-regularization characterization in a higher-dimensional space, with training expressible through polynomial-size convex optimization.
Takeaways & Limitations
The support threshold m* depends on an optimal measure representation, and convex-program solutions may be non-unique, for example under merging of positively colinear neurons.
Abstract
from arXiv · showhide
We develop exact representations of training two-layer neural networks with rectified linear units (ReLUs) in terms of a single convex program with number of variables polynomial in the number of training samples and the number of hidden neurons. Our theory utilizes semi-infinite duality and minimum norm regularization. We show that ReLU networks trained with standard weight decay are equivalent to block $\ell_1$ penalized convex models. Moreover, we show that certain standard convolutional linear networks are equivalent semi-definite programs which can be simplified to $\ell_1$ regularized linear models in a polynomial sized discrete Fourier feature space.
1. Introduction
The paper addresses the non-convexity and combinatorial complexity of training finite-width two-layer ReLU networks by developing exact finite-dimensional convex formulations. It contrasts this approach with infinite-width convexity and kernel-regime analyses.
- 1. Introduction: The paper introduces a finite-dimensional, polynomial-size convex program that globally solves two-layer ReLU training.The formulation targets scalar-output networks with squared loss and extends to broader settings described in the paper.
- 1. Introduction: Existing convexity arguments mainly concern infinite-width networks, requiring infinite-dimensional optimization, while adding neurons to finite models remains non-convex.The paper positions its finite-dimensional formulation as an exact alternative to these restrictions.
- 1.1. Related work and overview: Kernel-regime analyses show that randomly initialized gradient descent can fit training samples, but hidden neurons may barely move and learn useful features.The supplied passage also notes that kernel approximations do not fully explain the success of neural networks.
- 1. Introduction: The model uses ReLU activation φ(t) = max(t, 0), with hidden weights u_j and output weights α_j.The main setup considers two-layer ReLU networks with scalar output and squared loss, while noting extensions to other outputs, losses, and architectures.
- 1.1. Related work and overview: Training two-layer ReLU networks is highly non-convex because of nonlinear activations and products between hidden- and output-layer weights.Global optimization can require brute-force enumeration of piecewise-linear regions and output-layer sign patterns, producing exponential complexity in the number of neurons.
2. Convex Duality for Two-layer Networks
The paper converts the non-convex training problem into a measure-based convex formulation and derives its dual through semi-infinite optimization. Strong duality and finite-support arguments then connect the formulation to exact finite-dimensional neural-network representations and a Neural Gauge geometry.
- 2. Convex Duality for Two-layer Networks: The network objective is first represented using an ℓ1-penalized measure formulation, where finite neurons correspond to Dirac masses and total variation becomes an ℓ1 norm.This provides the bridge from finite-width networks to convex optimization over signed measures.
- 2. Convex Duality for Two-layer Networks: The resulting dual is a convex semi-infinite optimization problem with n variables and infinitely many constraints.Interchanging minimization and maximization yields a weak-duality lower bound before strong duality is established.
- 2. Convex Duality for Two-layer Networks: Strong duality holds when the number of hidden neurons satisfies m ≥ m*, where m* is bounded by n and can be smaller than n.The threshold m* is tied to the number of Dirac deltas in an optimal measure representation.
- 2. Convex Duality for Two-layer Networks: Carathéodory’s theorem guarantees an optimal bi-dual solution supported on at most m* ≤ n + 1 Dirac deltas.When m is sufficiently large, this finite-support representation matches the relevant optimal value through strong duality.
- 2.1. A geometric insight: Neural Gauge Function: As β approaches zero, the induced regularizer becomes the gauge of the convex hull of QX ∪ −QX, called the Neural Gauge.Its polar set is convex and appears as a constraint in the dual problem, enabling the finite-dimensional convex program.
3. An Exact Finite Dimensional Convex Program
The paper enumerates ReLU activation regions induced by the data and uses them to construct an exact finite-dimensional convex program. This program globally solves sufficiently wide two-layer ReLU training and has polynomial complexity in the sample size and width for fixed rank or dimension.
- Activation-pattern enumeration: The data induce P distinct ReLU activation patterns by partitioning the input space with hyperplanes through the origin.These patterns are represented by diagonal matrices D1, ..., DP, with P bounded for rank r ≤ n.
- Exact convex formulation: Theorem 1 establishes identical optimal values between the convex program (8) and the non-convex network problem when m ≥ m∗.An optimal network with m∗ neurons can be constructed from an optimal solution to the convex program.
- Computational complexity: The convex program uses 2dP variables and can be solved with standard interior-point methods.For fixed rank or dimension, its complexity is polynomial in n and m.
- Interpretation: The formulation represents ReLU networks as sparse mixtures of linear models with group ℓ1−ℓ2 regularization.This connects the neural-network training problem to structured sparsity and group Lasso methods.
- Approximation: Sampling diagonal activation matrices yields a reduced convex problem that the authors report often outperforming backpropagation.The sampling procedure is described as a type of coordinate descent applied to the full convex program.
4. Convolutional Neural Networks
The paper extends its convex approach to convolutional networks by reducing separable patch-based training to the fully connected formulation and expressing linear convolutional training through semidefinite programs. Under circular-padding assumptions, the SDP can be represented in a discrete Fourier feature space.
- Convolutional ReLU networks: The separable patch formulation does not exactly represent classical convolutional architectures because it is separable over patch indices.The network is described using patch matrices Xk and shared hidden-neuron structure across patches.
- Convolutional ReLU networks: The convex program solves the separable vector-regression convolutional problem exactly by reducing it to the fully connected case.The reduction concatenates the patch matrices and labels into a single fully connected instance.
- Linear convolutional networks: Linear convolutional network training admits an SDP formulation whose dual is a nuclear-norm-penalized convex optimization problem.The SDP arises from maximal-eigenvector characterizations of optimal filters.
- Linear convolutional networks: The nuclear norm is the ℓ1 norm of a matrix’s singular values in the resulting convex formulation.This identifies the regularizer used in the SDP dual.
- Linear circular convolutional networks: With sufficient zero padding and stride one, circulant convolution reduces the SDP using Fourier diagonalization.The circulant matrices are diagonalized by the DFT, with transformed data represented as X̃ = XF.
5. Proof of the Main Result (Theorem 1)
The proof converts the nonconvex two-layer ReLU training problem into a finite-dimensional convex optimization problem by enumerating hyperplane arrangements and applying duality. Strong duality and variable transformations establish equality between the convex program and the original objective.
- Hyperplane arrangements: The hyperplane-arrangement set is bounded, enabling a finite representation of all ReLU activation sign patterns.The proof uses the finite collection H_X and its equivalent positive-sign subsets to partition the parameter space.
- Finite-dimensional formulation: Enumerating all hyperplane arrangements converts the dual constraints into a finite-dimensional convex optimization problem with polynomially many variables and constraints.The arrangements are indexed as S_1,...,S_M, after which the dual is represented using variables v, α_i, β_i, and related cone constraints.
- Strong duality: Slater’s condition yields strong duality for the constructed second-order cone formulation when β > 0.The proof identifies a strictly feasible parameter choice with v = α_i = β_i = α′_i = 0.
- Exact equivalence: A change of variables produces a primal representation identical to convex program (8), so the two objectives have equal optimal values.The variables are transformed using w_i = λ_i r_i and w′_i = λ_i r′_i before matching the resulting objective to (8).
- Numerical illustration: The one-dimensional experiment’s Optimal solution is guaranteed by Theorem 1, whereas SGD can remain at local minima for small m.The figure compares ten SGD initialization trials with the proposed convex program.
6. Numerical Experiments
Experiments compare the exact convex formulation and approximations with SGD on synthetic datasets and CIFAR-10 subsets. The proposed and sampled convex approaches generally match or outperform SGD, while the CNN experiment finds convergence to the convex solution.
- One-dimensional data: The one-dimensional experiment evaluates ten SGD realizations against the convex program for m = 8, 15, and 50 using squared loss.The dataset has n = 5 and the regularized objective is plotted against iteration index.
- Two-dimensional data: Most SGD realizations converge to a slightly higher objective than Optimal, and Approximate can also outperform SGD on the two-dimensional dataset.Approximate uses a random subset of diagonal matrices, and the figure also displays the learned decision boundaries.
- CIFAR-10 ReLU networks: Alg1 achieves the lowest objective value and highest test accuracy among the CIFAR-10 ReLU-network methods.Alg1 samples sign patterns matching the SGD-optimized network, while Alg2 uses initialized patterns and Alg3 uses adaptive sampling.
- Linear CNN: All linear-CNN realizations converge to the objective value obtained by L1-Convex and find almost the same filters.The comparison uses five independent realizations on a CIFAR-10 subset.
7. Concluding Remarks
The paper presents neural-network training as an exact convex regularization problem over a higher-dimensional space partitioned by hyperplane arrangements. Its concluding perspective links ReLU expressiveness with parsimonious ℓ1−ℓ2 group regularization and identifies convexity and high-dimensional regularization as directions for further study.
- Main conclusion: The paper gives an exact polynomial-size convex representation of nonconvex neural-network objectives through a convex duality theory.The representation uses polynomially many variables and constraints.
- Regularization perspective: ReLU networks correspond to piecewise-linear models fitted with an ℓ1−ℓ2 group-norm regularizer over hyperplane-arrangement partitions.The paper characterizes this regularization as producing parsimonious fitted models.
- Future directions: The authors identify convexity and high-dimensional regularization theory as directions for understanding neural-network generalization.These are presented as open research directions rather than established consequences.
A.1. Additional numerical results
The additional experiments compare SGD with convex-program solutions and approximations across synthetic, regression, and convolutional classification tasks. Convex approaches achieve lower objectives in the challenging two-dimensional example, while the reported training-time comparison favors the introduced programs over GD.
- SGD trials became stuck at local minima and achieved significantly higher objective values than the Optimal and Approximate convex solutions.
- The experiments evaluate convex-program approximations and SGD on Boston Housing, Kinematics, Bank, and a CIFAR-10 subset using repeated initialization trials.
- Alg1 achieved a lower objective value and higher test accuracy than the other methods, including GD, on the CIFAR-10 subset.
- The reported training-time data show that the introduced convex programs outperform GD while requiring significantly less training time.
A.2. Constructing hyperplane arrangements in polynomial time
The construction enumerates distinct hyperplane arrangements to obtain a finite-dimensional convex representation, with complexity governed by the data rank and arrangement count. Duality arguments establish exact optimal-value equivalence and extend the framework to broader losses and architectures.
- Distinct sign patterns correspond to regions of hyperplanes through the origin, and the data dimension can be reduced from d to rank(X) without changing their count.
- An algorithm enumerates all hyperplane arrangements in O(n^r) time, enabling construction of the convex-program data.
- Strong duality is established through semi-infinite and finite-dimensional duality arguments, including Slater-type feasibility and discretization results.
- The convex program and the non-convex network problem have identical optimal values when the hidden-neuron count satisfies m ≥ m*, and an optimal network can be reconstructed.
- The framework extends to arbitrary convex loss functions and provides convex representations for additional network architectures.