Convergence Analysis in Deep Learning (Part 1)

0x00 Preface

This series organizes the convergence analysis of optimization methods. This installment unifies notation, introduces convexity, strong convexity, smoothness, stochastic gradient assumptions, and inequalities frequently used in subsequent proofs. I am not formally trained in optimization; I learned these topics out of research necessity. Please point out any omissions.

Throughout this article, the Euclidean norm $\Vert\cdot\Vert_2$ is used by default, abbreviated as $\Vert\cdot\Vert$. Unless otherwise specified, we discuss unconstrained problems $\min_{w\in\mathbb R^d}f(w)$. $w^{\ast}$ denotes the optimal solution that exists, $f^{\ast}=f(w^{\ast})$; when the minimum may not be attained, we use a finite lower bound $f_{\inf}$.

The objective functions of deep neural networks are typically non-convex. Theorems under convex or strongly convex conditions serve as theoretical models for understanding optimization and cannot be directly taken as guarantees for training general neural networks.

0x01 Fundamental Concepts

Convex Function

A function $f$ is convex on a convex set $\mathcal D$ if, for any $x,y\in\mathcal D$ and $\theta\in[0,1]$, we have

When $f$ is differentiable, the equivalent first-order condition is

Non-smooth convex functions do not necessarily have gradients. In such cases, we use subgradients $g\in\partial f(x)$, which satisfy $f(y)\ge f(x)+\langle g,y-x\rangle$ for all $y$.

$\mu$-strongly Convex

defination

For a differentiable function, $\mu$-strong convexity ($\mu>0$) is defined as

$$ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|^2. $$

In the non-smooth case, replace $\nabla f(x)$ with $g\in\partial f(x)$.

Under the Euclidean norm, $f$ being $\mu$-strongly convex is equivalent to $f(x)-\mu\Vert x\Vert^2/2$ being a convex function. We do not extend this equivalence to arbitrary norms here.

If $w^{\ast}$ is the unconstrained optimal solution of a differentiable function, then $\nabla f(w^{\ast})=0$. Applying the strong convexity inequality separately yields

Lipschitz Continuous

A function value $G$ being Lipschitz continuous means

On the entire space, for differentiable functions, this is equivalent to the gradient norm being uniformly bounded $\Vert\nabla f(x)\Vert\le G$. For non-smooth convex functions, the corresponding condition is bounded subgradients; on a restricted domain, one must specify which subgradients are selected and the boundary conditions.

Smoothness

defination

A differentiable function $f$ is $L$-smooth, meaning its gradient $L$ is Lipschitz continuous:

$$ \|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|. $$

Here, the constraint is on the variation of the gradient, which is a distinct property from Lipschitz continuity of the function values. Smoothness implies the descent lemma:

The proof follows from line integration:

For differentiable convex functions, a one-sided quadratic upper bound is equivalent to gradient Lipschitz continuity. However, for general non-convex functions, a one-sided upper bound cannot serve as this equivalence. For example, $f(x)=-x^4$ is a concave function that satisfies a one-sided upper bound for any positive $L$, yet its gradient is not Lipschitz over the entire space. Subsequent non-convex analysis adopts the gradient definition provided above.

0x02 Optimization Methods

Gradient Descent

Step sizes can be fixed or varying; the definition of gradient descent itself does not require the step size to be monotonically decreasing. The following identity serves as the starting point for distance analysis:

Stochastic and Mini-batch Gradient Descent

Let the loss for a single sample be $\ell(w;\xi)$, and the overall objective be $f(w)=\mathbb E_\xi[\ell(w;\xi)]$. Under conditions allowing the interchange of differentiation and expectation, independent sampling yields

$b=1$ corresponds to single-sample SGD; $b>1$ corresponds to mini-batch SGD. We use $\ell$ to distinguish sample losses from the objective function, avoiding confusion between single-sample gradients and batch averages.

0x03 Common Assumptions

These conditions are used as needed by specific theorems; not all analyses require them to hold simultaneously.

Bounded Domain and Bounded Subgradients

If constrained optimization is required, one may assume the diameter of the closed convex feasible set $\mathcal C$ does not exceed $D$, i.e., $\Vert x-y\Vert\le D$. This is bounded domain, not bounded variance.

Non-smooth analysis often assumes the selected subgradients satisfy $\Vert g_t\Vert\le G$. A strongly convex function on the entire space cannot simultaneously have globally bounded gradients: strong convexity implies at least quadratic growth, while function value Lipschitz continuity allows at most linear growth. Therefore, relevant theorems must restrict the feasible set or the iteration trajectory and specify how constraints are maintained.

Conditional Unbiasedness and Bounded Variance

Let $\mathcal F_t$ denote the historical information before sampling, and $w_t$ be measurable with respect to $\mathcal F_t$. Assume that new samples in each round are independent given the history, and

Then the mini-batch average satisfies

Variance reduction follows from the conditional expectation of the noise cross-terms in the average being zero. If samples are repeated or noise is correlated, unbiasedness alone does not imply that variance decreases by a factor of $1/b$. Here, vector variance is represented by the expected squared norm of the centered noise.

0x04 Common Inequalities

Cauchy-Schwarz and Triangle Inequalities

Jensen Inequality

If $f$ is a convex function, $\theta_i\ge0$ and $\sum_i\theta_i=1$, then

In the equal-weight case, it is $f(\bar x)\le n^{-1}\sum_i f(x_i)$, where $\bar x=n^{-1}\sum_i x_i$. This does not imply $f(n\bar x)\le nf(\bar x)$; one can construct a counterexample by taking $f(x)=x^2$.

Polyak–Łojasiewicz (PL) Inequality

defination

The PL condition is

$$ \|\nabla f(x)\|^2\ge2\mu(f(x)-f^*). $$

Differentiable, unconstrained $\mu$-strongly convex functions satisfy this condition; the PL condition itself does not require the function to be strongly convex, nor does it require convexity.

Proof that strong convexity implies PL: Fix $x$. Strong convexity yields, for any $y$,

The minimum value of the right-hand side with respect to $y$ is $f(x)-\Vert\nabla f(x)\Vert^2/(2\mu)$. Taking the infimum on both sides gives $f^{\ast}\ge f(x)-\Vert\nabla f(x)\Vert^2/(2\mu)$; rearranging terms yields the conclusion.

0x05 Acknowledgement

I have been studying optimization content intermittently for nearly a year, and I have taken quite a few detours along the way. In the learning process, I initially started by studying derivations from papers, but many definitions were difficult to understand or grasp, so I turned to specialized optimization textbooks. Perhaps my aptitude is not the best, but many of these books left me confused or were too far removed from my research direction, making me somewhat impatient, which is why my progress was intermittent. In the second half of 2022, I took the public elective course Professor Niulingfeng titled Practical Optimization Algorithms and Their Applications, which finally gave me a proper understanding and overview of the entire field. This year, reading related content in the field has become much easier. I would like to thank Professor Niulingfeng for offering this course, which allowed me to easily get started and understand optimization-related content without having to enroll in specialized courses like Theory and Methods of Optimization.

Reference

Sources: ^{1 2 3}.