Implicit bias of Normalized Steepest Descent in Multiclass Classification: Sign Descent, Spectral Descent, and Adam

• URL: http://arxiv.org/abs/2502.04664v2
• Date: Sat, 26 Apr 2025 05:18:23 GMT
• Title: Implicit bias of Normalized Steepest Descent in Multiclass Classification: Sign Descent, Spectral Descent, and Adam
• Authors: Chen Fan, Mark Schmidt, Christos Thrampoulidis,
• Abstract summary: We characterize the implicit bias of Adam and Sign gradient descent (SignGD) in multi-class cross-entropy minimization.<n>We generalize our analysis to p-norm normalized steepest descent (NSD) algorithms.<n>A key insight is that the analysis of general entry-wise and Schatten p-norms can be reduced to the analysis of NSD with max-norm.
• Score: 33.082961718280245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the optimization of overparameterized models, different gradient-based methods can achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. Despite a decade of research on implicit optimization bias, important questions remain open even in the foundational case of linear classification with separable data. We address this gap by characterizing the implicit bias of both Adam and Sign gradient descent (SignGD) in multi-class cross-entropy minimization: we prove that their iterates converge to solutions maximizing the margin with respect to the classifier matrix's max-norm, and we establish the corresponding convergence rates. We then generalize our analysis to p-norm normalized steepest descent (NSD) algorithms. This includes Spectral Descent, which we show converges to the max-margin solution with respect to the spectral norm. A key insight is that the analysis of general entry-wise and Schatten p-norms can be reduced to the analysis of NSD with max-norm (i.e., SignGD) by exploiting a natural ordering property between all p-norms relative to the max-norm and its dual sum-norm. Our results demonstrate that the multi-class linear setting, which is inherently richer than the binary counterpart, provides the most transparent playground for studying implicit biases of matrix-parameter optimization algorithms.

Related papers

• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Convex Parameter Estimation of Perturbed Multivariate Generalized Gaussian Distributions [18.95928707619676]
  We propose a convex formulation with well-established properties for MGGD parameters. The proposed framework is flexible as it combines a variety of regularizations for the precision matrix, the mean and perturbations. Experiments show a more accurate precision and covariance matrix estimation with similar performance for the mean vector parameter.
  arXiv  Detail & Related papers  (2023-12-12T18:08:04Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing [28.91482208876914]
  We consider the problem of parameter estimation in a high-dimensional generalized linear model. Despite their wide use, a rigorous performance characterization, as well as a principled way to preprocess the data, are available only for unstructured designs.
  arXiv  Detail & Related papers  (2023-08-28T11:49:23Z)
• Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models [4.093769373833101]
  We resolve the conjecture posed in Subramanian et al.'22, where the number of data points, features, and classes all grow together. Our new lower bounds are akin to an information-theoretic strong converse: they establish that the misclassification rate goes to 0 or 1ally. The key to our tight analysis is a new variant of the Hanson-Wright inequality which is broadly useful for multiclass problems with sparse labels.
  arXiv  Detail & Related papers  (2023-06-23T00:59:15Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in deep linear networks. We show that for all depth greater than one, with the standard Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters.
  arXiv  Detail & Related papers  (2023-06-22T23:14:57Z)
• The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks [117.93273337740442]
  We show that gradient descent converges to a uniform margin classifier on the training data with an $exp(-Omega(log2 t))$ convergence rate. We also show that batch normalization has an implicit bias towards a patch-wise uniform margin.
  arXiv  Detail & Related papers  (2023-06-20T16:58:00Z)
• Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond [33.593203156666746]
  We focus on the generalization properties of unregularized gradient-based learning procedures applied to separable linear classification. We give an additional unified explanation for this generalization, that we refer to as realizability and self-boundedness. In some of these cases, our bounds significantly improve upon the existing generalization error bounds in the literature.
  arXiv  Detail & Related papers  (2022-02-27T19:56:36Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization [118.50301177912381]
  We show that Adam can converge to different solutions of the objective with provably different errors, even with weight decay globalization. We show that if convex, and the weight decay regularization is employed, any optimization algorithms including Adam will converge to the same solution.
  arXiv  Detail & Related papers  (2021-08-25T17:58:21Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds [37.03247707259297]
  A suitable adaptive subspace can be generated by sampling a correlated random matrix whose second order statistics mirror the input data. We show that the relative error of the randomized approximations can be tightly characterized in terms of the spectrum of the data matrix. Experimental results show that the proposed approach enables significant speed ups in a wide variety of machine learning and optimization problems.
  arXiv  Detail & Related papers  (2020-12-13T13:02:31Z)
• When Does Preconditioning Help or Hurt Generalization? [74.25170084614098]
  We show how the textitimplicit bias of first and second order methods affects the comparison of generalization properties. We discuss several approaches to manage the bias-variance tradeoff, and the potential benefit of interpolating between GD and NGD.
  arXiv  Detail & Related papers  (2020-06-18T17:57:26Z)
• To Each Optimizer a Norm, To Each Norm its Generalization [31.682969645989512]
  We study the implicit regularization of optimization methods for linear models interpolating the training data in the under-parametrized and over-parametrized regimes. We argue that analyzing convergence to the standard maximum l2-margin is arbitrary and show that minimizing the norm induced by the data results in better generalizations.
  arXiv  Detail & Related papers  (2020-06-11T21:07:38Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.