Adaptivity via a Parallel Architecture for Stochastic Gradient Methods Adaptivity via a Parallel Architecture for Stochastic Gradient Methods Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

# Adaptivity via a Parallel Architecture for Stochastic Gradient Methods
Source: [https://arxiv.org/html/2607.28902](https://arxiv.org/html/2607.28902)
###### Abstract

We develop a parallel framework that assembles static gradient methods to achieve better adaptivity\. A static gradient method, denoted byGD​\(x0,T\)\\mathrm\{GD\}\(x\_\{0\},T\), takes as input an initial pointx0∈ℝnx\_\{0\}\\in\\mathbb\{R\}^\{n\}andT∈ℝ\+T\\in\\mathbb\{R\}^\{\+\}specifying the number⌊T⌋\\left\\lfloor T\\right\\rfloorof iterations\. The step size is chosen ass=S​\(T\)s=S\(T\), whereS​\(⋅\)S\(\\cdot\)is a predetermined function ofTT\. The method then performs the iterationsxi\+1=xi−ηs⋅gi,x\_\{i\+1\}=x\_\{i\}\-\\frac\{\\eta\}\{s\}\\cdot g\_\{i\},wheregig\_\{i\}is a stochastic gradient evaluated atxix\_\{i\}, andη\\etais a scaling factor\. For an integerp≥1p\\geq 1, theppprocessors in the proposed parallel framework search for an appropriate value ofTTaccording to a geometric sequence so that the resulting gradient descent satisfies the desired convergence conditions\. Each processor executes an infinite sequence of stages indexed byi=1,2,…i=1,2,\\ldots\. At stageii, processorjjis assignedTj,i=h​\(j,i\),T\_\{j,i\}=h\(j,i\),whereh:ℕ×ℕ→ℝ\+h:\\mathbb\{N\}\\times\\mathbb\{N\}\\rightarrow\\mathbb\{R\}^\{\+\}is a prescribed function\. Processorjj\(j=0,1,…,p−1\)\(j=0,1,\\ldots,p\-1\)executesGD​\(x0,Tj,i\)\\mathrm\{GD\}\(x\_\{0\},T\_\{j,i\}\)at stageii\.

The efficiency of the parallel framework is measured by its\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation guarantee\. Specifically, for every integerT≥T0T\\geq T\_\{0\}, there exists a processorjjand a stageiisuch thatT≤Tj,i≤Tj,i∗<αp​T,T\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}<\\alpha\_\{p\}T,whereTj,i∗=∑t=1iTj,tT\_\{j,i\}^\{\*\}=\\sum\_\{t=1\}^\{i\}T\_\{j,t\}is the cumulative number of iterations executed by processorjjthrough stageii\. Thus,Tj,i∗T\_\{j,i\}^\{\*\}represents the total computational effort spent by processorjjbefore completing stageii\. Leth​\(j,i\)=bp,jp\+i⋅T0,h\(j,i\)=b\_\{p\}^\{,jp\+i\}\\cdot T\_\{0\},wherebp=\(p\+1\)1/p,b\_\{p\}=\(p\+1\)^\{1/p\},andT0T\_\{0\}is the minimum number of iterations assigned to any stage of every processor\. We show that this construction achieves a\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation, whereαp=\(1\+1p\)​\(p\+1\)1/p≤1\+1\+ln⁡\(1\+p\)p\+1p2​\(2​\(ln⁡\(1\+p\)\)2\+ln⁡\(1\+p\)\)\.\\alpha\_\{p\}=\\left\(1\+\\frac\{1\}\{p\}\\right\)\(p\+1\)^\{1/p\}\\leq 1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\+\\frac\{1\}\{p^\{2\}\}\\left\(2\\left\(\{\\ln\(1\+p\)\}\\right\)^\{2\}\+\{\\ln\(1\+p\}\)\\right\)\.We further prove a lower bound showing that, for any functionh​\(j,i\)h\(j,i\)and any constantd\>1d\>1, if the resulting framework achieves a\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation, thenαp≥\(1\+1\+ln⁡\(1\+p\)p−d​ln⁡ln⁡pp\)\\alpha\_\{p\}\\geq\\left\(1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\-\\frac\{d\\ln\\ln p\}\{p\}\\right\)for all sufficiently largepp\. Since the convergence analysis of static gradient methods is typically much simpler than that of adaptive gradient methods, our parallel framework enables a simpler convergence analysis for gradient descent on a nonconvex objective functionF​\(x\)F\(x\)while retaining the adaptivity to parameters, such as the Lipschitz smoothness constant and the stochastic gradient characteristics \(e\.g\., variance or noise level\)\.

## 1Introduction

Stochastic Gradient Descent \(SGD\)\[[24](https://arxiv.org/html/2607.28902#bib.bib24)\]is one of the most widely used optimization methods in deep learning because of its efficiency and scalability in training large\-scale neural networks\. Unlike batch gradient descent, which computes the gradient using the entire training dataset at every iteration, SGD updates the model parameters using a single training example or a small mini\-batch\. Consequently, SGD requires significantly less memory and has a much lower computational cost per iteration\. By processing only a small subset of the data at each step, SGD often converges more quickly in practice, particularly for large\-scale datasets\.

Gradient descent with diminishing step sizes has a long history\. Classical stochastic approximation theory shows that the step sizesηi\{\\eta\_\{i\}\}should satisfy∑i=1∞ηi=\+∞and∑i=1∞ηi2<\+∞\\sum\_\{i=1\}^\{\\infty\}\\eta\_\{i\}=\+\\infty\\quad\\text\{and\}\\quad\\sum\_\{i=1\}^\{\\infty\}\\eta\_\{i\}^\{2\}<\+\\inftyto guarantee convergence to a stationary point\[[24](https://arxiv.org/html/2607.28902#bib.bib24)\]\. For stochastic optimization of smooth nonconvex functions, gradient descent with either a constant step size or a diminishing step sizeηi=O​\(1/i\)\\eta\_\{i\}=O\(1/\\sqrt\{i\}\)achieves anO​\(1/T\)O\(1/\\sqrt\{T\}\)convergence rate to a stationary point\[[10](https://arxiv.org/html/2607.28902#bib.bib10)\]\. In particular, the analysis in\[[10](https://arxiv.org/html/2607.28902#bib.bib10)\]selects the step size asηi=min⁡\(1L,2​\(F​\(x1\)−F​\(x∗\)\)L​σ02​N\),\\eta\_\{i\}=\\min\\left\(\\frac\{1\}\{L\},\\sqrt\{\\frac\{2\(F\(x\_\{1\}\)\-F\(x^\{\*\}\)\)\}\{L\\sigma\_\{0\}^\{2\}N\}\}\\right\),which depends on the Lipschitz smoothness constantLL, the stochastic gradient variance parameterσ0\\sigma\_\{0\}, and the optimality gapF​\(x1\)−F​\(x∗\)F\(x\_\{1\}\)\-F\(x^\{\*\}\), whereF​\(x∗\)=infx\(F​\(x\)\)F\(x^\{\*\}\)=\\inf\_\{x\}\(F\(x\)\)\. Since these problem\-dependent parameters are typically unknown in advance, the resulting static gradient method is non\-adaptive\. Moreover, the convergence rate ofO​\(1/T\)O\(1/\\sqrt\{T\}\)is known to be optimal, matching the corresponding lower bound\[[3](https://arxiv.org/html/2607.28902#bib.bib3),[1](https://arxiv.org/html/2607.28902#bib.bib1)\]\.

Adaptive gradient descent methods have become widely used in deep learning in recent years\. Unlike static gradient methods, adaptive methods dynamically adjust the learning rate during training according to the historical gradients of individual parameters\. This adaptive mechanism reduces the need for manual tuning of learning rates and often improves optimization efficiency and robustness across a wide range of machine learning tasks\. A large body of research has established convergence guarantees and convergence rates for adaptive gradient methods under various assumptions and optimization settings\[[8](https://arxiv.org/html/2607.28902#bib.bib8),[17](https://arxiv.org/html/2607.28902#bib.bib17),[19](https://arxiv.org/html/2607.28902#bib.bib19),[16](https://arxiv.org/html/2607.28902#bib.bib16),[27](https://arxiv.org/html/2607.28902#bib.bib27),[28](https://arxiv.org/html/2607.28902#bib.bib28),[29](https://arxiv.org/html/2607.28902#bib.bib29)\]\.

Since the introduction of AdaGrad\[[8](https://arxiv.org/html/2607.28902#bib.bib8)\], numerous adaptive gradient methods have been proposed, including AdaDelta\[[29](https://arxiv.org/html/2607.28902#bib.bib29)\], Adam\[[12](https://arxiv.org/html/2607.28902#bib.bib12)\], AdamW\[[15](https://arxiv.org/html/2607.28902#bib.bib15)\], AdaFTRL\[[20](https://arxiv.org/html/2607.28902#bib.bib20)\], SGD\-BB\[[25](https://arxiv.org/html/2607.28902#bib.bib25)\], AdaBatch\[[7](https://arxiv.org/html/2607.28902#bib.bib7)\], SC\-AdaGrad\[[18](https://arxiv.org/html/2607.28902#bib.bib18)\], AMSGrad\[[22](https://arxiv.org/html/2607.28902#bib.bib22)\], and Padam\[[4](https://arxiv.org/html/2607.28902#bib.bib4)\]\. These developments reflect the continuing effort to improve adaptive gradient methods by enhancing their efficiency, robustness, theoretical guarantees, and ease of use for large\-scale machine learning applications\.

Adaptive stochastic gradient descent methods dynamically adjust the step size according to predefined update rules\. For example, AdaGrad\-Norm\[[27](https://arxiv.org/html/2607.28902#bib.bib27)\]updates the accumulated scaling factor and the model parameters assi\+1=si\+\|G​\(ξ,xi\)\|2,s\_\{i\+1\}=s\_\{i\}\+\|G\(\\xi,x\_\{i\}\)\|^\{2\},andxi\+1=xi−ηsi\+1⋅G​\(ξ,xi\),x\_\{i\+1\}=x\_\{i\}\-\\frac\{\\eta\}\{\\sqrt\{s\_\{i\+1\}\}\}\\cdot G\(\\xi,x\_\{i\}\),whereG​\(ξ,xi\)G\(\\xi,x\_\{i\}\)denotes the stochastic gradient evaluated atxix\_\{i\}\. The convergence properties of adaptive stochastic gradient methods have been extensively studied in\[[27](https://arxiv.org/html/2607.28902#bib.bib27),[28](https://arxiv.org/html/2607.28902#bib.bib28),[9](https://arxiv.org/html/2607.28902#bib.bib9),[26](https://arxiv.org/html/2607.28902#bib.bib26)\]\. Under suitable assumptions, these methods are proven to converge to a stationary point with the optimal convergence rate ofO​\(1/N\)O\(1/\\sqrt\{N\}\)\.

Parallel gradient descent has become an important optimization framework for large\-scale machine learning and scientific computing because it enables gradient computations to be distributed across multiple processors, thereby significantly reducing training time and improving scalability\. Early theoretical foundations for parallel and asynchronous iterative optimization were established by Dimitri P\. Bertsekas and John N\. Tsitsiklis\[[2](https://arxiv.org/html/2607.28902#bib.bib2)\], who analyzed convergence properties under delayed and distributed updates\. Large\-scale machine learning later motivated parallel SGD algorithms such as Hogwild\[[21](https://arxiv.org/html/2607.28902#bib.bib21)\], parameter\-server architectures\[[14](https://arxiv.org/html/2607.28902#bib.bib14)\], and distributed deep learning systems\[[6](https://arxiv.org/html/2607.28902#bib.bib6)\]\. Recent adaptive parallel methods further combine distributed computation with adaptive learning\-rate mechanisms for improved convergence behavior\[[23](https://arxiv.org/html/2607.28902#bib.bib23)\]\. More recent research has focused on adaptive and communication\-efficient distributed optimization, including adaptive SGD methods\[[5](https://arxiv.org/html/2607.28902#bib.bib5)\]and multi\-timescale distributed adaptive optimization frameworks\[[11](https://arxiv.org/html/2607.28902#bib.bib11)\]\.

### 1\.1Our Contributions

Our goal is to endow static gradient methods with adaptivity through a parallel framework\. A static gradient method, denoted byGD​\(x0,T\)\\mathrm\{GD\}\(x\_\{0\},T\), takes as input an initial pointx0x\_\{0\}and an integerTTspecifying the number of iterations\. The step size is determined bys=S​\(T\),s=S\(T\),whereS​\(⋅\)S\(\\cdot\)is a prescribed function ofTT\. The method then performs the iterationsxi\+1=xi−ηs⋅gi,x\_\{i\+1\}=x\_\{i\}\-\\frac\{\\eta\}\{s\}\\cdot g\_\{i\},wheregig\_\{i\}is a stochastic gradient evaluated atxix\_\{i\}, andη\\etais a scaling factor\. A fundamental challenge in applying a static gradient method is selecting an appropriate value ofTT\. The parameterTTmust be sufficiently large to guarantee the desired convergence, yet the required number of iterations typically depends on unknown problem characteristics, such as the Lipschitz smoothness constant and the stochastic gradient parameters\. Our parallel framework addresses this challenge by searching for a suitable value ofTTthrough parallel execution\.

We develop a parallel framework for gradient descent that searches for an appropriate iteration budgetTTin parallel according to a carefully designed geometric sequence\. The framework assembles multiple static gradient methods into an adaptive gradient descent method\. It consists ofppprocessors running in parallel\. The number of iterations assigned to processorjjat stageiiis determined byTj,i=h​\(j,i\)\.T\_\{j,i\}=h\(j,i\)\.Processorjj\(j=0,1,…,p−1\)\(j=0,1,\\ldots,p\-1\)executesGD​\(x0,Tj,i\)\\mathrm\{GD\}\(x\_\{0\},T\_\{j,i\}\)at stageii\. We chooseh​\(j,i\)=bp,jp\+i​T0,h\(j,i\)=b\_\{p\}^\{,jp\+i\}T\_\{0\},wherebp=\(p\+1\)1/p,b\_\{p\}=\(p\+1\)^\{1/p\},andT0T\_\{0\}is the minimum number of iterations assigned to any stage\.

We prove that, for everyT≥T0T\\geq T\_\{0\}, there exist a processorjjand a stageiisuch that

T≤Tj,i≤Tj,i∗<αp​T,T\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}<\\alpha\_\{p\}T,whereTj,i∗=∑t=1iTj,tT\_\{j,i\}^\{\*\}=\\sum\_\{t=1\}^\{i\}T\_\{j,t\}is the total number of iterations executed by processorjjthrough stageii, and

αp=\(1\+1p\)​\(p\+1\)1/p≤1\+1\+ln⁡\(1\+p\)p\+1p2​\(2​\(ln⁡\(1\+p\)\)2\+ln⁡\(1\+p\)\)\.\\alpha\_\{p\}=\\left\(1\+\\frac\{1\}\{p\}\\right\)\(p\+1\)^\{1/p\}\\leq 1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\+\\frac\{1\}\{p^\{2\}\}\\left\(2\\left\(\{\\ln\(1\+p\)\}\\right\)^\{2\}\+\{\\ln\(1\+p\}\)\\right\)\.The approximation factorαp\\alpha\_\{p\}measures the computational overhead incurred before a processor reaches an iteration budget that is sufficient to satisfy the desired convergence guarantee\. A smaller value ofαp\\alpha\_\{p\}indicates that fewer iterations are wasted in the preceding stages\.

We further establish a nearly matching lower bound by proving that, for any scheduling functionh​\(j,i\)h\(j,i\)and any constantd\>1d\>1, every\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation must satisfy

αp≥\(1\+1\+ln⁡\(1\+p\)p−d​ln⁡ln⁡pp\)\\alpha\_\{p\}\\geq\\left\(1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\-\\frac\{d\\ln\\ln p\}\{p\}\\right\)for all sufficiently largepp\.

The convergence behavior of the resulting parallel algorithm is therefore essentially the same as that of the underlying static gradient methodGD​\(⋅\)\\mathrm\{GD\}\(\\cdot\), whose convergence is determined by the iteration budgetTT\. Consequently, our framework provides the adaptivity of parallel search while preserving the relatively simple convergence analysis of static gradient methods\. Theoretical analysis establishes nearly matching upper and lower bounds onαp\\alpha\_\{p\}, revealing an intrinsic tradeoff between parallelism, adaptivity, and computational overhead\.

We develop a static gradient descent method under the following\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)\-stochastic model\. Letξ\\xibe a random variable, and letG​\(ξ,x\)G\(\\xi,x\)denote a stochastic gradient ofF​\(x\)F\(x\)\. We assume that

⟨𝔼ξ\[G\(ξ,x\)\],,∇F\(x\)⟩≥λ\|∇F\(x\)\|2\\left\\langle\\mathbb\{E\}\_\{\\xi\}\[G\(\\xi,x\)\],,\\nabla F\(x\)\\right\\rangle\\geq\\lambda\|\\nabla F\(x\)\|^\{2\}for someλ∈\(0,∞\)\\lambda\\in\(0,\\infty\); and

𝔼ξ​\[\|∇F​\(x\)−G​\(ξ,x\)\|2\]≤σ02\+σ12​\|∇F​\(x\)\|2\\mathbb\{E\}\_\{\\xi\}\\left\[\|\\nabla F\(x\)\-G\(\\xi,x\)\|^\{2\}\\right\]\\leq\\sigma\_\{0\}^\{2\}\+\\sigma\_\{1\}^\{2\}\|\\nabla F\(x\)\|^\{2\}for someσ0,σ1∈\[0,∞\)\\sigma\_\{0\},\\sigma\_\{1\}\\in\[0,\\infty\)\.

This model generalizes the standard stochastic gradient model, which assumes𝔼ξ​\[G​\(ξ,x\)\]=∇F​\(x\),\\mathbb\{E\}\_\{\\xi\}\[G\(\\xi,x\)\]=\\nabla F\(x\),and𝔼ξ​\[\|∇F​\(x\)−G​\(ξ,x\)\|2\]≤σ02\\mathbb\{E\}\_\{\\xi\}\\left\[\|\\nabla F\(x\)\-G\(\\xi,x\)\|^\{2\}\\right\]\\leq\\sigma\_\{0\}^\{2\}for someσ0∈\[0,∞\)\\sigma\_\{0\}\\in\[0,\\infty\)\.

Rigorous convergence analysis of stochastic and adaptive gradient methods is essential for understanding their theoretical behavior, improving their performance, and ensuring their reliability across a broad range of machine learning tasks\. Such analyses also reveal how convergence depends on problem characteristics and algorithmic hyperparameters, thereby guiding the design of more robust optimization algorithms\.

To the best of our knowledge, convergence guarantees under the above\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)\-stochastic model, in which all three parametersλ\\lambda,σ0\\sigma\_\{0\}, andσ1\\sigma\_\{1\}are allowed to be positive, have not been established in the existing literature\. We establish the following convergence results under this model\.

We develop a new gradient descent method under the proposed\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)\-stochastic model\. Given an iteration budget ofTTsteps, the method performs the updates

xj\+1=xj−ηsT​G​\(ξ,xj\),x\_\{j\+1\}=x\_\{j\}\-\\frac\{\\eta\}\{s\_\{T\}\}G\(\\xi,x\_\{j\}\),wheresT=2⌈⌈log⁡T⌉2⌉,s\_\{T\}=2^\{\\left\\lceil\\frac\{\\lceil\\log T\\rceil\}\{2\}\\right\\rceil\},andη\>0\\eta\>0is an arbitrary input parameter\.

Assuming that the objective function satisfies the standardLL\-Lipschitz smoothness condition,

\|∇F​\(x\)−∇F​\(y\)\|≤L​\|x−y\|,\|\\nabla F\(x\)\-\\nabla F\(y\)\|\\leq L\|x\-y\|,we prove that the proposed method converges to a stationary point for nonconvex optimization under the\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)\-stochastic model\. Moreover, it achieves the optimal convergence rate ofO​\(1/T\)O\(1/\\sqrt\{T\}\)\.

In the gradient descent methods proposed in this paper, every denominator is of the form2t2^\{t\}for some integertt\. As a result, division and square\-root operations, which are commonly used in gradient descent algorithms, are eliminated and replaced by binary shift operations\. This simplification makes the proposed methods more suitable for efficient hardware implementation and chip design\.

The convergence analysis of the proposed stochastic model provides a theoretical explanation for why a parallel search over the iteration budgetTTis necessary\. Our algorithm is parameter\-adaptive: it automatically adapts to the unknown Lipschitz smoothness constantLLand the stochastic gradient parametersλ\\lambda,σ0\\sigma\_\{0\}, andσ1\\sigma\_\{1\}\. Moreover, the parallel architecture is constructed independently of these unknown parameters, making the framework broadly applicable without prior knowledge of the optimization problem\.

### 1\.2Organization of This Paper

The remainder of this paper is organized as follows\. In Section[2](https://arxiv.org/html/2607.28902#S2), we present an overview of the proposed parallel framework for static gradient descent\. Section[3](https://arxiv.org/html/2607.28902#S3)formally introduces the parallel model and the notion of a\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation\. In Section[4](https://arxiv.org/html/2607.28902#S4), we derive upper bounds onαp\\alpha\_\{p\}, while Section[5](https://arxiv.org/html/2607.28902#S5)establishes corresponding lower bounds\. Section[7](https://arxiv.org/html/2607.28902#S7)presents the convergence analysis of the proposed static stochastic gradient method and demonstrates how it fits into the parallel framework\. In Section[9](https://arxiv.org/html/2607.28902#S9), we introduce a refined parallel model that avoids repeatedly restarting from the same initial pointx0x\_\{0\}\. Instead, it progressively replacesx0x\_\{0\}with an improved starting pointx0∗x\_\{0\}^\{\*\}satisfyingF​\(x0∗\)≤F​\(x0\)F\(x\_\{0\}^\{\*\}\)\\leq F\(x\_\{0\}\)\. Finally, we conclude that adaptivity can be achieved through parallelization while preserving the simplicity of convergence analysis for static gradient methods\.

## 2Overview of Our Method

In the parallel framework developed in this paper, we assume thatppprocessors execute concurrently\. The processors cooperatively search for a suitable iteration budgetTTfor the given static gradient methodGD​\(x0,T\)\\mathrm\{GD\}\(x\_\{0\},T\)by exploring a geometric sequence of candidate values\. Each processorjj\(j=0,1,…,p−1\)\(j=0,1,\\ldots,p\-1\)proceeds through an infinite sequence of stages\. At stageii, processorjjis assigned an iteration budgetTj,iT\_\{j,i\}and executesGD​\(x0,Tj,i\)\\mathrm\{GD\}\(x\_\{0\},T\_\{j,i\}\)\.

The candidate iteration budgets are selected from the geometric sequence

T0,\(1\+ϵ\)​T0,\(1\+ϵ\)2​T0,…,\(1\+ϵ\)k​T0,…\.T\_\{0\},\\ \(1\+\\epsilon\)T\_\{0\},\\ \(1\+\\epsilon\)^\{2\}T\_\{0\},\\ \\ldots,\\ \(1\+\\epsilon\)^\{k\}T\_\{0\},\\ \\ldots\.Specifically, we define

Tj,i=h​\(j,i\)=\(1\+ϵ\)i​p\+j​T0,T\_\{j,i\}=h\(j,i\)=\(1\+\\epsilon\)^\{ip\+j\}T\_\{0\},forj=0,1,…,p−1j=0,1,\\ldots,p\-1\. Consequently, for any desired iteration budgetTTthat is sufficiently large to satisfy the convergence guarantee, there always exists a valueTj,iT\_\{j,i\}in the sequence such thatTj,iT\_\{j,i\}is only slightly larger thanTT\.

The scheduling functionh​\(j,i\)h\(j,i\)and the parameterϵ\\epsilonare determined by the number of processorspp\. Asppincreases, the value ofϵ\\epsilondecreases, yielding a denser geometric sequence and thereby reducing the gap between the selected iteration budget and the desired valueTT\.

![Refer to caption](https://arxiv.org/html/2607.28902v1/x1.png)Figure 1:Four Parallel Processors with Infinitely Many Stages\.We show that, for every target iteration budgetTT, there exist a processorjjand a stageiisuch that

T≤Tj,i≤∑t=1iTj,t<αp​T\.T\\leq T\_\{j,i\}\\leq\\sum\_\{t=1\}^\{i\}T\_\{j,t\}<\\alpha\_\{p\}T\.We derive both upper and lower bounds forαp\\alpha\_\{p\}, and show that these bounds are nearly tight in the proposed parallel model\. The scheduling functionh​\(j,i\)h\(j,i\)and the parameterϵ\\epsilonare designed according to the number of processorspp\. Asppincreases,αp\\alpha\_\{p\}approaches11, implying that only a small amount of computation is wasted before reaching an iteration budget that satisfies the desired convergence guarantee\.

Figure[1](https://arxiv.org/html/2607.28902#S2.F1)illustrates the parallel framework with four processors\. Each rectangle represents one stage of a processor, and the integer inside the rectangle denotes the number of iterations assigned to that stage\. For example, whenT=26T=26, processorP2P\_\{2\}reaches Stage 2 with

T≤T2,2=28,T\\leq T\_\{2,2\}=28,and the cumulative number of iterations executed by that processor is

T2,2∗=T2,1\+T2,2=36\.T\_\{2,2\}^\{\*\}=T\_\{2,1\}\+T\_\{2,2\}=36\.
We design the parameterϵ\\epsilonto balance two competing objectives: efficiently locating a suitable iteration budgetTj,iT\_\{j,i\}and keeping the approximation factorαp\\alpha\_\{p\}close to11\. Once a sufficiently large iteration budgetTj,iT\_\{j,i\}is identified, the corresponding step size, determined by the functionS​\(Tj,i\)S\(T\_\{j,i\}\), satisfies the conditions required for the convergence guarantee of the underlying static gradient methodGD​\(⋅\)\\mathrm\{GD\}\(\\cdot\)\.

## 3A Parallel Framework for Gradient Methods

In this section, we introduce a parallel architecture that enables a gradient method to adapt automatically to unknown problem parameters\. By running multiple instances of a static gradient method in parallel, each with a different fixed step size, our framework transforms a static gradient method into an adaptive one\.

Letℝ=\(−∞,\+∞\)\\mathbb\{R\}=\(\-\\infty,\+\\infty\)denote the set of real numbers, and letℝ\+=\(0,\+∞\)\\mathbb\{R\}^\{\+\}=\(0,\+\\infty\)denote the set of positive real numbers\. Letℕ=\{0,1,2,…\}\\mathbb\{N\}=\\\{0,1,2,\\ldots\\\}denote the set of nonnegative integers\. For a real numberxx, let⌈x⌉\\lceil x\\rceildenote the smallest integer greater than or equal toxx, and⌊x⌋\\left\\lfloor x\\right\\rfloordenote the largest integer less than or equal toxx\.

###### Definition 1

A functionh:ℕ×ℕ→ℝh:\\mathbb\{N\}\\times\\mathbb\{N\}\\rightarrow\\mathbb\{R\}is called*geometric*if there exist constantsh0\>0h\_\{0\}\>0,a0\>1a\_\{0\}\>1, and an integerp≥1p\\geq 1such that

h​\(j,i\)=h0​a0j​p\+ih\(j,i\)=h\_\{0\}a\_\{0\}^\{jp\+i\}for allj,i∈ℕj,i\\in\\mathbb\{N\}\. Equivalently, the values ofh​\(j,i\)h\(j,i\)are given by the geometric sequence

h0,h0​a0,h0​a02,…\.h\_\{0\},\\ h\_\{0\}a\_\{0\},\\ h\_\{0\}a\_\{0\}^\{2\},\\ \\ldots\.

We first describe a static gradient method whose step size is determined by a functionS​\(T\)S\(T\)of the prescribed number of iterationsTT\. For example, letS​\(T\)=TS\(T\)=\\sqrt\{T\}\. Instead of computingT\\sqrt\{T\}exactly, we seek an integermmsuch that

2m∈\[T,4​T\]\.2^\{m\}\\in\[\\sqrt\{T\},\\,4\\sqrt\{T\}\]\.This approximation eliminates square\-root and division operations while preserving the desired asymptotic behavior\.

We give a description of a static gradient descent\. Its step size is determined by a functionS​\(T\)S\(T\)\. For example,S​\(T\)=TS\(T\)=\\sqrt\{T\}\. We tend to find an integermmsuch thatS​\(T\)=2m∈\[T,4​T\]S\(T\)=2^\{m\}\\in\[\\sqrt\{T\},4\\sqrt\{T\}\]\. This can remove division and square root operations\.

AlgorithmStatic\-SGD\(x0,T\)\(x\_\{0\},T\)

Related Parameters:

- •x0x\_\{0\}is the start point
- •T∈\[1,\+∞\)T\\in\[1,\+\\infty\)controls the number of iterations
- •η\\etais a scaling factor
- •S​\(T\):ℝ\+→ℝ\+S\(T\):\\mathbb\{R^\{\+\}\}\\rightarrow\\mathbb\{R^\{\+\}\}is a function to determine the stepsize based onTT
- •G​\(ξ,x\)G\(\\xi,x\)is a stochastic \(approximate\) gradient forxx\.

Steps:

1. 1\.i=1i=1
2. 2\.s=S​\(T\)s=S\(T\)
3. 3\.whilei≤Ti\\leq T
4. 4\.\{\\\{
5. 5\.gi=G​\(ξ,xi\)g\_\{i\}=G\(\\xi,x\_\{i\}\)
6. 6\.xi\+1=xi−ηs⋅gix\_\{i\+1\}=x\_\{i\}\-\\frac\{\\eta\}\{s\}\\cdot g\_\{i\}
7. 7\.\}\\\}

End of Algorithm

We have the following parallel framework that calls a static gradient descent methodG​D​\(x0,T\)GD\(x\_\{0\},T\)\. The parallel executions of GD\(x0,Tj,i\)\(x\_\{0\},T\_\{j,i\}\)finds aTj,iT\_\{j,i\}that will satisfy the condition of convergence\.

AlgorithmParallel\-GD\(GD\(\.,\.\),x0,h\(\.,\.\),T0,p\)\(GD\(\.,\.\),x\_\{0\},h\(\.,\.\),T\_\{0\},p\)

Related Parameters:

- •GD\(x0,T\)\(x\_\{0\},T\)is a gradient descent method with start pointx0x\_\{0\}, andTTiterations\.
- •T0T\_\{0\}is the least number of steps to execute
- •h​\(j,i\):ℕ×ℕ→ℕh\(j,i\):\\mathbb\{N\}\\times\\mathbb\{N\}\\rightarrow\\mathbb\{N\}is a function to assign the number of iterations when calling a existing gradient descent method\.
- •x0∈ℝmx\_\{0\}\\in\\mathbb\{R\}^\{m\}is the start point,
- •ppis the number of processors\.

Processorjj\(j=0,1,…,p−1j=0,1,\\ldots,p\-1\):

1. 1\.Leti=1i=1
2. 2\.Repeat
3. 3\.\{\\\{
4. 4\.LetTj,i=h​\(j,i\)T\_\{j,i\}=h\(j,i\)
5. 5\.GD\(x0,Tj,i\)\(x\_\{0\},T\_\{j,i\}\)
6. 6\.Leti=i\+1i=i\+1
7. 7\.\}\\\}

End of Algorithm

###### Definition 2

LetParallel​\-​GD​\(⋅\)\\mathrm\{Parallel\\mbox\{\-\}GD\}\(\\cdot\)denote the parallel framework defined by the algorithm\.

1. i\.We say thatParallel​\-​GD​\(⋅\)\\mathrm\{Parallel\\mbox\{\-\}GD\}\(\\cdot\)has a\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximationif it consists ofppprocessors indexed by0,1,…,p−10,1,\\ldots,p\-1, and for every integerT≥T0T\\geq T\_\{0\}, there exist a processorj<pj<pand a stageiisuch that T≤Tj,i≤Tj,i∗<αp​T,\\displaystyle T\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}<\\alpha\_\{p\}T,\(1\) whereTj,i∗=∑t=1iTj,t\.T\_\{j,i\}^\{\*\}=\\sum\_\{t=1\}^\{i\}T\_\{j,t\}\.
2. ii\.Ageometric parallel framework ofppprocessoris a parallel framework in which the scheduling functionh​\(j,i\)h\(j,i\)forppprocessors generates the iteration budgets according to a geometric progression, and can be expressed ash​\(j,i\)=bpi​p\+j​T0h\(j,i\)=b\_\{p\}^\{ip\+j\}T\_\{0\}for somebp\>1b\_\{p\}\>1andT0≥1T\_\{0\}\\geq 1\.

In Definition[2](https://arxiv.org/html/2607.28902#Thmtheoremfoo2), the condition \([1](https://arxiv.org/html/2607.28902#S3.E1)\) measures the computational overhead incurred before reaching an iteration budgetTj,iT\_\{j,i\}that is at least the target valueTT\. We derive both upper and lower bounds for the approximation factorαp\\alpha\_\{p\}\. Furthermore, the proposed parallel framework guarantees thatαp\\alpha\_\{p\}can be made arbitrarily close to11as the number of processorsppincreases\.

Lemma[3](https://arxiv.org/html/2607.28902#Thmtheoremfoo3)establishes a monotonicity property ofTj,iT\_\{j,i\}andTj,i∗T\_\{j,i\}^\{\*\}in the geometric parallel framework withppprocessors\. This property will be used to derive a lower bound that matches the corresponding upper bound forαp\\alpha\_\{p\}in a geometric parallel framework\.

###### Lemma 3

For the geometric parallel framework withppprocessors, if0≤j<k≤p−10\\leq j<k\\leq p\-1, then

Tj,i<Tk,iandTj,i∗<Tk,i∗T\_\{j,i\}<T\_\{k,i\}\\quad\\text\{and\}\\quad T\_\{j,i\}^\{\*\}<T\_\{k,i\}^\{\*\}for every stageii\.

Proof:The result follows directly from Definition[2](https://arxiv.org/html/2607.28902#Thmtheoremfoo2), which definesTj,iT\_\{j,i\},Tj,i∗T\_\{j,i\}^\{\*\}, and the geometric parallel framework, together with the assumptionsbp\>1b\_\{p\}\>1andT0≥1T\_\{0\}\\geq 1\.

## 4Upper Bound forαp\\alpha\_\{p\}in Parallel Model

In this section, we show a\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation for the parallel model\. An upper bound for the parameterαp\\alpha\_\{p\}will be derived\.

###### Lemma 4

Forx∈\[0,1\]x\\in\[0,1\],ex≤1\+x\+x2e^\{x\}\\leq 1\+x\+x^\{2\}\.

Proof:It follows from the Taylor expansion ofexe^\{x\}:ex=1\+x\+x22\!\+x33\!\+…≤1\+x\+x22\!\+x3​\(13\!\+14\!\+…\)≤1\+x\+x22\!\+x3​\(122\+123\+…\)≤1\+x\+x2e^\{x\}=1\+x\+\\frac\{x^\{2\}\}\{2\!\}\+\\frac\{x^\{3\}\}\{3\!\}\+\\ldots\\leq 1\+x\+\\frac\{x^\{2\}\}\{2\!\}\+x^\{3\}\(\\frac\{1\}\{3\!\}\+\\frac\{1\}\{4\!\}\+\\ldots\)\\leq 1\+x\+\\frac\{x^\{2\}\}\{2\!\}\+x^\{3\}\(\\frac\{1\}\{2^\{2\}\}\+\\frac\{1\}\{2^\{3\}\}\+\\ldots\)\\leq 1\+x\+x^\{2\}\.

###### Lemma 5

Ifppis an integer withp≥1p\\geq 1, then

\(1\+1p\)​\(1\+p\)1/p≤1\+1\+ln⁡\(1\+p\)p\+1p2​\(2​\(ln⁡\(1\+p\)\)2\+ln⁡\(1\+p\)\)\.\\displaystyle\\left\(1\+\\frac\{1\}\{p\}\\right\)\(1\+p\)^\{1/p\}\\leq 1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\+\\frac\{1\}\{p^\{2\}\}\\left\(2\\left\(\{\\ln\(1\+p\)\}\\right\)^\{2\}\+\{\\ln\(1\+p\}\)\\right\)\.

Proof:It is easy to verify thatln⁡\(1\+p\)p<1\\frac\{\\ln\(1\+p\)\}\{p\}<1for all integersp≥1p\\geq 1\. A simple induction showsln⁡\(1\+p\)<p\\ln\(1\+p\)<p\. It is true atp=1p=1ase≈2\.71828e\\approx 2\.71828\. Assumeln⁡\(1\+p\)≤p\\ln\(1\+p\)\\leq p\. We haveln⁡\(1\+\(p\+1\)\)<ln⁡e​\(1\+p\)=1\+ln⁡\(1\+p\)<1\+p\\ln\(1\+\(p\+1\)\)<\\ln e\(1\+p\)=1\+\\ln\(1\+p\)<1\+p\. By Lemma[4](https://arxiv.org/html/2607.28902#Thmtheoremfoo4), we have

\(1\+p\)1/p=eln⁡\(1\+p\)p≤1\+\(ln⁡\(1\+p\)p\)\+\(ln⁡\(1\+p\)p\)2\.\\displaystyle\(1\+p\)^\{1/p\}=e^\{\\frac\{\\ln\(1\+p\)\}\{p\}\}\\leq 1\+\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)\+\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)^\{2\}\.
Therefore,

\(1\+1p\)​\(1\+p\)1/p≤\(1\+1p\)​\(1\+\(ln⁡\(1\+p\)p\)\+\(ln⁡\(1\+p\)p\)2\)\\displaystyle\\left\(1\+\\frac\{1\}\{p\}\\right\)\(1\+p\)^\{1/p\}\\leq\\left\(1\+\\frac\{1\}\{p\}\\right\)\\left\(1\+\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)\+\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)^\{2\}\\right\)=\\displaystyle=1\+1p\+\(ln⁡\(1\+p\)p\)\+\(ln⁡\(1\+p\)p\)2\+1p​\(\(ln⁡\(1\+p\)p\)\+\(ln⁡\(1\+p\)p\)2\)\\displaystyle 1\+\\frac\{1\}\{p\}\+\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)\+\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)^\{2\}\+\\frac\{1\}\{p\}\\left\(\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)\+\\left\(\\frac\{\\ln\(1\+p\)\}\{p\}\\right\)^\{2\}\\right\)≤\\displaystyle\\leq1\+1\+ln⁡\(1\+p\)p\+1p2​\(2​\(ln⁡\(1\+p\)\)2\+ln⁡\(1\+p\)\)\.\\displaystyle 1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\+\\frac\{1\}\{p^\{2\}\}\\left\(2\\left\(\{\\ln\(1\+p\)\}\\right\)^\{2\}\+\{\\ln\(1\+p\}\)\\right\)\.
Theorem[6](https://arxiv.org/html/2607.28902#Thmtheoremfoo6)shows an upper bound forαp\\alpha\_\{p\}for\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation\. It covers all the cases forp≥1p\\geq 1\. Its proof shows how to select functionh\(\.,\.\)h\(\.,\.\)\.

###### Theorem 6

Let functionh​\(j,i\)=bpi​p\+j​T0h\(j,i\)=b\_\{p\}^\{ip\+j\}T\_\{0\}andbp=\(p\+1\)1pb\_\{p\}=\(p\+1\)^\{\\frac\{1\}\{p\}\}\. For any integerT≥T0T\\geq T\_\{0\}, the parallel\-GD\(\.\) has\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation withαp=\(1\+1p\)​\(1\+p\)1p≤1\+1\+ln⁡\(1\+p\)p\+1p2​\(2​\(ln⁡\(1\+p\)\)2\+ln⁡\(1\+p\)\)\.\\alpha\_\{p\}=\(1\+\\frac\{1\}\{p\}\)\(1\+p\)^\{\\frac\{1\}\{p\}\}\\leq 1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\+\\frac\{1\}\{p^\{2\}\}\\left\(2\\left\(\{\\ln\(1\+p\)\}\\right\)^\{2\}\+\{\\ln\(1\+p\}\)\\right\)\.

Proof:The processorjjwill use the stepsbpj⋅T0,bpp\+j⋅T0,bp2​p\+j⋅T0,…,bpi​p\+j⋅T0,⋯b\_\{p\}^\{j\}\\cdot T\_\{0\},b\_\{p\}^\{p\+j\}\\cdot T\_\{0\},b\_\{p\}^\{2p\+j\}\\cdot T\_\{0\},\\ldots,b\_\{p\}^\{ip\+j\}\\cdot T\_\{0\},\\cdots\. At phaseii, processorjjusesTj,i=h​\(j,i\)=bpi​p\+j​T0T\_\{j,i\}=h\(j,i\)=b\_\{p\}^\{ip\+j\}T\_\{0\}to control the number of of iterations in GD\(x0,Tj,ix\_\{0\},T\_\{j,i\}\)\. The proof also shows howbpb\_\{p\}is computed to get a minimalαp\\alpha\_\{p\}\.

Define

Tj,i∗=∑t=0ibpt​p\+j​T0=bpj​T0​∑t=0ibpt​p=bpj​T0⋅bp\(i\+1\)​p−1bpp−1<bp\(i\+1\)​p\+j​T0bpp−1=bpp​Tj,ibpp−1\.\\displaystyle T\_\{j,i\}^\{\*\}=\\sum\_\{t=0\}^\{i\}b\_\{p\}^\{tp\+j\}T\_\{0\}=b\_\{p\}^\{j\}T\_\{0\}\\sum\_\{t=0\}^\{i\}b\_\{p\}^\{tp\}=b\_\{p\}^\{j\}T\_\{0\}\\cdot\\frac\{b\_\{p\}^\{\(i\+1\)p\}\-1\}\{b\_\{p\}^\{p\}\-1\}<\\frac\{b\_\{p\}^\{\(i\+1\)p\+j\}T\_\{0\}\}\{b\_\{p\}^\{p\}\-1\}=\\frac\{b\_\{p\}^\{p\}T\_\{j,i\}\}\{b\_\{p\}^\{p\}\-1\}\.
We note thatTj,t=bpt​p\+j​T0T\_\{j,t\}=b\_\{p\}^\{tp\+j\}T\_\{0\}is the number of steps in thett\-th iteration\. LetTj,t=bpt​p\+j⋅T0T\_\{j,t\}=b\_\{p\}^\{tp\+j\}\\cdot T\_\{0\}be the least withT≤Tj,tT\\leq T\_\{j,t\}\. We haveT≤Tj,t<bp​TT\\leq T\_\{j,t\}<b\_\{p\}T\.

T≤Tj,t≤Tj,t∗\\displaystyle T\\leq T\_\{j,t\}\\leq T\_\{j,t\}^\{\*\}<\\displaystyle<bppbpp−1⋅Tj,t\\displaystyle\\frac\{b\_\{p\}^\{p\}\}\{b\_\{p\}^\{p\}\-1\}\\cdot T\_\{j,t\}≤\\displaystyle\\leqbpp\+1bpp−1⋅T\\displaystyle\\frac\{b\_\{p\}^\{p\+1\}\}\{b\_\{p\}^\{p\}\-1\}\\cdot T
Definef​\(x\)f\(x\)by

f​\(x\)=xp\+1xp−1\.\\displaystyle f\(x\)=\\frac\{x^\{p\+1\}\}\{x^\{p\}\-1\}\.\(2\)
Take derivative forf​\(x\)f\(x\)\.

f​\(x\)′=\(p\+1\)​xp​\(xp−1\)−p​x2​p\(xp−1\)2\.\\displaystyle f\(x\)^\{\\prime\}=\\frac\{\(p\+1\)x^\{p\}\(x^\{p\}\-1\)\-px^\{2p\}\}\{\(x^\{p\}\-1\)^\{2\}\}\.\(3\)
Let

\(p\+1\)​xp​\(xp−1\)−p​x2​p=0\.\\displaystyle\(p\+1\)x^\{p\}\(x^\{p\}\-1\)\-px^\{2p\}=0\.\(4\)It transformed into

xp−\(p\+1\)=0\.\\displaystyle x^\{p\}\-\(p\+1\)=0\.\(5\)So, we can letbp=\(p\+1\)1/pb\_\{p\}=\(p\+1\)^\{1/p\}to have leastf​\(bp\)f\(b\_\{p\}\)\.

So,

f​\(bp\)\\displaystyle f\(b\_\{p\}\)=\\displaystyle=bpp\+1bpp−1=\(1\+p\)​bpp\\displaystyle\\frac\{b\_\{p\}^\{p\+1\}\}\{b\_\{p\}^\{p\}\-1\}=\\frac\{\(1\+p\)b\_\{p\}\}\{p\}=\\displaystyle=\(1\+p\)​\(1\+p\)1/pp=\(1\+1p\)​\(1\+p\)1/p\\displaystyle\\frac\{\(1\+p\)\(1\+p\)^\{1/p\}\}\{p\}=\\left\(1\+\\frac\{1\}\{p\}\\right\)\{\(1\+p\)^\{1/p\}\}≤\\displaystyle\\leq1\+1\+ln⁡\(1\+p\)p\+1p2​\(2​\(ln⁡\(1\+p\)\)2\+ln⁡\(1\+p\)\)​\(b​y​L​e​m​m​a​[5](https://arxiv.org/html/2607.28902#Thmtheoremfoo5)\)\.\\displaystyle 1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\+\\frac\{1\}\{p^\{2\}\}\\left\(2\\left\(\{\\ln\(1\+p\)\}\\right\)^\{2\}\+\{\\ln\(1\+p\}\)\\right\)\(by~Lemma~\\ref\{help\-lemma\}\)\.
Therefore, ifbp=\(p\+1\)1/pb\_\{p\}=\(p\+1\)^\{1/p\}, we haveT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}Twithαp=\(1\+1p\)​\(1\+p\)1p\\alpha\_\{p\}=\(1\+\\frac\{1\}\{p\}\)\(1\+p\)^\{\\frac\{1\}\{p\}\}\.

We have Corollary[7](https://arxiv.org/html/2607.28902#Thmtheoremfoo7)for the casesp=1,2p=1,2\. They correspond to the cases for one processor, and two processors, respectively\.

###### Corollary 7

Letppbe the number of processors in Parallel\-GD\(\.\)\. We have

1. i\.Forp=1p=1, parallel\-GD\(\.\) has\(1,4\)\(1,4\)\-approximation withb1=2b\_\{1\}=2\.
2. ii\.Forp=2p=2, parallel\-GD\(\.\) has\(2,2\.5981\)\(2,2\.5981\)\-approximation withb2=3b\_\{2\}=\\sqrt\{3\}\.

Proof:It follows from Theorem[6](https://arxiv.org/html/2607.28902#Thmtheoremfoo6)withαp=\(1\+1p\)​\(1\+p\)1p\\alpha\_\{p\}=\(1\+\\frac\{1\}\{p\}\)\(1\+p\)^\{\\frac\{1\}\{p\}\}\.

Using the numerical solutions for the expression ofαp\\alpha\_\{p\}in Theorem[6](https://arxiv.org/html/2607.28902#Thmtheoremfoo6), we have upper bounds below:

α3\\displaystyle\\alpha\_\{3\}≤\\displaystyle\\leq2\.11654,α4≤1\.86919,α5≤1\.71717,α6≤1\.61229,α7≤1\.53459\\displaystyle 2\.11654,\\alpha\_\{4\}\\leq 1\.86919,\\alpha\_\{5\}\\leq 1\.71717,\\alpha\_\{6\}\\leq 1\.61229,\\alpha\_\{7\}\\leq 1\.53459α8\\displaystyle\\alpha\_\{8\}≤\\displaystyle\\leq1\.474397,α9≤1\.42615,α10≤1\.38644,α11≤1\.35309,α12≤1\.32459,\\displaystyle 1\.474397,\\alpha\_\{9\}\\leq 1\.42615,\\alpha\_\{10\}\\leq 1\.38644,\\alpha\_\{11\}\\leq 1\.35309,\\alpha\_\{12\}\\leq 1\.32459,α13\\displaystyle\\alpha\_\{13\}≤\\displaystyle\\leq1\.29994,α14≤1\.27844,α15≤1\.25966,α16≤1\.24329\.\\displaystyle 1\.29994,\\alpha\_\{14\}\\leq 1\.27844,\\alpha\_\{15\}\\leq 1\.25966,\\alpha\_\{16\}\\leq 1\.24329\.

## 5Lower Bounds forαp\\alpha\_\{p\}with Arbitraryh\(\.,\.\)h\(\.,\.\)

In this section, we show a lower bound in the parallel model\. The lower bound of this section has a small gap with the upper bound of Section[3](https://arxiv.org/html/2607.28902#S3)\. Our lower bound almost matches the upper bound\.

###### Lemma 8

For any functionh​\(j,i\)h\(j,i\), if Parallel\-GD\(\.\) has\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation, then we have

1. i\.for any positive integerzz,αp≥1\+1αpp\+1αp2​p\+…\+1αpz​p\\alpha\_\{p\}\\geq 1\+\\frac\{1\}\{\\alpha\_\{p\}^\{p\}\}\+\\frac\{1\}\{\\alpha\_\{p\}^\{2p\}\}\+\\ldots\+\\frac\{1\}\{\\alpha\_\{p\}^\{zp\}\}, and
2. ii\.αp≥r0\\alpha\_\{p\}\\geq r\_\{0\}, wherer0\>1r\_\{0\}\>1is a root ofxp−xp−1−1=0x^\{p\}\-x^\{p\-1\}\-1=0\.

Proof:We fixppandαp\>1\\alpha\_\{p\}\>1\(by its definition\)\. DefineTj,i∗=∑1≤i≤tTj,tT\_\{j,i\}^\{\*\}=\\sum\_\{1\\leq i\\leq t\}T\_\{j,t\}Let consider the sequenceV0=T0,V1=β​V0,…,Vk=βk​T0,…V\_\{0\}=T\_\{0\},V\_\{1\}=\\beta V\_\{0\},\\ldots,V\_\{k\}=\\beta^\{k\}T\_\{0\},\\ldots\. By the condition of\(a,αp\)\(a,\\alpha\_\{p\}\)\-approximation \(Definition[2](https://arxiv.org/html/2607.28902#Thmtheoremfoo2)\), for eachVkV\_\{k\}, we have aTj,iT\_\{j,i\}such thatVk≤Tj,i≤Tj,i∗≤αp​VkV\_\{k\}\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}V\_\{k\}\. Let

H=∑k=0mVk=T0​\(1\+β\+β2\+…\+βm\)=βm\+1−1β−1​T0\.\\displaystyle H=\\sum\_\{k=0\}^\{m\}V\_\{k\}=T\_\{0\}\(1\+\\beta\+\\beta^\{2\}\+\\ldots\+\\beta^\{m\}\)=\\frac\{\\beta^\{m\+1\}\-1\}\{\\beta\-1\}T\_\{0\}\.\(6\)
We have that for eachk≤mk\\leq m,Vk≤Tj,ij∗<αp​VkV\_\{k\}\\leq T\_\{j,i\_\{j\}\}^\{\*\}<\\alpha\_\{p\}V\_\{k\}\. We will selectβ=αp\\beta=\\alpha\_\{p\}\. This makes the case for eachTj,iT\_\{j,i\}, there is at most oneVkV\_\{k\}to haveVk≤Tj,i≤Tj,i∗<αp​VkV\_\{k\}\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}<\\alpha\_\{p\}V\_\{k\}\. This is becauseVk\+1=Vk​β=Vk​αp\>Tj,i∗V\_\{k\+1\}=V\_\{k\}\\beta=V\_\{k\}\\alpha\_\{p\}\>T\_\{j,i\}^\{\*\}\. Thus,Vk\+1V\_\{k\+1\}does not satisfy the inequalityVk\+1≤Tj,i≤Tj,i∗<αp​Vk\+1V\_\{k\+1\}\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}<\\alpha\_\{p\}V\_\{k\+1\}\.

LetQ⊆\{0,1,…,p−1\}Q\\subseteq\\\{0,1,\\ldots,p\-1\\\}such that for eachq∈Qq\\in Q, there is aVkV\_\{k\}with0≤k≤m0\\leq k\\leq mandVk≤Tq,i≤Tq,i∗≤αp​VkV\_\{k\}\\leq T\_\{q,i\}\\leq T\_\{q,i\}^\{\*\}\\leq\\alpha\_\{p\}V\_\{k\}for someii\. For aq∈Qq\\in Q, letTq,iqT\_\{q,i\_\{q\}\}be the largest withVk≤Tq,iq≤Tq,iq∗<αp​VkV\_\{k\}\\leq T\_\{q,i\_\{q\}\}\\leq T\_\{q,i\_\{q\}\}^\{\*\}<\\alpha\_\{p\}V\_\{k\}for someVkV\_\{k\}\(0≤k≤m0\\leq k\\leq m\)\.

Among the seriesV1,V2,…,VmV\_\{1\},V\_\{2\},\\ldots,V\_\{m\}, the largestppitems areVm−p\+1,Vm−p\+2,…,VmV\_\{m\-p\+1\},V\_\{m\-p\+2\},\\ldots,V\_\{m\}\. For eachq∈Qq\\in Q, there is only oneTq,iqT\_\{q,i\_\{q\}\}according to its definition\. As eachVkV\_\{k\}has at most oneTj,iT\_\{j,i\}withVk≤Tj,i≤Tj,i∗<αp​VkV\_\{k\}\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}<\\alpha\_\{p\}V\_\{k\}, we have inequality

∑j∈QTj,ij∗<αp⋅∑\(m−p\+1\)≤k≤mVk\.\\displaystyle\\sum\_\{j\\in Q\}T\_\{j,i\_\{j\}\}^\{\*\}<\\alpha\_\{p\}\\cdot\\sum\_\{\(m\-p\+1\)\\leq k\\leq m\}V\_\{k\}\.
By equation \([6](https://arxiv.org/html/2607.28902#S5.E6)\), we have

βm\+1−1β−1​T0=H\\displaystyle\\frac\{\\beta^\{m\+1\}\-1\}\{\\beta\-1\}T\_\{0\}=H≤\\displaystyle\\leq∑j∈QTj,ij∗<αp⋅∑\(m−p\+1\)≤k≤mVk\\displaystyle\\sum\_\{j\\in Q\}T\_\{j,i\_\{j\}\}^\{\*\}<\\alpha\_\{p\}\\cdot\\sum\_\{\(m\-p\+1\)\\leq k\\leq m\}V\_\{k\}=\\displaystyle=αp⋅∑\(m−p\+1\)≤k≤mβk​T0\\displaystyle\\alpha\_\{p\}\\cdot\\sum\_\{\(m\-p\+1\)\\leq k\\leq m\}\\beta^\{k\}T\_\{0\}=\\displaystyle=αp⋅βm−p\+1​T0​\(1\+β\+…\+βp−1\)\\displaystyle\\alpha\_\{p\}\\cdot\\beta^\{m\-p\+1\}T\_\{0\}\(1\+\\beta\+\\ldots\+\\beta^\{p\-1\}\)=\\displaystyle=αp⋅βm−p\+1⋅βp−1β−1⋅T0\.\\displaystyle\\alpha\_\{p\}\\cdot\\beta^\{m\-p\+1\}\\cdot\\frac\{\\beta^\{p\}\-1\}\{\\beta\-1\}\\cdot T\_\{0\}\.
Therefore,

αp\\displaystyle\\alpha\_\{p\}≥\\displaystyle\\geq\(βm\+1−1\)βm−p\+1⋅\(βp−1\)=βm\+1−1βm\+1−βm−p\+1\\displaystyle\\frac\{\(\\beta^\{m\+1\}\-1\)\}\{\\beta^\{m\-p\+1\}\\cdot\(\\beta^\{p\}\-1\)\}=\\frac\{\\beta^\{m\+1\}\-1\}\{\\beta^\{m\+1\}\-\\beta^\{m\-p\+1\}\}=\\displaystyle=1−1βm\+11−1βp\\displaystyle\\frac\{1\-\\frac\{1\}\{\\beta^\{m\+1\}\}\}\{1\-\\frac\{1\}\{\\beta^\{p\}\}\}
Letm=\(z\+1\)​p−1m=\(z\+1\)p\-1\. We have

αp≥1−1β\(z\+1\)​p1−1βp=1\+1βp\+1β2​p\+…\+1βz​p\.\\displaystyle\\alpha\_\{p\}\\geq\\frac\{1\-\\frac\{1\}\{\\beta^\{\(z\+1\)p\}\}\}\{1\-\\frac\{1\}\{\\beta^\{p\}\}\}=1\+\\frac\{1\}\{\\beta^\{p\}\}\+\\frac\{1\}\{\\beta^\{2p\}\}\+\\ldots\+\\frac\{1\}\{\\beta^\{zp\}\}\.
Asβ=αp\\beta=\\alpha\_\{p\}, this proves \([i](https://arxiv.org/html/2607.28902#S5.I1.i1)\) of the lemma\. We have

1≥1αp\+\+1αpp\+1\+1αp2​p\+1\+…\+1αpz​p\+1\.\\displaystyle 1\\geq\\frac\{1\}\{\\alpha\_\{p\}\}\+\+\\frac\{1\}\{\\alpha\_\{p\}^\{p\+1\}\}\+\\frac\{1\}\{\\alpha\_\{p\}^\{2p\+1\}\}\+\\ldots\+\\frac\{1\}\{\\alpha\_\{p\}^\{zp\+1\}\}\.
The numberαp\\alpha\_\{p\}is fixed in the beginning of this proof\. Taking limit forz→\+∞z\\rightarrow\+\\infty, we have

1≥1αp\+\+1αpp\+1\+1αp2​p\+1\+…\+1αpz​p\+1\+…\.\\displaystyle 1\\geq\\frac\{1\}\{\\alpha\_\{p\}\}\+\+\\frac\{1\}\{\\alpha\_\{p\}^\{p\+1\}\}\+\\frac\{1\}\{\\alpha\_\{p\}^\{2p\+1\}\}\+\\ldots\+\\frac\{1\}\{\\alpha\_\{p\}^\{zp\+1\}\}\+\\ldots\.
We consider the equation,

1\\displaystyle 1=\\displaystyle=1x\+1xp\+1\+1x2​p\+1\+…\+1xz​p\+1\+…\\displaystyle\\frac\{1\}\{x\}\+\\frac\{1\}\{x^\{p\+1\}\}\+\\frac\{1\}\{x^\{2p\+1\}\}\+\\ldots\+\\frac\{1\}\{x^\{zp\+1\}\}\+\\ldots\(7\)=\\displaystyle=1x⋅11−1xp=xp−1xp−1\\displaystyle\\frac\{1\}\{x\}\\cdot\\frac\{1\}\{1\-\\frac\{1\}\{x^\{p\}\}\}=\\frac\{x^\{p\-1\}\}\{x^\{p\}\-1\}\(8\)
Thus, we have equationxp−xp−1−1=0x^\{p\}\-x^\{p\-1\}\-1=0\. Ifr0\>1r\_\{0\}\>1is a root, thenr0r\_\{0\}is also the root of equation \([7](https://arxiv.org/html/2607.28902#S5.E7)\)\. The right side of equation \([7](https://arxiv.org/html/2607.28902#S5.E7)\) is strictly decreasing\. We haveαp≥r0\\alpha\_\{p\}\\geq r\_\{0\}\.

### 5\.1The Case for Large Number of Processorspp

We derive a lower bound for the caseppis large\. A special analysis for be given for the casep=1p=1in the next section\.

###### Theorem 9

For any functionh​\(j,i\)h\(j,i\), if Parallel\-GD\(\.\) has\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation, then for any fixedd\>1d\>1,αp≥1\+1\+ln⁡\(1\+p\)p−d​ln⁡ln⁡pp\\alpha\_\{p\}\\geq 1\+\\frac\{1\+\\ln\(1\+p\)\}\{p\}\-\\frac\{d\\ln\\ln p\}\{p\}for all largepp\.

Proof:By \([i](https://arxiv.org/html/2607.28902#S5.I1.i1)\) of Lemma[8](https://arxiv.org/html/2607.28902#Thmtheoremfoo8), we have

αp≥1\+1αpp\.\\displaystyle\\alpha\_\{p\}\\geq 1\+\\frac\{1\}\{\\alpha\_\{p\}^\{p\}\}\.
We will use the classical fact that\(1\+1x\)x\(1\+\\frac\{1\}\{x\}\)^\{x\}is increasing for allx\>1x\>1, andlimx→\+∞\(1\+1x\)x=e≈2\.71828\\lim\_\{x\\rightarrow\+\\infty\}\(1\+\\frac\{1\}\{x\}\)^\{x\}=e\\approx 2\.71828\(Euler’s number\)\. It can be found in most calculus textbooks\.

Assume thatαp<1\+1\+ln⁡\(1\+p\)−d​ln⁡ln⁡pp\\alpha\_\{p\}<1\+\\frac\{1\+\\ln\(1\+p\)\-d\\ln\\ln p\}\{p\}with a fixedd∈\(1,\+∞\)d\\in\(1,\+\\infty\)\. We have

1\+1αpp\\displaystyle 1\+\\frac\{1\}\{\\alpha\_\{p\}^\{p\}\}≥\\displaystyle\\geq1\+1\(1\+1\+ln⁡\(1\+p\)−d​ln⁡ln⁡pp\)p\\displaystyle 1\+\\frac\{1\}\{\(1\+\\frac\{1\+\\ln\(1\+p\)\-d\\ln\\ln p\}\{p\}\)^\{p\}\}=\\displaystyle=1\+1\(1\+1\+ln⁡\(1\+p\)−d​ln⁡ln⁡pp\)p\(1\+ln⁡\(1\+p\)−d​ln⁡ln⁡p\)⋅\(1\+ln⁡\(1\+p\)−d​ln⁡ln⁡p\)\\displaystyle 1\+\\frac\{1\}\{\\left\(1\+\\frac\{1\+\\ln\(1\+p\)\-d\\ln\\ln p\}\{p\}\\right\)^\{\\frac\{p\}\{\(1\+\\ln\(1\+p\)\-d\\ln\\ln p\)\}\\cdot\(1\+\\ln\(1\+p\)\-d\\ln\\ln p\)\}\}\>\\displaystyle\>1\+1e1\+ln⁡\(1\+p\)−d​ln⁡ln⁡p\\displaystyle 1\+\\frac\{1\}\{e^\{1\+\\ln\(1\+p\)\-d\\ln\\ln p\}\}=\\displaystyle=1\+\(ln⁡p\)de​\(1\+p\)\>1\+1\+ln⁡\(1\+p\)−d​ln⁡ln⁡pp\>αp\(f​o​r​a​l​a​r​g​e​p\)\.\\displaystyle 1\+\\frac\{\(\\ln p\)^\{d\}\}\{e\(1\+p\)\}\>1\+\\frac\{1\+\\ln\(1\+p\)\-d\\ln\\ln p\}\{p\}\>\\alpha\_\{p\}\\ \\ \(for~a~large~p\)\.This brings a contradiction whenppis large\.

### 5\.2The Case for Small Number of Processorspp

In this section, we give a lower for the casep=1,2p=1,2\. The casep=1p=1is important as it is related to single processor computation\. The casep=2p=2is the simplest parallel computation with two processors\.

###### Theorem 10

In the Parallel\-GD\(\.\) model, for any functionh​\(j,i\)h\(j,i\), we have

1. i\.if the parallel model has\(1,α1\)\(1,\\alpha\_\{1\}\)\-approximation, thenα1≥2\\alpha\_\{1\}\\geq 2\.
2. ii\.if the parallel model has\(2,α3\)\(2,\\alpha\_\{3\}\)\-approximation, thenα2≥5\+12\\alpha\_\{2\}\\geq\\frac\{\\sqrt\{5\}\+1\}\{2\}\.

Proof:By Lemma[8](https://arxiv.org/html/2607.28902#Thmtheoremfoo8), we have the equationxp−xp−1−1=0x^\{p\}\-x^\{p\-1\}\-1=0for the casesp=1,2p=1,2\. Forp=1p=1,x=2x=2is the only root\. Forp=2p=2,x=5\+12x=\\frac\{\\sqrt\{5\}\+1\}\{2\}is the root greater than11\. Therefore, we haveα1≥2\\alpha\_\{1\}\\geq 2, andα2≥5\+12\\alpha\_\{2\}\\geq\\frac\{\\sqrt\{5\}\+1\}\{2\}\.

###### Theorem 11

For any functionh​\(j,i\)h\(j,i\), if Parallel\-GD\(\.\) has\(3,α3\)\(3,\\alpha\_\{3\}\)\-approximation, then we haveα3≥r3\\alpha\_\{3\}\\geq r\_\{3\}, wherer3=13\+2954\+311083\+2954−311083≥1\.46557r\_\{3\}=\\frac\{1\}\{3\}\+\\sqrt\[3\]\{\\frac\{29\}\{54\}\+\\sqrt\{\\frac\{31\}\{108\}\}\}\+\\sqrt\[3\]\{\\frac\{29\}\{54\}\-\\sqrt\{\\frac\{31\}\{108\}\}\}\\geq 1\.46557\.

Proof:By Lemma[8](https://arxiv.org/html/2607.28902#Thmtheoremfoo8), we have the equationx3−x2−1=0x^\{3\}\-x^\{2\}\-1=0for the casesp=3p=3\. With the transformationx=y\+13x=y\+\\frac\{1\}\{3\}, it removes the quadratic term, and becomes the Cardano’s form:

y3−13​y−2927=0\.\\displaystyle y^\{3\}\-\\frac\{1\}\{3\}y\-\\frac\{29\}\{27\}=0\.We have rooty=2954\+311083\+2954−311083y=\\sqrt\[3\]\{\\frac\{29\}\{54\}\+\\sqrt\{\\frac\{31\}\{108\}\}\}\+\\sqrt\[3\]\{\\frac\{29\}\{54\}\-\\sqrt\{\\frac\{31\}\{108\}\}\}to satisfy thatxxis real number greater than11\. It has root forxx:

r3=13\+2954\+311083\+2954−311083≥1\.46557\.\\displaystyle r\_\{3\}=\\frac\{1\}\{3\}\+\\sqrt\[3\]\{\\frac\{29\}\{54\}\+\\sqrt\{\\frac\{31\}\{108\}\}\}\+\\sqrt\[3\]\{\\frac\{29\}\{54\}\-\\sqrt\{\\frac\{31\}\{108\}\}\}\\geq 1\.46557\.
Using the numerical solutions, we have lower bounds whenppgoes from44to1616below:

α4\\displaystyle\\alpha\_\{4\}≥\\displaystyle\\geq1\.38027,α5≥1\.32471,α6≥1\.28519,α7≥1\.25542,α8≥1\.23205,\\displaystyle 1\.38027,\\alpha\_\{5\}\\geq 1\.32471,\\alpha\_\{6\}\\geq 1\.28519,\\alpha\_\{7\}\\geq 1\.25542,\\alpha\_\{8\}\\geq 1\.23205,α9\\displaystyle\\alpha\_\{9\}≥\\displaystyle\\geq1\.21314,α10≥1\.19749,α11≥1\.18427,α12≥1\.17295,α13≥1\.16311,\\displaystyle 1\.21314,\\alpha\_\{10\}\\geq 1\.19749,\\alpha\_\{11\}\\geq 1\.18427,\\alpha\_\{12\}\\geq 1\.17295,\\alpha\_\{13\}\\geq 1\.16311,α14\\displaystyle\\alpha\_\{14\}≥\\displaystyle\\geq1\.15449,α15≥1\.14685,α16≥1\.14003\.\\displaystyle 1\.15449,\\alpha\_\{15\}\\geq 1\.14685,\\alpha\_\{16\}\\geq 1\.14003\.

## 6Tight Lower Bounds forαp\\alpha\_\{p\}with Geometrich\(\.,\.\)h\(\.,\.\)

In this section, we derive lower bound forαp\\alpha\_\{p\}whenh​\(j,i\)=T0​bpi​p\+jh\(j,i\)=T\_\{0\}b\_\{p\}^\{ip\+j\}for somebp\>1b\_\{p\}\>1\. It matches the upper bound for each integerp≥1p\\geq 1\.

###### Theorem 12

Let functionh​\(j,i\)=bpi​p\+j​T0h\(j,i\)=b\_\{p\}^\{ip\+j\}T\_\{0\}for somebp\>1b\_\{p\}\>1\. If parallel\-GD\(\.\) has\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation, thenαp≥\(1\+1p\)​\(p\+1\)1/p\\alpha\_\{p\}\\geq\(1\+\\frac\{1\}\{p\}\)\(p\+1\)^\{1/p\}\.

Proof:We fixppandαp\>1\\alpha\_\{p\}\>1\(by its definition\)\. At phaseii, processorjjusesTj,i=h​\(j,i\)=bpi​p\+j​T0T\_\{j,i\}=h\(j,i\)=b\_\{p\}^\{ip\+j\}T\_\{0\}to control the number of of iterations in GD\(x0,Tj,ix\_\{0\},T\_\{j,i\}\)\.

Define

Tj,i∗=∑t=0ibpt​p\+j​T0=bpj​T0​∑t=0ibpt​p=bpj​T0⋅bp\(i\+1\)​p−1bpp−1\.\\displaystyle T\_\{j,i\}^\{\*\}=\\sum\_\{t=0\}^\{i\}b\_\{p\}^\{tp\+j\}T\_\{0\}=b\_\{p\}^\{j\}T\_\{0\}\\sum\_\{t=0\}^\{i\}b\_\{p\}^\{tp\}=b\_\{p\}^\{j\}T\_\{0\}\\cdot\\frac\{b\_\{p\}^\{\(i\+1\)p\}\-1\}\{b\_\{p\}^\{p\}\-1\}\.
We note thatTj,t=bpt​p\+j​T0T\_\{j,t\}=b\_\{p\}^\{tp\+j\}T\_\{0\}is the number of steps in thett\-th iteration\. LetT=bpt​p\+j−1\+1T=b\_\{p\}^\{tp\+j\-1\}\+1with a largett\. So,Tj,t=bpt​p\+jT\_\{j,t\}=b\_\{p\}^\{tp\+j\}is the least withT≤Tj,tT\\leq T\_\{j,t\}\. We haveT≤Tj,t<bp​TT\\leq T\_\{j,t\}<b\_\{p\}T\.

By Definition[2](https://arxiv.org/html/2607.28902#Thmtheoremfoo2)and Lemma[3](https://arxiv.org/html/2607.28902#Thmtheoremfoo3), we have

αp​T≥\\displaystyle\\alpha\_\{p\}T\\geqTj,t∗=bpj​T0⋅bp\(t\+1\)​p−1bpp−1\\displaystyle T\_\{j,t\}^\{\*\}=b\_\{p\}^\{j\}T\_\{0\}\\cdot\\frac\{b\_\{p\}^\{\(t\+1\)p\}\-1\}\{b\_\{p\}^\{p\}\-1\}=\\displaystyle=bp\(t\+1\)​p\+j​T0−bpj​T0bpp−1\\displaystyle\\frac\{b\_\{p\}^\{\(t\+1\)p\+j\}T\_\{0\}\-b\_\{p\}^\{j\}T\_\{0\}\}\{b\_\{p\}^\{p\}\-1\}=\\displaystyle=bpp\+1​\(bpt​p\+j−1​T0\)−bpj​T0bpp−1\\displaystyle\\frac\{b\_\{p\}^\{p\+1\}\(b\_\{p\}^\{tp\+j\-1\}T\_\{0\}\)\-b\_\{p\}^\{j\}T\_\{0\}\}\{b\_\{p\}^\{p\}\-1\}=\\displaystyle=bpp\+1​\(T−1\)−bpj​T0bpp−1\\displaystyle\\frac\{b\_\{p\}^\{p\+1\}\(T\-1\)\-b\_\{p\}^\{j\}T\_\{0\}\}\{b\_\{p\}^\{p\}\-1\}=\\displaystyle=bpp\+1​T−bpp\+1−bpj​T0bpp−1\\displaystyle\\frac\{b\_\{p\}^\{p\+1\}T\-b\_\{p\}^\{p\+1\}\-b\_\{p\}^\{j\}T\_\{0\}\}\{b\_\{p\}^\{p\}\-1\}≥\\displaystyle\\geqbpp\+1​Tbpp−1−bpp\+1\+bpj​T0bpp−1\\displaystyle\\frac\{b\_\{p\}^\{p\+1\}T\}\{b\_\{p\}^\{p\}\-1\}\-\\frac\{b\_\{p\}^\{p\+1\}\+b\_\{p\}^\{j\}T\_\{0\}\}\{b\_\{p\}^\{p\}\-1\}
We have

αp≥bpp\+1bpp−1−bpj​T0T​\(bpp−1\)\\displaystyle\\alpha\_\{p\}\\geq\\frac\{b\_\{p\}^\{p\+1\}\}\{b\_\{p\}^\{p\}\-1\}\-\\frac\{b\_\{p\}^\{j\}T\_\{0\}\}\{T\(b\_\{p\}^\{p\}\-1\)\}
Letf​\(x\)=xp\+1xp−1f\(x\)=\\frac\{x^\{p\+1\}\}\{x^\{p\}\-1\}\. Taking derivative, we have

f​\(x\)′=\(p\+1\)​xp​\(xp−1\)−p​xp−1⋅xp\+1\(xp−1\)2=x2​p−\(p\+1\)​xp\(xp−1\)2\.\\displaystyle f\(x\)^\{\\prime\}=\\frac\{\(p\+1\)x^\{p\}\(x^\{p\}\-1\)\-px^\{p\-1\}\\cdot x^\{p\+1\}\}\{\(x^\{p\}\-1\)^\{2\}\}=\\frac\{x^\{2p\}\-\(p\+1\)x^\{p\}\}\{\(x^\{p\}\-1\)^\{2\}\}\.
So, we letxp=p\+1x^\{p\}=p\+1to have minimalf​\(x\)=\(p\+1\)​\(p\+1\)1/pp=\(1\+1p\)​\(p\+1\)1/pf\(x\)=\\frac\{\(p\+1\)\(p\+1\)^\{1/p\}\}\{p\}=\(1\+\\frac\{1\}\{p\}\)\(p\+1\)^\{1/p\}\.

Therefore,

αp\\displaystyle\\alpha\_\{p\}≥\\displaystyle\\geq\(1\+1p\)​\(p\+1\)1/p−bpj​T0T​\(bpp−1\)\\displaystyle\(1\+\\frac\{1\}\{p\}\)\(p\+1\)^\{1/p\}\-\\frac\{b\_\{p\}^\{j\}T\_\{0\}\}\{T\(b\_\{p\}^\{p\}\-1\)\}≥\\displaystyle\\geq\(1\+1p\)​\(p\+1\)1/p−ϵ\(f​o​r​l​a​r​g​e​T\)\.\\displaystyle\(1\+\\frac\{1\}\{p\}\)\(p\+1\)^\{1/p\}\-\\epsilon\\ \\ \\ \(for\\ large\\ T\)\.Since bothppandαp\\alpha\_\{p\}are fixed in the beginning of this proof andϵ\\epsilonis arbitrarily close to zero, we haveα≥\(1\+1p\)​\(p\+1\)1/p\\alpha\\geq\(1\+\\frac\{1\}\{p\}\)\(p\+1\)^\{1/p\}\.

## 7Arithmetically Simple Gradient Descent for Nonconvex Optimization

In this section, we present an arithmetically simple static gradient descent method for nonconvex optimization\. The algorithm takes the iteration budgetTTas input, which determines the total number of gradient descent iterations\. The step size is computed using a denominator of the form2t2^\{t\}, where the integerttis determined fromTT\.

This design makes the algorithm particularly suitable for hardware implementation\. Since every denominator is a power of two, division operations can be replaced by binary shift operations, eliminating expensive floating\-point division\. Moreover, the algorithm avoids square\-root computations altogether\. These arithmetic simplifications make the proposed method attractive for hardware accelerators and chip implementations\.

The convergence analysis in this section also explains the motivation for the proposed parallel framework\. Because the convergence guarantee of the static gradient method depends on selecting an appropriate iteration budgetTT, the parallel framework searches for a suitable value ofTTadaptively while preserving the simplicity of the underlying static algorithm\.

### 7\.1Notations for Gradient Descent

A vector inℝm\\mathbb\{R\}^\{m\}is\(a1,a2,…,am\)\(a\_\{1\},a\_\{2\},\\ldots,a\_\{m\}\)withai∈ℝa\_\{i\}\\in\\mathbb\{R\}fori=1,2,⋯,mi=1,2,\\cdots,m\. The inner product between two vectorsV=\(v1,v2,…,vm\)V=\(v\_\{1\},v\_\{2\},\\ldots,v\_\{m\}\)andU=\(u1,u2,…,um\)U=\(u\_\{1\},u\_\{2\},\\ldots,u\_\{m\}\)is denoted by⟨U,V⟩=∑i=1mui​vi\\langle U,V\\rangle=\\sum\_\{i=1\}^\{m\}u\_\{i\}v\_\{i\}\. The length of a vectorV=\(v1,v2,…,vm\)V=\(v\_\{1\},v\_\{2\},\\ldots,v\_\{m\}\)is denoted by‖V‖=v12\+v22\+…\+vm2\\\|V\\\|=\\sqrt\{v\_\{1\}^\{2\}\+v\_\{2\}^\{2\}\+\\ldots\+v\_\{m\}^\{2\}\}\. For a differentiable functionF​\(x1,x2,⋯,xm\):ℝm→ℝF\(x\_\{1\},x\_\{2\},\\cdots,x\_\{m\}\):\\mathbb\{R\}^\{m\}\\rightarrow\\mathbb\{R\}, its gradient at a point\(x1,x2,⋯,xm\)\(x\_\{1\},x\_\{2\},\\cdots,x\_\{m\}\)is▽F​\(x1,x2,⋯,xm\)=\(∂F​\(x1,x2,⋯,xm\)∂x1,∂F​\(x1,x2,⋯,xm\)∂x2,…,∂F​\(x1,x2,⋯,xm\)∂xm\)\\bigtriangledown F\(x\_\{1\},x\_\{2\},\\cdots,x\_\{m\}\)=\\left\(\\frac\{\\partial F\(x\_\{1\},x\_\{2\},\\cdots,x\_\{m\}\)\}\{\\partial x\_\{1\}\},\\frac\{\\partial F\(x\_\{1\},x\_\{2\},\\cdots,x\_\{m\}\)\}\{\\partial x\_\{2\}\},\\ldots,\\frac\{\\partial F\(x\_\{1\},x\_\{2\},\\cdots,x\_\{m\}\)\}\{\\partial x\_\{m\}\}\\right\)\. In the rest of this paper, letx∗∈ℝmx^\{\*\}\\in\\mathbb\{R\}^\{m\}be a point withF​\(x∗\)=infx\{F​\(x\)\}F\(x^\{\*\}\)=\\inf\_\{x\}\\\{F\(x\)\\\}ifinfx\{F​\(x\)\}\>−∞\\inf\_\{x\}\\\{F\(x\)\\\}\>\-\\infty\. The expectation on a random variableξ\\xiis expressed𝔼ξ\(\.\)\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(\.\)\. For example, a stochastic gradientG​\(ξ,x\)G\(\\xi,x\)for functionF​\(x\)F\(x\)may satisfy the condition𝔼ξ​\(ξ,x\)=▽F​\(x\)\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(\\xi,x\)=\\bigtriangledown F\(x\), which is often assumed in many SGD algorithms\. In this section, we give some theoretical results about the rate of convergence\. The following two conditions are often assumed for non\-convex optimization\.

- •LL\-Lipschitzsmoothness:∥▽\(F\(x\)\)−▽\(F\(y\)\)∥≤L∥x−y∥\\\|\\bigtriangledown\(F\(x\)\)\-\\bigtriangledown\(F\(y\)\)\\\|\\leq L\\\|x\-y\\\|\.
- •F∗=infxF​\(x\)\>−∞F^\{\*\}=\\inf\_\{x\}F\(x\)\>\-\\infty

LetCL1C\_\{L\}^\{1\}be the class of functions that areLL\-Lipschitz smooth\. The following Lemma[13](https://arxiv.org/html/2607.28902#Thmtheoremfoo13), which is often mentioned in existing publications, can be easily proven byLL\-Lipschitz condition and Taylor expansion \(See\[[13](https://arxiv.org/html/2607.28902#bib.bib13)\]\)\.

###### Lemma 13

LetF​\(x1,⋯,xd\)F\(x\_\{1\},\\cdots,x\_\{d\}\)be a functionℝd→ℝ\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}inCL1C\_\{L\}^\{1\}, we haveF​\(x\)≤F​\(y\)\+\(▽F​\(y\),x−y\)\+L2​‖x−y‖2F\(x\)\\leq F\(y\)\+\(\\bigtriangledown F\(y\),x\-y\)\+\\frac\{L\}\{2\}\\\|x\-y\\\|^\{2\}\.

The stochastic gradient is controlled by three parametersλ,σ0\\lambda,\\sigma\_\{0\}, andσ1\\sigma\_\{1\}\. It is given in Definition[14](https://arxiv.org/html/2607.28902#Thmtheoremfoo14)\.

###### Definition 14

A\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)\-stochastic gradientG​\(ξ,x\)G\(\\xi,x\)forF​\(x\):ℝm→ℝF\(x\):\\mathbb\{R\}^\{m\}\\rightarrow\\mathbb\{R\}is thatξ\\xiis a random variable andG​\(ξ,x\)G\(\\xi,x\)is an approximation for▽F​\(x\)\\bigtriangledown F\(x\)satisfying the conditions:

1. i\.⟨𝔼ξ​\(G​\(ξ,x\)\),▽F​\(x\)⟩≥λ​‖▽F​\(x\)‖2\\langle\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(G\(\\xi,x\)\),\\bigtriangledown F\(x\)\\rangle\\geq\\lambda\\\|\\bigtriangledown F\(x\)\\\|^\{2\}for someλ∈\(0,\+∞\)\\lambda\\in\(0,\+\\infty\), and
2. ii\.𝔼ξ​\(‖▽F​\(x\)−G​\(ξ,x\)‖2\)≤σ02\+σ12​‖▽F​\(x\)‖2\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(\\\|\\bigtriangledown F\(x\)\-G\(\\xi,x\)\\\|^\{2\}\)\\leq\\sigma\_\{0\}^\{2\}\+\\sigma\_\{1\}^\{2\}\\\|\\bigtriangledown F\(x\)\\\|^\{2\}for someσ0,σ1∈\[0,\+∞\)\\sigma\_\{0\},\\sigma\_\{1\}\\in\[0,\+\\infty\)\.

A standard stochastic model, which is broadly used in stochastic gradient descent, is the special case withλ=1\\lambda=1andσ1=0\\sigma\_\{1\}=0\. Our stochastic model is more general, and fits the convergence analysis for our algorithm\.

###### Lemma 15

AssumeF​\(x\)F\(x\)andG​\(ξ,x\)G\(\\xi,x\)satisfy𝔼ξ​\(‖▽F​\(x\)−G​\(ξ,x\)‖2\)≤σ02\+σ12​‖▽F​\(x\)‖2\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(\\\|\\bigtriangledown F\(x\)\-G\(\\xi,x\)\\\|^\{2\}\)\\leq\\sigma\_\{0\}^\{2\}\+\\sigma\_\{1\}^\{2\}\\\|\\bigtriangledown F\(x\)\\\|^\{2\}for someσ0,σ1∈\[0,\+∞\)\\sigma\_\{0\},\\sigma\_\{1\}\\in\[0,\+\\infty\)\. Then𝔼ξ​\(‖G​\(ξ,x\)‖2\)≤2​σ02\+\(2\+2​σ12\)​‖▽F​\(x\)‖2\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(\\\|G\(\\xi,x\)\\\|^\{2\}\)\\leq 2\\sigma\_\{0\}^\{2\}\+\(2\+2\\sigma\_\{1\}^\{2\}\)\\\|\\bigtriangledown F\(x\)\\\|^\{2\}\.

Proof:By inequality\(a\+b\)2≤2​\(a2\+b2\)\(a\+b\)^\{2\}\\leq 2\(a^\{2\}\+b^\{2\}\), we have

∥G\(ξ,x\)∥2≤2∥G\(ξ,x\)−▽F\(x\)∥2\+2∥▽F\(x\)∥2\.\\displaystyle\\\|G\(\\xi,x\)\\\|^\{2\}\\leq 2\\\|G\(\\xi,x\)\-\\bigtriangledown F\(x\)\\\|^\{2\}\+2\\\|\\bigtriangledown F\(x\)\\\|^\{2\}\.\(9\)Therefore,

𝔼ξ​\(‖G​\(ξ,x\)‖2\)\\displaystyle\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(\\\|G\(\\xi,x\)\\\|^\{2\}\)≤\\displaystyle\\leq𝔼\(2∥G\(ξ,x\)−▽F\(x\)∥2\+2∥▽F\(x\)∥2\)\\displaystyle\\bf\\rm\\mathbb\{E\}\(2\\\|G\(\\xi,x\)\-\\bigtriangledown F\(x\)\\\|^\{2\}\+2\\\|\\bigtriangledown F\(x\)\\\|^\{2\}\)=\\displaystyle=2𝔼\(∥G\(ξ,x\)−▽F\(x\)∥2\)\+2∥▽F\(x\)∥2\\displaystyle 2\\bf\\rm\\mathbb\{E\}\(\\\|G\(\\xi,x\)\-\\bigtriangledown F\(x\)\\\|^\{2\}\)\+2\\\|\\bigtriangledown F\(x\)\\\|^\{2\}≤\\displaystyle\\leq2​\(σ02\+σ12​‖▽F​\(x\)‖2\)\+2​‖▽F​\(x\)‖2\\displaystyle 2\(\\sigma\_\{0\}^\{2\}\+\\sigma\_\{1\}^\{2\}\\\|\\bigtriangledown F\(x\)\\\|^\{2\}\)\+2\\\|\\bigtriangledown F\(x\)\\\|^\{2\}=\\displaystyle=2​σ02\+\(2\+2​σ12\)​‖▽F​\(x\)‖2\.\\displaystyle 2\\sigma\_\{0\}^\{2\}\+\(2\+2\\sigma\_\{1\}^\{2\}\)\\\|\\bigtriangledown F\(x\)\\\|^\{2\}\.

### 7\.2A Static Gradient Method

We give a static gradient descent algorithm in this section\. The learning rate is computed based on one of the parameters\.

###### Definition 16

A gradient descent method isarithmetically simpleif the operations are limited to\+,−,×\+,\-,\\times, and divisionx/yx/ywithy=2ty=2^\{t\}for some integertt\.

We present a version of SGD that is arithmetically simple\. When the stochastic gradient oracleG​\(⋅\)G\(\\cdot\)is treated as a black box, the algorithm requires neither floating\-point division nor square\-root computations\.

AlgorithmSGD\(G\(\.,\.\),η,x0,t,T\)\(G\(\.,\.\),\\eta,x\_\{0\},t,T\)

Input:

- •G​\(ξ,x\):ℝm→ℝG\(\\xi,x\):\\mathbb\{R\}^\{m\}\\rightarrow\\mathbb\{R\}is an stochastic approximation for▽F​\(x\)\\bigtriangledown F\(x\),
- •η∈\(0,\+∞\)\\eta\\in\(0,\+\\infty\),
- •x0∈ℝmx\_\{0\}\\in\\mathbb\{R\}^\{m\}is the start point,
- •ttis an integer to control rate,
- •TTis for the number of steps

Steps:

1. 1\.Letx1=x0x\_\{1\}=x\_\{0\}
2. 2\.Letst=2ts\_\{t\}=2^\{t\}
3. 3\.Letj=1j=1
4. 4\.Repeat
5. 5\.\{\\\{
6. 6\.Letxj\+1=xj−ηst⋅G​\(ξj,xj\)x\_\{j\+1\}=x\_\{j\}\-\\frac\{\\eta\}\{s\_\{t\}\}\\cdot G\(\\xi\_\{j\},x\_\{j\}\)
7. 7\.Letj=j\+1j=j\+1
8. 8\.\}\\\}
9. 9\.Untilj\>Tj\>T

End of Algorithm

### 7\.3Convergence at\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)\-Stochastic Model

The convergence of the algorithm at\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)\-Stochastic Model is proven in this section\. Witht=⌈⌈log2⁡T⌉/2⌉t=\\left\\lceil\\left\\lceil\\log\_\{2\}T\\right\\rceil/2\\right\\rceil, it converges to a stationary point with rateΩ​\(1T\)\\Omega\\left\(\\frac\{1\}\{\\sqrt\{T\}\}\\right\)\.

Lemma[17](https://arxiv.org/html/2607.28902#Thmtheoremfoo17)derives an upper bound by summing the inequalities in Lemma[13](https://arxiv.org/html/2607.28902#Thmtheoremfoo13)for the gradient method\. It then follows that at least one iterate generated by SGD\(\.\) has a gradient whose expected norm is close to zero\.

###### Lemma 17

AssumeF​\(x\)F\(x\)isLL\-Lipschitz smooth andG​\(ξ,x\)G\(\\xi,x\)satifies the condition in Definition[14](https://arxiv.org/html/2607.28902#Thmtheoremfoo14)\. Then

∑j=1T𝔼​\(η​λst​‖▽F​\(xj\)‖2\)−η2​L2​st2​∑j=1T𝔼​\(‖G​\(ξj,xj\)‖2\)≤F​\(x1\)−F​\(x∗\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\(\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)

Proof:AsF​\(x\)F\(x\)isLL\-Lipschitz smooth, by Lemma[13](https://arxiv.org/html/2607.28902#Thmtheoremfoo13), we have

F​\(xj\+1\)\\displaystyle F\(x\_\{j\+1\}\)≤\\displaystyle\\leqF​\(xj\)\+\(▽F​\(xj\),xj\+1−xj\)\+L2​‖xj\+1−xj‖2\\displaystyle F\(x\_\{j\}\)\+\(\\bigtriangledown F\(x\_\{j\}\),x\_\{j\+1\}\-x\_\{j\}\)\+\\frac\{L\}\{2\}\\\|x\_\{j\+1\}\-x\_\{j\}\\\|^\{2\}=\\displaystyle=F​\(xj\)−ηst​⟨▽F​\(xj\),G​\(ξj,xj\)⟩\+L2​‖xj\+1−xj‖2\\displaystyle F\(x\_\{j\}\)\-\\frac\{\\eta\}\{s\_\{t\}\}\\langle\\bigtriangledown F\(x\_\{j\}\),G\(\\xi\_\{j\},x\_\{j\}\)\\rangle\+\\frac\{L\}\{2\}\\\|x\_\{j\+1\}\-x\_\{j\}\\\|^\{2\}≤\\displaystyle\\leqF\(xj\)−ηst⟨▽F\(xj\),G\(ξj,xj\)⟩\+η2​L2​st2∥G\(ξj,xj\)⟩∥2\\displaystyle F\(x\_\{j\}\)\-\\frac\{\\eta\}\{s\_\{t\}\}\\langle\\bigtriangledown F\(x\_\{j\}\),G\(\\xi\_\{j\},x\_\{j\}\)\\rangle\+\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\rangle\\\|^\{2\}≤\\displaystyle\\leqF\(xj\)−η​λst\(∥▽F\(xj\)∥2\+η2​L2​st2∥G\(ξj,xj\)∥2\(byCondition[i](https://arxiv.org/html/2607.28902#S7.I2.i1)inDefinition[14](https://arxiv.org/html/2607.28902#Thmtheoremfoo14)\)\\displaystyle F\(x\_\{j\}\)\-\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\+\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\\|^\{2\}\\ \\ \\ \(by\\ Condition~\\ref\{condition1\-def\}\\ in\\ Definition~\\ref\{condition\}\)
Thus,

\(η​λst\(∥▽F\(xj\)∥2\)−η2​L2​st2∥G\(ξj,xj\)∥2≤F\(xj\)−F\(xj\+1\)\.\\displaystyle\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\\|^\{2\}\\leq F\(x\_\{j\}\)\-F\(x\_\{j\+1\}\)\.
We have

∑j=1T𝔼\(η​λst∥▽F\(xj\)∥2\)−∑j=1T𝔼\(η2​L2​st2\(∥G\(ξj,xj\)∥2\)≤F\(x1\)−F\(x∗\)\.\\displaystyle\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\(\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\(\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\.Thus,

∑j=1T𝔼​\(η​λst​‖▽F​\(xj\)‖2\)−η2​L2​st2​∑j=1T𝔼​\(‖G​\(ξj,xj\)‖2\)≤F​\(x1\)−F​\(x∗\)\.\\displaystyle\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\(\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\.
Lemma[18](https://arxiv.org/html/2607.28902#Thmtheoremfoo18)shows that one of the iterates generated by SGD\(\.\) has a gradient whose expected norm is close to zero\. Consequently, SGD\(\.\) converges to a stationary point\.

###### Lemma 18

AssumeF​\(x\)F\(x\)isLL\-Lipschitz\-smooth andG​\(ξ,x\)G\(\\xi,x\)satisfies the condition in Definition[14](https://arxiv.org/html/2607.28902#Thmtheoremfoo14)\. Assume thatst∈\[T,4​T\]s\_\{t\}\\in\[\\sqrt\{T\},4\\sqrt\{T\}\]andTTsatisfy the conditions:

η​L​\(1\+σ12\)st​λ\\displaystyle\\frac\{\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{s\_\{t\}\\lambda\}≤\\displaystyle\\leq12\\displaystyle\\frac\{1\}\{2\}\(10\)Thenmini⁡𝔼​\(‖▽F​\(xi\)‖2\)≤U​\(η,σ0,λ,L\)T\\min\_\{i\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{i\}\)\\\|^\{2\}\)\\leq\\frac\{U\(\\eta,\\sigma\_\{0\},\\lambda,L\)\}\{\\sqrt\{T\}\}, where

U​\(η,σ0,λ,L\)=max⁡\(\(2​σ02​η​Lλ\),\(4η​λ​\(F​\(x0\)−F​\(x∗\)\)\+2​η​σ02​Lλ\)\)\.\\displaystyle U\(\\eta,\\sigma\_\{0\},\\lambda,L\)=\\max\\left\(\\left\(\\frac\{2\\sigma\_\{0\}^\{2\}\\eta L\}\{\\lambda\}\\right\),\\left\(\\frac\{4\}\{\\eta\\lambda\}\(F\(x\_\{0\}\)\-F\(x^\{\*\}\)\)\+\\frac\{2\\eta\\sigma\_\{0\}^\{2\}L\}\{\\lambda\}\\right\)\\right\)\.\(11\)

Proof:By Lemma[17](https://arxiv.org/html/2607.28902#Thmtheoremfoo17), we have

∑j=1T𝔼​\(η​\(λ\)st​‖▽F​\(xj\)‖2\)−η2​L2​st2​∑j=1T𝔼​\(‖G​\(ξj,xj\)‖2\)≤F​\(x1\)−F​\(x∗\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\\left\(\\frac\{\\eta\(\\lambda\)\}\{s\_\{t\}\}\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\(\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)
By Lemma[15](https://arxiv.org/html/2607.28902#Thmtheoremfoo15), we have

∑j=1T𝔼​\(η​λst​‖▽F​\(xj\)‖2\)−∑j=1Tη2​L2​st2​𝔼​\(2​σ02\+\(2\+2​σ12\)​‖▽F​\(x\)‖2\)≤F​\(x1\)−F​\(x∗\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\sum\_\{j=1\}^\{T\}\\frac\{\\eta^\{2\}L\}\{2s\_\{t\}^\{2\}\}\\bf\\rm\\mathbb\{E\}\(2\\sigma\_\{0\}^\{2\}\+\(2\+2\\sigma\_\{1\}^\{2\}\)\\\|\\bigtriangledown F\(x\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)
∑j=1Tη​λst​\(1−η​L​\(1\+σ12\)st​λ\)​𝔼​\(‖▽F​\(xj\)‖2\)−∑j=1Tη2​σ02​Lst2≤F​\(x1\)−F​\(x∗\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\left\(1\-\\frac\{\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{s\_\{t\}\\lambda\}\\right\)\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\-\\sum\_\{j=1\}^\{T\}\\frac\{\\eta^\{2\}\\sigma\_\{0\}^\{2\}L\}\{s\_\{t\}^\{2\}\}\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)
∑j=1T\(η​λ2​st𝔼\(∥▽F\(xj\)∥2−η2​σ02​Lst2\)≤F\(x1\)−F\(x∗\)\(byinequality\([10](https://arxiv.org/html/2607.28902#S7.E10)\)\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\left\(\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\-\\frac\{\\eta^\{2\}\\sigma\_\{0\}^\{2\}L\}\{s\_\{t\}^\{2\}\}\\right\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\\ \\ \\ \(by~inequality~\(\\ref\{first0\-ineqn\}\)\)
Case 1: There is ajjsuch that

\(η​λ2​st𝔼\(∥F\(xj\)∥2\)−η2​σ02​Lst2≤0\\displaystyle\\left\(\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\bf\\rm\\mathbb\{E\}\(\\\|F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\frac\{\\eta^\{2\}\\sigma\_\{0\}^\{2\}L\}\{s\_\{t\}^\{2\}\}\\leq 0We have

𝔼​\(‖▽F​\(xj\)‖2\)≤2​σ02​η​Lst​λ≤2​σ02​η​Lλ​T\.\\displaystyle\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{2\\sigma\_\{0\}^\{2\}\\eta L\}\{s\_\{t\}\\lambda\}\\leq\\frac\{2\\sigma\_\{0\}^\{2\}\\eta L\}\{\\lambda\\sqrt\{T\}\}\.
Case 2\. Case 1 is not satisfied\. In this case we have for alljj:

\(η​λ2​st𝔼\(∥▽F\(xj\)∥2\)−σ02​η2​Lst2\>0\\displaystyle\\left\(\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\frac\{\\sigma\_\{0\}^\{2\}\\eta^\{2\}L\}\{s\_\{t\}^\{2\}\}\>0
We have

∑j=1Tη​λ2​st​𝔼​\(‖▽F​\(xj\)‖2\)−∑j=1Tσ02​η2​Lst2≤F​\(x1\)−F​\(x∗\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\-\\sum\_\{j=1\}^\{T\}\\frac\{\\sigma\_\{0\}^\{2\}\\eta^\{2\}L\}\{s\_\{t\}^\{2\}\}\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)
∑j=1Tη​λ2​st​𝔼​\(‖▽F​\(xj\)‖2\)−σ02​η2​LTst2≤F​\(x1\)−F​\(x∗\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\-\\frac\{\\sigma\_\{0\}^\{2\}\\eta^\{2\}LT\}\{s\_\{t\}^\{2\}\}\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)
η​λ2​st⋅T​min1≤j≤T⁡𝔼​\(‖▽F​\(xj\)‖2\)\\displaystyle\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\cdot T\\min\_\{1\\leq j\\leq T\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)≤\\displaystyle\\leq∑j=1Tη​λ2​st​𝔼​\(‖▽F​\(xj\)‖2\)\\displaystyle\\sum\_\{j=1\}^\{T\}\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)≤\\displaystyle\\leq\(F​\(x1\)−F​\(x∗\)\)\+σ02​η2​L​Tst2\.\\displaystyle\(F\(x\_\{1\}\)\-F\(x^\{\*\}\)\)\+\\frac\{\\sigma\_\{0\}^\{2\}\\eta^\{2\}LT\}\{s\_\{t\}^\{2\}\}\.
We have

min1≤j≤T⁡𝔼​\(‖▽F​\(xj\)‖2\)≤stT​η​λ​\(F​\(x1\)−F​\(x∗\)\)\+2​η​σ02​Lst​λ\\displaystyle\\min\_\{1\\leq j\\leq T\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{s\_\{t\}\}\{T\\eta\\lambda\}\\left\(F\(x\_\{1\}\)\-F\(x^\{\*\}\)\\right\)\+\\frac\{2\\eta\\sigma\_\{0\}^\{2\}L\}\{s\_\{t\}\\lambda\}≤\\displaystyle\\leq4T​η​λ​\(F​\(x1\)−F​\(x∗\)\)\+2​η​σ02​LT​λ\\displaystyle\\frac\{4\}\{\\sqrt\{T\}\\eta\\lambda\}\(F\(x\_\{1\}\)\-F\(x^\{\*\}\)\)\+\\frac\{2\\eta\\sigma\_\{0\}^\{2\}L\}\{\\sqrt\{T\}\\lambda\}≤\\displaystyle\\leq1T​\(4η​λ​\(F​\(x1\)−F​\(x∗\)\)\+2​η​σ02​Lλ\)\\displaystyle\\frac\{1\}\{\\sqrt\{T\}\}\\left\(\\frac\{4\}\{\\eta\\lambda\}\(F\(x\_\{1\}\)\-F\(x^\{\*\}\)\)\+\\frac\{2\\eta\\sigma\_\{0\}^\{2\}L\}\{\\lambda\}\\right\)=\\displaystyle=1T​\(4η​λ​\(F​\(x0\)−F​\(x∗\)\)\+2​η​σ02​Lλ\)\.\\displaystyle\\frac\{1\}\{\\sqrt\{T\}\}\\left\(\\frac\{4\}\{\\eta\\lambda\}\(F\(x\_\{0\}\)\-F\(x^\{\*\}\)\)\+\\frac\{2\\eta\\sigma\_\{0\}^\{2\}L\}\{\\lambda\}\\right\)\.
AssumeF\(\.\)F\(\.\)and it stochastic gradientG​\(ξ,x\)G\(\\xi,x\)satisfy the conditions in Definition[14](https://arxiv.org/html/2607.28902#Thmtheoremfoo14)\. Theorem[19](https://arxiv.org/html/2607.28902#Thmtheoremfoo19)shows that the gradient descent algorithm SGD\(\.\) converges to a stationary point at rateΩ​\(1T\)\\Omega\\left\(\\frac\{1\}\{\\sqrt\{T\}\}\\right\)\.

###### Theorem 19

SupposeF\(\.\)F\(\.\)is inℂL1\\mathbb\{C\}\_\{L\}^\{1\}andinfxF​\(x\)\>−∞\\inf\_\{x\}F\(x\)\>\-\\infty\. FunctionG​\(ξ,x\)G\(\\xi,x\)satisfies the conditions in Definition[14](https://arxiv.org/html/2607.28902#Thmtheoremfoo14)\. Assume that integersTTandttsatisfy the conditions

T\\displaystyle T≥\\displaystyle\\geq\(2​η​L​\(1\+σ12\)λ\)2\\displaystyle\\left\(\\frac\{2\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{\\lambda\}\\right\)^\{2\}\(12\)t\\displaystyle t=\\displaystyle=⌈⌈log2⁡T⌉/2⌉\.\\displaystyle\\left\\lceil\\left\\lceil\\log\_\{2\}T\\right\\rceil/2\\right\\rceil\.\(13\)Then the algorithm SGD\(G\(\.,\.\),η,x0,t,T\)\(G\(\.,\.\),\\eta,x\_\{0\},t,T\)is arithmetically simple and hasmin1≤i≤T⁡𝔼​\(‖▽F​\(xi\)‖2\)≤U​\(η,σ0,λ,L\)T\\min\_\{1\\leq i\\leq T\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{i\}\)\\\|^\{2\}\)\\leq\\frac\{U\(\\eta,\\sigma\_\{0\},\\lambda,L\)\}\{\\sqrt\{T\}\}, whereU\(\.\)U\(\.\)is given at equation \([11](https://arxiv.org/html/2607.28902#S7.E11)\)\.

Proof:LetTTbe the number of steps to run\. We selecta=⌈log2⁡T⌉a=\\left\\lceil\\log\_\{2\}T\\right\\rceil, which is the number of bits ifTTis in binary format \(for example, number77has binary format111111, and⌈log2⁡7⌉=3\\left\\lceil\\log\_\{2\}7\\right\\rceil=3\)\. We haveT≤2a≤2​TT\\leq 2^\{a\}\\leq 2T\. Lett=⌈a2⌉≤a2\+1t=\\left\\lceil\\frac\{a\}\{2\}\\right\\rceil\\leq\\frac\{a\}\{2\}\+1\. We haveT≤2a2≤2t≤2​2a≤2​2​T<4​T\\sqrt\{T\}\\leq 2^\{\\frac\{a\}\{2\}\}\\leq 2^\{t\}\\leq 2\\sqrt\{2^\{a\}\}\\leq 2\\sqrt\{2T\}<4\\sqrt\{T\}\. Thus,st=2t∈\[T,4​T\]s\_\{t\}=2^\{t\}\\in\[\\sqrt\{T\},4\\sqrt\{T\}\]\. With the conditionT≥\(2​η​L​\(1\+σ12\)λ\)2T\\geq\\left\(\\frac\{2\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{\\lambda\}\\right\)^\{2\}, we havest≥T≥\(2​η​L​\(1\+σ12\)λ\)s\_\{t\}\\geq\\sqrt\{T\}\\geq\\left\(\\frac\{2\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{\\lambda\}\\right\)\. So, inequality \([10](https://arxiv.org/html/2607.28902#S7.E10)\) is satisfied\.

Run GD\(G\(\.\),η,x0,t,T\)\(G\(\.\),\\eta,x\_\{0\},t,T\)\. We havemin1≤i≤T⁡𝔼​\(‖▽F​\(xi\)‖2\)≤U​\(η,σ0,λ,L\)T\\min\_\{1\\leq i\\leq T\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{i\}\)\\\|^\{2\}\)\\leq\\frac\{U\(\\eta,\\sigma\_\{0\},\\lambda,L\)\}\{\\sqrt\{T\}\}by Lemma[18](https://arxiv.org/html/2607.28902#Thmtheoremfoo18)\.

AlgorithmStatic1\-SGD\(x0,T\)\(x\_\{0\},T\)

Input:

- •x0x\_\{0\}is the start point
- •TTis the number of iterations

Steps:

1. 1\.Assign tottas equation \([13](https://arxiv.org/html/2607.28902#S7.E13)\)
2. 2\.SGD\(G\(\.,\.\),η,x0,t,T\)\(G\(\.,\.\),\\eta,x\_\{0\},t,T\)

End of Algorithm

###### Corollary 20

Letδ∈\(0,1\)\\delta\\in\(0,1\)\. SupposeF\(\.\)F\(\.\)is inℂL1\\mathbb\{C\}\_\{L\}^\{1\}andinfxF​\(x\)\>−∞\\inf\_\{x\}F\(x\)\>\-\\infty\. FunctionG​\(ξ,x\)G\(\\xi,x\)satisfies the conditions in Definition[14](https://arxiv.org/html/2607.28902#Thmtheoremfoo14)\. AssumeTTsatisfies \([12](https://arxiv.org/html/2607.28902#S7.E12)\)\. Then with probability at least1−δ1\-\\delta, the algorithm Static1\-SGD\(G\(\.,\.\),η,x0,t,T\)\(G\(\.,\.\),\\eta,x\_\{0\},t,T\)is arithmetically simple and hasmini⁡\(‖▽F​\(xi\)‖2\)≤U​\(η,σ0,λ,L\)δ​T\\min\_\{i\}\(\\\|\\bigtriangledown F\(x\_\{i\}\)\\\|^\{2\}\)\\leq\\frac\{U\(\\eta,\\sigma\_\{0\},\\lambda,L\)\}\{\\delta\\sqrt\{T\}\}\.

Proof:It follows Theorem[19](https://arxiv.org/html/2607.28902#Thmtheoremfoo19)and Markov inequalityProb​\(X≥𝔼​\(X\)δ\)≤δ\\rm Prob\(X\\geq\\frac\{\\bf\\rm\\mathbb\{E\}\(X\)\}\{\\delta\}\)\\leq\\delta\. The proof of Theorem[19](https://arxiv.org/html/2607.28902#Thmtheoremfoo19)also shows thatttis computed via a arithmetically simple way\.

### 7\.4Faster Convergence in\(λ,0,σ1\)\(\\lambda,0,\\sigma\_\{1\}\)Stochastic Model

In this section we show a faster adaptive gradient descent analysis in\(λ,0,σ1\)\(\\lambda,0,\\sigma\_\{1\}\)stochastic Model\. It is convergence rate is almost linear, and faster than the general\(λ,σ0,σ1\)\(\\lambda,\\sigma\_\{0\},\\sigma\_\{1\}\)stochastic Model\.

###### Definition 21

A\(λ,0,σ1\)\(\\lambda,0,\\sigma\_\{1\}\)\-stochastic gradientG​\(ξ,x\)G\(\\xi,x\)forF​\(x\):ℝm→ℝF\(x\):\\mathbb\{R\}^\{m\}\\rightarrow\\mathbb\{R\}is thatξ\\xiis a random variable andG​\(ξ,x\)G\(\\xi,x\)is an approximation for▽F​\(x\)\\bigtriangledown F\(x\)satisfying the conditions:

1. i\.⟨𝔼ξ​\(G​\(ξ,x\)\),▽F​\(x\)⟩≥λ​‖▽F​\(x\)‖2\\langle\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(G\(\\xi,x\)\),\\bigtriangledown F\(x\)\\rangle\\geq\\lambda\\\|\\bigtriangledown F\(x\)\\\|^\{2\}for someλ∈\(0,\+∞\)\\lambda\\in\(0,\+\\infty\), and
2. ii\.𝔼ξ​\(‖▽F​\(x\)−G​\(ξ,x\)‖2\)≤σ12​‖▽F​\(x\)‖2\\bf\\rm\\mathbb\{E\}\_\{\\xi\}\(\\\|\\bigtriangledown F\(x\)\-G\(\\xi,x\)\\\|^\{2\}\)\\leq\\sigma\_\{1\}^\{2\}\\\|\\bigtriangledown F\(x\)\\\|^\{2\}for someσ1∈\[0,\+∞\)\\sigma\_\{1\}\\in\[0,\+\\infty\)\.

###### Lemma 22

AssumeF​\(x\)F\(x\)isLL\-smooth andG​\(ξ,x\)G\(\\xi,x\)satisfies the condition in Definition[21](https://arxiv.org/html/2607.28902#Thmtheoremfoo21)\. AssumeTTandsts\_\{t\}satisfy the following conditions:

2​η​\(2\+2​σ12\)​Lst​λ\\displaystyle\\frac\{2\\eta\(2\+2\\sigma\_\{1\}^\{2\}\)L\}\{s\_\{t\}\\lambda\}≤\\displaystyle\\leq12\\displaystyle\\frac\{1\}\{2\}\(14\)Then

min1≤j≤T⁡𝔼​\(‖▽F​\(xj\)‖2\)≤2​stT​η​λ​\(F​\(x0\)−F​\(x∗\)\)\.\\displaystyle\\min\_\{1\\leq j\\leq T\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{2s\_\{t\}\}\{T\\eta\\lambda\}\(F\(x\_\{0\}\)\-F\(x^\{\*\}\)\)\.

Proof:By Lemma[17](https://arxiv.org/html/2607.28902#Thmtheoremfoo17), we have

∑j=1T𝔼​\(η​λst​‖▽F​\(xj\)‖2\)−2​η2​Lst2​∑j=1T𝔼​\(‖G​\(ξj,xj\)‖2\)≤F​\(x1\)−F​\(x∗\)\.\\displaystyle\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\frac\{2\\eta^\{2\}L\}\{s\_\{t\}^\{2\}\}\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\(\\\|G\(\\xi\_\{j\},x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\.By Lemma[15](https://arxiv.org/html/2607.28902#Thmtheoremfoo15), we have

∑j=1T𝔼​\(η​λst​‖▽F​\(xj\)‖2\)−∑j=1T2​η2​Lst2​\(\(2\+2​σ12\)​‖▽F​\(xj\)‖2\)≤F​\(x1\)−F​\(x∗\)\.\\displaystyle\\sum\_\{j=1\}^\{T\}\\bf\\rm\\mathbb\{E\}\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\-\\sum\_\{j=1\}^\{T\}\\frac\{2\\eta^\{2\}L\}\{s\_\{t\}^\{2\}\}\(\(2\+2\\sigma\_\{1\}^\{2\}\)\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\.
∑j=1T\(η​λst−2​η2​\(2\+2​σ12\)​Lst2\)​𝔼​\(‖▽F​\(xj\)‖2\)≤F​\(x1\)−F​\(x∗\)\.\\displaystyle\\sum\_\{j=1\}^\{T\}\\left\(\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\-\\frac\{2\\eta^\{2\}\(2\+2\\sigma\_\{1\}^\{2\}\)L\}\{s\_\{t\}^\{2\}\}\\right\)\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\.
∑j=1Tη​λst​\(1−2​η​\(2\+2​σ12\)​Lst​λ\)​𝔼​\(‖▽F​\(xj\)‖2\)≤F​\(x1\)−F​\(x∗\)\.\\displaystyle\\sum\_\{j=1\}^\{T\}\\frac\{\\eta\\lambda\}\{s\_\{t\}\}\\left\(1\-\\frac\{2\\eta\(2\+2\\sigma\_\{1\}^\{2\}\)L\}\{s\_\{t\}\\lambda\}\\right\)\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\.
By inequality \([14](https://arxiv.org/html/2607.28902#S7.E14)\), we have

∑j=1T\(η​λ2​st𝔼\(∥▽F\(xj\)∥2\)≤F\(x1\)−F\(x∗\)\.\\displaystyle\\sum\_\{j=1\}^\{T\}\\left\(\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\\right\)\\leq F\(x\_\{1\}\)\-F\(x^\{\*\}\)\.
We have

T⋅\(η​λ2​st\)​minj⁡𝔼​\(‖▽F​\(xj\)‖2\)≤∑j=1T\(η2​st\)​𝔼​\(‖▽F​\(xj\)‖2\)≤\(F​\(x1\)−F​\(x∗\)\)\.\\displaystyle T\\cdot\\left\(\\frac\{\\eta\\lambda\}\{2s\_\{t\}\}\\right\)\\min\_\{j\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\sum\_\{j=1\}^\{T\}\(\\frac\{\\eta\}\{2s\_\{t\}\}\)\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\(F\(x\_\{1\}\)\-F\(x^\{\*\}\)\)\.
This brings inequality

min1≤j≤T⁡𝔼​\(‖▽F​\(xj\)‖2\)≤2​stT​η​λ​\(F​\(x1\)−F​\(x∗\)\)=2​stT​η​λ​\(F​\(x0\)−F​\(x∗\)\)\.\\displaystyle\\min\_\{1\\leq j\\leq T\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{2s\_\{t\}\}\{T\\eta\\lambda\}\(F\(x\_\{1\}\)\-F\(x^\{\*\}\)\)=\\frac\{2s\_\{t\}\}\{T\\eta\\lambda\}\(F\(x\_\{0\}\)\-F\(x^\{\*\}\)\)\.
AssumeF\(\.\)F\(\.\)and it stochastic gradientG​\(ξ,x\)G\(\\xi,x\)satisfy the conditions in Definition[21](https://arxiv.org/html/2607.28902#Thmtheoremfoo21)\. Theorem[23](https://arxiv.org/html/2607.28902#Thmtheoremfoo23)shows that the gradient descent algorithm SGD\(\.\) converges to a stationary point at rateΩ​\(1T1−β0\)\\Omega\\left\(\\frac\{1\}\{T^\{1\-\\beta\_\{0\}\}\}\\right\)for anyβ0∈\(0,1\)\\beta\_\{0\}\\in\(0,1\)\. The parameterttdepends on parameterβ0\\beta\_\{0\}\.

###### Theorem 23

Letβ0∈\(0,1\)\\beta\_\{0\}\\in\(0,1\)\. SupposeF\(\.\)F\(\.\)is inℂL1\\mathbb\{C\}\_\{L\}^\{1\}andinfxF​\(x\)\>−∞\\inf\_\{x\}F\(x\)\>\-\\infty\. FunctionG​\(ξ,x\)G\(\\xi,x\)satisfies the conditions in Definition[21](https://arxiv.org/html/2607.28902#Thmtheoremfoo21)\. Assume

T\\displaystyle T≥\\displaystyle\\geq\(2​η​L​\(1\+σ12\)λ\)1β0\\displaystyle\\left\(\\frac\{2\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{\\lambda\}\\right\)^\{\\frac\{1\}\{\\beta\_\{0\}\}\}\(15\)t\\displaystyle t=\\displaystyle=⌈⌈log2⁡T⌉⋅β0⌉\.\\displaystyle\\left\\lceil\\left\\lceil\\log\_\{2\}T\\right\\rceil\\cdot\\beta\_\{0\}\\right\\rceil\.\(16\)Then the algorithm SGD\(G\(\.,\.\),η,x0,t,T\)\(G\(\.,\.\),\\eta,x\_\{0\},t,T\)is arithmetically simple and has

min1≤j≤T⁡𝔼​\(‖▽F​\(xj\)‖2\)≤V​\(η,λ,L\)T1−β0,\\displaystyle\\min\_\{1\\leq j\\leq T\}\\bf\\rm\\mathbb\{E\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{V\(\\eta,\\lambda,L\)\}\{T^\{1\-\\beta\_\{0\}\}\},\(17\)
whereV​\(η,λ,L\)=8η​λ​\(F​\(x0\)−F​\(x∗\)\)V\(\\eta,\\lambda,L\)=\\frac\{8\}\{\\eta\\lambda\}\(F\(x\_\{0\}\)\-F\(x^\{\*\}\)\)\.

Proof:LetTTbe the number of steps to run\. We selecta=⌈log2⁡T⌉a=\\left\\lceil\\log\_\{2\}T\\right\\rceil\. We haveT≤2a≤2​TT\\leq 2^\{a\}\\leq 2T\. Lett=⌈a​β0⌉≤a​β0\+1t=\\left\\lceil a\\beta\_\{0\}\\right\\rceil\\leq\{a\\beta\_\{0\}\}\+1\. We haveTβ0≤2a​β0≤2t≤2a​β0\+1=2⋅\(2a\)β0≤2⋅\(2​T\)β0≤4​Tβ0T^\{\\beta\_\{0\}\}\\leq 2^\{a\\beta\_\{0\}\}\\leq 2^\{t\}\\leq 2^\{a\\beta\_\{0\}\+1\}=2\\cdot\(2^\{a\}\)^\{\\beta\_\{0\}\}\\leq 2\\cdot\(2T\)^\{\\beta\_\{0\}\}\\leq 4T^\{\\beta\_\{0\}\}\. Thus,st=2t∈\[Tβ0,4​Tβ0\]s\_\{t\}=2^\{t\}\\in\[T^\{\\beta\_\{0\}\},4T^\{\\beta\_\{0\}\}\]\. With the conditionT≥\(2​η​L​\(1\+σ12\)λ\)1β0T\\geq\\left\(\\frac\{2\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{\\lambda\}\\right\)^\{\\frac\{1\}\{\\beta\_\{0\}\}\}, we havest=2t≥Tβ0≥\(2​η​L​\(1\+σ12\)λ\)s\_\{t\}=2^\{t\}\\geq T^\{\\beta\_\{0\}\}\\geq\\left\(\\frac\{2\\eta L\(1\+\\sigma\_\{1\}^\{2\}\)\}\{\\lambda\}\\right\)\. So, inequality \([14](https://arxiv.org/html/2607.28902#S7.E14)\) is satisfied\.

Run the algorithm with SGD\(G\(\.\),η,x0,t,T\)\(G\(\.\),\\eta,x\_\{0\},t,T\)\. By Lemma[22](https://arxiv.org/html/2607.28902#Thmtheoremfoo22), we get inequality \([17](https://arxiv.org/html/2607.28902#S7.E17)\)\.

AlgorithmStatic2\-SGD\(x0,T\)\(x\_\{0\},T\)

Input:

- •x0x\_\{0\}is the start point
- •TTis the number of iterations

Steps:

1. 1\.Assign tottas equation \([16](https://arxiv.org/html/2607.28902#S7.E16)\)
2. 2\.SGD\(G\(\.,\.\),η,x0,t,T\)\(G\(\.,\.\),\\eta,x\_\{0\},t,T\)

End of Algorithm

###### Corollary 24

Letδ∈\(0,1\)\\delta\\in\(0,1\)\. Letβ0∈\(0,1\)\\beta\_\{0\}\\in\(0,1\)\. SupposeF\(\.\)F\(\.\)is inℂL1\\mathbb\{C\}\_\{L\}^\{1\}andinfxF​\(x\)\>−∞\\inf\_\{x\}F\(x\)\>\-\\infty\. FunctionG​\(ξ,x\)G\(\\xi,x\)satisfies the conditions in Definition[21](https://arxiv.org/html/2607.28902#Thmtheoremfoo21)\. AssumeTTsatisfies condition \([15](https://arxiv.org/html/2607.28902#S7.E15)\)\. Then with probability at least1−δ1\-\\delta, the algorithm Static2\-SGD\(G\(\.,\.\),η,x0,t,T\)\(G\(\.,\.\),\\eta,x\_\{0\},t,T\)is arithmetically simple and has

min1≤j≤T⁡\(‖▽F​\(xj\)‖2\)≤V​\(η,λ,L\)δ​Tβ0\.\\displaystyle\\min\_\{1\\leq j\\leq T\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{V\(\\eta,\\lambda,L\)\}\{\\delta T^\{\\beta\_\{0\}\}\}\.

Proof:It follows Theorem[23](https://arxiv.org/html/2607.28902#Thmtheoremfoo23)and Markov inequalityProb​\(X≥𝔼​\(X\)δ\)≤δ\\rm Prob\(X\\geq\\frac\{\\bf\\rm\\mathbb\{E\}\(X\)\}\{\\delta\}\)\\leq\\delta\. The proof of Theorem[23](https://arxiv.org/html/2607.28902#Thmtheoremfoo23)also shows thatttis computed via a arithmetically simple way\.

### 7\.5Why Do Static Gradient Methods Need a Parallel Framework?

Theorems[19](https://arxiv.org/html/2607.28902#Thmtheoremfoo19)and[23](https://arxiv.org/html/2607.28902#Thmtheoremfoo23)require Conditions \([12](https://arxiv.org/html/2607.28902#S7.E12)\) and \([15](https://arxiv.org/html/2607.28902#S7.E15)\), respectively, to guarantee convergence\. In practice, however, the parametersLL,η\\eta, andσ1\\sigma\_\{1\}are typically unknown or difficult to estimate accurately\. Consequently, selecting an appropriate iteration budgetTTin advance is a challenging task\. Our parallel framework addresses this difficulty by allowing multiple processors to search over a geometric sequence of candidate valuesTj,iT\_\{j,i\}simultaneously until one of them satisfies the required convergence conditions\.

To illustrate the motivation, suppose a single processor tests the iteration budgets

1,,2,,22,,…,,2m,,…,1,,2,,2^\{2\},,\\ldots,,2^\{m\},,\\ldots,and assume that the smallest satisfactory choice isT=2m\+1T=2^\{m\}\+1\. Before reaching the first candidate that is at leastTT, namely2m\+12^\{m\+1\}, the processor must execute

1\+2\+⋯\+2m=2m\+1−11\+2\+\\cdots\+2^\{m\}=2^\{m\+1\}\-1iterations\. Thus, a substantial amount of computation is wasted before identifying a suitable iteration budget\. Our parallel framework significantly reduces this overhead by distributing the search across multiple processors\. Theorem[12](https://arxiv.org/html/2607.28902#Thmtheoremfoo12)establishes a nearly tight lower bound on the unavoidable gap between the target iteration budgetTTand the cumulative number of iterationsTj,i∗T\_\{j,i\}^\{\*\}executed before reaching it\.

## 8Better Adaptivity via the Parallel Framework

In this section, we apply the parallel framework to static gradient descent, thereby improving the adaptivity of the gradient descent algorithm\. Both conditions, \([12](https://arxiv.org/html/2607.28902#S7.E12)\) and \([15](https://arxiv.org/html/2607.28902#S7.E15)\), rely on choosing the parameterTTto be sufficiently large\.

###### Definition 25

LetG​D​\(x0,T\)GD\(x\_\{0\},T\)be a gradient descent method for a functionF​\(x\)F\(x\)\. The output ofG​D​\(x0,T\)GD\(x\_\{0\},T\)is the listZ=⟨x1,x2,…,x⌊T⌋⟩Z=\\langle x\_\{1\},x\_\{2\},\\ldots,x\_\{\\left\\lfloor T\\right\\rfloor\}\\ranglegenerated in its⌊T⌋\\left\\lfloor T\\right\\rflooriterations\. It is denoted byZ=G​D​\(x0,T\)Z=GD\(x\_\{0\},T\)\.

###### Definition 26

Let GD\(x0,T\)\(x\_\{0\},T\)be a gradient descent method for a functionF​\(x\)F\(x\)\. A list of elements⟨x1,x2,…,x⌊Tj,i⌋⟩\\langle x\_\{1\},x\_\{2\},\\ldots,x\_\{\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\\rangleis from Parallel\-GD\(GD\(\.\),\.\) at⟨j,i⟩\\langle j,i\\rangleif⟨x1,…,x⌊Tj,i⌋⟩\\langle x\_\{1\},\\ldots,x\_\{\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\\rangleis the output of GD\(x0,Tj,i\)\(x\_\{0\},T\_\{j,i\}\)\.

###### Proposition 27

Let GD\(x0,T\)x\_\{0\},T\)be a gradient\. Assume that Parallel\-GD\(GD\(\.\),\.\)\(GD\(\.\),\.\)has\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation\. Then for anyT≥T0T\\geq T\_\{0\}, Parallel\-GD\(GD\(\.\)\)\(GD\(\.\)\)executesG​D​\(x0,Tj,i\)GD\(x\_\{0\},T\_\{j,i\}\)satisfyingT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\.

Proof:By the condition of\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation, we haveT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\. It follows from Theorem[6](https://arxiv.org/html/2607.28902#Thmtheoremfoo6)\.

We embed the first static gradient descent to Parallel framework ans have Theorem[28](https://arxiv.org/html/2607.28902#Thmtheoremfoo28)about its convergence\. It shows that some processorjjgenerates a list of points at a stageiiconverging to a stationary points with a high probability\.

###### Theorem 28

SupposeF\(\.\)F\(\.\)is inℂL1\\mathbb\{C\}\_\{L\}^\{1\}andinfxF​\(x\)\>−∞\\inf\_\{x\}F\(x\)\>\-\\infty\. FunctionG​\(ξ,x\)G\(\\xi,x\)satisfies the conditions in Definition[21](https://arxiv.org/html/2607.28902#Thmtheoremfoo21)\. Assume thatTTsatisfies \([12](https://arxiv.org/html/2607.28902#S7.E12)\)\. Then with probability at least1−δ1\-\\delta, Parallel\-GD\(Static1\-SGD\(\.,\.\),x0,h\(\.,\.\),T0,p\)x\_\{0\},h\(\.,\.\),T\_\{0\},p\)generates⟨x1,x2,…,x⌊Tj,i⌋⟩\\langle x\_\{1\},x\_\{2\},\\ldots,x\_\{\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\\rangleat⟨j,i⟩\\langle j,i\\rangle

min1≤j≤⌊Tj,i⌋⁡\(‖▽F​\(xj\)‖2\)≤U​\(η,σ0,λ,L\)δ​T\.\\displaystyle\\min\_\{1\\leq j\\leq\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{U\(\\eta,\\sigma\_\{0\},\\lambda,L\)\}\{\\delta\\sqrt\{T\}\}\.after runningTj,i∗T\_\{j,i\}^\{\*\}iterations withT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\.

Proof:By Proposition[27](https://arxiv.org/html/2607.28902#Thmtheoremfoo27), Parallel\-GD\(Static1\-SGD\(\.,\.\),x0,h\(\.,\.\),T0,p\)x\_\{0\},h\(\.,\.\),T\_\{0\},p\)executes Static1\-SGD\(x0,Tj,i\)\(x\_\{0\},T\_\{j,i\}\)that generates⟨x1,x2,…,x⌊Tj,i⌋⟩\\langle x\_\{1\},x\_\{2\},\\ldots,x\_\{\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\\rangleat⟨j,i⟩\\langle j,i\\rangleand hasT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\. It follows from Corollary[20](https://arxiv.org/html/2607.28902#Thmtheoremfoo20)\.

We embed the gradient descent Static2\-SGD\(\.\) to Parallel framework in Theorem[29](https://arxiv.org/html/2607.28902#Thmtheoremfoo29)\. It has a faster convergence\.

###### Theorem 29

Letδ∈\(0,1\)\\delta\\in\(0,1\)\. Letβ0∈\(0,1\)\\beta\_\{0\}\\in\(0,1\)\. SupposeF\(\.\)F\(\.\)is inℂL1\\mathbb\{C\}\_\{L\}^\{1\}andinfxF​\(x\)\>−∞\\inf\_\{x\}F\(x\)\>\-\\infty\. FunctionG​\(ξ,x\)G\(\\xi,x\)satisfies the conditions in Definition[21](https://arxiv.org/html/2607.28902#Thmtheoremfoo21)\. Assume thatTTsatisfies \([15](https://arxiv.org/html/2607.28902#S7.E15)\)\. Then with probability at least1−δ1\-\\delta, Parallel\-GD\(Static2\-SGD\(\.,\.\),x0,h\(\.,\.\),T0,p\)x\_\{0\},h\(\.,\.\),T\_\{0\},p\)generates⟨x1,x2,…,x⌊Tj,i⌋⟩\\langle x\_\{1\},x\_\{2\},\\ldots,x\_\{\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\\rangleat⟨j,i⟩\\langle j,i\\rangle

min1≤j≤⌊Tj,i⌋⁡\(‖▽F​\(xj\)‖2\)≤V​\(η,λ,L\)δ​T1−β0\.\\displaystyle\\min\_\{1\\leq j\\leq\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\(\\\|\\bigtriangledown F\(x\_\{j\}\)\\\|^\{2\}\)\\leq\\frac\{V\(\\eta,\\lambda,L\)\}\{\\delta T^\{1\-\\beta\_\{0\}\}\}\.after runningTj,i∗T\_\{j,i\}^\{\*\}iterations at processjjwithT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\.

Proof:By Proposition[27](https://arxiv.org/html/2607.28902#Thmtheoremfoo27), Parallel\-GD\(Static2\-SGD\(\.,\.\),x0,h\(\.,\.\),T0,p\)x\_\{0\},h\(\.,\.\),T\_\{0\},p\)executes Static2\-SGD\(x0,Tj,i\)\(x\_\{0\},T\_\{j,i\}\)that generates⟨x1,x2,…,x⌊Tj,i⌋⟩\\langle x\_\{1\},x\_\{2\},\\ldots,x\_\{\\left\\lfloor T\_\{j,i\}\\right\\rfloor\}\\rangleat⟨j,i⟩\\langle j,i\\rangleand hasT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\. It follows from Corollary[24](https://arxiv.org/html/2607.28902#Thmtheoremfoo24)\.

The adaptivity is achieved by embedding static gradient descent into the parallel framework\. WhenTTis sufficiently large, conditions \([12](https://arxiv.org/html/2607.28902#S7.E12)\) and \([15](https://arxiv.org/html/2607.28902#S7.E15)\) are satisfied\. The parametersttandsts\_\{t\}are chosen independently ofLL,η\\eta,λ\\lambda,σ0\\sigma\_\{0\}, andσ1\\sigma\_\{1\}\. The parallel framework employs a geometric sequence, determined by the numberppof processors, to search for an appropriate value ofTT\. The step sizests\_\{t\}is then adjusted according to the selected value ofTT\.

## 9Avoiding Restarting from Scratch

In this section, we present a refined parallel framework that avoids restarting from scratch at each new stage of a processor\. Instead of always using the same initial pointx0x\_\{0\}, the next stage starts from an improved pointx0∗x\_\{0\}^\{\*\}obtained from theppprocessors, where

F​\(x0∗\)≤F​\(x0\)\.F\(x\_\{0\}^\{\*\}\)\\leq F\(x\_\{0\}\)\.In this way, the framework exploits the partial progress made during previous stages and reuses it to accelerate convergence in subsequent stages across all processors\.

This refinement requires evaluating the objective functionF​\(⋅\)F\(\\cdot\)and introduces communication among processors to identify the best current iterate\. In this section, we briefly describe this extension and discuss its potential advantages\.

### 9\.1A Refined Parallel Framework

In this subsection, we describe a refined parallel framework for gradient descent\. For an objective function of the form

F​\(x\)=∑i=1kfi​\(x\)2,F\(x\)=\\sum\_\{i=1\}^\{k\}f\_\{i\}\(x\)^\{2\},evaluating the objective functionF​\(x\)F\(x\)may take significantly longer than computing a stochastic gradient\. We therefore introduce a time parametera1a\_\{1\}to represent the computational cost of evaluatingF​\(x\)F\(x\)\.

We also introduce a parameterb1b\_\{1\}to represent the time required for a processor to access the shared tuple\(x0∗,y0∗\)\(x\_\{0\}^\{\*\},y\_\{0\}^\{\*\}\), taking into account the synchronization overhead caused by mutual exclusion\. Finally, we introduce a parameterδ\\deltato control the tradeoff between performing gradient descent iterations and searching for an iteratexix\_\{i\}satisfyingF​\(xi\)<F​\(x0∗\)\.F\(x\_\{i\}\)<F\(x\_\{0\}^\{\*\}\)\.These parameters allow the refined framework to model both computational costs and communication overhead in a parallel implementation\.

We give a description of a revised framework for gradient descent\. For a functionF​\(x\)=∑i=1kfi​\(x\)2F\(x\)=\\sum\_\{i=1\}^\{k\}f\_\{i\}\(x\)^\{2\}, it may take much longer time to computeF​\(x\)F\(x\)than to get a stochastic gradient\. We also have a parameterδ\\deltato control how many steps for iterations and how many steps to find somexix\_\{i\}withF​\(xi\)<F​\(x0∗\)F\(x\_\{i\}\)<F\(x\_\{0\}^\{\*\}\)\.

AlgorithmParallel2\-GD\(GD\(\.,\.\),x0,h\(\.,\.\),T0,p,δ\)\(GD\(\.,\.\),x\_\{0\},h\(\.,\.\),T\_\{0\},p,\\delta\)

Input:

1. 1\.GD\(x0,T\)\(x\_\{0\},T\)is a gradient descent method with start pointx0x\_\{0\}, andTTiterations\.
2. 2\.T0T\_\{0\}is the least number of steps to execute\.
3. 3\.h​\(j,i\)≥T0:ℕ×ℕ→ℕh\(j,i\)\\geq T\_\{0\}:\\mathbb\{N\}\\times\\mathbb\{N\}\\rightarrow\\mathbb\{N\}is a function to assign the number of iterations when calling a gradient descent method GD\(\.\)\.
4. 4\.h​\(T\):ℕ→ℕh\(T\):\\mathbb\{N\}\\rightarrow\\mathbb\{N\}is a function to determine how many steps will be used to run the selection function\. For example,h​\(T\)=⌊T/10⌋h\(T\)=\\left\\lfloor T/10\\right\\rfloor\.
5. 5\.x0∈ℝmx\_\{0\}\\in\\mathbb\{R\}^\{m\}is the start point\.
6. 6\.ppis the number of processors\.
7. 7\.δ∈\(0,1\)\\delta\\in\(0,1\)\.
8. 8\.\{\\\{
9. 9\.Letx0∗=x0x\_\{0\}^\{\*\}=x\_\{0\}be shared by all processors\.
10. 10\.Processorjj\(j=0,1,…,p−1j=0,1,\\ldots,p\-1\): 1. \(a\)Leti=1i=1 2. \(b\)Repeat 3. \(c\)\{\\\{ 4. \(d\)Tj,i=h​\(j,i\)T\_\{j,i\}=h\(j,i\) 5. \(e\)t=δ⋅Tj,it=\\delta\\cdot T\_\{j,i\} 6. \(f\)Z=Z=GD\(x0∗,Tj,i−t\)\(x\_\{0\}^\{\*\},T\_\{j,i\}\-t\) 7. \(g\)Select\(Z,x0∗,y0∗,F\(\.\),t\)\(Z,x\_\{0\}^\{\*\},y\_\{0\}^\{\*\},F\(\.\),t\) 8. \(h\)Leti=i\+1i=i\+1 9. \(i\)\}\\\}
11. 11\.\}\\\}

End of Algorithm

We require a selection function, denoted by Select\(\.\), that chooses one iterate from the sequencex1,x2,…,xTx\_\{1\},x\_\{2\},\\ldots,x\_\{T\}generated by executing GD\(x0,T\)\(x\_\{0\},T\)\. The parameterttspecifies the maximum number of iterates that Select\(\.\) is allowed to access\.

The following principles may be used to design Select\(\.\):

- •It accesses at mostttiterates\.
- •If an iteratexix\_\{i\}satisfyingF​\(xi\)<F​\(x0∗\)F\(x\_\{i\}\)<F\(x\_\{0\}^\{\*\}\)is found after examining a subset ofZZ, thenx0∗x\_\{0\}^\{\*\}is updated toxix\_\{i\}\.

We introduce a time parametera1a\_\{1\}to represent the time complexity of evaluatingF​\(x\)F\(x\)\. We also introduce a parameterb1b\_\{1\}to represent the time complexity of accessing the shared tuple\(x0∗,y0∗\)\(x\_\{0\}^\{\*\},y\_\{0\}^\{\*\}\)among all processors, taking mutual exclusion into account\. The selection function Select\(\.\) may invoke the following function S\(\.\) when the three parametersa1a\_\{1\},b1b\_\{1\}, andc1c\_\{1\}are available\.

AlgorithmS\(Z,x0∗,y0∗,F\(\.\),t,a1,b1,c1\)\(Z,x\_\{0\}^\{\*\},y\_\{0\}^\{\*\},F\(\.\),t,a\_\{1\},b\_\{1\},c\_\{1\}\)

Input:

- •Z=⟨x1,…,xT⟩Z=\\langle x\_\{1\},\\ldots,x\_\{T\}\\rangle
- •y0∗=F​\(x0∗\)y\_\{0\}^\{\*\}=F\(x\_\{0\}^\{\*\}\)
- •a1a\_\{1\}is the complexity for computingF​\(x\)F\(x\)\.
- •b1b\_\{1\}is the complexity for mutual exclusion access to shared memory\.
- •c1c\_\{1\}is the complexity for a few extra cost\.

Steps:

1. 1\.Letuube the largest integer witht≥u⋅a1\+b1\+c1t\\geq u\\cdot a\_\{1\}\+b\_\{1\}\+c\_\{1\}, wherea1a\_\{1\}is the time forF​\(x\)F\(x\)andb1b\_\{1\}is the time for mututal exclusion\.
2. 2\.If \(the following steps can finish inttsteps\) then \{\\\{ 1. \(a\)select some elementsxT−a1\+1,xT−a1\+2,…,xTx\_\{T\-a\_\{1\}\+1\},x\_\{T\-a\_\{1\}\+2\},\\ldots,x\_\{T\}fromZ=⟨x1,…,xT⟩Z=\\langle x\_\{1\},\\ldots,x\_\{T\}\\rangle\. 2. \(b\)letxix\_\{i\}\(T−a1\+1≤i≤T\)\(T\-a\_\{1\}\+1\\leq i\\leq T\)have the leastyi=F​\(xi\)y\_\{i\}=F\(x\_\{i\}\) 3. \(c\)If\(yi<y0∗\)\(y\_\{i\}<y\_\{0\}^\{\*\}\)let\(x0∗,y0∗\)=\(xi,yi\)\(x\_\{0\}^\{\*\},y\_\{0\}^\{\*\}\)=\(x\_\{i\},y\_\{i\}\)\(with mutual exclusion access\) \}\\\}

End of Algorithm

The purpose of line \([2\.c](https://arxiv.org/html/2607.28902#S9.I4.i2.I1.i3)\) in Select\(\.\) is to ensure thatx0∗x\_\{0\}^\{\*\}always stores the iteratexix\_\{i\}with the smallest objective valueF​\(xi\)F\(x\_\{i\}\)among all iterates generated by the processors\. Consequently, the next gradient descent phase can be initialized from the best solution found so far, rather than restarting from the initial pointx0x\_\{0\}\.

###### Proposition 30

Assume that GD\(x0,T\)x\_\{0\},T\)is a gradient descent method and has monotonic convergence rateD​\(Z\)≤H​\(x0,T\)D\(Z\)\\leq H\(x\_\{0\},T\)\. Assume that Parallel\-GD\(GD\(\.\)\)\(GD\(\.\)\)has\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation\. Then Parallel\-GD\(GD\(\.\)\)\(GD\(\.\)\)executesG​D​\(x0,\(1−δ\)​Tj,i\)GD\(x\_\{0\},\(1\-\\delta\)T\_\{j,i\}\)satisfyingT≤\(1−δ\)​Tj,i≤Tj,i≤Tj,i∗≤αp​T1−δT\\leq\(1\-\\delta\)T\_\{j,i\}\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\frac\{\\alpha\_\{p\}T\}\{1\-\\delta\}\.

Proof:By the condition of\(p,αp\)\(p,\\alpha\_\{p\}\)\-approximation, we haveT≤Tj,i≤Tj,i∗≤αp​TT\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\. LetT′=T1−δT^\{\\prime\}=\\frac\{T\}\{1\-\\delta\}\. By Theorem[6](https://arxiv.org/html/2607.28902#Thmtheoremfoo6), there isTj,iT\_\{j,i\}withT′≤Tj,i≤Tj,i∗≤αp​T′T^\{\\prime\}\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T^\{\\prime\}\. This impliesG​D​\(x0,\(1−δ\)​Tj,i\)GD\(x\_\{0\},\(1\-\\delta\)T\_\{j,i\}\)satisfyingT≤\(1−δ\)​Tj,i≤Tj,i≤Tj,i∗≤αp​T1−δT\\leq\(1\-\\delta\)T\_\{j,i\}\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\frac\{\\alpha\_\{p\}T\}\{1\-\\delta\}\.

## 10Conclusions and Future Developments

In this paper, we develop a parallel framework that transforms static gradient descent methods into adaptive ones through parallel execution\. Given a target number of iterationsTTthat may satisfy the desired convergence conditions, theppprocessors in the framework search for a suitable parameterTj,iT\_\{j,i\}according to a carefully designed geometric sequence\. The objective is to minimize the approximation factorαp\\alpha\_\{p\}while ensuring thatT≤Tj,i≤Tj,i∗≤αp​T\.T\\leq T\_\{j,i\}\\leq T\_\{j,i\}^\{\*\}\\leq\\alpha\_\{p\}T\.

Several research directions remain open\. First, it will be valuable to identify additional static gradient methods that can be incorporated into this framework\. Second, after the number of iterationsTTis determined, more effective strategies for selecting the corresponding learning rate should be investigated\. Third, the arithmetically simple gradient descent methods proposed in this paper eliminate division and square\-root operations by replacing them with binary shift operations\. Drawing on the author’s experience as an FPGA hardware engineer in the computer industry, we believe that this design is more suitable for hardware implementation and chip design\. Developing even more efficient gradient descent algorithms for specialized hardware accelerators is therefore an interesting direction for future research\.

Another interesting open problem is to close the gap between the current upper bound of44\(Corollary[7](https://arxiv.org/html/2607.28902#Thmtheoremfoo7)\) and the lower bound of22\(Theorem[10](https://arxiv.org/html/2607.28902#Thmtheoremfoo10)\) for the approximation factorα1\\alpha\_\{1\}in a\(1,α1\)\(1,\\alpha\_\{1\}\)\-approximation\. Progress on narrowing this gap for the single\-processor case may also provide new insights into closing the corresponding gap forαp\\alpha\_\{p\}whenp\>1p\>1\.

## References

- \[1\]Y\. Arjevani, Y\. Carmon, J\. C\. Duchi, D\. J\. Foster, N\. Srebro, and B\. E\. Woodworth\.Lower bounds for non\-convex stochastic optimization\.Math\. Program\., 199\(1\):165–214, 2023\.
- \[2\]D\. P\. Bertsekas and J\. N\. Tsitsiklis\.Parallel and Distributed Computation: Numerical Methods\.Prentice Hall, 1989\.
- \[3\]L\. Bottou, F\. E\. Curtis, and J\. Nocedal\.Optimization methods for large\-scale machine learning\.SIAM Rev\., 60\(2\):223–311, 2018\.
- \[4\]J\. Chen, D\. Zhou, Y\. Tang, Z\. Yang, Y\. Cao, and Q\. Gu\.Closing the generalization gap of adaptive gradient methods in training deep neural networks\.In C\. Bessiere, editor,Proceedings of the Twenty\-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 3267–3275\. ijcai\.org, 2020\.
- \[5\]A\. Cutkosky and R\. Busa\-Fekete\.Distributed stochastic optimization via adaptive sgd\.arXiv preprint arXiv:1802\.05811, 2018\.
- \[6\]J\. Dean, G\. Corrado, R\. Monga, K\. Chen, M\. Devin, et al\.Large scale distributed deep networks\.Advances in Neural Information Processing Systems, 25, 2012\.
- \[7\]A\. Défossez and F\. R\. Bach\.Adabatch: Efficient gradient aggregation rules for sequential and parallel stochastic gradient methods\.CoRR, abs/1711\.01761, 2017\.
- \[8\]J\. Duchi, E\. Hazan, and Y\. Singer\.Adaptive subgradient methods for online learning and stochastic optimization\.The Journal of Machine Learning Research, 12:2121–2159, 2011\.
- \[9\]M\. Faw, L\. Rout, C\. Caramanis, and S\. Shakkottai\.Beyond uniform smoothness: A stopped analysis of adaptive SGD\.In G\. Neu and L\. Rosasco, editors,The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12\-15 July 2023, Bangalore, India, volume 195 ofProceedings of Machine Learning Research, pages 89–160\. PMLR, 2023\.
- \[10\]S\. Ghadimi and G\. Lan\.Stochastic first\- and zeroth\-order methods for nonconvex stochastic programming\.SIAM J\. Optim\., 23\(4\):2341–2368, 2013\.
- \[11\]A\. Iacob, A\. Jovanovic, M\. Safaryan, M\. Kurmanji, L\. Sani, S\. Horvath, W\. F\. Shen, X\. Qiu, and N\. D\. Lane\.Mt\-dao: Multi\-timescale distributed adaptive optimizers with local updates\.arXiv preprint arXiv:2510\.05361, 2025\.
- \[12\]D\. P\. Kingma and J\. Ba\.Adam: A method for stochastic optimization\.arXiv:1412\.6980, 2015\.
- \[13\]G\. Lan\.First\-order and Stochastic Optimization Methods for Machine Learning\.Springer, 2020\.
- \[14\]M\. Li, D\. G\. Andersen, J\. W\. Park, A\. Smola, A\. Ahmed, et al\.Scaling distributed machine learning with the parameter server\.USENIX Symposium on Operating Systems Design and Implementation, 2014\.
- \[15\]I\. Loshchilov and F\. Hutter\.Decoupled weight decay regularization\.InInternational Conference on Learning Representations \(ICLR\), 2019\.
- \[16\]J\. N\. Léon Bottou, Frank E\. Curtis\.Optimization methods for large\-scale machine learning\.SIAM Reviews, 60\(2\):223–311, 2018\.
- \[17\]H\. B\. McMahan and M\. J\. Streeter\.Adaptive bound optimization for online convex optimization\.CoRR, abs/1002\.4908, 2010\.
- \[18\]M\. C\. Mukkamala and M\. Hein\.Variants of rmsprop and adagrad with logarithmic regret bounds\.In D\. Precup and Y\. W\. Teh, editors,Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\-11 August 2017, volume 70 ofProceedings of Machine Learning Research, pages 2545–2553\. PMLR, 2017\.
- \[19\]A\. Nemirovski, A\. Juditsky, G\. Lan, and A\. Shapiro\.Robust stochastic approximation approach to stochastic programming\.SIAM Journal on Optimization, 19:1574–1609, 2009\.
- \[20\]F\. Orabona and D\. P´al\.Scale\-free algorithms for online linear optimization\.InAlgorithmic Learning Theory\. ALT 2015\. Lecture Notes in Computer Science, vol 9355\., page 287–301, 2015\.
- \[21\]B\. Recht, C\. Re, S\. Wright, and F\. Niu\.Hogwild\!: A lock\-free approach to parallelizing stochastic gradient descent\.InAdvances in Neural Information Processing Systems, volume 24, 2011\.
- \[22\]S\. J\. Reddi, S\. Kale, and S\. Kumar\.On the convergence of adam and beyond\.In6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 \- May 3, 2018, Conference Track Proceedings\. OpenReview\.net, 2018\.
- \[23\]S\. J\. Reddi, S\. Kale, and S\. Kumar\.On the convergence of adam and beyond\.InInternational Conference on Learning Representations \(ICLR\), 2018\.
- \[24\]H\. Robbins and S\. Monro\.A stochastic approximation method\.Annuals of Mathematical Statistics, 22\(3\):400–407, 1951\.
- \[25\]C\. Tan, S\. Ma, Y\.\-H\. Dai, and Y\. Qian\.Barzilai\-borwein step size for stochastic gradient descent\.In30th Conference on Neural Information Processing Systems \(NIPS 2016\), Barcelona, Spain, pages 685–693, 2016\.
- \[26\]B\. Wang, H\. Zhang, Z\. Ma, and W\. Chen\.Convergence of adagrad for non\-convex objectives: Simple proofs and relaxed assumptions\.In G\. Neu and L\. Rosasco, editors,The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12\-15 July 2023, Bangalore, India, volume 195 ofProceedings of Machine Learning Research, pages 161–190\. PMLR, 2023\.
- \[27\]R\. Ward, X\. Wu, and L\. Bottou\.Adagrad stepsizes: Sharp convergence over nonconvex landscapes\.Journal of Machine Learning Research, 21 \(219\):1–30, 2020\.
- \[28\]Y\. Xie, X\. Wu, and R\. Ward\.Linear convergence of adaptive stochastic gradient descent\.InProceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages PMLR 108:1475–1485, 2020\.
- \[29\]M\. D\. Zeiler\.ADADELTA: an adaptive learning rate method\.CoRR, abs/1212\.5701, 2012\.