Lin Yang, Na Xian^*
Key Laboratory of Optimization Theory and Applications, School of Mathematical Sciences, China West Normal University, Nanchong, China.
DOI: 10.4236/jamp.2026.144076   PDF    HTML   XML   14 Downloads   146 Views   Citations

Abstract

The proximal gradient method (PGD) is an important approach for solving composite optimization problems consisting of the sum of a smooth function and a nonsmooth function. Classical convergence analysis of PGD typically assumes that the smooth function has a globally Lipschitz continuous gradient. In recent years, researchers have relaxed this assumption from various perspectives, thereby providing theoretical support for the application of PGD to more general problems. In particular, for unconstrained smooth optimization problems, Li et al. introduced the concept of $\ell (\cdot )$ -smoothness, studied the convergence rates of classical gradient methods, and showed that under this generalized smoothness condition, the convergence rates of classical gradient methods remain consistent with those under the classical smoothness condition. Nevertheless, existing results are mostly focused on unconstrained smooth optimization, and the corresponding theoretical analysis of PGD for composite optimization problems still requires further development. To this end, this paper further investigates the convergence rates of PGD for solving composite optimization problems within the $\ell (\cdot )$ -smoothness framework. Under the assumption that the smooth component in the composite optimization problem is convex, we prove that the sequence of function values generated by the constant-stepsize PGD under-smoothness achieves a convergence rate of $O\left(1/k\right)$ .

Keywords

Generalized Smoothness, Proximal Gradient Method, Composite Optimization Problem

Share and Cite:

1. Introduction

This paper considers the following composite convex optimization problem:

$\underset{x\in R^d}{\min }F\left(x\right)=f\left(x\right)+g\left(x\right)$ (1)

where $f:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ is a proper closed convex function that is differentiable on the open effective domain $\mathcal{X}=\text{dom}f$ , $g:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ is a proper closed convex function satisfying $\text{dom}g\subseteq \mathcal{X}$ .

Problem (1) has wide applications in fields such as compressed sensing, sparse phase retrieval [1] [2], network quantization [3], and machine learning. Currently, researchers have proposed various classical methods for solving problem (1), including the subgradient algorithm, splitting algorithms [4], and the proximal gradient method [5].

The proximal gradient method (PGD) combines gradient descent with the proximal operator to solve optimization problems with nonsmooth regularization terms by decomposing complex objective functions. Its iterative scheme is as follows:

$x^{t+1}={\text{prox}}_{{\lambda }_t,g}\left\{x^t-\nabla f\left(x\right)\right\},$

where ${\lambda }_t>0$ is the step size parameter, and ${\text{prox}}_{{\lambda }_t,g}$ denotes the proximal operator of the function $g$ defined as

${\text{prox}}_{{\lambda }_t,g}\left(z\right)=\text{arg}\underset{x\in {ℝ}^d}{\text{min}}\left\{g\left(x\right)+\frac{1}{2{\lambda }_t}{\Vert x-z\Vert }^2\right\}.$

In the convergence theory analysis of traditional PGD, it is often required that the gradient satisfy Lipschitz continuity. Under this smoothness condition, if $f$ is convex, the algorithm can achieve a sublinear convergence rate of $O\left(1/k\right)$ .

However, the classical smoothness condition of gradient Lipschitz continuity is relatively strict. For functions with rapidly changing curvature or uneven local geometric structures, this assumption is often difficult to satisfy. Particularly in machine learning and large-scale optimization, many objective functions, although differentiable or even twice differentiable, may not have globally Lipschitz continuous gradients. Even in some standard models, the global smoothness constant may be unbounded [6], such as the ${\ell }_2$ -regression function. Additionally, when the function $f$ is an augmented Lagrangian function or the dual function of the original problem (which is not necessarily uniformly convex), the objective function may also exhibit nonsmooth or non-uniformly smooth characteristics [7] [8]. Therefore, how to establish algorithm convergence theory under conditions weaker than classical smoothness remains an important question.

Significant progress has been made in research on weakening the classical smoothness assumption. In 2020, Zhang et al. [9], based on an in-depth study of the training process of deep neural networks such as LSTM [10] and ResNet [11], first proposed a non-uniform smoothness condition—$\left(L_0,L_1\right)$ -smoothness—to characterize the dependence between the variation of the function gradient and the gradient norm. Compared with the classical smoothness condition of gradient Lipschitz continuity, this type of condition allows the local smoothness degree to vary with the position of the iteration point or the gradient norm, thus covering a broader class of functions, such as univariate polynomials and exponential functions. Under this generalized smoothness condition, Zhang et al. proved the convergence rate of gradient clipping [12] and demonstrated its advantages over gradient descent methods in neural network training. Since the introduction of this generalized smoothness condition, related research has been extensively developed in various fields, including minimax optimization [13], bilevel optimization [14], and variational inequalities [15].

On this basis, Chen et al. [16] further proposed a more general class of symmetric generalized smoothness conditions—$\alpha$ -symmetric $\left(L_0,L_1\right)$ -smoothness. This concept generalizes existing smoothness definitions and covers many mainstream machine learning problems and important function classes, such as distributionally robust optimization [17] [18], higher-order polynomials, and exponential functions. Under this framework, the researchers established corresponding descent lemmas for different values of $\alpha$ . On this basis, to solve non-convex optimization problems, Chen et al. designed several deterministic normalized gradient descent algorithms [19], which achieve an optimal complexity of $O\left({ϵ}^{-2}\right)$ . Meanwhile, they found that under the stochastic setting, the classic variance reduction algorithm SPIDER [20] can also achieve the optimal sample complexity of $O\left({ϵ}^{-3}\right)$ .

In the same year, Li et al. [21] also generalized the $\left(L_0,L_1\right)$ -smoothness condition by replacing the original affine function $L_0+L_1\Vert \cdot \Vert$ with a more general non-decreasing continuous function $\ell (\cdot )$ to characterize the dependence between the norm of the Hessian matrix and the gradient norm, thereby proposing a more generalized smoothness concept—$\ell (\cdot )$ -smoothness. That is, there exists a non-decreasing continuous function $\ell (\cdot )$ such that $f$ satisfies

$\Vert {\nabla }^{2}f\left(x\right)\Vert \le \ell \left(\Vert \nabla f\left(x\right)\Vert \right).$

This generalization significantly expands the applicability of the generalized smoothness theory, enabling researchers to handle function classes with more complex curvature variations. Based on this new framework, Li et al. systematically analyzed the convergence rates of gradient descent methods in convex, strongly convex, and non-convex settings. Notably, under the condition that the objective function is convex, they further proved that Nesterov’s accelerated gradient method [22] achieves an optimal computational complexity of $O\left({ϵ}^{-0.5}\right)$ , which exactly matches the optimal bound under the classical smoothness condition. In addition, they also conducted an in-depth study of stochastic non-convex optimization problems and, under the assumption of bounded variance, proved that stochastic gradient descent achieves an optimal complexity of $O\left({ϵ}^{-4}\right)$ , which also matches its optimal bound under the classical smoothness condition.

Related Work

Overall, existing literature mainly focuses on smooth unconstrained problems, while studies for composite optimization problems are relatively limited. In particular, for the proximal gradient method, a fundamental algorithm for solving composite optimization problems, its theoretical analysis under the generalized smooth framework remains incomplete. Although the convergence analysis of proximal gradient methods based on the Kurdyka-Łojasiewicz (KL) property has successfully extended the theoretical framework to non-convex and non-globally Lipschitz settings [8], such methods still have obvious limitations: their convergence relies on line search strategies to ensure iterative descent, and they can only yield a unified sublinear convergence rate determined by the KL exponent, failing to recover the classical exact convergence rate under convex structures. Therefore, it is necessary to re-examine the algorithmic theory for optimization problems under generalized smoothness conditions and establish a systematic analysis framework applicable to proximal gradient algorithms.

Against the above background, this paper focuses on the composite optimization problem (1) under generalized smoothness conditions, and systematically studies the convergence rate of the PGD. For problem (1), we rigorously establish the achievable convergence rate of the PGD method with a constant step size, provided that the function $f$ is $\ell$ -smooth and convex. This result shows that the PGD method can still retain the same convergence rate as that under the classical Lipschitz smoothness assumption, even under the weaker generalized smoothness condition.

2. Preliminaries

This paper mainly conducts research in the finite-dimensional Euclidean space ${ℝ}^d$ . Let $\mathcal{X}\subseteq {ℝ}^d$ be a non-empty convex set. For any $x,y\in {ℝ}^d$ , the inner product is denoted by $\langle x,y\rangle$ , and the induced norm is defined as $\Vert x\Vert :=\sqrt{\langle x,x\rangle }$ . In this thesis, $B\left(x,R\right)$ denotes the Euclidean ball centered at $x$ with radius $R$ .

Definition 1 ($\ell$ -smoothness [21]). Let $f:\mathcal{X}\to ℝ$ be a real-valued differentiable function. If there exists a non-decreasing continuous function $\ell :\left[0,+\infty \right)\to \left(0,+\infty \right)$ such that the spectral norm of the Hessian matrix of $f$ satisfies

$\Vert {\nabla }^{2}f\left(x\right)\Vert \le \ell \left(\Vert \nabla f\left(x\right)\Vert \right)$

almost everywhere on $\mathcal{X}$ (with respect to the Lebesgue measure), then $f$ is called an $\ell$ -smooth function.

Remark. When the function $\ell$ is a constant function $\ell \left(\mu \right)=L$ , the definition of $\ell$ -smoothness degenerates to the classical smoothness definition; when $\ell$ is an affine function $\ell \left(\mu \right)=L_0+L_1\mu$ , the $\ell$ -smoothness corresponds to the $\left(L_0,L_1\right)$ -smoothness definition [9].

Definition 2 (($r$ , $\ell$ )-smoothness). Let $f:\mathcal{X}\to ℝ$ be a real-valued differentiable function. Suppose there exist a non-decreasing continuous function $\ell :\left[0,+\infty \right)\to \left(0,+\infty \right)$ and a non-increasing continuous function $r:\left[0,+\infty \right)\to \left(0,+\infty \right)$ such that

1) $\forall x\in \mathcal{X}$ , $B\left(x,r\left(\Vert \nabla f\left(x\right)\Vert \right)\right)\subseteq \mathcal{X}$ ;

2) $\forall x_1,x_2\in B\left(x,r\left(\Vert \nabla f\left(x\right)\Vert \right)\right)$ , $\Vert \nabla f\left(x_1\right)-\nabla f\left(x_2\right)\Vert \le \ell \left(\Vert \nabla f\left(x\right)\Vert \right)\Vert x_1-x_2\Vert$ ;

Then $f$ is called an $\left(r,\ell \right)$ -smooth function.

Remark. Here, the function $r:\left[0,+\infty \right)\to \left(0,+\infty \right)$ is assumed to be nonincreasing and the function $\ell :\left[0,+\infty \right)\to \left(0,+\infty \right)$ is assumed to be nondecreasing. This restriction is usually without loss of generality. When $r$ and $\ell$ do not satisfy the required monotonicity, the desired monotonicity can be achieved by the following construction technique:

1) Replace the original function $r$ with $\widehat{r}:={\text{inf}}_{0\le v\le u}r\left(v\right)\le r\left(u\right)$;

2) Replace the original function $\ell$ with the nonincreasing function $\widehat{\ell }:={\text{sup}}_{0\le v\le u}\ell \left(v\right)\ge \ell \left(u\right)$.

Next, we elaborate on the intrinsic relationship between the two types of smooth functions. In fact, under appropriate assumptions, $\ell$ -smooth functions and $\left(r,\ell \right)$ -smooth functions are equivalent.

Proposition 1. If $f$ is $\left(r,\ell \right)$ -smooth, then $f$ is also $\ell$ -smooth; if $f$ is $\ell$ -smooth and $f$ is a differentiable closed function on the open effective domain $X$ , then $f$ is an $\left(r,m\right)$ -smooth function, where $m\left(u\right):=\ell \left(u+a\right)$ , $r\left(u\right):=a/m\left(u\right)$ , and the constant $a>0$ is arbitrary.

The proof of the above proposition can be found in appendix A.2 of [21]. The objective function considered in this paper obviously satisfies the assumptions of Proposition 1. In view of the equivalence between $\ell$ -smoothness and $\left(r,\ell \right)$ -smoothness in the above framework, the subsequent theoretical analysis will mainly focus on $\left(r,\ell \right)$ -generalized smooth functions.

Lemma 2 (Descent Lemma [23]). Let $f:\mathcal{X}\to ℝ$ be a $M$ -smooth function, where $\mathcal{X}$ is a convex set. Then for all $x,y\in \mathcal{X}$ , we have

$f\left(y\right)\le f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle +\frac{M}{2}{\Vert x-y\Vert }^2.$

Lemma 3. [21] Suppose the differentiable function $f:\mathcal{X}\to ℝ$ satisfies $\left(r,\ell \right)$ -smoothness, and for all $x\in \mathcal{X}$ , $\Vert \nabla f\left(x\right)\Vert \le C$ , Then

1) $B\left(x,r\left(C\right)\right)\subseteq \mathcal{X}$ ;

2) For any $x_1,x_2\in B\left(x,r\left(C\right)\right)$ ,

$\Vert \nabla f\left(x_1\right)-\nabla f\left(x_2\right)\Vert \le L_f\Vert x_1-x_2\Vert ,$ (2)

$f\left(x_1\right)\le f\left(x_2\right)+\langle \nabla f\left(x_2\right),x_1-x_2\rangle +\frac{L_f}{2}{\Vert x_1-x_2\Vert }^2,$ (3)

where $L_f:=\ell \left(C\right)$ denotes an effective smoothness constant.

Proof of the above lemma can be found in appendix A.3 of [21].

Remark. From Lemma 3, it is not difficult to see that when the gradient norm of an $\left(r,\ell \right)$ -smooth function is bounded, it also satisfies the property of a classical smooth function in a local neighborhood $B\left(x,r\left(C\right)\right)$ , i.e., the descent lemma.

Remark. From Proposition 1, the two classes of smooth functions are equivalent. Therefore, the conclusion of Lemma 3 obviously also holds for $\ell$ -smooth functions. When $a:=C$ , it suffices to take $L_f=\ell \left(2C\right)$ and $r\left(C\right)=C/L_f$ to obtain the corresponding conclusion [21].

Lemma 4 (Nonexpansiveness of the Proximal Operator [23]). Let $g:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ be a closed proper convex function. Then for any $x,y\in {ℝ}^d$ , we have

$\langle x-y,{\text{prox}}_g\left(x\right)-{\text{prox}}_g\left(y\right)\rangle \ge {\Vert {\text{prox}}_g\left(x\right)-{\text{prox}}_g\left(y\right)\Vert }^2,$ (4)

and

$\Vert {\text{prox}}_g\left(x\right)-{\text{prox}}_g\left(y\right)\Vert \le \Vert x-y\Vert .$

3. The Proximal Gradient Method

3.1. The Proximal Gradient Method

This paper mainly considers the framework of generalized smoothness assumptions, and investigates the iterative convergence rate of PGD for solving unconstrained composite convex optimization problems. In the following, this chapter will discuss the convex case, present and prove the convergence rate of PGD.

Before proceeding with the study, we first introduce an important fundamental assumption in the field of optimization algorithm research, namely, the existence of an optimal solution.

Assumption 1. Assume there exists a point $x^{*}\in \mathcal{X}$ such that $F\left(x^{*}\right)=F^{*}={\inf }_{x\in \mathcal{X}}F\left(x\right)$ .

This chapter mainly considers the constant step-size version of PGD. Let the iteration step size be $\frac{1}{L}$ , where $L>0$ . The iteration scheme is given by

$x^{t+1}={\text{prox}}_{\frac{1}{L}g}\left(x^t-\frac{1}{L}\nabla f\left(x^t\right)\right),$ (5)

For simplicity, we define $T_L\left(x\right):={\text{prox}}_{\frac{1}{L}g}\left(x-\frac{1}{L}\nabla f\left(x\right)\right)$ . Then the PGD iteration scheme is abbreviated as

$x^{t+1}=T_L\left(x^t\right).$

Next, we introduce an important tool, the gradient mapping, which is defined as follows.

Definition 3. When solving the objective problem (1) using PGD (5), combined with the definition of the operator $T_L$ , the mapping $G_L:\mathcal{X}\to {ℝ}^d$ is defined as

$G_L\left(x\right)=L\left(x-T_L\left(x\right)\right),x\in \mathcal{X},$

and is called the gradient mapping.

Based on the above definition of the gradient mapping, the proximal gradient iteration can be equivalently transformed into a gradient descent iteration format, i.e.,

$x^{t+1}=x^t-\frac{1}{L}{G}_L\left(x^t\right).$

Through this structural reconstruction, it is not difficult to see that PGD can be regarded as a natural extension of the classical gradient descent method in composite optimization problems.

Since cocoercivity serves as an important theoretical guarantee for the convergence analysis of the PGD iteration framework. However, in the composite convex optimization problem (1) considered in this paper, the function $f$ is only $\left(r,\ell \right)$ -smooth. Therefore, we need to verify whether the corresponding co-coercivity still holds when the function satisfies $\left(r,\ell \right)$ -smoothness. Li et al. [21] pointed out that when a function is both convex and $\left(r,\ell \right)$ -smooth, its gradient also possesses cocoercivity, as stated in the following lemma.

Lemma 5 (cocoercivity [21]). Let the function $f:\mathcal{X}\to ℝ$ be an $\left(r,\ell \right)$ -smooth convex function. Then for $\forall x\in \mathcal{X},y\in B\left(x,\frac{r\left(\Vert \nabla f\left(x\right)\Vert \right)}{2}\right)$ , we have

$\langle \nabla f\left(x\right)-\nabla f\left(y\right),x-y\rangle \ge \frac{1}{\ell \left(\Vert \nabla f\left(x\right)\Vert \right)}{\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert }^2.$ (6)

Furthermore, we will investigate the convergence rate of PGD iterations based on the concept of co-coercivity. Since we will utilize Lemma 4 in the convergence analysis of PGD, it requires that consecutive iterates $x^{k+1},x^k$ of PGD satisfy $\Vert x^{k+1}-x^k\Vert =\frac{1}{L}\Vert G_L\left(x^k\right)\Vert \le r\left(C\right)/2$ , Based on this, we prove that the norm of the gradient mapping $\Vert G_L\left(x^k\right)\Vert$ is monotonically decreasing.

Lemma 6. Let $f:\mathcal{X}\to ℝ$ be an $\left(r,\ell \right)$ -smooth differentiable convex function satisfying $\Vert \nabla f\left(x\right)\Vert \le C$ ; and let $g:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ be a proper closed convex function. If for $x\in \mathcal{X}$ , $T_L\left(x\right)\in B\left(x,\frac{r\left(C\right)}{2}\right)\subseteq B\left(x,\frac{r\left(\Vert \nabla f\left(x\right)\Vert \right)}{2}\right)$ , then

$\Vert G_L\left(T_L\left(x\right)\right)\Vert \le \Vert G_L\left(x\right)\Vert ,$ (7)

where $L\ge \frac{L_f}{2}=\frac{\ell \left(C\right)}{2}$ .

Proof. Let $x\in \mathcal{X},y\in B\left(x,\frac{r\left(\Vert \nabla f\left(x\right)\Vert \right)}{2}\right)$ . By Lemma 4, the proximal operator is nonexpansive. When we choose $x:=x-\frac{1}{L}\nabla f\left(x\right)$ , $y:=y-\frac{1}{L}\nabla f\left(y\right)$ respectively, Equation (4) becomes

$\langle T_L\left(x\right)-T_L\left(y\right),\left(x-\frac{1}{L}\nabla f\left(x\right)\right)-\left(y-\frac{1}{L}\nabla f\left(y\right)\right)\rangle \ge {\Vert T_L\left(x\right)-T_L\left(y\right)\Vert }^2.$

Since the mapping $T_L=\text{Id}-\frac{1}{L}{G}_L$ , the above inequality can be transformed into

$\begin{array}{l}\langle \left(x-\frac{1}{L}{G}_L\left(x\right)\right)-\left(y-\frac{1}{L}{G}_L\left(y\right)\right),\left(x-\frac{1}{L}\nabla f\left(x\right)\right)-\left(y-\frac{1}{L}\nabla f\left(y\right)\right)\rangle \\ \ge {\Vert \left(x-\frac{1}{L}{G}_L\left(x\right)\right)-\left(y-\frac{1}{L}{G}_L\left(y\right)\right)\Vert }^2.\end{array}$

Because $L>0$ , the above inequality can be simplified as

$\langle \left(x-\frac{1}{L}{G}_L\left(x\right)\right)-\left(y-\frac{1}{L}{G}_L\left(y\right)\right),\left(G_L\left(x\right)-\nabla f\left(x\right)\right)-\left(G_L\left(y\right)-\nabla f\left(y\right)\right)\rangle \ge 0,$

Further, by expanding the inner product and rearranging terms, we obtain

$\begin{array}{c}\langle G_L\left(x\right)-G_L\left(y\right),x-y\rangle \ge \langle \nabla f\left(x\right)-\nabla f\left(y\right),x-y\rangle +\frac{1}{L}{\Vert G_L\left(x\right)-G_L\left(y\right)\Vert }^2\\ -\frac{1}{L}\langle G_L\left(x\right)-G_L\left(y\right),\nabla f\left(x\right)-\nabla f\left(y\right)\rangle .\end{array}$ (8)

Since the function $f$ is an $\left(r,\ell \right)$ -smooth differentiable convex function and satisfies $\Vert \nabla f\left(x\right)\Vert \le C$ , it follows from Lemma 5 that

$\begin{array}{c}\langle \nabla f\left(x\right)-\nabla f\left(y\right),x-y\rangle \ge \frac{1}{\ell \left(\Vert \nabla f\left(x\right)\Vert \right)}{\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert }^2\\ \ge \frac{1}{\ell \left(C\right)}{\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert }^2,\end{array}$

where the second inequality holds because $\Vert \nabla f\left(x\right)\Vert \le C$ and the function $\ell$ is nondecreasing and continuous. Therefore, based on the above inequality, Equation (8) can be further transformed into

$\begin{array}{l}\ell \left(C\right)\langle G_L\left(x\right)-G_L\left(y\right),x-y\rangle \\ \ge \frac{\ell \left(C\right)}{L}{\Vert G_L\left(x\right)-G_L\left(y\right)\Vert }^2+{\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert }^2\\ -\frac{\ell \left(C\right)}{L}\langle G_L\left(x\right)-G_L\left(y\right),\nabla f\left(x\right)-\nabla f\left(y\right)\rangle ,\end{array}$ (9)

For convenience, let $a:=G_L\left(x\right)-G_L\left(y\right)$ , $b:=\nabla f\left(x\right)-\nabla f\left(y\right)$ . Then the right-hand side of the above inequality can be further simplified as

$\frac{\ell \left(C\right)}{L}{\Vert a\Vert }^2+{\Vert b\Vert }^2-\frac{\ell \left(C\right)}{L}{a}^{\text{T}}b=\frac{4L\cdot \ell \left(C\right)-\ell {\left(C\right)}^2}{4L^2}{\Vert a\Vert }^2+{\Vert \frac{\ell \left(C\right)}{2L}a-b\Vert }^2$

Substituting the simplified result back into (9) yields

$\ell \left(C\right)\langle G_L\left(x\right)-G_L\left(y\right),x-y\rangle \ge \frac{4L\cdot \ell \left(C\right)-\ell {\left(C\right)}^2}{4L^2}{\Vert G_L\left(x\right)-G_L\left(y\right)\Vert }^2.$

Since the function $\ell :\left[0,+\infty \right)\to \left(0,+\infty \right)$ , we have $\ell \left(C\right)>0$ always holds. Dividing both sides of the above inequality by $\ell \left(C\right)$ , we obtain

$\langle G_L\left(x\right)-G_L\left(y\right),x-y\rangle \ge \frac{4L-\ell \left(C\right)}{4L^2}{\Vert G_L\left(x\right)-G_L\left(y\right)\Vert }^2.$ (10)

Next, we estimate the left-hand side of (10). Using the Cauchy-Schwarz inequality, we obtain

$\langle G_L\left(x\right)-G_L\left(y\right),x-y\rangle \le \Vert G_L\left(x\right)-G_L\left(y\right)\Vert \Vert x-y\Vert ,$

Therefore, combining the above inequality with (10) yields

$\Vert G_L\left(x\right)-G_L\left(y\right)\Vert \le \frac{4L^2}{4L-\ell \left(C\right)}\Vert x-y\Vert .$ (11)

According to the definition of the gradient mapping $G_L\left(x\right)=L\left(x-T_L\left(x\right)\right)$ , and taking $y=T_L\left(x\right)$ , we obtain

$x-y=x-T_L\left(x\right)=\frac{1}{L}{G}_L\left(x\right)$

and

$G_L\left(y\right)=L\left(y-T_L\left(y\right)\right)=G_L\left(T_L\left(x\right)\right)=L\left(T_L\left(x\right)-T_L\left(T_L\left(x\right)\right)\right),$

Let $x^{+}:=T_L\left(x\right)$ , the last equality is abbreviated as $G_L\left(y\right)=G_L\left(x^{+}\right)=L\left(x^{+}-T_L\left(x^{+}\right)\right)$ . Substituting these two equalities into (10), we obtain

$\begin{array}{l}\langle G_L\left(x^{+}\right)-G_L\left(x\right),-\frac{1}{L}{G}_L\left(x\right)\rangle \ge \frac{4L-\ell \left(C\right)}{4L^2}{\Vert G_L\left(x^{+}\right)-G_L\left(x\right)\Vert }^2\\ \iff -\frac{1}{L}\left(\langle G_L\left(x^{+}\right),G_L\left(x\right)\rangle -{\Vert G_L\left(x\right)\Vert }^2\right)\\ \ge \frac{4L-\ell \left(C\right)}{4L^2}\left({\Vert G_L\left(x^{+}\right)\Vert }^2-2\langle G_L\left(x^{+}\right),G_L\left(x\right)\rangle +{\Vert G_L\left(x\right)\Vert }^2\right)\\ \iff \frac{2L-\ell \left(C\right)}{2L^2}\langle G_L\left(x^{+}\right),G_L\left(x\right)\rangle \ge \frac{4L-\ell \left(C\right)}{4L^2}{\Vert G_L\left(x^{+}\right)\Vert }^2-\frac{\ell \left(C\right)}{4L^2}{\Vert G_L\left(x\right)\Vert }^2.\end{array}$ (12)

1) If $L=\frac{\ell \left(C\right)}{2}$ , Equation (12) can be simplified as

$\frac{1}{\ell \left(C\right)}{\Vert G_L\left(x\right)\Vert }^2\ge \frac{1}{\ell \left(C\right)}{\Vert G_L\left(x^{+}\right)\Vert }^2,$

Multiplying both sides by $\ell \left(C\right)>0$ , we obtain

${\Vert G_L\left(x\right)\Vert }^2\ge {\Vert G_L\left(x^{+}\right)\Vert }^2.$

Further, by letting $x^{+}:=T_L\left(x\right)$ , we arrive at the final conclusion ${\Vert G_L\left(x\right)\Vert }^2\ge {\Vert G_L\left(T_L\left(x\right)\right)\Vert }^2$ .

2) Similarly, when $L\in \left(\frac{\ell \left(C\right)}{2},+\infty \right)$ , combining with Equation (12) and using the Cauchy-Schwarz inequality, we obtain

$\frac{2L-\ell \left(C\right)}{2L^2}\Vert G_L\left(x^{+}\right)\Vert \Vert G_L\left(x\right)\Vert \ge \frac{4L-\ell \left(C\right)}{4L^2}{\Vert G_L\left(x^{+}\right)\Vert }^2-\frac{\ell \left(C\right)}{4L^2}{\Vert G_L\left(x\right)\Vert }^2,$ (13)

By rearranging terms and factoring, the above inequality becomes

$\left(\Vert G_L\left(x\right)\Vert -\Vert G_L\left(x^{+}\right)\Vert \right)\left(\frac{\ell \left(C\right)}{4L^2}\Vert G_L\left(x\right)\Vert +\frac{4L-\ell \left(C\right)}{4L^2}\Vert G_L\left(x^{+}\right)\Vert \right)\ge 0.$ (14)

(i) If $\Vert G_L\left(x^{+}\right)\Vert =0$ , by the non-negativity of the norm we have $\Vert G_L\left(x\right)\Vert \ge 0$ . Furthermore, since $\Vert G_L\left(x^{+}\right)\Vert =0$ , it follows that $\Vert G_L\left(x\right)\Vert \ge \Vert G_L\left(x^{+}\right)\Vert$ , the conclusion holds.

(ii) If $\Vert G_L\left(x^{+}\right)\Vert \ne 0$ , by the non-negativity of the norm we have $\Vert G_L\left(x^{+}\right)\Vert >0$ . In this case, $\Vert G_L\left(x\right)\Vert >0$ must also hold. If $\Vert G_L\left(x\right)\Vert >0$ were not true, then by the non-negativity of the norm we would have $\Vert G_L\left(x\right)\Vert =0$ . From (11), with $x^{+}:=T_L\left(x\right)$ and $G_L\left(x\right)=L\left(x-T_L\left(x\right)\right)$ , we obtain

$\begin{array}{c}\Vert G_L\left(x^{+}\right)-G_L\left(x\right)\Vert \le \frac{4L^2}{4L-\ell \left(C\right)}\Vert x^{+}-x\Vert =\frac{4L^2}{4L-\ell \left(C\right)}\Vert T_L\left(x\right)-x\Vert \\ =\frac{4L^2}{4L-\ell \left(C\right)}\cdot \frac{1}{L}\Vert G_L\left(x\right)\Vert ,\end{array}$

Since $\Vert G_L\left(x\right)\Vert =0$ , it follows that $\Vert G_L\left(x^{+}\right)\Vert \le 0$ , which contradicts the premise $\Vert G_L\left(x^{+}\right)\Vert >0$ . Therefore, given $L>\frac{\ell \left(C\right)}{2}$ and $\ell \left(C\right)>0$ , we have $4L-\ell \left(C\right)>0$ , and consequently

$\frac{\ell \left(C\right)}{4L^2}\Vert G_L\left(x\right)\Vert +\frac{4L-\ell \left(C\right)}{4L^2}\Vert G_L\left(x^{+}\right)\Vert >0.$

At this point, combining the above inequality with (14), it is easy to see that $\Vert G_L\left(x\right)\Vert \ge \Vert G_L\left(x^{+}\right)\Vert$ , so the conclusion holds.

□

Next, we present the key descent inequality in the convergence analysis.

Lemma 7 (Basic Proximal Gradient Inequality). Let $f:\mathcal{X}\to ℝ$ be a differentiable convex function, where $\mathcal{X}$ is an open set, and let $g:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ be a proper closed convex function. For any $x,y\in \mathcal{X}$ and $L>0$ , if

$f\left(T_L\left(x\right)\right)\le f\left(y\right)+\langle \nabla f\left(y\right),T_L\left(y\right)-y\rangle +\frac{L}{2}{\Vert T_L\left(y\right)-y\Vert }^2,$ (15)

then

$F\left(x\right)-F\left(T_L\left(y\right)\right)\ge \frac{L}{2}{\Vert x-T_L\left(y\right)\Vert }^2-\frac{L}{2}{\Vert x-y\Vert }^2+h\left(x,y\right),$ (16)

where $h\left(x,y\right)=f\left(x\right)-f\left(y\right)-\langle \nabla f\left(y\right),x-y\rangle$ .

Proof. Define the function

$\varphi \left(u\right):=f\left(y\right)+\langle \nabla f\left(y\right),u-y\rangle +g\left(u\right)+\frac{L}{2}{\Vert u-y\Vert }^2.$ (17)

Clearly, $\varphi$ is a strongly convex function with strong convexity modulus $L$ . From the definition of $T_L\left(x\right)$ , we have

$\begin{array}{c}{T}_L\left(y\right)={\text{prox}}_{\frac{1}{L}g}\left(y-\frac{1}{L}\nabla f\left(y\right)\right)\\ =\text{arg}\underset{u\in {ℝ}^d}{\text{min}}\left\{g\left(u\right)+\frac{L}{2}{\Vert u-\left(y-\frac{1}{L}\nabla f\left(y\right)\right)\Vert }^2\right\}\\ =\text{arg}\underset{u\in {ℝ}^d}{\text{min}}\varphi \left(u\right).\end{array}$ (18)

By strong convexity, we obtain

$\varphi \left(x\right)-\varphi \left(T_L\left(y\right)\right)\ge \frac{L}{2}{\Vert x-T_L\left(y\right)\Vert }^2.$ (19)

Using the convexity of $f$ , we have

$f\left(y\right)\ge f\left(T_L\left(y\right)\right)+\langle \nabla f\left(y\right),y-T_L\left(y\right)\rangle .$

Letting $u:=T_L\left(y\right)$ and substituting it into (17), together with the above inequality, we get

$\begin{array}{c}\varphi \left(T_L\left(y\right)\right)=f\left(y\right)+\langle \nabla f\left(y\right),T_L\left(y\right)-y\rangle +\frac{L}{2}{\Vert T_L\left(y\right)-y\Vert }^2+g\left(T_L\left(y\right)\right)\\ \ge f\left(T_L\left(y\right)\right)+g\left(T_L\left(y\right)\right)=F\left(T_L\left(y\right)\right),\end{array}$

furthermore, from (19), it is not difficult to see that

$\varphi \left(x\right)-F\left(T_L\left(x\right)\right)\ge \frac{L}{2}{\Vert x-T_L\left(y\right)\Vert }^2.$

Next, substituting $u:=x$ into the expression for $\varphi \left(u\right)$ and combining with the above inequality, we obtain

$f\left(y\right)+\langle \nabla f\left(x\right),x-y\rangle +g\left(x\right)+\frac{L}{2}{\Vert x-y\Vert }^2-F\left(T_L\left(y\right)\right)\ge \frac{L}{2}{\Vert x-T_L\left(y\right)\Vert }^2,$

by rearranging terms, we get

$F\left(x\right)-F\left(T_L\left(y\right)\right)\ge \frac{L}{2}{\Vert x-T_L\left(y\right)\Vert }^2-\frac{L}{2}{\Vert x-y\Vert }^2+f\left(x\right)-f\left(y\right)-\langle \nabla f\left(x\right),x-y\rangle .$

This completes the proof. □

Since $y$ is arbitrary, we may replace $y$ with $x$ , and thus the following corollary can be deduced from Lemma 7.

Corollary 1. Let $f:\mathcal{X}\to ℝ$ be a continuously differentiable convex function, where $\mathcal{X}$ is an open set, and let $g:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ be a proper closed convex function. For any $x,y\in \mathcal{X}$ and $L>0$ , if

$f\left(T_L\left(x\right)\right)\le f\left(x\right)+\langle \nabla f\left(x\right),T_L\left(x\right)-x\rangle +\frac{L}{2}{\Vert T_L\left(x\right)-x\Vert }^2,$

then

$F\left(x\right)-F\left(T_L\left(x\right)\right)\ge \frac{1}{2L}{\Vert G_L\left(x\right)\Vert }^2.$

Since the consecutive iterates $x^{t+1}$ and $x^t$ of the proximal gradient method satisfy $x^{t+1}=T_L\left(x^t\right)$ , Corollary 1 directly establishes the sufficient descent property of the PGD algorithm. In what follows, we combine the above lemmas to study the convergence rate of PGD for solving convex problems.

3.2. Convergence Rate Analysis of the Proximal Gradient Method in the Convex Case

In this subsection, we consider the case where $f$ in the objective function is convex, and analyze the convergence of PGD iterations under the generalized smoothness assumption. Specifically, the convergence rate results obtained through theoretical analysis are as follows.

Theorem 8. Consider problem (1). Let $g:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ be a proper closed convex function, and let $f:\mathcal{X}\to ℝ$ be a differentiable proper closed convex function, where $\mathcal{X}$ is an open convex set and $\text{dom}g\subseteq \mathcal{X}$ . Assume that $f$ is an $\left(r,\ell \right)$ -smooth function, where $\ell :\left[0,+\infty \right)\to \left(0,+\infty \right)$ is a nondecreasing continuous function and $r:\left[0,+\infty \right)\to \left(0,+\infty \right)$ is a nonincreasing continuous function. Moreover, suppose that $f$ is $C$ -Lipschitz continuous. If the parameter $L$ satisfies

$L\ge \text{max}\left\{\ell \left(C\right),2\Vert G_L\left(x_0\right)\Vert /r\left(C\right)\right\},$

then

$F\left(x^k\right)-F^{\text{*}}\le \frac{L{\Vert x^0-x^{\text{*}}\Vert }^2}{2k}.$

Proof. Since $f$ is $C$ -Lipschitz continuous, for any $x,y\in \mathcal{X}$ , we have

$\Vert \nabla f\left(x\right)\Vert =\underset{y\to x}{\text{lim}}\frac{\Vert f\left(y\right)-f\left(x\right)\Vert }{\left|y-x\right|}\le \frac{C\left|y-x\right|}{\left|y-x\right|}=C.$

Given that $f$ is convex and $\left(r,\ell \right)$ -smooth, and $g$ is a proper closed convex function. First, from

$x^{t+1}=T_L\left(x^t\right)$

and $G_L\left(x\right)=L\left(x-T_L\left(x\right)\right)$ , together with Lemma 6, we obtain

$\Vert x^{t+1}-x^t\Vert =\Vert T_L\left(x^t\right)-x^t\Vert =\frac{1}{L}\Vert G_L\left(x^t\right)\Vert \le \frac{1}{L}\Vert G_L\left(x^{t-1}\right)\Vert \le \cdots \le \frac{1}{L}\Vert G_L\left(x^0\right)\Vert \le \frac{r\left(C\right)}{2},$

which implies

$x^{t+1}\in B\left(x^t,\frac{r\left(C\right)}{2}\right).$

Secondly, by Lemma 3, the two consecutive iterates $x^{t+1},x^t$ of PGD always satisfy

$f\left(x^{t+1}\right)\le f\left(x^t\right)+\langle \nabla f\left(x^t\right),x^{t+1}-x^t\rangle +\frac{\ell \left(C\right)}{2}{\Vert x^{t+1}-x^t\Vert }^2.$ (20)

Finally, in Lemma 7, due to the arbitrariness of $L$ , we may set $L=\ell \left(C\right)$ . Together with $x^{t+1}=T_L\left(x^t\right)$ , we have for any $t\in {\mathbb{N}}^{\text{*}}$ ,

$\frac{2}{\ell \left(C\right)}\left(F\left(x^{\text{*}}\right)-F\left(x^{t+1}\right)\right)\ge {\Vert x^{\text{*}}-x^{t+1}\Vert }^2-{\Vert x^{\text{*}}-x^t\Vert }^2+\frac{2}{\ell \left(C\right)}h\left(x^{\text{*}},x^t\right),$ (21)

where, by Assumption 1, $x^{\text{*}}$ is the optimal solution of the objective function, and the second inequality follows from the convexity of $f$ . Now, letting $t$ run over $0,1,2,\cdots ,k-1$ and summing the inequalities, we obtain

$\frac{2}{\ell \left(C\right)}{\displaystyle \sum }_{t=0}^{k-1}\left(F\left(x^{\text{*}}\right)-F\left(x^{t+1}\right)\right)\ge {\Vert x^{\text{*}}-x^t\Vert }^2-{\Vert x^{\text{*}}-x^0\Vert }^2.$

Multiplying both sides of the above inequality by $\frac{\ell \left(C\right)}{2}$ , we get

${\displaystyle \sum }_{t=0}^{k-1}\left(F\left(x^{\text{*}}\right)-F\left(x^t\right)\right)\le \frac{\ell \left(C\right)}{2}{\Vert x^{\text{*}}-x^0\Vert }^2-\frac{\ell \left(C\right)}{2}{\Vert x^{\text{*}}-x^k\Vert }^2\le \frac{\ell \left(C\right)}{2}{\Vert x^{\text{*}}-x^0\Vert }^2.$

From Corollary 1, we also have $F\left(x^{t+1}\right)\le F\left(x^{\text{*}}\right)$ . Combining this with the above inequality yields

$\frac{2}{\ell \left(C\right)}{\displaystyle \sum }_{t=0}^{k-1}{\left(F\left(x^{\text{*}}\right)-F\left(x^{t+1}\right)\right)}^2\ge {\Vert x^{\text{*}}-x^k\Vert }^2-{\Vert x^{\text{*}}-x^0\Vert }^2.$

Multiplying both sides of the above inequality by $\frac{\ell \left(C\right)}{2}$ , we obtain

${\displaystyle \sum }_{t=0}^{k-1}\left(F\left(x^{\text{*}}\right)-F\left(x^t\right)\right)\le \frac{\ell \left(C\right)}{2}{\Vert x^{\text{*}}-x^0\Vert }^2-\frac{\ell \left(C\right)}{2}{\Vert x^{\text{*}}-x^k\Vert }^2\le \frac{\ell \left(C\right)}{2}{\Vert x^{\text{*}}-x^0\Vert }^2.$

From Corollary 1, we also have $F\left(x^{t+1}\right)\le F\left(x^t\right)$ . Combining this with the above inequality yields

$k\left(F\left(x^k\right)-F\left(x^{\text{*}}\right)\right)\le {\displaystyle \sum }_{t=1}^{k-1}\left(F\left(x^{t+1}\right)-F\left(x^{\text{*}}\right)\right)\le \frac{\ell \left(C\right)}{2}{\Vert x^{\text{*}}-x^0\Vert }^2,$

which can be rearranged as

$F\left(x^k\right)-F\left(x^{\text{*}}\right)\le \frac{\ell \left(C\right){\Vert x^{\text{*}}-x^0\Vert }^2}{2k}\le \frac{L{\Vert x^{\text{*}}-x^0\Vert }^2}{2k}.$

This completes the proof. □

4. Conclusions

To address the strict limitation of the classic gradient Lipschitz smoothness assumption on the applicability of the PGD, this paper introduces a novel class of generalized smoothness conditions—$\ell (\cdot )$ —smoothness, establishing a more general framework for analyzing composite convex optimization problems. Under this generalized smoothness framework, we systematically derive the convergence theory of the constant-stepsize PGD algorithm and rigorously prove that: even under the generalized smoothness assumption that relaxes the classic Lipschitz gradient continuity, the constant-stepsize PGD can still achieve the exact same sublinear convergence rate $O\left(1/k\right)$ as in the classic smoothness scenario, provided that the function $f$ satisfies $\ell (\cdot )$ —smoothness and Lipschitz continuity.

However, the analysis framework in this paper relies on the core assumption that the objective function $f$ satisfies gradient Lipschitz continuity. While this assumption guarantees the gradient Lipschitz continuity of $f$ in local regions and provides theoretical support for the convergence analysis of the constant-step-size PGD algorithm, it also significantly limits the scope of application of the method: for composite convex optimization problems that do not satisfy gradient Lipschitz continuity (such as scenarios with unbounded gradients or rapidly changing gradients), the sublinear convergence rate theory of the constant-step-size PGD algorithm established in this paper will no longer hold.

Acknowledgements

Sincere thanks to the members of JAMP for their professional performance, and special thanks to managing editor Hellen XU for a rare attitude of high quality.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Shechtman, Y., Beck, A. and Eldar, Y.C. (2014) GESPAR: Efficient Phase Retrieval of Sparse Signals. IEEE Transactions on Signal Processing, 62, 928-938.[CrossRef]
[2]	Cai, J.F., Long, Y., Wen, R.X. and Ying, J. (2023) A Fast and Provable Algorithm for Sparse Phase Retrieval.[CrossRef]
[3]	Bai, Y., Wang, Y.X. and Liberty, E. (2019) ProxQuant: Quantized Neural Networks Via Proximal Operators. 7th International Conference on Learning Representations (ICLR), New Orleans, 6-9 May 2019, 1-20.
[4]	Vũ, B.C. (2013) A Splitting Algorithm for Dual Monotone Inclusions Involving Cocoercive Operators. Advances in Computational Mathematics, 38, 667-681.[CrossRef]
[5]	Rockafellar, R.T. (2001) Monotone Operators and the Proximal Point Algorithm. SIAM Journal on Control and Optimization, 14, 877-898.[CrossRef]
[6]	Faw, M., Tziotis, I., Caramanis, C. and Mokhtari, A. (2022) The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance. Proceedings of the 35th Conference on Learning Theory (COLT), London, 2-5 July 2022, 313-355.
[7]	De Marchi, A., Jia, X., Kanzow, C. and Mehlitz, P. (2023) Constrained Composite Optimization and Augmented Lagrangian Methods. Mathematical Programming, 201, 863-896.[CrossRef]
[8]	Jia, X., Kanzow, C. and Mehlitz, P. (2023) Convergence Analysis of the Proximal Gradient Method in the Presence of the Kurdyka-Łojasiewicz Property without Global Lipschitz Assumptions. SIAM Journal on Optimization, 33, 3038-3056.[CrossRef]
[9]	Zhang, J., He, T., Sra, S. and Jadbabaie, A. (2020) Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity.[CrossRef]
[10]	Merity, S., Keskar, N.S. and Socher, R. (2018) Regularizing and Optimizing LSTM Language Models.[CrossRef]
[11]	He, K., Zhang, X., Ren, S. and Sun, J. (2016) Deep Residual Learning for Image Recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, 27-30 June 2016, 770-778.[CrossRef]
[12]	Mikolov, T. (2012) Statistical Language Models Based on Neural Networks. Brno University of Technology, Faculty of Information Technology. https://www.fit.vut.cz/study/phd-thesis/283/
[13]	Xian, W., Chen, Z. and Huang, H. (2024) Delving into the Convergence of Generalized Smooth Minimax Optimization. Communications in Mathematical Physics, 235, 54191-54211.
[14]	Hao, J., Gong, X. and Liu M. (2024) Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis. https://arxiv.org/abs/2401.09587
[15]	Vankov, D., Nedich, A. and Sankar, L. (2024) Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes. Proceedings of the 41st International Conference on Machine Learning (ICML), Vienna, 21-27 July 2024, 49137-49170. https://proceedings.mlr.press/v235/vankov24a.html
[16]	Chen, Z., Zhou, Y., Liang, Y. and Lu, Z. (2023) Generalized-Smooth Nonconvex Optimization Is as Efficient as Smooth Nonconvex Optimization. Proceedings of the 40th International Conference on Machine Learning (ICML), Honolulu, 23-29 July 2023, 5396-5427. https://proceedings.mlr.press/v202/chen23v.html
[17]	Levy, D., Carmon, Y., Duchi, J.C. and Sidford, A. (2020) Large-Scale Methods for Distributionally Robust Optimization. https://arxiv.org/abs/2010.05893
[18]	Jin, J., Zhang, B., Wang, H. and Wang, L. (2021) Non-Convex Distributionally Robust Optimization: Non-Asymptotic Analysis. https://arxiv.org/abs/2110.12459
[19]	Cortés, J. (2006) Finite-time Convergent Gradient Flows with Applications to Network Consensus. Automatica, 42, 1993-2000.[CrossRef]
[20]	Fang, C., Li, C., Lin, Z. and Zhang, T. (2018) SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator. https://arxiv.org/pdf/1807.01695
[21]	Li, H., Tian, Y., Rakhlin, A. and Jadbabaie, A. (2023) Convex and Non-Convex Optimization under Generalized Smoothness. https://arxiv.org/pdf/2306.01264.pdf
[22]	Nesterov, Y.E. (1983) A Method for Solving the Convex Programming Problem with Convergence Rate O(1/k2). Proceedings of the USSR Academy of Sciences, 269, 543-547.
[23]	Beck, A. (2017) First-Order Methods in Optimization. Society for Industrial and Applied Mathematics.[CrossRef]