Almost Sure Convergence of Proximal Stochastic Accelerated Gradient Methods

Xin Xiang, Haoming Xia^*

Key Laboratory of Optimization Theory and Applications, School of Mathematics and Information, China West Normal University, Nanchong, China.

DOI: 10.4236/jamp.2024.124081                

Abstract

Proximal gradient descent and its accelerated version are resultful methods for solving the sum of smooth and non-smooth problems. When the smooth function can be represented as a sum of multiple functions, the stochastic proximal gradient method performs well. However, research on its accelerated version remains unclear. This paper proposes a proximal stochastic accelerated gradient (PSAG) method to address problems involving a combination of smooth and non-smooth components, where the smooth part corresponds to the average of multiple block sums. Simultaneously, most of convergence analyses hold in expectation. To this end, under some mind conditions, we present an almost sure convergence of unbiased gradient estimation in the non-smooth setting. Moreover, we establish that the minimum of the squared gradient mapping norm arbitrarily converges to zero with probability one.

Keywords

Proximal Stochastic Accelerated Method, Almost Sure Convergence, Composite Optimization, Non-Smooth Optimization, Stochastic Optimization, Accelerated Gradient Method

1. Introduction

We consider the following composite optimization problem:

$\underset{x\in {ℝ}^d}{\min }\mathrm{<mi>\; </mi>\; <mi>\; </mi>}F\left(x\right)\stackrel{\text{def}}{=}f\left(x\right)+g\left(x\right)\mathrm{,}$ (1)

where $g\mathrm{<mo>\; :\; </mo>}{ℝ}^d\to ℝ$ is the average of the smooth functions $g_1\mathrm{,}\cdots \mathrm{,}{g}_n$ , i.e. $g\left(x\right)=\frac{1}{n}{\displaystyle {\sum }_{i=1}^n}{g}_i\left(x\right)$ and $f\mathrm{<mo>\; :\; </mo>}{ℝ}^d\to ℝ$ is a closed proper function that can be non-differentiable. One of the most well-studied instances of this type of problem is ${\mathcal{l}}_1$ -regularized least squares [1] :

$\underset{x\in {ℝ}^d}{\min }\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\frac{1}{2}{\left(a_i^{\text{T}}x-b_i\right)}^2+\lambda {\Vert x\Vert }_1$

where $\Vert \cdot \Vert$ denotes the standard ${\mathcal{l}}_1$ -norm.

We frequently encounter optimization problems of this nature in various fields such as machine learning, statistics, signal processing, and imaging [2] [3] [4] [5] . Specifically, we address the task of minimizing the aggregate of two functions: one represents the average of numerous smooth component functions, while the other characterizes a general function amenable to a straightforward proximal mapping. It is imperative for us to ensure that the problem is well-defined, denoted by $\arg \min F\ne \varnothing$ , and that each $g_i$ remains bounded from below. Compared with the classical gradient descent (GD) method and stochastic gradient descent (SGD) method [6] , the proximal gradient descent (PGD) method has a relatively limited application scope, primarily employed for addressing objective functions that include non-differentiable components. To tackle the non-smooth optimization problem (1), mentioned earlier, we introduce the PGD. It can be delineated by the following update rule for $k=\mathrm{1,2,}\cdots$ :

$x_{k+1}={\text{prox}}_{t_{k}f}\left(x_k-t_k\nabla g\left(x_k\right)\right)\mathrm{,}$ (2)

where $t_k$ is the step size at the kth iteration and the proximity operator of f ${\text{prox}}_f(\cdot )$ is defined by:

${\text{prox}}_{tf}\left(y\right)=\underset{x\in {ℝ}^d}{\arg \min }\left\{\frac{1}{2}{\Vert x-y\Vert }^2+tf\left(x\right)\right\}\mathrm{.}$

We note that ${\text{prox}}_{tf}\left(y\right)$ maps to a singleton since $f\left(y\right)$ is proper and closed, see for example (Beck, Theorem 6.3, 2017 [7] ). PGD has adopted attributes to proximal operators no longer rely on $g\left(x\right)$ , only $f\left(x\right)$ . That is, $F\left(x\right)=g\left(x\right)+f\left(x\right)$ could be a combination of a very complex differentiable function and a less complex non-differentiable function originally, but with this method, we don’t need to consider $g\left(x\right)$ (because it is differentiable and the gradient is easy to calculate), we just have to focus on the non-differentiable function $f\left(x\right)$ , which greatly simplifies our problem. PGD can achieve an error level on the objective function of $O\left(1/k\right)$ after k iterations [8] .

1.1. Related Work

1.1.1. Accelerated Proximal Gradient (APG) Method

Another effective method for solving problem (1) is the accelerated proximal gradient (APG) method, initially proposed by Nesterov [8] for minimizing smooth convex functions with constraints. It was later extended by Beck and Teboulle [9] to composite convex objective functions. The Fast Iterative Shrinkage-Threholding Algorithm (FISTA), an accelerated version of the proximal gradient method, has found applications in various fields, including image and signal processing. APG represents an accelerated variant of the deterministic gradient descent method, incorporating an extrapolation step in the algorithm. One simple version involves selecting an initial point $x_0=x_{-1}\in {ℝ}^n$ , and repeating for $k=\mathrm{1,2,3,}\cdots$ .

$y_{k+1}\mathrm{<mo>\; :\; </mo>}=x_k+{\beta }_k\left(x_k-x_{k-1}\right)$

$x_{k+1}\mathrm{<mo>\; :\; </mo>}={\text{prox}}_{t_{k}f}\left(y_{k+1}-t_k\nabla g\left(y_{k+1}\right)\right)$

where ${\beta }_k\in \left[\mathrm{0,1}\right)$ is an extrapolation parameter and $t_k$ is the usual step size.

These parameters must be chosen in specific ways to achieve the convergence accelerated. One simple choice takes ${\beta }_k=\frac{k}{k+3}$ [10] . It remains to choose the step sizes $t_k$ . When $\nabla g$ is Lipschitz continuous with constant L, this method can be shown to converge in objective value with $O\left(1/k^2\right)$ when a fixed step size $t_k=t\in \left(\mathrm{0,}1/L\right]$ is used [8] [9] . Following Nesterov, this method is called an accelerated or optimal first-order method and there are several versions of such methods, such as Nesterov [8] ; the software package TFOCS [11] is based on and contains several implementations of such methods. Li et al. [12] were the first to provide APG-type algorithms for general non-convex and non-smooth problems ensuring that every accumulation point is a critical point.

1.1.2. Proximal Stochastic Gradient Descent (PSGD) Method

With the emergence of big data, the efficiency of deterministic optimization algorithm has gradually become a bottleneck. In the PGD (2), we need to calculate the full gradient of $g(\cdot )$ . When the size of the datasets n is very large, where the calculation costs will be high, first-order stochastic gradient methods have proven to be very effective thanks to their low iteration complexity. Therefore, one way to reduce calculation is to use stochastic algorithms that take advantage of the finite sum structure of the problem (1) to use cheaper iterations while preserving fast convergence. When $f\left(x\right)=0$ , problem (1) reduces to general minimization optimization problem: $\underset{x\in {ℝ}^d}{\min }F\left(x\right)\stackrel{\text{def}}{=}\frac{1}{n}{\displaystyle {\sum }_{i=1}^n}{g}_i\left(x\right)$ , where $F\left(x\right)$ arise as averages of a very large number of smooth functions. This problem often arises by approximation of the stochastic optimization loss function: $F\left(x\right)={\mathbb{E}}_{\xi \in \mathcal{D}}\left[g_{\xi }\left(x\right)\right]$ , where $\xi$ is a random variable, $g_{\xi }\mathrm{<mo>\; :\; </mo>}{ℝ}^d\to ℝ$ is smooth for all $\xi$ . First-order stochastic methods for the case of a non-smooth regularizer $f\left(x\right)$ are an active research area. Non-asymptotic convergence results were first achieved in [13] . For finite-sum problems, Reddi et al. [14] were the first to develop a proximal stochastic variance reduced gradient algorithm with improved convergence complexity. Metel et al. [15] first presented the non-asymptotic convergence results for the non-smooth non-covex constrained sparse optimization problem and they presented two simple stochastic proximal gradient algorithms, for stochastic and finite-sum optimization problems. Kawashima et al. [16] considered $f\left(x\right)$ as a non-smooth quasi-convex function and achieved the same convergence complexity as in Ghadimi et al. (2016) [13] . A stochastic variant of PGD is proximal stochastic gradient descent (PSGD). At each iteration $k=\mathrm{1,2,}\cdots$ , it picks $i_k$ with probability $\frac{1}{n}$ from $\left[n\right]=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ via independent identically distribution. The PSGD takes the following update:

$x_{k+1}={\text{prox}}_{t_{k}f}\left(x_k-t_k\nabla g_{i_k}\left(x_k\right)\right)\text{.}$ (3)

where $t_k>0$ is a sequence of step size (also known as learning rate). Sampling the index $i_k$ over all indices $\left[n\right]=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ with i.i.d., the gradient $\nabla g_{i_k}\left(x_k\right)$ satisfies the unbiased estimation:

$\mathbb{E}\left[\nabla g_{i_k}\left(x_k\right)\right]={\displaystyle \underset{i=1}{\overset{n}{\sum }}}\frac{1}{n}\nabla g_{i_k}\left(x_k\right)=\nabla g\left(x_k\right).$ (4)

The advantage of PSGD over PGD lies in the fact that, at each iteration, PSGD only necessitates the computation of a single gradient $\nabla g_{i_k}\left(x_k\right)$ . In contrast, each iteration of PGD evaluates n g gradients. As a result, the computational cost of PSGD per iteration is $\frac{1}{n}$ of that of PGD. Consequently, the computation of $\nabla g_{i_k}\left(x_k\right)$ is approximately n times less expensive than that of $\nabla g\left(x\right)$ . Numerous algorithms have been devised to tackle the composite optimization problem (1). Gorbunov et al. [17] provided a unified analysis covering a broad range of variants of PSGD. In a study by Cevher et al. [18] , it was demonstrated that PSGD, assuming strong convexity, displays linear convergence towards a region dominated by noise.

1.1.3. Convergence Criteria

The vast majority of the convergence rates analysis results for stochastic gradient methods in the literature are obtained in terms of the expectation (see, e.g. SGD, stochastic heavy ball (SHB) [19] , stochastic Nesterov’s accelerated gradient (SNAG) and so forth). However, almost sure convergence (a.s. for short, also known as “convergence with probability 1”) [20] properties are important, because they represent what happens to individual trajectories of the stochastic iterations, which are instantiations of the stochastic algorithms actually used in practice. Therefore, almost sure convergence of methods based on stochastic gradient is of practical relevance. For SGD, in the convex and smooth setting, Sebbouh et al. [21] provided the almost sure asymptotic convergence rates for a weighted average of the iterates. The almost sure convergence of the last iteration of SGD on non-convex functions is generalized by Orabona [22] . Liu et al. [23] provide a unified almost sure convergence rates analysis for SGD, SHB and SNAG. Recently, Liang et al. [24] presented an almost sure convergence analysis of stochastic composite objective mirror descent (SCOMID).

Remark 1.1. It is worth noting that our proof does not rely on the convexity of the function f, so convexity of f is not assumed in the model. However, to ensure the continuity of the generalized gradient operator, we assume that f is convex.

1.2. Proximal Stochastic Accelerated Gradient (PSAG) Method

Based on the above, we now consider an accelerated version of proximal stochastic

Table 1. Comparison of problem setting, momentum, algorithm and convergence results with some relevant literature.

SCOMID = Stochastic Composite Objective Mirror Descent; PSGD = Proximal Stochastic Gradient Descent; SGD = Stochastic Gradient Descent; AdaGrad = Adaptive Stochastic Gradient Descent; SHB = Stochastic Heavy Ball; SNAG = Stochastic Nesterov’s Accelerated graDient; PSAG = Proximal Stochastic Accelerated Gradient (in this paper).

gradient method and use the unbiased stochastic gradient (see the last column of Table 1), the iteration of the PSAG method is given by:

$y_{k+1}\mathrm{<mo>\; :\; </mo>}=x_k+{\beta }_k\left(x_k-x_{k-1}\right)$

$x_{k+1}\mathrm{<mo>\; :\; </mo>}={\text{prox}}_{t_{k}f}\left(y_{k+1}-t_k{\mathcal{G}}_k\right)$ (5)

where ${\beta }_k\in \left[\mathrm{0,1}\right)$ is an extrapolation parameter and $t_k$ is the usual step size, ${\mathcal{G}}_k=\nabla g_{i_k}\left(y_{k+1}\right)$ is an unbiased estimator of the gradient, where $i_k$ is randomly picked from $\left[n\right]=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ with probability $\frac{1}{n}$ via the independent identically distribution. Then, we have:

$x_{k+1}\in \underset{x\in {ℝ}^d}{\arg \min }\left\{t\langle {\mathcal{G}}_k,x\rangle +tf\left(x\right)+\frac{1}{2}{\Vert x-x_k\Vert }^2\right\}.$ (6)

where in (5), $t=t_k$ is the stepsize, ${\mathcal{G}}_k$ is the stochastic gradient and $x_k=y_{k+1}$ is an extrapolation step. For non-smooth composite problem (1), we establish almost sure convergence rates of PSAG that the minimum of the squared gradient mapping norm is arbitrarily close to zero with probability one. It is noted that PSAG method reduces to PSGD method when ${\beta }_k=0$ in (5).

The rest of this paper is organized as follows. In Section 2, we recall some definitions and known results for further analysis. Then, we present our convergence analysis of PSAG and its convergence rate in Section 3. Finally, we summarize our findings and draw conclusions in Section 4.

2. Preliminaries

2.1. Notations

The optimal solution of problem (1) is denoted by $x^{\mathrm{<mo>\; *\; </mo>}}$ , and the optimal set of problem (1) is non-empty and denoted by $X^{\mathrm{<mo>\; *\; </mo>}}$ . The optimal value of the problem (1) is denoted by $F^{\mathrm{<mo>\; *\; </mo>}}=F\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ . In the rest of this work, for notational brevity, we will omit the subscript of norm ${\Vert \cdot \Vert }_2$ for $\Vert \cdot \Vert$ .

2.2. Definitions

Definition 2.1. (Convexity). A function $g\mathrm{<mo>\; :\; </mo>}{ℝ}^d\to ℝ$ is said to be convex; i.e. for all $x\mathrm{,}y\in {ℝ}^d$ ,

$g\left(x\right)\ge g\left(y\right)+\langle \nabla g\left(y\right)\mathrm{,}x-y\rangle \mathrm{.}$ (7)

Definition 2.2. (L-smoothness). A function $g\mathrm{<mo>\; :\; </mo>}{ℝ}^d\to ℝ$ is said to be L-smooth if the gradient $\nabla g\left(x\right)$ is Lipschitz continuous with constant L, i.e. there exists a constant $L>0$ such that:

$\Vert \nabla g\left(x\right)-\nabla g\left(y\right)\Vert \le L\Vert x-y\Vert$ , for all $x,y\in {ℝ}^d$ . (8)

It is well-known that Definition 2.2 implies the following inequality (see, e.g. Nesterov [31] (Lemma 1.2.3)):

$g\left(x\right)\le g\left(y\right)+\langle \nabla g\left(y\right)\mathrm{,}x-y\rangle +\frac{L}{2}{\Vert x-y\Vert }^2\mathrm{,\; <mi>\; </mi>\; <mi>\; </mi>}\forall \mathrm{<mi>\; </mi>}x\mathrm{,}y\in {ℝ}^d\mathrm{.}$ (9)

Remark 2.1. Definition 2.2 essentially implies that gradient descent with sufficiently small step size is well behaved, and we also have $g\left(x\right)={\displaystyle {\sum }_{i=1}^n}{g}_i\left(x\right)$ is L-smooth where $L={\displaystyle {\sum }_i^n}{L}_i$ ( $g_i\left(x\right)$ is $L_i$ -smooth).

Definition 2.3. (Unbiasedness). Given a random iterate ${\left\{x_k\right\}}_{k\ge 0}$ . We call the stochastic gradient $\nabla g_{i_k}\left(x_k\right)$ ( $i_k$ is sampled randomly from $\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ ) is unbiased if:

$\mathbb{E}\left[\nabla g_{i_k}\left(x_k\right)\right]=\nabla g\left(x_k\right)$ (10)

holds.

Definition 2.4. (Prox-grad operator). Consider the composite optimization problem (1), we have:

$x_k^{+}=T_{t_k}^{f\mathrm{,}g}(\; x\; k\; )$

where $T_t^{f\mathrm{,}g}\mathrm{<mo>\; :\; </mo>}int\left(dom\left(g\right)\right)\to \mathbb{E}\left(t>0\right)$ is the prox-grad operator defined by:

$T_t^{f\mathrm{,}g}\left(x\right)\equiv {\text{prox}}_{tf}\left(x-t\nabla g\left(x\right)\right)$ (11)

Definition 2.5. (Gradient mapping). Suppose that $f\mathrm{,}g$ satisfy the problem (1) settings. Then, the gradient mapping is the operator $G_t^{f\mathrm{,}g}\mathrm{<mo>\; :\; </mo>}int\left(dom\left(g\right)\right)\to \mathbb{E}$ defined by:

$G_t^{f\mathrm{,}g}\left(x\right)\equiv \frac{1}{t}\left(x-T_t^{f\mathrm{,}g}\left(x\right)\right)$ (12)

for any $x\in int\left(dom\left(g\right)\right)$ .

3. Convergence Analysis

3.1. Lemmas on Supermartingale Convergence Rates

The proof about almost sure convergence relies on the classical Robbins-Siegmund supermartingale convergence result (Theorem 1 in [32] ).

Lemma 3.1. (Theorem 1, [32] ) Assume that $\left\{X_k\right\}\mathrm{,}\left\{Y_k\right\}$ and $\left\{Z_k\right\}$ are three non-negative sequences of random variable, $\left\{{\gamma }_k\right\}$ is a non-negative real sequence and ${\mathcal{F}}_k$ is a σ-algebra. If $X_k\mathrm{,\; <mi>\; </mi>}{Y}_k\mathrm{,\; <mi>\; </mi>}{Z}_k$ are all ${\mathcal{F}}_k$ -measurable and the following conditions holds:

1) $\mathbb{E}\left[Y_{k+1}|{\mathcal{F}}_k\right]\le \left(1+{\gamma }_k\right)Y_k-X_k+Z_k$ .

2) ${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}{\gamma }_k<\infty ,{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}{Z}_k<\infty$ almost surely.

Then, $Y_k$ converges almost surely and ${\displaystyle {\sum }_{k=1}^{\infty }}{X}_k<\infty$ almost surely (a.s.)

Lemma 3.2. (Lemma 3, [23] ) Assume that $\left\{X_k\right\}$ is a non-negative sequence of random variable and $t_k\ge 0$ is non-increasing. If the following conditions hold:

${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}\frac{t_{k+1}}{{\displaystyle {\sum }_{s=1}^k{t}_s}}=\infty ,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}{t}_{k+1}{X}_k<\infty \mathrm{<mi>\; </mi>}a.s.$ (13)

then we have:

$\underset{1\le i\le k}{\min }{X}_i=o\left(\frac{1}{{\displaystyle {\sum }_{j=1}^k{t}_s}}\right)\mathrm{<mi>\; </mi>\; <mi>\; </mi>}a.s.$ (14)

where o denotes the higher-order infinitesimal. i.e. for two sequences $\left\{a_k\right\}\to 0$ and $\left\{b_k\right\}\to 0$ , $a_k=o\left(b_k\right)$ if and only if ${\lim }_{k\to \infty }{a}_k/b_k=0$ .

3.2. Almost Sure Convergence Rate Analysis for Stochastic Proximal Accelerated Gradient Method

Reviewing the iteration of PSAG (5), using the Definition 2.4, 2.5, we rewrite the PSAG as follows:

$y_{k+1}\mathrm{<mo>\; :\; </mo>}=x_k+\beta \left(x_k-x_{k-1}\right)\mathrm{,}$

$x_{k+1}:=y_{k+1}-t_k{G}_{t_k}\left(y_{k+1}\right).$ (15)

where $G_{t_k}\left(y_{k+1}\right)=\frac{1}{t_k}\left(y_{k+1}-T_{t_k}^{f,g_{i_k}}\left(y_{k+1}\right)\right)$ , $T_{t_k}^{f,g_{i_k}}\left(y_{k+1}\right)={\text{prox}}_{t_{k}f}\left(y_{k+1}-t_k\nabla g_{i_k}\left(y_{k+1}\right)\right)$ , $t_k$ is the step size and $\beta ={\beta }_k\in \left[0,1\right)$ and $i_k$ is randomly picked from $\left[n\right]=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ with probability $\frac{1}{n}$ via the independent identically distribution.

Lemma 3.3. Suppose that $u\in \arg {\min }_{x\in {ℝ}^d}\left\{t\langle z,x\rangle +tf\left(x\right)+\frac{1}{2}{\Vert x-y\Vert }^2\right\}$ for some $z\mathrm{,}y\in {ℝ}^d$ . If $g\left(x\right)$ is L-smooth, the for any $x\in {ℝ}^d$ , we have:

$F\left(u\right)\le F\left(x\right)+\langle \nabla g\left(y\right)-z\mathrm{,}u-x\rangle +\frac{1}{2t}{\Vert x-y\Vert }^2-\frac{1}{2t}{\Vert u-y\Vert }^2+\frac{L}{2}{\Vert u-y\Vert }^2\mathrm{.}$ (16)

Proof By the optimality of u, we can show that for any $x\in {ℝ}^d$ ,

$t\langle z\mathrm{,}u\rangle +tf\left(u\right)+\frac{1}{2}{\Vert u-y\Vert }^2\le t\langle z\mathrm{,}x\rangle +tf\left(x\right)+\frac{1}{2}{\Vert x-y\Vert }^2$ (17)

Upon rearranging the above equation, we have:

$f\left(u\right)\le f\left(x\right)+\langle z\mathrm{,}x-u\rangle +\frac{1}{2t}{\Vert x-y\Vert }^2-\frac{1}{2t}{\Vert u-y\Vert }^2\mathrm{.}$ (18)

Since $g\left(x\right)$ is L-smooth, we can apply Definition 2.2 to have:

$g\left(u\right)\le g\left(y\right)+\langle \nabla g\left(y\right)\mathrm{,}u-y\rangle +\frac{L}{2}{\Vert u-y\Vert }^2\mathrm{.}$ (19)

$g\left(x\right)\ge g\left(y\right)+\langle \nabla g\left(y\right)\mathrm{,}x-y\rangle +\frac{1}{2L}{\Vert \nabla g\left(x\right)-\nabla g\left(y\right)\Vert }^2\mathrm{.}$ (20)

Next, upon combining (19) and (20), we arrive at:

$\begin{array}{c}g\left(u\right)\le g\left(y\right)+\langle \nabla g\left(y\right)\mathrm{,}u-y\rangle +\frac{L}{2}{\Vert u-y\Vert }^2\\ \le g\left(x\right)+\langle \nabla g\left(y\right)\mathrm{,}y-x\rangle -\frac{1}{2L}{\Vert \nabla g\left(x\right)-\nabla g\left(y\right)\Vert }^2\\ +\langle \nabla g\left(y\right)\mathrm{,}u-y\rangle +\frac{L}{2}{\Vert u-y\Vert }^2\\ \le g\left(x\right)+\langle \nabla g\left(y\right)\mathrm{,}u-x\rangle +\frac{L}{2}{\Vert u-y\Vert }^2\mathrm{.}\end{array}$ (21)

By the fact that $F\left(u\right)=g\left(u\right)+f\left(u\right)$ , we finally obtain:

$\begin{array}{c}F\left(u\right)=g\left(u\right)+f\left(u\right)\\ \le g\left(u\right)+f\left(x\right)+\langle z,x-u\rangle +\frac{1}{2t}{\Vert x-y\Vert }^2-\frac{1}{2t}{\Vert u-y\Vert }^2\\ \le g\left(x\right)+\langle \nabla g\left(y\right),u-x\rangle +\frac{L}{2}{\Vert u-y\Vert }^2\\ \mathrm{<mi>\; </mi>\; <mi>\; </mi>}+f\left(x\right)+\langle z,x-u\rangle +\frac{1}{2t}{\Vert x-y\Vert }^2-\frac{1}{2t}{\Vert u-y\Vert }^2\\ =F\left(x\right)+\langle \nabla g\left(y\right)-z,u-x\rangle +\frac{1}{2t}{\Vert x-y\Vert }^2-\frac{1}{2t}{\Vert u-y\Vert }^2+\frac{L}{2}{\Vert u-y\Vert }^2.\end{array}$ (22)

Theorem 3.1. Suppose that $F\left(x\right)$ is lower bounded and there exists $\sigma >0$ , $A_k\ge 0$ such that:

$\mathbb{E}\left[{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]\le A_k\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)+{\sigma }^2\mathrm{,}$ (23)

where ${\mathcal{G}}_k=\nabla g_{i_k}\left(y_{k+1}\right)$ , $i_k$ is randomly picked from $\left[n\right]=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ with probability $\frac{1}{n}$ via the independent identically distribution, the iteration of PSAG (15) is employed with a non-increasing stepsize $t_k$ such that:

${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}{t}_k^2<\infty ,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}{A}_k{t}_k<\infty ,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}\frac{t_{k+1}}{{\displaystyle {\sum }_{s=1}^k{t}_s}}=\infty$ and $t_k\le \frac{1}{4L}$ ,

where $A_k\ge 0$ is defined in (23), then we have:

$\left\{F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right\}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.}$

If $f\mathrm{<mo>\; :\; </mo>}{ℝ}^d\to ℝ$ is convex, we obtain:

$\underset{1\le i\le k}{\min }{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2=o\left(\frac{1}{{\displaystyle {\sum }_{s=1}^k{t}_s}}\right)\mathrm{<mi>\; </mi>\; <mi>\; </mi>}a.s.$ (24)

Proof We begin with the conclusion in (16) of Lemma 3.3. Firstly, by the definition of $x_k^{+}$ in Definition 2.4, let $u=x_k^{+}$ , then set $t=\frac{t_k}{2}$ , $z=\nabla g\left(x_k\right)$ and $y=x_k$ to meet the condition $u\in \arg {\min }_{x\in {ℝ}^d}\left\{t\langle z,x\rangle +tf\left(x\right)+\frac{1}{2}{\Vert x-y\Vert }^2\right\}$ , i.e.

$x_k^{+}\in \arg {\min }_{x\in {ℝ}^d}\left\{\frac{t_k}{2}\langle \nabla g\left(x_k\right),x\rangle +\frac{t_k}{2}f\left(x\right)+\frac{1}{2}{\Vert x-x_k\Vert }^2\right\}$ (25)

From the update in (2), we can show that the iterate $x_k\in {ℝ}^d$ for any $k\ge 1$ . Upon applying Lemma 3.3 with $u=x_k^{+}$ , $t=\frac{t_k}{2}$ , $z=\nabla g\left(x_k\right)$ and $y=x_k$ for $x=x_k\in {ℝ}^d$ , we have:

$\begin{array}{c}F\left(x_k^{+}\right)\le F\left(x_k\right)+\langle \nabla g\left(x_k\right)-\nabla g\left(x_k\right)\mathrm{,}{x}_k^{+}-x_k\rangle +\frac{1}{t_k}{\Vert x_k-x_k\Vert }^2\\ -\frac{1}{t_k}{\Vert x_k^{+}-x_k\Vert }^2+\frac{L}{2}{\Vert x_k^{+}-x_k\Vert }^2\\ =F\left(x_k\right)+\left(\frac{L}{2}-\frac{1}{t_k}\right){\Vert x_k^{+}-x_k\Vert }^2\mathrm{.}\end{array}$ (26)

Next, by the update rule in (6) of PSAG algorithm, we choose $u=x_{k+1}$ , then set $t=t_k$ , $z={\mathcal{G}}_k=\nabla g_i\left(y_{k+1}\right)$ and $y=y_{k+1}$ to meet the condition $u\in \arg {\min }_{x\in {ℝ}^n}\left\{t\langle z,x\rangle +tf\left(x\right)+\frac{1}{2}{\Vert x-y\Vert }^2\right\}$ , i.e.

$x_{k+1}\in \arg {\min }_{x\in {ℝ}^d}\left\{t_k\langle {\mathcal{G}}_k,x\rangle +t_{k}f\left(x\right)+\frac{1}{2}{\Vert x-y_{k+1}\Vert }^2\right\}$ (27)

Similarly, from the definition of $x_k^{+}$ in (25), we can show that for any $k\ge 1$ , the sequence $x_k^{+}\in {ℝ}^d$ . Now, upon applying Lemma 3.3 with $u=x_{k+1}$ , $t=t_k$ , $z={\mathcal{G}}_k$ , and $y=y_{k+1}$ , for $x=x_k^{+}\in {ℝ}^d$ , we then obtain:

$\begin{array}{c}F\left(x_{k+1}\right)\le F\left(x_k^{+}\right)+\langle \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\mathrm{,}{x}_{k+1}-x_k^{+}\rangle +\frac{1}{2t_k}{\Vert x_k^{+}-y_{k+1}\Vert }^2\\ -\frac{1}{2t_k}{\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{L}{2}{\Vert x_{k+1}-y_{k+1}\Vert }^2\\ =F\left(x_k^{+}\right)+\left(\frac{L}{2}-\frac{1}{2t_k}\right){\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{1}{2t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\\ +\langle \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\mathrm{,}{x}_{k+1}-x_k^{+}\rangle \mathrm{.}\end{array}$ (28)

Now, we consider $\langle \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\mathrm{,}{x}_{k+1}-x_k^{+}\rangle$ ,

$\begin{array}{l}\langle \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\mathrm{,}{x}_{k+1}-x_k^{+}\rangle \\ \le \Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert \cdot \Vert x_{k+1}-x_k^{+}\Vert \\ \le 2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2+\frac{1}{8t_k}{\Vert x_{k+1}-x_k^{+}\Vert }^2\\ =2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2+\frac{1}{8t_k}{\Vert x_{k+1}-y_{k+1}+y_{k+1}-x_k^{+}\Vert }^2\\ \le 2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2+\frac{1}{4t_k}{\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{1}{4t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\mathrm{,}\end{array}$ (29)

where we use the Cauchy-Schwarz $\left|\langle a\mathrm{,}b\rangle \right|\le \Vert a\Vert \Vert b\Vert$ in the first inequality, and the second inequality follows from $ab\le \left(1/2\right)\left(a^2+b^2\right)$ with $a=2\sqrt{t_k}\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert$ and $b=\frac{1}{2\sqrt{t_k}}\Vert x_{k+1}-x_k^{+}\Vert$ . The last inequality holds by ${\Vert a+b\Vert }^2\le 2{\Vert a\Vert }^2+2{\Vert b\Vert }^2$ with $a=x_{k+1}-y_{k+1}$ and $b=y_{k+1}-x_k^{+}$ .

Upon substituting (29) back into (28), we further have:

$\begin{array}{c}F\left(x_{k+1}\right)\le F\left(x_k^{+}\right)+\left(\frac{L}{2}-\frac{1}{2t_k}\right){\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{1}{2t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\\ +\langle \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\mathrm{,}{x}_{k+1}-x_k^{+}\rangle \\ \le F\left(x_k^{+}\right)+\left(\frac{L}{2}-\frac{1}{2t_k}\right){\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{1}{2t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\\ +2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2+\frac{1}{4t_k}{\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{1}{4t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\end{array}$

$\begin{array}{c}=F\left(x_k^{+}\right)+\left(\frac{L}{2}-\frac{1}{4t_k}\right){\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{3}{4t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\\ +2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2\\ \le F\left(x_k\right)+\left(\frac{L}{2}-\frac{1}{t_k}\right){\Vert x_k^{+}-x_k\Vert }^2+2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2\\ +\left(\frac{L}{2}-\frac{1}{4t_k}\right){\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{3}{4t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\\ \le F\left(x_k\right)+2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2-\frac{1}{8t_k}{\Vert x_{k+1}-y_{k+1}\Vert }^2+\frac{3}{4t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2\mathrm{.}\end{array}$ (30)

where the last inequality holds by the stepsize condition $t_k\le 1/4L$ , i.e. $L/2-1/4t_k\le -1/8t_k$ .

Next, we consider $\frac{3}{4t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2$ and combine Definition 2.4 with (5) and (15), we have:

$x_k^{+}=T_{t_k}^{f\mathrm{,}{g}_{i_k}}\left(y_{k+1}\right)={\text{prox}}_{t_{k}f}\left(y_{k+1}-t_k\nabla g_{i_k}\left(y_{k+1}\right)\right)\mathrm{,}$

and

$\begin{array}{c}{G}_{t_k}\left(y_{k+1}\right)=\frac{1}{t_k}\left(y_{k+1}-T_{t_k}^{f\mathrm{,}{g}_{i_k}}\left(y_{k+1}\right)\right)\\ =\frac{1}{t_k}\left(y_{k+1}-x_k^{+}\right)\mathrm{,}\end{array}$

Due to the convexity of f, we know that there exists $M>0$ such that:

$\Vert G_{t_k}\left(y_{k+1}\right)\Vert <M\mathrm{.}$

Therefore,

$\frac{3}{4t_k}{\Vert y_{k+1}-x_k^{+}\Vert }^2=\frac{3t_k}{4}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2\le \frac{3M^2}{4}{t}_k\mathrm{.}$ (31)

Then, by (15), we also have:

$-\frac{1}{8t_k}{\Vert x_{k+1}-y_{k+1}\Vert }^2=-\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2\mathrm{.}$ (32)

Upon combining (31) and (32) with (30), we have:

$F\left(x_{k+1}\right)\le F\left(x_k\right)-\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+2t_k{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2+\frac{3M^2}{4}{t}_k\mathrm{.}$ (33)

Now, the conditional expectation on (33) with respect to ${\mathcal{F}}_k$ gives:

$\begin{array}{l}\mathbb{E}\left[F\left(x_{k+1}\right)\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]\\ \le \mathbb{E}\left[F\left(x_k\right)\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]-\frac{t_k}{8}\mathbb{E}\left[{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]\\ +2t_k\mathbb{E}\left[{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]+\frac{3M^2}{4}{t}_k\\ =F\left(x_k\right)-\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+2t_k\mathbb{E}\left[{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]+\frac{3M^2}{4}{t}_k\\ \le F\left(x_k\right)-\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+2t_k\left(A_k\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)+{\sigma }^2\right)+\frac{3M^2}{4}{t}_k\\ =F\left(x_k\right)-\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+2A_k{t}_k\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)+\left(2{\sigma }^2+\frac{3M^2}{4}\right)t_k\mathrm{.}\end{array}$ (34)

where the first equality holds by the fact that $x_k$ is ${\mathcal{F}}_k$ -measurable, i.e. $\mathbb{E}\left[F\left(x_k\right)\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]=F\left(x_k\right)$ and $\mathbb{E}\left[{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]={\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2$ . The last inequality follows from $\mathbb{E}\left[{\Vert \nabla g\left(y_{k+1}\right)-{\mathcal{G}}_k\Vert }^2\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]\le A_k\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)+{\sigma }^2$ .

Upon subtracting $F^{\mathrm{<mo>\; *\; </mo>}}$ from both sides of (34), we have:

$\begin{array}{l}\mathbb{E}\left[F\left(x_{k+1}\right)-F^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right]\\ \le F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}-\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+2A_k{t}_k\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)+\left(2{\sigma }^2+\frac{3M^2}{4}\right)t_k\\ =\left(1+2A_k{t}_k\right)\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)-\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+\left(2{\sigma }^2+\frac{3M^2}{4}\right)t_k\mathrm{.}\end{array}$ (35)

Upon multiplying (35) by $t_{k+1}$ , we can obtain:

$\begin{array}{l}\mathbb{E}\left[t_{k+1}\left(F\left(x_{k+1}\right)-F^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; |\; </mo>}{\mathcal{F}}_k\right)\right]\\ \le \left(1+2A_k{t}_k\right)t_{k+1}\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)-\frac{t_k{t}_{k+1}}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+\left(2{\sigma }^2+\frac{3M^2}{4}\right)t_k{t}_{k+1}\\ \le \left(1+2A_k{t}_k\right)t_k\left(F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right)-\frac{t_k{t}_{k+1}}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2+\left(2{\sigma }^2+\frac{3M^2}{4}\right)t_k^2\mathrm{.}\end{array}$ (36)

where the last inequality follows from the non-increasing behaviour of the stepsize $t_k$ , i.e. $t_{k+1}<t_k$ .

Finally, let $Y_k=t_k\left(F\left(x_k\right)-F^{*}\right)$ , ${\gamma }_k=2A_k{t}_k$ , $X_k=\frac{t_k}{8}{\Vert G_{t_k}\left(y_{k+1}\right)\Vert }^2$ and $Z_k=\left(2{\sigma }^2+\frac{3M^2}{4}\right)t_k^2$ , then (36) becomes:

$\mathbb{E}\left[Y_{k+1}|{\mathcal{F}}_k\right]\le \left(1+{\gamma }_k\right)Y_k-t_{k+1}{X}_k+Z_k\mathrm{.}$

Recalling the stepsize conditions ${\displaystyle {\sum }_{k=1}^{\infty }}{t}_k^2<\infty$ and ${\displaystyle {\sum }_{k=1}^{\infty }}{A}_k{t}_k<\infty$ , we know that ${\displaystyle {\sum }_{k=1}^{\infty }}{Z}_k<\infty$ , ${\displaystyle {\sum }_{k=1}^{\infty }}{\gamma }_k<\infty$ . Thus, by Lemma 3.1, we have:

${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}{t}_{k+1}{X}_k<\infty \mathrm{<mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\left\{F\left(x_k\right)-F^{\mathrm{<mo>\; *\; </mo>}}\right\}\mathrm{<mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.}$

Finally, with the condition ${\displaystyle {\sum }_{k=1}^{\infty }}\frac{t_{k+1}}{{\displaystyle {\sum }_{s=1}^k}{t}_s}=\infty$ of Lemma 3.2, we have:

$\underset{1\le r\le k}{\min }{t}_r{\Vert G_{t_r}\left(y_{k+1}\right)\Vert }^2=o\left(\frac{1}{{\displaystyle {\sum }_{s=1}^k{t}_s}}\right)\mathrm{<mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.}$ (37)

This completes the proof.

Remark 3.1. (23) is a new variance assumption on the stochastic gradient, where ${\mathcal{G}}_k$ is weaker than the bounded variance assumption (i.e. $A_k=0$ in [33] ).

Remark 3.2. It is noting that we get the boundedness of the gradient mapping $G_{t_k}\left(y_{k+1}\right)$ due to the continuity of the prox-grad operator $T_{t_k}^{f\mathrm{,}{g}_{i_k}}\left(y_{k+1}\right)$ which is deduced by the convexity of f.

Corollary 3.1. Following the setting of Theorem 3.1 and choosing the stepsize $t_k=\frac{\beta }{1+\gamma \beta k^{\frac{1}{2}+\epsilon }}$ for any $\gamma \mathrm{,}\beta \ge 0$ where $\epsilon \in \left(\mathrm{0,}\frac{1}{2}\right)$ gives:

$\underset{1\le r\le k}{\min }{\Vert G_{t_r}\left(y_{k+1}\right)\Vert }^2=o\left(1\right)\mathrm{<mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.}$ (38)

Proof Stepsize satisfying $t_k=\frac{\beta }{1+\gamma \beta k^{\frac{1}{2}+\epsilon }}$ has been studied in [23] . It follows that:

$1+\gamma \beta k^{\frac{1}{2}+\epsilon }\le k^{\frac{1}{2}+\epsilon }+\gamma \beta k^{\frac{1}{2}+\epsilon }=\left(1+\gamma \beta \right)k^{\frac{1}{2}+\epsilon }\mathrm{,}$ (39)

which implies that $t_k\ge \frac{\beta }{\left(1+\gamma \beta \right)k^{\frac{1}{2}+\epsilon }}$ . Upon by the integral test inequality, we have:

$\begin{array}{c}{\displaystyle \underset{s=1}{\overset{k}{\sum }}}{t}_s\ge {\displaystyle \underset{s=1}{\overset{k}{\sum }}}\frac{\beta }{\left(1+\gamma \beta \right)s^{\frac{1}{2}+\epsilon }}\ge {\displaystyle {\int }_1^k}\frac{\beta }{\left(1+\gamma \beta \right)x^{\frac{1}{2}+\epsilon }}\text{d}x\\ =\frac{\beta \left(k^{\frac{1}{2}-\epsilon }-1\right)}{\left(1+\gamma \beta \right)\left(\frac{1}{2}-\epsilon \right)}\ge \frac{\beta k^{-\frac{1}{2}-\epsilon }\left(k-1\right)}{1+\gamma \beta },\end{array}$ (40)

where the last inequality follows from the concavity of $h\left(x\right)=x^{\frac{1}{2}-\epsilon }$ , so that:

$h\left(y\right)\le h\left(x\right)+h^{\prime }\left(x\right)\left(y-x\right)\mathrm{.}$

In other words, by taking $y=1$ and $x=k$ , we can get $k^{\frac{1}{2}-\epsilon }-1\ge \left(\frac{1}{2}-\epsilon \right)k^{-\frac{1}{2}-\epsilon }\left(k-1\right)$ .

Next, combining (39) and (40), we can obtain:

$\left({\displaystyle \underset{s=1}{\overset{k}{\sum }}}{t}_s\right)t_k\ge \frac{\beta k^{-\frac{1}{2}-\epsilon }\left(k-1\right)}{1+\gamma \beta }\frac{\beta }{\left(1+\gamma \beta \right)k^{\frac{1}{2}+\epsilon }}=\frac{{\beta }^2{k}^{-1-2\epsilon }\left(k-1\right)}{{\left(1+\gamma \beta \right)}^2}.$ (41)

Upon setting $G_r={\Vert G_{t_r}\left(y_{k+1}\right)\Vert }^2$ , and applying the inequality ${\min }_{1\le r\le k}{t}_r{G}_r\ge t_k{\min }_{1\le r\le k}{G}_r$ , we have:

$\left({\displaystyle \underset{s=1}{\overset{k}{\sum }}}{t}_s\right)\underset{1\le r\le k}{\min }{t}_r{G}_r\ge \left({\displaystyle \underset{s=1}{\overset{k}{\sum }}}{t}_s\right)t_k\underset{1\le r\le k}{\min }{G}_r\ge \frac{{\beta }^2{k}^{-1-2\epsilon }\left(k-1\right)}{{\left(1+\gamma \beta \right)}^2}\underset{1\le r\le k}{\min }{G}_r\ge 0.$ (42)

For the left hand side of (42), we apply Theorem 3.1 to get:

$\underset{k\to \infty }{\lim }\left({\displaystyle \underset{s=1}{\overset{k}{\sum }}}{t}_s\right)\underset{1\le r\le k}{\min }{t}_k{G}_r=\mathrm{0\; <mi>\; </mi>\; <mi>\; </mi>}a.s.$

The application of Squeeze theorem in conjunction with (42) gives:

$\underset{k\to \infty }{\lim }{k}^{-1-2\epsilon }\left(k-1\right)\underset{1\le r\le k}{\min }{G}_r=\mathrm{0\; <mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.}$

When $\epsilon \to 0$ , we have $\frac{k-1}{k^{1+2\epsilon }}\to 1$ , which implies that:

$\underset{k\to \infty }{\lim }\underset{1\le r\le k}{\min }{G}_r=\mathrm{0\; <mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.}$

Therefore, we finally obtain:

$\underset{1\le r\le k}{\min }{G}_r=\underset{1\le r\le k}{\min }{\Vert G_{t_r}\left(y_{k+1}\right)\Vert }^2=o\left(1\right)\mathrm{<mi>\; </mi>\; <mi>\; </mi>}a\mathrm{.}s\mathrm{.}$

This completes the proof.

Remark 3.3. Corollary 3.1 indicates that ${\min }_{1\le r\le k}{\Vert G_{t_r}\left(y_{k+1}\right)\Vert }^2$ is arbitrarily close to 0 with probability one.

4. Conclusion

This paper presents PSAG with unbiased gradient estimation and analyzes its almost sure convergence for solving composite optimization problems, wherein the objective function comprises a smooth component and a non-smooth component. By leveraging certain key assumptions, we have established the almost sure convergence of PSAG with unbiased gradient estimation. Furthermore, we have demonstrated that the minimum of the squared gradient mapping norm approaches zero arbitrarily closely with probability one.

Founding

This paper was supported by the Natural Science Foundation of China (Grant No. 11801455), the Sichuan Science and Technology Program (Grant No. 2023NSFSC1922), the Innovation Team Funds of China West Normal University (Grant No. KCXTD2023-3), and the Fundamental Research Funds of China West Normal University (Grant No. 23kc010).

Conflicts of Interest

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

References

[1]	Wright, S.J., Nowak, R.D. and Figueiredo, M.A.T. (2009) Sparse Reconstruction by Separable Approximation. IEEE Transactions on Signal Processing, 57, 2479-2493. https://doi.org/10.1109/TSP.2009.2016892
[2]	Bottou, L., Curtis, F.E. and Nocedal, J. (2018) Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60, 223-311. https://doi.org/10.1137/16M1080173
[3]	Mandic, D. and Chambers, J. (2001) Recurrent Neural Networks for Prediction: Learning Algorithms, Architectures and Stability. Wiley, New York. https://doi.org/10.1002/047084535X
[4]	Shalev-Shwartz, S. and Ben-David, S. (2014) Understanding Machine Learning: from Theory to Algorithms. Cambridge University Press, New York. https://doi.org/10.1017/CBO9781107298019
[5]	Sun, R.Y. (2020) Optimization for Deep Learning: An Overview. Journal of the Operations Research Society of China, 8, 249-294. https://doi.org/10.1007/s40305-020-00309-6
[6]	Robbins, H. and Monro, S. (1951) A Stochastic Approximation Method. Annals of Mathematical Statistics, 22, 400-407. https://doi.org/10.1214/aoms/1177729586
[7]	Beck, A. (2017) First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia. https://doi.org/10.1137/1.9781611974997
[8]	Nesterov, Y. (2013) Gradient Methods for Minimizing Composite Functions. Mathematical Programming, 140, 125-161. https://doi.org/10.1007/s10107-012-0629-5
[9]	Beck, A. and Teboulle, M. (2009) A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM Journal on Imaging Sciences, 2, 183-202. https://doi.org/10.1137/080716542
[10]	Vandenberghe, L. (2010) Fast Proximal Gradient Methods. http://faculty.bicmr.pku.edu.cn/~wenzw/courses/fgrad.pdf
[11]	Becker, S., Candès, E. and Grant, M. (2011) Templates for Convex Cone Problems with Applications to Sparse Signal Recovery. Mathematical Programming Computation, 3, 165-218. https://doi.org/10.1007/s12532-011-0029-5
[12]	Li, H. and Lin, Z.C. (2015) Accelerated Proximal Gradient Methods for Nonconvex Programming. The 28th International Conference on Neural Information Processing Systems, Montreal, 7-12 December 2015, 379-387.
[13]	Ghadimi, S., Lan, G. and Zhang, H. (2016) Mini-Batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization. Mathematical Programming, 155, 267-305. https://doi.org/10.1007/s10107-014-0846-1
[14]	Reddi, S.J., Sra, S., Póczos, B. and Smola, A.J. (2016) Proximal Stochastic Methods for Nonsmooth Nonconvex Finite-Sum Optimization. Advances in Neural Information Processing Systems, 29, 1145-1153.
[15]	Metel, M.R. and Takeda, A. (2019) Stochastic Proximal Methods for Non-Smooth Non-Covex Constrained Sparse Optimization. Journal of Machine Learning Research, 22, 1-36.
[16]	Kawashima, T. and Fujisawa, H. (2018) Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization. arXiv: 1805.07960.
[17]	Gorbunov, E., Hanzely, F. and Richtárik, P. (2020) A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent. arXiv: 1905.11261. https://arxiv.org/abs/1905.11261
[18]	Cevher, V. and Vũ, B.C. (2019) On the Linear Convergence of the Stochastic Gradient Method with Constant Step-Size. Optimization Letters, 13, 1177-1187. https://doi.org/10.1007/s11590-018-1331-1
[19]	Polyak, T.B. (1964) Some Methods of Speeding up the Convergence of Iteration Methods. USSR Computational Mathematics and Mathematical Physics, 4, 1-17. https://doi.org/10.1016/0041-5553(64)90137-5
[20]	Biscarat, C.J. (1994) Almost Sure Convergence of a Class of Stochastic Algorithms. Stochastic Processes and their Applications, 50, 83-99. https://doi.org/10.1016/0304-4149(94)90149-X
[21]	Sebbouh, O., Gower, M.R. and Defazio, A. (2021) Almost Sure Convergence Rates for Stochastic Gradient Descent and Stochastic Heavy Ball. Proceedings of Machine Learning Research, 134, 1-37.
[22]	Orabona, F. (2020) Almost Sure Convergence of SGD on Smooth Nonconvex Functions. http://parameterfree.com https://parameterfree.com/2020/10/05/almost-sure-convergence-of-sgd-on-smooth-non-convex-functions/
[23]	Liu, J. and Yuan, Y. (2022) On Almost Sure Convergence Rates of Stochastic Gradient Methods. arXiv: 2202.04295. https://arxiv.org/abs/2202.04295
[24]	Liang, Y.Q., Xu, D.P., Zhang, N.M. and Mandic, D.P. (2023) Almost Sure Convergence of Stochastic Composite Objective Mirror Descent for Non-Convex Non-Smooth Optimization. Optimization Letters. https://doi.org/10.1007/s11590-023-01972-3
[25]	Khaled, A. and Richtárik, P. (2020) Better Theory for SGD in the Nonconvex World. arXiv: 2002.03329.
[26]	Gower, R., Sebbouh, O. and Loizou, N. (2021) SGD for Structured Nonconvex Functions: Learning Rates, Mini-Batching and Interpolation. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Vol. 130, 13-15 April 2021, 1315-1323.
[27]	Mertikopoulos, P., Hallak, N., Kavis, A. and Cevher, V. (2020) On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems. Optimization and Control, 33, 1117-1128. https://arxiv.org/abs/2006.11144
[28]	Ward, R., Wu, X. and Bottou, L. (2020) AdaGrad Stepsizes: Sharp Convergence over Nonconvex Landscapes. Journal of Machine Learning Research, 21, 9047-9076.
[29]	Alacaoglu, A., Malitsky, Y. and Cevher, V. (2020) Convergence of Adaptive Algorithms for Weakly Convex Constrained Optimization. arXiv: 2006.06650.
[30]	Davis, D. and Drusvyatskiy, D. (2019) Stochastic Model-Based Minimization of Weakly Convex Functions. SIAM Journal on Optimization, 29, 207-239. https://doi.org/10.1137/18M1178244
[31]	Nesterov, Y. (2003) Introductory Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media, New York. https://doi.org/10.1007/978-1-4419-8853-9
[32]	Robbins, H. and Siegmund, D. (1971) A Convergence Theorem for Non-Negative Almost Supermartingales and Some Applications. In: Rustagi, J.S., Ed., Optimizing Methods in Statistics, Academic Press, Cambridge, 233-257. https://doi.org/10.1016/B978-0-12-604550-5.50015-8
[33]	Nesterov, Y. (2018) Smooth Convex Optimization. Lectures on Convex Optimization, 137, 59-137. https://doi.org/10.1007/978-3-319-91578-4_2