# Overparameterization from Computational Constraints

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 27 Aug 2022.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time](https://mlsanity.com/paper/2203.05482/) (2022)
- [CoCa: Contrastive Captioners are Image-Text Foundation Models](https://mlsanity.com/paper/2205.01917/) (2022)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [CoAtNet: Marrying Convolution and Attention for All Data Sizes](https://mlsanity.com/paper/2106.04803/) (2021)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Provable Benefits of Overparameterization in Model Compression: From Double Descent to Pruning Neural Networks](https://mlsanity.com/paper/2012.08749/) (2020)
- [Adversarially Robust Learning Could Leverage Computational Hardness](https://mlsanity.com/paper/1905.11564/) (2019)
- [Can Adversarially Robust Learning Leverage Computational Hardness?](https://mlsanity.com/paper/1810.01407/) (2018)
- [Benefits of over-parameterization with EM](https://mlsanity.com/paper/1810.11344/) (2018)
- [Computational Limitations in Robust Classification and Win-Win Results](https://mlsanity.com/paper/1902.01086/) (2019)

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

- [Understanding Learning Invariance in Deep Linear Networks](https://mlsanity.com/paper/2506.13714/) (2025)

## Abstract (arXiv)

Overparameterized models with millions of parameters have been hugely successful. In this work, we ask: can the need for large models be, at least in part, due to the computational limitations of the learner? Additionally, we ask, is this situation exacerbated for robust learning? We show that this indeed could be the case. We show learning tasks for which computationally bounded learners need significantly more model parameters than what information-theoretic learners need. Furthermore, we show that even more model parameters could be necessary for robust learning. In particular, for computationally bounded learners, we extend the recent result of Bubeck and Sellke [NeurIPS'2021] which shows that robust models might need more parameters, to the computational regime and show that bounded learners could provably need an even larger number of parameters. Then, we address the following related question: can we hope to remedy the situation for robust computationally bounded learning by restricting adversaries to also be computationally bounded for sake of obtaining models with fewer parameters? Here again, we show that this could be possible. Specifically, building on the work of Garg, Jha, Mahloujifar, and Mahmoody [ALT'2020], we demonstrate a learning task that can be learned efficiently and robustly against a computationally bounded attacker, while to be robust against an information-theoretic attacker requires the learner to utilize significantly more parameters.