# Component-based Sketching for Deep ReLU Nets

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 56 references that are in the map.
- First posted on arXiv 21 Sep 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Universality of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1805.10769/) (2018)
- [Why does deep and cheap learning work so well?](https://mlsanity.com/paper/1608.08225/) (2016)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [Provable approximation properties for deep neural networks](https://mlsanity.com/paper/1509.07385/) (2015)
- [Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1902.01384/) (2019)
- [The Global Landscape of Neural Networks: An Overview](https://mlsanity.com/paper/2007.01429/) (2020)
- [Global Convergence of Block Coordinate Descent in Deep Learning](https://mlsanity.com/paper/1803.00225/) (2018)
- [On the Benefit of Width for Neural Networks: Disappearance of Bad Basins](https://mlsanity.com/paper/1812.11039/) (2018)
- [Universal Consistency of Deep Convolutional Neural Networks](https://mlsanity.com/paper/2106.12498/) (2021)
- [Classification with Deep Neural Networks and Logistic Loss](https://mlsanity.com/paper/2307.16792/) (2023)
- [On ADMM in Deep Learning: Convergence and Saturation-Avoidance](https://mlsanity.com/paper/1902.02060/) (2019)
- [Depth Selection for Deep ReLU Nets in Feature Extraction and Generalization](https://mlsanity.com/paper/2004.00245/) (2020)
- [Generalization and Expressivity for Deep Nets](https://mlsanity.com/paper/1803.03772/) (2018)
- [Deep Neural Networks for Rotation-Invariance Approximation and Learning](https://mlsanity.com/paper/1904.01814/) (2019)
- [Realization of spatial sparseness by deep ReLU nets with massive data](https://mlsanity.com/paper/1912.07464/) (2019)
- [Learning Ability of Interpolating Deep Convolutional Neural Networks](https://mlsanity.com/paper/2210.14184/) (2022)
- [Realizing data features by deep nets](https://mlsanity.com/paper/1901.00130/) (2019)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [Deep Convolutional Neural Networks with Zero-Padding: Feature Extraction and Learning](https://mlsanity.com/paper/2307.16203/) (2023)
- [Constructive neural network learning](https://mlsanity.com/paper/1605.00079/) (2016)
- [Learning through deterministic assignment of hidden parameters](https://mlsanity.com/paper/1803.08374/) (2018)
- [Optimal Approximation and Learning Rates for Deep Convolutional Neural Networks](https://mlsanity.com/paper/2308.03259/) (2023)

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

- [Feature Qualification by Deep Nets: A Constructive Approach](https://mlsanity.com/paper/2503.18676/) (2025)

## Abstract (arXiv)

Deep learning has made profound impacts in the domains of data mining and AI, distinguished by the groundbreaking achievements in numerous real-world applications and the innovative algorithm design philosophy. However, it suffers from the inconsistency issue between optimization and generalization, as achieving good generalization, guided by the bias-variance trade-off principle, favors under-parameterized networks, whereas ensuring effective convergence of gradient-based algorithms demands over-parameterized networks. To address this issue, we develop a novel sketching scheme based on deep net components for various tasks. Specifically, we use deep net components with specific efficacy to build a sketching basis that embodies the advantages of deep networks. Subsequently, we transform deep net training into a linear empirical risk minimization problem based on the constructed basis, successfully avoiding the complicated convergence analysis of iterative algorithms. The efficacy of the proposed component-based sketching is validated through both theoretical analysis and numerical experiments. Theoretically, we show that the proposed component-based sketching provides almost optimal rates in approximating saturated functions for shallow nets and also achieves almost optimal generalization error bounds. Numerically, we demonstrate that, compared with the existing gradient-based training methods, component-based sketching possesses superior generalization performance with reduced training costs.