# Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time

arXiv: https://arxiv.org/abs/2006.14798 · HTML: https://mlsanity.com/paper/2006.14798/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2020.

## Built on by (most cited first, 4 of 4)

- [Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes](https://mlsanity.com/paper/2311.10972/) (2023)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks with Soft-Thresholding](https://mlsanity.com/paper/2304.06959/) (2023)
- [On the Loss Landscape Geometry of Regularized Deep Matrix Factorization: Uniqueness and Sharpness](https://mlsanity.com/paper/2603.27072/) (2026)

## Abstract (arXiv)

We study training of Convolutional Neural Networks (CNNs) with ReLU activations and introduce exact convex optimization formulations with a polynomial complexity with respect to the number of data samples, the number of neurons, and data dimension. More specifically, we develop a convex analytic framework utilizing semi-infinite duality to obtain equivalent convex optimization problems for several two- and three-layer CNN architectures. We first prove that two-layer CNNs can be globally optimized via an ℓ2 norm regularized convex program. We then show that multi-layer circular CNN training problems with a single ReLU layer are equivalent to an ℓ1 regularized convex program that encourages sparsity in the spectral domain. We also extend these results to three-layer CNNs with two ReLU layers. Furthermore, we present extensions of our approach to different pooling methods, which elucidates the implicit architectural bias as convex regularizers.