# Measuring Complexity of Learning Schemes Using Hessian-Schatten Total Variation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 74 references that are in the map.
- First posted on arXiv 12 Dec 2021.

## Builds on (most cited first, 24 of 24)

- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)](https://mlsanity.com/paper/1511.07289/) (2015)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [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)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Mish: A Self Regularized Non-Monotonic Activation Function](https://mlsanity.com/paper/1908.08681/) (2019)
- [Path-SGD: Path-Normalized Optimization in Deep Neural Networks](https://mlsanity.com/paper/1506.02617/) (2015)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (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)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon](https://mlsanity.com/paper/1812.11167/) (2018)
- [Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks](https://mlsanity.com/paper/2109.08844/) (2021)
- [A representer theorem for deep neural networks](https://mlsanity.com/paper/1802.09210/) (2018)
- [Towards an Understanding of Benign Overfitting in Neural Networks](https://mlsanity.com/paper/2106.03212/) (2021)
- [Deep Neural Networks with Trainable Activations and Controlled Lipschitz Constant](https://mlsanity.com/paper/2001.06263/) (2020)
- [Higher-order total variation approaches and generalisations](https://mlsanity.com/paper/1912.01587/) (2019)
- [Sparsest Piecewise-Linear Regression of One-Dimensional Data](https://mlsanity.com/paper/2003.10112/) (2020)
- [Convex Optimization in Sums of Banach Spaces](https://mlsanity.com/paper/2104.13127/) (2021)
- [Native Banach spaces for splines and variational inverse problems](https://mlsanity.com/paper/1904.10818/) (2019)

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

- [Spectral complexity of deep neural networks](https://mlsanity.com/paper/2405.09541/) (2024)
- [Fractal and Regular Geometry of Deep Neural Networks](https://mlsanity.com/paper/2504.06250/) (2025)
- [Delaunay-Triangulation-Based Learning with Hessian Total-Variation Regularization](https://mlsanity.com/paper/2208.07787/) (2022)
- [Critical Points of Random Neural Networks](https://mlsanity.com/paper/2505.17000/) (2025)

## Abstract (arXiv)

In this paper, we introduce the Hessian-Schatten total variation (HTV) -- a novel seminorm that quantifies the total "rugosity" of multivariate functions. Our motivation for defining HTV is to assess the complexity of supervised-learning schemes. We start by specifying the adequate matrix-valued Banach spaces that are equipped with suitable classes of mixed norms. We then show that the HTV is invariant to rotations, scalings, and translations. Additionally, its minimum value is achieved for linear mappings, which supports the common intuition that linear regression is the least complex learning model. Next, we present closed-form expressions of the HTV for two general classes of functions. The first one is the class of Sobolev functions with a certain degree of regularity, for which we show that the HTV coincides with the Hessian-Schatten seminorm that is sometimes used as a regularizer for image reconstruction. The second one is the class of continuous and piecewise-linear (CPWL) functions. In this case, we show that the HTV reflects the total change in slopes between linear regions that have a common facet. Hence, it can be viewed as a convex relaxation (l1-type) of the number of linear regions (l0-type) of CPWL mappings. Finally, we illustrate the use of our proposed seminorm.