Characterizing Implicit Bias in Terms of Optimization Geometry

By Suriya Gunasekar, Jason D. Lee, Daniel Soudry, Nati Srebro. 2018

476 citations recorded by the source corpus.

We study the implicit bias of generic optimization methods, such as mirror descent, natural gradient descent, and steepest descent with respect to different potentials and norms, when optimizing underdetermined linear regression or separable linear classification problems. We explore the question of whether the specific global minimum (among the many possible global minima) reached by an algorithm can be characterized in terms of the potential or norm of the optimization geometry, and independently of hyperparameter choices such as step-size and momentum.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, background): “Using a low-rank update (as we do) can be viewed as implicitly performing spectral regularization (Gunasekar et al., 2018) and hence can be expected to have good generalization properties (Yoshida & Miyato, 2017).”
Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, background): “In fact it is easy to construct examples where this happens for SIGNSGD (Balles & Hennig, 2018), as well as top-k sparsification (Gunasekar et al., 2018), perhaps explaining the poor generalization of these schemes.”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “…established that ﬁrst-order methods can automatically ﬁnd minimum-norm/maximum-margin solutions that ﬁt the data in the settings of logistic regression, deep linear networks, and symmetric matrix factorization (Soudry et al., 2018; Gunasekar et al., 2018a,b; Ji & Telgarsky, 2018; Li et al., 2018b).”
The Implicit Bias of Gradient Descent on Separable Data (2017, methodology): “Degenerate and Non-Degenerate Data Sets An earlier conference version of this paper (Soudry et al., 2018) included a partial version of Theorem 3, which only applies to almost all data sets, in which case we can ensure the residual ρ ( t ) is bounded.”
Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, methodology): “First, the sequence of gradients Gunasekar et al. [2018]), and this result relies on the loss function (cid:96) being exponential tailed.”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “since they concern mirror descent, are the works of [20] and [21].”
Towards Understanding the Spectral Bias of Deep Learning (2019, methodology): “In order to understand neural network training, a line of work (Soudry et al., 2018; Gunasekar et al., 2018b,a) has made eﬀorts in the perspective of “implicit bias”, which states that training algorithms for deep learning implicitly pose an inductive bias onto the training process and lead to a…”
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes (2019, background): “Whereas there is a growing literature in analyzing the behavior of SGD on non-convex objectives (Soudry et al., 2017; Ji and Telgarsky, 2018; Gunasekar et al., 2018; Wilson et al., 2017), we focus here on properties of the optimization problem above that are algorithm independent.”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, background): “Assumption 3 is often satisﬁed by most standard loss functions with a ﬁnite unique minima [12] such as squared loss, hinge loss, etc. Assumption 3 ( Equal minimum values ) .”
Risk and parameter convergence of logistic regression (2018, background): “The other works show that not just gradient descent but also steepest descent with other norms can lead to margin maximization (Gunasekar et al., 2018) (see also (Telgarsky, 2013)), and also that constructing loss functions with an explicit goal of margin maximization can lead to better rates…”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, unknown): “Fine analyses of convergence rates have been carried out by Nacson et al. (2019b); Ji and Telgarsky (2019b, 2018), and extensions to other gradient-based algorithms and to factored parameterizations are considered by Gunasekar et al. (2018a).”
Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization (2018, background): “Note that the result of (Gunasekar et al., 2018) does not say anything about whether the algorithm converges or not .”
Size-free generalization bounds for convolutional neural networks (2019, background): “[11] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro.”
How catastrophic can catastrophic forgetting be in linear regression? (2022, background): “In addition, for each task, (S)GD at convergence returns the unique solution which implicitly minimizes the `2 distance to the initialization [22, 80], hence we can express wt as the unique solution to the following optimization problem: wt = argmin w ‖w −wt−1‖ , s.”
Generalization bounds for deep convolutional neural networks (2019, background): “(For some deeper theoretical exploration of implicit bias in deep learning and related settings, see (Gunasekar et al., 2017; 2018a;b; Ma et al., 2018).)”
Interplay Between Optimization and Generalization of Stochastic Gradient Descent with Covariance Noise (2019, unknown): “The choice of an optimization algorithm and the choice of optimization metaparameters induces an implicit bias (Neyshabur et al., 2017a;b; Gunasekar et al., 2018; Wilson et al., 2017) which can lead to solutions of varying generalization quality.”