文章

Convergence Analysis of GD and SGD

作者：Mipha

发布于 2026-08-04T10:57:34Z · 公开内容更新于 2026-08-17T13:59:12Z

In this blog, we won't talk about various optimization algorithms, but focus on the two basic algorithms: Gradient Descent and Stochastic Gradient Descent. We w

Convergence of Optimization Algorithms

Mipha

(August 17, 2026)

1 Introduction

We often analyze the convergence rate of optimization algorithms from theoretical perspective. These proofs are often based on some assumptions while the practical scenarios may not satisfy these assumptions. However, these theretical analysis can still provide us some insights of the convergence in application. In this chapter, we won’t talk about various optimization algorithms, but focus on the two basic algorithms: Gradient Descent and Stochastic Gradient Descent. We will analyze the convergence of these two algorithms under different assumptions because many optimization algorithms can be viewed as extensions of these two, and the techniques used in the convergence analysis of these two algorithms can be applied to other optimization algorithms just with some subtle modifications.

References

2 Assumptions and Properties

We can often see some assumptions in the analysis of optimization algorithms in textbooks and research papers. These assumptions are often related to the properties of the objective function or variables. In this section, we will introduce some common assumptions and properties that are often used in the convergence analysis of optimization algorithms.

Assumption 1 (L-Smooth).

A function $𝑓$ is L-smooth if it is differentiable and its gradient is L-Lipschitz continuous, i.e., there exists a constant $𝐿 > 0$ such that for all $𝑥, 𝑦 \in ℝ 𝑑$ ,

‖ \nabla 𝑓 (𝑥) - \nabla 𝑓 (𝑦) ‖ 2 \leq 𝐿 ‖ 𝑥 - 𝑦 ‖ 2 .

Lemma 2 (Descent Lemma).

If $𝑓$ is L-smooth, then for all $𝑥, 𝑦 \in ℝ 𝑑$ ,

𝑓 (𝑦) \leq 𝑓 (𝑥) + \nabla 𝑓 (𝑥) 𝑇 (𝑦 - 𝑥) + 𝐿 2 ‖ 𝑦 - 𝑥 ‖ 22 .

Proposition 3 (Hessian Characterization of L-Smoothness).

A function $𝑓$ is L-smooth if and only if it is differentiable and for all $𝑥 \in ℝ 𝑑$ ,

\nabla 2 𝑓 (𝑥) ⪯ 𝐿 𝐼 .

Assumption 4 (Strongly Convex).

A function $𝑓$ is $𝜇$ -strongly convex if it is convex and there exists a constant $𝜇 > 0$ such that for all $𝑥, 𝑦 \in ℝ 𝑑$ ,

𝑓 (𝑦) \geq 𝑓 (𝑥) + \nabla 𝑓 (𝑥) 𝑇 (𝑦 - 𝑥) + 𝜇 2 ‖ 𝑦 - 𝑥 ‖ 22 .

Proposition 5 (Hessian Characterization of Strong Convexity).

A function $𝑓$ is $𝜇$ -strongly convex if and only if it is twice differentiable and for all $𝑥 \in ℝ 𝑑$ ,

\nabla 2 𝑓 (𝑥) ⪰ 𝜇 𝐼 .

All above are definitions and basic properties of L-smoothness and strongly convexity which can be viewed in many textbooks. Following we will introduce some other properties that are often used in the convergence analysis of optimization algorithms.

Proposition 6 (Convexity and L-Smoothness).

For a function $𝑓$ that is convex and L-smooth, suppose $𝑥 *$ is a minimizer of $𝑓$ , then for all $𝑥 \in ℝ 𝑑$ ,

𝑓 (𝑥) - 𝑓 (𝑥 *) \geq 1 2 𝐿 ‖ \nabla 𝑓 (𝑥) ‖ 22 .

Proposition 7 (Strongly Convexity and L-Smoothness).

For a function $𝑓$ that is $𝜇$ -strongly convex and L-smooth, suppose $𝑥 *$ is a minimizer of $𝑓$ , then for all $𝑥 \in ℝ 𝑑$ ,

𝜇 2 ‖ 𝑥 - 𝑥 * ‖ 22 \leq 𝑓 (𝑥) - 𝑓 (𝑥 *) \leq 1 2 𝜇 ‖ \nabla 𝑓 (𝑥) ‖ 22 .

Proposition 8 (co-coercivity of the gradient).

For a function $𝑓$ that is convex and L-smooth, for all $𝑥, 𝑦 \in ℝ 𝑑$ ,

⟨ \nabla 𝑓 (𝑥) - \nabla 𝑓 (𝑦), 𝑥 - 𝑦 ⟩ \geq 1 𝐿 ‖ \nabla 𝑓 (𝑥) - \nabla 𝑓 (𝑦) ‖ 22 .

Proposition 9 (strengthened co-coercivity).

For a function $𝑓$ that is $𝜇$ -strongly convex and L-smooth, for all $𝑥, 𝑦 \in ℝ 𝑑$ ,

⟨ \nabla 𝑓 (𝑥) - \nabla 𝑓 (𝑦), 𝑥 - 𝑦 ⟩ \geq 𝜇 𝐿 𝜇 + 𝐿 ‖ 𝑥 - 𝑦 ‖ 22 + 1 𝜇 + 𝐿 ‖ \nabla 𝑓 (𝑥) - \nabla 𝑓 (𝑦) ‖ 22 .

Assumption 10 (Bounded Second Moment of Stochastic Gradient).

For a function $𝑓$ that is differentiable, we assume that the stochastic gradient $𝑔 (𝑥, 𝜉)$ satisfies

𝔼 [‖ 𝑔 (𝑥, 𝜉) ‖ 22] \leq 𝐺 2,

for some constant $𝐺 > 0$ .

It is the most common assumption in the convergence analysis of stochastic gradient descent. However, it is not a realistic assumption in many practical scenarios. For example, if $𝑓$ is L-smooth, then $‖ \nabla 𝑓 (𝑥) ‖ 2$ can be arbitrarily large when $‖ 𝑥 ‖ 2$ is large. In this case, the stochastic gradient $𝑔 (𝑥, 𝜉)$ can also be arbitrarily large. Therefore, the bounded second moment assumption may not hold in practice.

Assumption 11 (Bounded Variance of Stochastic Gradient).

For a function $𝑓$ that is differentiable, we assume that the stochastic gradient $𝑔 (𝑥, 𝜉)$ satisfies

𝔼 [‖ 𝑔 (𝑥, 𝜉) - \nabla 𝑓 (𝑥) ‖ 22] \leq 𝜎 2,

for some constant $𝜎 > 0$ .

Under the assumption of bounded variance of stochastic gradient, we can derive the following bias-variance decomposition.

Proposition 12 (Bias-Variance Decomposition).

For a function $𝑓$ that is differentiable, we have

𝔼 [‖ 𝑔 (𝑥, 𝜉) ‖ 22] = ‖ \nabla 𝑓 (𝑥) ‖ 22 + 𝔼 [‖ 𝑔 (𝑥, 𝜉) - \nabla 𝑓 (𝑥) ‖ 22] .

And furthermore, if the stochastic gradient $𝑔 (𝑥, 𝜉)$ satisfies the bounded variance assumption, then we have

𝔼 [‖ 𝑔 (𝑥, 𝜉) ‖ 22] \leq ‖ \nabla 𝑓 (𝑥) ‖ 22 + 𝜎 2 .

3 Get One-step Inequalities

3.1 Smooth and Convex GD

By the update rule of GD:

𝑥 𝑡 + 1 = 𝑥 𝑡 - 𝜂 \nabla 𝑓 (𝑥 𝑡)

Expanding the squared distance to the optimal solution $𝑥 *$ :

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 = ‖ 𝑥 𝑡 - 𝜂 \nabla 𝑓 (𝑥 𝑡) - 𝑥 * ‖ 22 = ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 ⟨ \nabla 𝑓 (𝑥 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ + 𝜂 2 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22

By Proposition 8, we have

⟨ \nabla 𝑓 (𝑥 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ \geq 𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *) + 1 2 𝐿 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22

Substituting this into the previous inequality, we get

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) - 𝜂 𝐿 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝜂 2 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 = ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + (𝜂 2 - 𝜂 𝐿) ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22

Take $𝜂 = 1 𝐿$ , we have

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝐿 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) .

3.2 Smooth and Strongly Convex GD

Function Value Convergence:

By Lemma 2, we have

𝑓 (𝑥 𝑡 + 1) \leq 𝑓 (𝑥 𝑡) + \nabla 𝑓 (𝑥 𝑡) 𝑇 (𝑥 𝑡 + 1 - 𝑥 𝑡) + 𝐿 2 ‖ 𝑥 𝑡 + 1 - 𝑥 𝑡 ‖ 22

Substituting the update rule of GD into the above inequality, we get

𝑓 (𝑥 𝑡 + 1) \leq 𝑓 (𝑥 𝑡) - 𝜂 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝐿 𝜂 2 2 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 = 𝑓 (𝑥 𝑡) - (𝜂 - 𝐿 𝜂 2 2) ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22

Applying Proposition 7, we have

𝑓 (𝑥 𝑡 + 1) - 𝑓 (𝑥 *) \leq 𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *) - (𝜂 - 𝐿 𝜂 2 2) 2 𝜇 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) = (1 - 2 𝜇 𝜂 + 𝐿 𝜇 𝜂 2) (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *))

Take $𝜂 = 1 𝐿$ , we have

𝑓 (𝑥 𝑡 + 1) - 𝑓 (𝑥 *) \leq (1 - 𝜇 𝐿) (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *))

Distance Convergence: By Propositon 9, we have

⟨ \nabla 𝑓 (𝑥 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ \geq 𝜇 𝐿 𝜇 + 𝐿 ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 + 1 𝜇 + 𝐿 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 .

Take $𝜂 = 2 𝜇 + 𝐿$ , we have

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 = ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 ⟨ \nabla 𝑓 (𝑥 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ + 𝜂 2 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 4 𝜇 + 𝐿 (𝜇 𝐿 𝜇 + 𝐿 ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 + 1 𝜇 + 𝐿 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22) + 4 (𝜇 + 𝐿) 2 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 = (1 - 4 𝜇 𝐿 (𝜇 + 𝐿) 2) ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 4 (𝜇 + 𝐿) 2 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 4 (𝜇 + 𝐿) 2 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 = (1 - 4 𝜇 𝐿 (𝜇 + 𝐿) 2) ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 = (𝜇 - 𝐿 𝜇 + 𝐿) 2 ‖ 𝑥 𝑡 - 𝑥 * ‖ 22

3.3 Convex and Possibly Non-smooth SGD

The update rule of SGD is

𝑥 𝑡 + 1 = 𝑥 𝑡 - 𝜂 𝑔 (𝑥 𝑡, 𝜉 𝑡)

where $𝑔 (𝑥 𝑡, 𝜉 𝑡)$ is the stochastic gradient at $𝑥 𝑡$ with respect to the random variable $𝜉 𝑡$ . We assume that $𝑔 (𝑥 𝑡, 𝜉 𝑡)$ is an unbiased estimator of the true gradient $\nabla 𝑓 (𝑥 𝑡)$ , i.e.,

𝔼 [𝑔 (𝑥 𝑡, 𝜉 𝑡)] = \nabla 𝑓 (𝑥 𝑡)

and that the stochastic gradient is bounded, i.e. Assumption 10 holds. Consider the squared distance to the optimal solution $𝑥 *$ :

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 = ‖ 𝑥 𝑡 - 𝜂 𝑔 (𝑥 𝑡, 𝜉 𝑡) - 𝑥 * ‖ 22 = ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 ⟨ 𝑔 (𝑥 𝑡, 𝜉 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ + 𝜂 2 ‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22

Taking expectation with respect to $𝜉 𝑡$ , we have

𝔼 [‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22] = ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 ⟨ \nabla 𝑓 (𝑥 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ + 𝜂 2 𝔼 [‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22] \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝜂 2 𝐺 2

Take $𝜂 = 1 \sqrt 𝑡$ , we have

𝔼 [‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22] \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 \sqrt 𝑡 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝐺 2 𝑡

3.4 Strongly Convex and Possibly Non-smooth SGD

We assume that $𝑓$ is $𝜇$ -strongly convex and that the stochastic gradient is bounded, i.e. Assumption 10 holds. Consider the squared distance to the optimal solution $𝑥 *$ :

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 = ‖ 𝑥 𝑡 - 𝜂 𝑔 (𝑥 𝑡, 𝜉 𝑡) - 𝑥 * ‖ 22 = ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 ⟨ 𝑔 (𝑥 𝑡, 𝜉 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ + 𝜂 2 ‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22

Taking expectation with respect to $𝜉 𝑡$ , we have

𝔼 [‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22] = ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 ⟨ \nabla 𝑓 (𝑥 𝑡), 𝑥 𝑡 - 𝑥 * ⟩ + 𝜂 2 𝔼 [‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22] \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝜂 2 𝐺 2 \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝜂 𝜇 2 ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 + 𝜂 2 𝐺 2 = (1 - 𝜇 𝜂) ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 + 𝜂 2 𝐺 2

Take $𝜂 = 1 𝜇 𝑡$ , we have

𝔼 [‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22] \leq (1 - 1 𝑡) ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 + 𝐺 2 𝜇 2 𝑡 2

3.5 Smooth and Non-convex SGD

We assume that $𝑓$ is L-smooth and that the stochastic gradient has bounded variance, i.e. Assumption 11 holds. By descent lemma, we have

𝑓 (𝑥 𝑡 + 1) \leq 𝑓 (𝑥 𝑡) + \nabla 𝑓 (𝑥 𝑡) 𝑇 (𝑥 𝑡 + 1 - 𝑥 𝑡) + 𝐿 2 ‖ 𝑥 𝑡 + 1 - 𝑥 𝑡 ‖ 22 = 𝑓 (𝑥 𝑡) - 𝜂 \nabla 𝑓 (𝑥 𝑡) 𝑇 𝑔 (𝑥 𝑡, 𝜉 𝑡) + 𝐿 𝜂 2 2 ‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22

Taking expectation with respect to $𝜉 𝑡$ , we have

𝔼 [𝑓 (𝑥 𝑡 + 1)] \leq 𝑓 (𝑥 𝑡) - 𝜂 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝐿 𝜂 2 2 𝔼 [‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22] \leq 𝑓 (𝑥 𝑡) - 𝜂 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝐿 𝜂 2 2 (‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝜎 2) = 𝑓 (𝑥 𝑡) - (𝜂 - 𝐿 𝜂 2 2) ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝐿 𝜂 2 𝜎 2 2

Take $𝜂 = 1 𝐿$ , we have

𝔼 [𝑓 (𝑥 𝑡 + 1)] \leq 𝑓 (𝑥 𝑡) - 1 2 𝐿 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝜎 2 2 𝐿 .

3.6 Smooth and Strongly Convex SGD

We assume that $𝑓$ is L-smooth and $𝜇$ -strongly convex, and that the stochastic gradient has bounded variance, i.e. Assumption 11 holds. By descent lemma, we have

𝑓 (𝑥 𝑡 + 1) \leq 𝑓 (𝑥 𝑡) + \nabla 𝑓 (𝑥 𝑡) 𝑇 (𝑥 𝑡 + 1 - 𝑥 𝑡) + 𝐿 2 ‖ 𝑥 𝑡 + 1 - 𝑥 𝑡 ‖ 22 = 𝑓 (𝑥 𝑡) - 𝜂 \nabla 𝑓 (𝑥 𝑡) 𝑇 𝑔 (𝑥 𝑡, 𝜉 𝑡) + 𝐿 𝜂 2 2 ‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22

Taking expectation with respect to $𝜉 𝑡$ , we have

𝔼 [𝑓 (𝑥 𝑡 + 1)] \leq 𝑓 (𝑥 𝑡) - 𝜂 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝐿 𝜂 2 2 𝔼 [‖ 𝑔 (𝑥 𝑡, 𝜉 𝑡) ‖ 22] \leq 𝑓 (𝑥 𝑡) - 𝜂 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝐿 𝜂 2 2 (‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝜎 2) = 𝑓 (𝑥 𝑡) - (𝜂 - 𝐿 𝜂 2 2) ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝐿 𝜂 2 𝜎 2 2

Applying Proposition 7, we have

𝔼 [𝑓 (𝑥 𝑡 + 1)] - 𝑓 (𝑥 *) \leq 𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *) - (𝜂 - 𝐿 𝜂 2 2) 2 𝜇 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝐿 𝜂 2 𝜎 2 2 = (1 - 2 𝜇 𝜂 + 𝐿 𝜇 𝜂 2) (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝐿 𝜂 2 𝜎 2 2

Take $𝜂 = 1 𝐿$ , we have

𝔼 [𝑓 (𝑥 𝑡 + 1)] - 𝑓 (𝑥 *) \leq (1 - 𝜇 𝐿) (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝜎 2 2 𝐿 .

4 Solve the Recursion

In last section, we have derived some one-step inequalities for different scenarios. In this section, we will solve these recursions to get the convergence rates of GD and SGD. For the recursion of smooth and convex GD, we have

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 𝐿 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *))

Summing up the above inequality from $𝑡 = 0$ to $𝑡 = 𝑇 - 1$ , we have

‖ 𝑥 𝑇 - 𝑥 * ‖ 22 \leq ‖ 𝑥 0 - 𝑥 * ‖ 22 - 2 𝐿 𝑇 - 1 \sum 𝑡 = 0 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *))

Thus, we have

1 𝑇 𝑇 - 1 \sum 𝑡 = 0 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) \leq 𝐿 2 𝑇 ‖ 𝑥 0 - 𝑥 * ‖ 22

By convexity of $𝑓$ , we have

𝑓 (1 𝑇 𝑇 - 1 \sum 𝑡 = 0 𝑥 𝑡) - 𝑓 (𝑥 *) \leq 1 𝑇 𝑇 - 1 \sum 𝑡 = 0 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) \leq 𝐿 2 𝑇 ‖ 𝑥 0 - 𝑥 * ‖ 22

Thus, we have the convergence rate of smooth and convex GD:

𝑓 (1 𝑇 𝑇 - 1 \sum 𝑡 = 0 𝑥 𝑡) - 𝑓 (𝑥 *) \leq O (1 𝑇)

For the recursion of smooth and strongly convex GD, we have

𝑓 (𝑥 𝑡 + 1) - 𝑓 (𝑥 *) \leq (1 - 𝜇 𝐿) (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *))

By induction, we have

𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *) \leq (1 - 𝜇 𝐿) 𝑡 (𝑓 (𝑥 0) - 𝑓 (𝑥 *))

Thus, we have the convergence rate of smooth and strongly convex GD:

𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *) \leq O ((1 - 𝜇 𝐿) 𝑡)

For the distance convergence of smooth and strongly convex GD, we have

‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22 \leq (𝜇 - 𝐿 𝜇 + 𝐿) 2 ‖ 𝑥 𝑡 - 𝑥 * ‖ 22

By induction, we have

‖ 𝑥 𝑡 - 𝑥 * ‖ 22 \leq (𝜇 - 𝐿 𝜇 + 𝐿) 2 𝑡 ‖ 𝑥 0 - 𝑥 * ‖ 22

Thus, we have the distance convergence rate of smooth and strongly convex GD:

‖ 𝑥 𝑡 - 𝑥 * ‖ 22 \leq O ((𝜇 - 𝐿 𝜇 + 𝐿) 2 𝑡)

For the recursion of convex and possibly non-smooth SGD, we have

𝔼 [‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22] \leq ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 - 2 \sqrt 𝑡 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝐺 2 𝑡

Summing up the above inequality from $𝑡 = 0$ to $𝑡 = 𝑇 - 1$ , we have

𝔼 [‖ 𝑥 𝑇 - 𝑥 * ‖ 22] \leq ‖ 𝑥 0 - 𝑥 * ‖ 22 - 2 𝑇 - 1 \sum 𝑡 = 0 1 \sqrt 𝑡 (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝐺 2 𝑇 - 1 \sum 𝑡 = 0 1 𝑡

Thus, we have the convergence rate of convex and possibly non-smooth SGD:

𝔼 [𝑓 (𝑥 𝑇) - 𝑓 (𝑥 *)] \leq O (1 \sqrt 𝑇)

For the recursion of strongly convex and possibly non-smooth SGD, we have

𝔼 [‖ 𝑥 𝑡 + 1 - 𝑥 * ‖ 22] \leq (1 - 1 𝑡) ‖ 𝑥 𝑡 - 𝑥 * ‖ 22 + 𝐺 2 𝜇 2 𝑡 2

By induction, we have

𝔼 [‖ 𝑥 𝑡 - 𝑥 * ‖ 22] \leq 𝐺 2 𝜇 2 𝑡

Thus, we have the convergence rate of strongly convex and possibly non-smooth SGD:

𝔼 [𝑓 (𝑥 𝑇) - 𝑓 (𝑥 *)] \leq O (1 𝑇)

For the recursion of smooth and non-convex SGD, we have

𝔼 [𝑓 (𝑥 𝑡 + 1)] \leq 𝑓 (𝑥 𝑡) - 1 2 𝐿 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝜎 2 2 𝐿

Summing up the above inequality from $𝑡 = 0$ to $𝑡 = 𝑇 - 1$ , we have

𝔼 [𝑓 (𝑥 𝑇)] \leq 𝑓 (𝑥 0) - 1 2 𝐿 𝑇 - 1 \sum 𝑡 = 0 ‖ \nabla 𝑓 (𝑥 𝑡) ‖ 22 + 𝑇 𝜎 2 2 𝐿

Thus, we have the convergence rate of smooth and non-convex SGD:

1 𝑇 𝑇 - 1 \sum 𝑡 = 0 𝔼 [| \nabla 𝑓 (𝑥 𝑡) ‖ 22] \leq O (1 \sqrt 𝑇)

For the recursion of smooth and strongly convex SGD, we have

𝔼 [𝑓 (𝑥 𝑡 + 1)] - 𝑓 (𝑥 *) \leq (1 - 𝜇 𝐿) (𝑓 (𝑥 𝑡) - 𝑓 (𝑥 *)) + 𝜎 2 2 𝐿

By induction, we have

𝔼 [𝑓 (𝑥 𝑡)] - 𝑓 (𝑥 *) \leq (1 - 𝜇 𝐿) 𝑡 (𝑓 (𝑥 0) - 𝑓 (𝑥 *)) + 𝜎 2 2 𝐿 𝑡 - 1 \sum 𝑖 = 0 (1 - 𝜇 𝐿) 𝑖

Thus, we have the convergence rate of smooth and strongly convex SGD:

𝔼 [𝑓 (𝑥 𝑡)] - 𝑓 (𝑥 *) \leq O ((1 - 𝜇 𝐿) 𝑡) + O (𝜎 2 𝜇)