Beyond First-Order: Training LLMs with Stochastic Conjugate Subgradients and AdamW

Di Zhang, Yihang Zhang · 2025

Read Beyond First-Order: Training LLMs with Stochastic Conjugate Subgradients and AdamW by Di Zhang, Yihang Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01241.txt.

Introduction

Di Zhang and Yihang Zhang propose a new training method for large language models that looks beyond plain gradient steps, in a 2025 paper. Standard training leans on simple descent rules, whose limits show at large scale. Their method mixes conjugate search directions with random sampling.

Sample sizes adapt as training proceeds, guided by theory on how many examples are needed. Step sizes adjust with a rule borrowed from a popular adaptive method. The design keeps the perks of simple methods while handling the rough, non-smooth shape of model training. Tests show faster progress per step and equal or better scaling than standard descent. The authors supply a detailed analysis of why the method gains ground.

Catalog record

CREATORDi Zhang, Yihang Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-01241

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond First-Order: Training LLMs with Stochastic Conjugate Subgradients and AdamW Di Zhang, Yihang Zhang Abstract Stochastic gradient-based descent (SGD), have long been central to training large language models (LLMs). However, their effectiveness is increasingly being questioned, particularly in large-scale applications where empirical evidence suggests potential performance limitations. In response, this paper proposes a stochastic conjugate subgradient method together with adaptive sampling tailored specifically for training LLMs. The method not only achieves faster convergence per iteration but also demonstrates improved scalability compared to traditional SGD techniques. It leverages sample complexity analysis to adaptively choose the sample size, employs a stochastic conjugate subgradient approach to determine search directions and utilizing an AdamW-like algorithm to adaptively adjust step sizes. This approach preserves the key advantages of first-order methods while effectively addressing the nonconvexity and non-smoothness inherent in LLMs training. Additionally, we provide a detailed analysis of the advantage of the algorithm. Experimental results show that the proposed method not only maintains, but in many cases surpasses, the scalability of traditional SGD techniques, significantly enhancing both the speed and accuracy of the optimization process. 1 Introduction 1.1 Problem Setup Large Language Models (LLMs) are trained to predict the next token in a sequence, given the preceding tokens. The training objective is defined as minimizing the Negative Log-Likelihood (NLL) of the training data. Given a dataset \mathcal{D}=\{(x^{(i)},y^{(i)})\}_{i=1}^{N} , where x^{(i)} is the input text sequence and y^{(i)} is the target token sequence, the objective function can be written as: L(\theta)=-\sum_{i=1}^{N}\sum_{t=1}^{T_{i}}\log P_{\theta}(y_{t}^{(i)}\mid y_{1:t-1}^{(i)}) (1) where: • T_{i} is the length of the i -th sequence. • y_{1:t-1}^{(i)} represents the tokens preceding token y_{t}^{(i)} . • P_{\theta} is the model’s predicted probability distribution over the vocabulary, parameterized by \theta . To train the LLMs, many stochastic gradient-based descent (SGD) algorithms have been proposed such as Adam and AdamW. SGD methods dominate the field for convincing reasons: low computational cost, simplicity of implementation, and strong empirical results. However, despite the advantages, there are also many limitations: a) SGD methods are not known for their numerical accuracy especially when the functions are non-smooth and b) establishing rigorous convergence guarantees is highly challenging because of the non-smooth and non-convex property of the objective function. 1.2 Contributions Instead of relying solely on the SGD approaches, a stochastic conjugate subgradient (SCS) ZS2024 ; zhang2024sampling ; zhang2024stochastic ; zhang2025stochastic method together with adaptive sampling strategy is considered in this paper. Originated from W1975 ; sen2022stochastic , the method accommodates the curvature of a objective functions, inherits the spirit of the momentum methods and apply the sample complexity analysis to reduce the computational burden. This combination enhances the power of SGD approaches without the additional burden of second-order approximations. In other words, our method shares the spirit of Hessian-Free (HF) optimization, which has gained attention in the machine learning community MJ2010 ; CScheinberg2017 . As our theoretical analysis and computational results reveal, the new method provides a “sweet spot" at the intersection of speed, accuracy, and scalability of algorithms. Our main contributions are: • To address the challenges posed by the non-smoothness of LLMs, we extend the non-smooth SCS method W1975 ; zhang2024stochastic to the training of LLMs. The SCS technique exhibits behavior similar to that of higher-order methods but avoids the significant computational overhead typically associated with maintaining a Hessian matrix at each iteration. To the best of our knowledge, this is the first attempt to apply such a beyond-first-order optimization technique to the training of LLMs. • While a straightforward application of W1975 to LLMs using sample average approximation (SAA) Shapiro2003 might be considered, our focus is on solving LLMs with extremely large datasets. Consequently, we employ an adaptive sampling strategy over a deterministic finite sum approximation. By leveraging the sample complexity analysis, we can take advantage of an adaptive sampling strategy which dramatically reduce the computational burden of training LLMs. • The computational results demonstrate that, from an optimization standpoint, the solutions produced by SCS yield lower objective function values compared with SGD methods. More crucially, the efficiency and accuracy of our algorithm surpasses those of algorithms such as Adam and AdamW, which are specialized SGD algorithms for training LLMs. • The proposed algorithm integrates several disparate notions such as adaptive sampling, decomposition, conjugate subgradients, and dynamic learning rate in Adam and AdamW. We demonstrate that this amalgamation effectively approximates solutions for LLMs with extremely large datasets. The structure of this paper is as follows. In § 2 , we will discuss some related work in the literature. In § 3 , we propose a SCS + AdamW algorithm which integrated the AdamW algorithm with SCS first moment direction. In § 4 , some good properties of the SCS direction are discussed. Then in § 5 , we present preliminary computational results that demonstrate the advantages of the proposed method over baseline approaches. Next, in § 6 , we discuss the limitations of this paper and some work directions in the future. Finally, conclusions are summarized in § 7 . 2 Related Work 2.1 SGD, Adam and AdamW Gradient-based optimization methods have evolved to handle complex, high-dimensional problems in deep learning and machine learning. Kingma and Ba kingma2014adam introduced Adam, an optimization algorithm that combines the advantages of Momentum and RMSProp. It maintains two moving averages for each parameter: (a) First moment estimate (mean of past gradients) (b) Second moment estimate (uncentered variance of past gradients). However, the major limitation of it is that the L2 regularization interacts with adaptive learning rates, making weight decay less effective. Loshchilov and Hutter loshchilov2017decoupled proposed AdamW, addressing the key limitation of Adam. Empirical results show that AdamW improves performance on NLP and vision tasks compared to Adam. 2.2 Stochastic Conjugate Subgradient Method In contrast to first-order methods, algorithms based on conjugate gradients (CG) provide finite termination when the objective function is a linear-quadratic deterministic function N2006 . Furthermore, CG algorithms are also used for large-scale nonsmooth convex optimization problems W1975 ; Y2016 . However, despite its many strengths, (e.g., fast per-iteration convergence, frequent explicit regularization on step-size, and better parallelization than first-order methods), the use of conjugate gradient methods for Stochastic Optimization is uncommon. Although J2018 ; Y2022 proposed some new stochastic conjugate gradient (SCG) algorithms, their assumptions do not support non-smooth objective functions, and hence not directly applicable to LLMs. 2.3 Adaptive sampling The LLMs algorithm typically employs sample average approximation (SAA) S1998 which has a fixed sample size to estimate the uncertainty. However, it is difficult to determine the sample size S2016 ; DS2024 when applying such methods. While adaptive sampling M1999 has emerged as a powerful approach for instances with a large number of outcomes (especially for multi-dimensional uncertainty, see HS1991 ; HS1994 ; lin2024economic ), such adaptive sampling has remained elusive in the context of LLMs. Our algorithm will strategically sample a subset of scenario subproblems in each iteration, facilitating dynamic scenario updates to enhance computational efficiency. We will also leverage sample complexity analysis V1998 to support the choice of the ultimate sample size used at termination. This approach ensures a theoretically grounded, and computationally realistic approach. This paper propose an integrated framework that combines the SCS with AdamW. Our goal is to create an efficient and rubust algorithm that

Read the complete text