Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data

• URL: http://arxiv.org/abs/2502.04664v3
• Date: Mon, 19 May 2025 03:35:21 GMT
• Title: Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data
• Authors: Chen Fan, Mark Schmidt, Christos Thrampoulidis,
• Abstract summary: We provide the first complete characterization of implicit optimization bias for p-norm normalized steepest descent (NSD) and momentum steepest descent (NMD)<n>Our results prove that these algorithms converge to solutions maximizing the margin with respect to the matrix's p-norm, with established convergence rates.
• Score: 33.082961718280245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Different gradient-based methods for optimizing overparameterized models can all achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. We provide the first complete characterization of implicit optimization bias for p-norm normalized steepest descent (NSD) and momentum steepest descent (NMD) algorithms in multi-class linear classification with cross-entropy loss. Our key theoretical contribution is proving that these algorithms converge to solutions maximizing the margin with respect to the classifier matrix's p-norm, with established convergence rates. These results encompass important special cases including Spectral Descent and Muon, which we show converge to max-margin solutions with respect to the spectral norm. A key insight of our contribution is that the analysis of general entry-wise and Schatten p-norms can be reduced to the analysis of NSD/NMD with max-norm by exploiting a natural ordering property between all p-norms relative to the max-norm and its dual sum-norm. For the specific case of descent with respect to the max-norm, we further extend our analysis to include preconditioning, showing that Adam converges to the matrix's max-norm solution. Our results demonstrate that the multi-class linear setting, which is inherently richer than the binary counterpart, provides the most transparent framework for studying implicit biases of matrix-parameter optimization algorithms.

Related papers

• Extreme value theory for singular subspace estimation in the matrix denoising model [0.4297070083645049]
  We study fine-grained singular subspace estimation in the matrix denoising model.<n>We apply our distributional theory to test hypotheses of low-rank signal structure encoded in the leading singular vectors.
  arXiv  Detail & Related papers  (2025-07-26T15:28:36Z)
• 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)
• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model. Our method captures intricate patterns and relationships, enhancing classification performance.
  arXiv  Detail & Related papers  (2024-02-14T16:10:42Z)
• 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)
• Flat Minima in Linear Estimation and an Extended Gauss Markov Theorem [0.0]
  We derive simple and explicit formulas for the optimal estimator in the cases of Nuclear and Spectral norms. We analytically derive the generalization error in multiple random matrix ensembles, and compare with Ridge regression.
  arXiv  Detail & Related papers  (2023-11-18T14:45:06Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• 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.