Provable Benefit of Sign Descent: A Minimal Model Under Heavy-Tailed Class Imbalance

• URL: http://arxiv.org/abs/2512.00763v1
• Date: Sun, 30 Nov 2025 07:21:02 GMT
• Title: Provable Benefit of Sign Descent: A Minimal Model Under Heavy-Tailed Class Imbalance
• Abstract summary: We study the benefit of $ell_infty$-norm descent directly from properties of the data distribution, namely, heavy-tailed class imbalance.<n>We propose a minimal yet representative setting of next-token prediction, where we can provably show faster convergence of coordinate-wise algorithms.
• Score: 12.08350675783261
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Adaptive optimization methods (such as Adam) play a major role in LLM pretraining, significantly outperforming Gradient Descent (GD). Recent studies have proposed new smoothness assumptions on the loss function to explain the advantages of adaptive algorithms with structured preconditioners, e.g., coordinate-wise or layer-wise, and steepest descent methods w.r.t. non-euclidean norms, e.g., $\ell_\infty$ norm or spectral norm, over GD. However, it remains unclear how these smoothness assumptions manifest in language modelling tasks. In this work, we aim to analyze the benefit of $\ell_\infty$-norm descent (a.k.a. sign descent) directly from properties of the data distribution, namely, heavy-tailed class imbalance. We propose a minimal yet representative setting of next-token prediction, where we can provably show faster convergence of coordinate-wise algorithms such as Sign descent (steepest descent w.r.t. $\ell_\infty$ norm) over normalized GD (steepest descent w.r.t. to $\ell_2$ norm) in the presence of heavy tail class imbalance.

Related papers

• PriFT: Prior-Support Guided Supervised Fine-Tuning [74.65198014829393]
  Supervised fine-tuning (SFT) is an efficient approach for downstream task adaptation.<n>SFT fits fixed demonstrations token by token, including targets poorly aligned with the model's pretrained distribution.<n>We propose PriFT, which derives token weights from a frozen pretrained reference to obtain a stable reweighting signal unaffected by fine-tuning.
  arXiv  Detail & Related papers  (2026-06-08T12:14:06Z)
• Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noise [12.977441534320041]
  We show that a scale-invariant first-order method with spectral norm requires $(minm, n-frac3p-2p-1) calls.<n>We prove that a batched method achieves the matching bound of $(minm, n-frac5p2p-2p-2)$ when the norm is spectral and the Hessian is Lipschitz.
  arXiv  Detail & Related papers  (2026-05-18T15:13:18Z)
• Verifier-Free RL for LLMs via Intrinsic Gradient-Norm Reward [69.99652051809737]
  In this work, we propose Verifier-free Intrinsic Gradient-Norm Reward (VIGOR)<n>VIGOR is a simple reward that uses only the policy model itself.<n>It exhibits cross-domain transfer to code benchmarks when trained only on math data.
  arXiv  Detail & Related papers  (2026-05-11T03:15:37Z)
• When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds [15.724495678714007]
  Sign-based optimization algorithms, such as SignSGD and Muon, have garnered significant attention for their remarkable performance in training large foundation models.<n>We show that SignSGD effectively reduces the complexity by a factor of $d$ under emphsparse noise, where $d$ is the problem dimension.
  arXiv  Detail & Related papers  (2026-05-07T17:32:09Z)
• Preconditioned Score and Flow Matching [15.378063594292955]
  We show that the covariance $_t$ of $p_t$ governs optimization bias.<n>We propose reversible, label-conditional emphpreconditioning maps that reshape the geometry of $p_t$.<n>We show that preconditioning consistently yields better-trained models by avoiding suboptimal plateaus.
  arXiv  Detail & Related papers  (2026-03-02T19:09:15Z)
• Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise [17.899443444882888]
  We develop a worst-case complexity theory for inequalityally preconditioned gradient descent (SPSGD)<n>We demonstrate that normalization guarantees convergence to a first-order stationary point at rate $mathcalO(T-fracp-13p-2)$ when problem parameters are known, and $mathcalO(T-fracp-12p)$ when problem parameters are unknown.<n>In contrast, we prove that clipping may fail to converge in the worst case due to the statistical dependence between the preconditioner and the gradient estimates.
  arXiv  Detail & Related papers  (2026-02-13T19:29:17Z)
• FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
  Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)<n>Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)
  arXiv  Detail & Related papers  (2025-05-19T07:32:56Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)
• Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
  Adaptive gradient methods are among the most successful neural network training algorithms.<n>These methods are known to achieve better dimensional dependence than over convex SGD-normarity.<n>In this paper we introduce new assumptions on the smoothness of the structure and the gradient noise variance.
  arXiv  Detail & Related papers  (2024-06-07T02:55:57Z)
• Sparse is Enough in Fine-tuning Pre-trained Large Language Models [98.46493578509039]
  We propose a gradient-based sparse fine-tuning algorithm, named Sparse Increment Fine-Tuning (SIFT) We validate its effectiveness on a range of tasks including the GLUE Benchmark and Instruction-tuning.
  arXiv  Detail & Related papers  (2023-12-19T06:06:30Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  This paper attempts to characterize the particular regularization effect of SGD in the moderate learning rate regime. We show that SGD converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions.
  arXiv  Detail & Related papers  (2020-11-04T21:07:52Z)
• Convergence of Online Adaptive and Recurrent Optimization Algorithms [0.0]
  We prove local convergence of several notable descent algorithms used in machine learning. We adopt an "ergodic" rather than probabilistic viewpoint, working with empirical time averages instead of probability distributions.
  arXiv  Detail & Related papers  (2020-05-12T09:48:52Z)
• The Geometry of Sign Gradient Descent [29.8753797565422]
  We show a close connection between separable smoothness and $ell_infty$-smoothness and argue that the latter is the weaker and more natural assumption. We then proceed to study the smoothness constant with respect to the $ell_infty$-norm and thereby isolate geometric properties of the objective function. In short, we find sign-based methods to be preferable over gradient descent if (i) the Hessian is to some degree concentrated on its diagonal, and (ii) its maximal eigenvalue is much larger than the average eigenvalue.
  arXiv  Detail & Related papers  (2020-02-19T08:45:54Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

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.