# Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2020.

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

- [Stochastic Training is Not Necessary for Generalization](https://mlsanity.com/paper/2109.14119/) (2021)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm](https://mlsanity.com/paper/2102.12238/) (2021)
- [Never Go Full Batch (in Stochastic Convex Optimization)](https://mlsanity.com/paper/2107.00469/) (2021)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization](https://mlsanity.com/paper/2202.13328/) (2022)
- [Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems](https://mlsanity.com/paper/2403.08585/) (2024)
- [Make Optimization Once and for All with Fine-grained Guidance](https://mlsanity.com/paper/2503.11462/) (2025)
- [Limitation of Characterizing Implicit Regularization by Data-independent Functions](https://mlsanity.com/paper/2201.12198/) (2022)
- [Towards understanding deep learning with the natural clustering prior](https://mlsanity.com/paper/2203.08174/) (2022)
- [Zero Generalization Error Theorem for Random Interpolators via Algebraic Geometry](https://mlsanity.com/paper/2512.06347/) (2025)
- [All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension](https://mlsanity.com/paper/2602.08350/) (2026)

## Abstract (arXiv)

The notion of implicit bias, or implicit regularization, has been suggested as a means to explain the surprising generalization ability of modern-days overparameterized learning algorithms. This notion refers to the tendency of the optimization algorithm towards a certain structured solution that often generalizes well. Recently, several papers have studied implicit regularization and were able to identify this phenomenon in various scenarios. We revisit this paradigm in arguably the simplest non-trivial setup, and study the implicit bias of Stochastic Gradient Descent (SGD) in the context of Stochastic Convex Optimization. As a first step, we provide a simple construction that rules out the existence of a distribution-independent implicit regularizer that governs the generalization ability of SGD. We then demonstrate a learning problem that rules out a very general class of distribution-dependent implicit regularizers from explaining generalization, which includes strongly convex regularizers as well as non-degenerate norm-based regularizations. Certain aspects of our constructions point out to significant difficulties in providing a comprehensive explanation of an algorithm's generalization performance by solely arguing about its implicit regularization properties.