Lune

NeurIPS2022Top-tier venue

Overparameterization from Computational Constraints

Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, Mingyuan Wang

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time cites CoAtNet: Marrying Convolution and Attention for All Data Sizes
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on4

  1. CoAtNet: Marrying Convolution and Attention for All Data SizesZihang Dai, Hanxiao Liu, Quoc V. Le, Mingxing TanNeurIPS 2021 · 1,747 citations
  2. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference timeMitchell Wortsman, Gabriel Ilharco, Samir Yitzhak Gadre, Rebecca Roelofs et al.ICML 2022 · 1,464 citations
  3. A Universal Law of Robustness via IsoperimetrySébastien Bubeck, Mark SellkeNeurIPS 2021 · 260 citations
  4. Provable Benefits of Overparameterization in Model Compression: From Double Descent to Pruning Neural NetworksXiangyu Chang, Yingcong Li, Samet Oymak, Christos ThrampoulidisAAAI 2021 · 58 citations

Related papers

  1. Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent KernelsSimone Bombari, Shayan Kiyani, Marco MondelliICML 2023 · 13 citations
  2. The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU NetsYujun Kim, Chaewon Moon, Chulhee YunNeurIPS 2025
  3. Query Complexity of Adversarial AttacksGrzegorz Gluch, Rüdiger L. UrbankeICML 2021 · 9 citations
  4. On the Adversarial Robustness of Mixture of ExpertsJoan Puigcerver, Rodolphe Jenatton, Carlos Riquelme, Pranjal Awasthi et al.NeurIPS 2022 · 33 citations
  5. A Characterization of Semi-Supervised Adversarially Robust PAC LearnabilityIdan Attias, Steve Hanneke, Yishay MansourNeurIPS 2022 · 19 citations
Dusk over the sea between two cliffs drawn in fine vertical lines