Characterizing Implicit Bias in Terms of Optimization Geometry

Abstract

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.

arXiv comment(1) A bug in the proof of implicit bias for matrix factorization was fixed. v2 gives a characterization of the asymptotic bias of the factor matrices, while v1 made a stronger claim on the limit direction of the unfactored matrix. (2) v2 also includes new results on implicit bias of mirror descent with realizable affine constraints

References in corpus (15)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Don't Decay the Learning Rate, Increase the Batch Size
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Geometry of Optimization and Implicit Regularization in Deep Learning
• Margins, Shrinkage, and Boosting

Cited by in corpus (81)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• The Modern Mathematics of Deep Learning
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Implicit Regularization in Deep Matrix Factorization
• Towards Understanding the Spectral Bias of Deep Learning
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Risk and parameter convergence of logistic regression
• Kernel and Rich Regimes in Overparametrized Models
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• The Implicit and Explicit Regularization Effects of Dropout
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Convergence of Gradient Descent on Separable Data
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• NeurIPS 2020 Competition: Predicting Generalization in Deep Learning
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers
• A Continuous-Time View of Early Stopping for Least Squares
• High-Dimensional Linear Regression via Implicit Regularization
• Directional convergence and alignment in deep learning
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• Directional Pruning of Deep Neural Networks
• An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
• Hold me tight! Influence of discriminative features on deep network boundaries
• When Does Preconditioning Help or Hurt Generalization?
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Convergence and Margin of Adversarial Training on Separable Data
• SGD Generalizes Better Than GD (And Regularization Doesn't Help)
• On Dropout and Nuclear Norm Regularization
• Inductive Bias of Gradient Descent based Adversarial Training on Separable Data
• Finding the Needle in the Haystack with Convolutions: on the benefits of architectural bias
• Label Noise SGD Provably Prefers Flat Global Minimizers
• Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study
• Neural Anisotropy Directions
• On the Hyperparameters in Stochastic Gradient Descent with Momentum
• Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Implicit Regularization in ReLU Networks with the Square Loss
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• On generalization bounds for deep networks based on loss surface implicit regularization
• Implicit Regularization and Convergence for Weight Normalization
• Implicit Gradient Regularization
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods
• Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
• Bridging the Gap Between Adversarial Robustness and Optimization Bias
• The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Explicit Regularization of Stochastic Gradient Methods through Duality
• Implicit bias of deep linear networks in the large learning rate phase
• Implicit Regularization in Tensor Factorization
• Ridge Regression with Over-Parametrized Two-Layer Networks Converge to Ridgelet Spectrum
• Iterative regularization for convex regularizers
• On Alignment in Deep Linear Neural Networks
• On Margin Maximization in Linear and ReLU Networks
• MUSO: Achieving Exact Machine Unlearning in Over-Parameterized Regimes
• Unique Properties of Flat Minima in Deep Networks
• Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors
• Dissecting Supervised Contrastive Learning
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Implicit Regularization in Matrix Sensing via Mirror Descent
• An Upper Limit of Decaying Rate with Respect to Frequency in Deep Neural Network
• Implicit Bias of Linear Equivariant Networks
• Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks
• Painless step size adaptation for SGD
• Deep orthogonal linear networks are shallow
• Minimum complexity interpolation in random features models