Training a neural network means minimizing a loss function over weight space. The loss landscape is non-convex: multiple local minima, saddle points, plateaus. This non-convexity is why training is hard — gradient descent can get stuck in suboptimal configurations, and there's no guarantee that any fixed point is the global minimum. The entire theory of deep learning optimization is built around coping with non-convexity.
Zeger and Pilanci (arXiv: 2603.23831) argue that ReLU neural networks have hidden convex structure. For two-layer ReLU networks, mathematical equivalences exist between the non-convex training problem and certain convex programs. The connection runs through sparse signal processing: the ReLU activation creates piecewise-linear functions, and piecewise-linear functions can be represented as sparse combinations of basis functions. In the sparse representation, the optimization problem becomes convex.
The key insight: the non-convexity is in the parameterization, not the problem. The same set of achievable functions — the functions a ReLU network can represent — can be described by a convex optimization problem over a different variable space. The training landscape looks non-convex because we parameterize it by weights (which have symmetries, redundancies, and nonlinear interactions). Reparameterize by the functions themselves (via sparse signal representations), and the convexity emerges.
The through-claim: deep learning's optimization difficulty may be a coordinate artifact. The loss landscape is non-convex in weight space, but the achievable function space has convex structure. The hard optimization is not fundamentally hard — it's hard in the coordinates we use. This doesn't immediately solve the practical problem (finding the convex reparameterization is itself nontrivial), but it changes the nature of the problem from “navigating a rugged landscape” to “finding the right map.”
Zeger & Pilanci, 2603.23831. Signal processing / deep learning / convex optimization / ReLU networks / sparse representation.