# Sparsest Univariate Learning Models Under Lipschitz Constraint

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 83 references that are in the map.
- First posted on arXiv 27 Dec 2021.

## Builds on (most cited first, 30 of 31)

- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising](https://mlsanity.com/paper/1608.03981/) (2016)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Deep Convolutional Neural Network for Inverse Problems in Imaging](https://mlsanity.com/paper/1611.03679/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [On instabilities of deep learning in image reconstruction - Does AI come at a cost?](https://mlsanity.com/paper/1902.05300/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [CNN-Based Projected Gradient Descent for Consistent Image Reconstruction](https://mlsanity.com/paper/1709.01809/) (2017)
- [RARE: Image Reconstruction using Deep Priors Learned without Ground Truth](https://mlsanity.com/paper/1912.05854/) (2019)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Mad Max: Affine Spline Insights into Deep Learning](https://mlsanity.com/paper/1805.06576/) (2018)
- [A representer theorem for deep neural networks](https://mlsanity.com/paper/1802.09210/) (2018)
- [Block Coordinate Regularization by Denoising](https://mlsanity.com/paper/1905.05113/) (2019)
- [Sparsity of solutions for variational inverse problems with finite-dimensional data](https://mlsanity.com/paper/1809.05045/) (2018)
- [Deep Neural Networks with Trainable Activations and Controlled Lipschitz Constant](https://mlsanity.com/paper/2001.06263/) (2020)
- [A unifying representer theorem for inverse problems and machine learning](https://mlsanity.com/paper/1903.00687/) (2019)
- [A Rate-Distortion Framework for Explaining Neural Network Decisions](https://mlsanity.com/paper/1905.11092/) (2019)
- [Exact Support Recovery for Sparse Spikes Deconvolution](https://mlsanity.com/paper/1306.6909/) (2013)
- [The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy](https://mlsanity.com/paper/1811.06416/) (2018)
- [SIMBA: Scalable Inversion in Optical Tomography using Deep Denoising Priors](https://mlsanity.com/paper/1911.13241/) (2019)
- [Convex Optimization in Sums of Banach Spaces](https://mlsanity.com/paper/2104.13127/) (2021)
- [In-Distribution Interpretability for Challenging Modalities](https://mlsanity.com/paper/2007.00758/) (2020)
- [Native Banach spaces for splines and variational inverse problems](https://mlsanity.com/paper/1904.10818/) (2019)
- [Exact solutions of infinite dimensional total-variation regularized problems](https://mlsanity.com/paper/1708.02157/) (2017)

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

- [Improving Lipschitz-Constrained Neural Networks by Learning Activation Functions](https://mlsanity.com/paper/2210.16222/) (2022)
- [Controlled Learning of Pointwise Nonlinearities in Neural-Network-Like Architectures](https://mlsanity.com/paper/2408.13114/) (2024)

## Abstract (arXiv)

Beside the minimization of the prediction error, two of the most desirable properties of a regression scheme are stability and interpretability. Driven by these principles, we propose continuous-domain formulations for one-dimensional regression problems. In our first approach, we use the Lipschitz constant as a regularizer, which results in an implicit tuning of the overall robustness of the learned mapping. In our second approach, we control the Lipschitz constant explicitly using a user-defined upper-bound and make use of a sparsity-promoting regularizer to favor simpler (and, hence, more interpretable) solutions. The theoretical study of the latter formulation is motivated in part by its equivalence, which we prove, with the training of a Lipschitz-constrained two-layer univariate neural network with rectified linear unit (ReLU) activations and weight decay. By proving representer theorems, we show that both problems admit global minimizers that are continuous and piecewise-linear (CPWL) functions. Moreover, we propose efficient algorithms that find the sparsest solution of each problem: the CPWL mapping with the least number of linear regions. Finally, we illustrate numerically the outcome of our formulations.