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

Abstract

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 \emph{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 \emph{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.

References in corpus (7)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Uniform convergence may be unable to explain generalization in deep learning
• Geometry of Optimization and Implicit Regularization in Deep Learning
• Implicit Regularization in Deep Learning
• Generalization Properties and Implicit Regularization for Multiple Passes SGM

Cited by in corpus (6)

• On Convergence and Generalization of Dropout Training
• Is SGD a Bayesian sampler? Well, almost
• Implicit Regularization in ReLU Networks with the Square Loss
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• Limitations of Implicit Bias in Matrix Sensing: Initialization Rank Matters
• A Limitation of the PAC-Bayes Framework