A Variance Reducing Stochastic Proximal Method with Acceleration Techniques

ADProx-SAGA algorithm is introduced in Algorithm 1. It is easy to see that this algorithm maintains five sequences, $x^k,y^k,z_j^k,u^k$ , and $g_j^k$ , which are the iterations points. The initial point $x^0$ is chosen arbitrarily, $g_i^0$ is chosen as gradient/subgradient of $f_i(x)$ at $x^0$ , and the algorithm adds momentum factor ${\beta }_k,$ in addition to the parameter learning date $\gamma$ .

In the $k$ -th iteration, the loss function $f_i(x)$ is chosen randomly. The variable $y^k$ is updated in terms of Eq. ( 4 ), $u^k$ iterates over $y^k$ using Eq. ( 5 ). According to the definition of $z_j^k$ in Eq. ( 3 ) and the update of $x^{k+1}$ in Eq. ( 6 ), $z_j^k$ , $y^{k+1}$ , and $u^{k+1}$ can be treated as intermediate variables in the update from $x^k$ to $x^{k+1}$ . According to Eqs. ( 2 ) and ( 3 ), the main steps of Algorithm 1 can also be written as

$$y^{k+1}=x^k-\gamma (g_j^{k+1}-g_j^k+{\displaystyle \frac{1}{n}}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{g}_i^k),$$

where $g_j^{k+1}-g_j^k+\frac{1}{n}{\sum }_{i=1}^n{g}_i^k$ indicates the unbiased estimation of the gradient $g_j^k$ , which is similar to the gradient update formula in SAGA. The gradient table is designed to reduce the computational effort by $1/n$ compared to SVRG, and $g_j^{k+1}$ is the gradient mapping of $f_j(x)$ at $z_j^k+x^k-y^k$ .

In each iteration of our algorithm, unlike Prox-SAGA which contains only one proximal operator to handle the nonsmooth term $h(x)$ , we borrow the idea of the Douglas–Rachford splitting to use the proximal operator of $f_i(x)$ to calculate the gradient mapping, in addition to the proximal operator of $h(x)$ , enabling it to achieve two proximal calculations, and this design can achieve fast convergence when the loss function $f_i(x)$ is ill-conditioned.

In particular, our algorithm differs from Prox-SAGA in the definition of gradient. In Prox-SAGA, $g_j^{k+1}$ is the gradient of $f_i(x)$ at $x^k$ , while in our algorithm, $g_j^{k+1}$ is the subgradient of $x$ at the point ${prox}_{f_j}^{\gamma }(z_j^k+x^k-y^k)$ . We have learned that Point-SAGA achieves the effect of acceleration of SAGA by involving the “future” point $x^{k+1}$ . According to Eq. ( 5 ) and the definition of $g_j^{k+1}$ , ${prox}_{f_j}^{\gamma }(z_j^k+x^k-y^k)=y^{k+1}+x^k-y^k$ can be obtained. We can see that Algorithm 1 also involves “future” points and the two proximal operators are combined by using DR splitting. In addition, on top of combining DR splitting operators, we can achieve a faster convergence compared to Prox-SAGA and Point-SAGA by adding momentum terms to the iteration points.

We wish to speed up the proximal point gradient algorithm, so we apply Nesterov’s momentum at the iteration point $y^{k+1}$ . For the choice of value of ${\beta }_k$ , we set ${\beta }_k=\frac{k-2}{k+1}$ in Algorithm 1 according to the FISTA algorithm. However, FISTA algorithm is not guaranteed to be a descent algorithm, so it is necessary to verify the function value at the iteration point, and this step is essential in the later theoretical proofs.

In this paper, two cases (strongly convex and non-strongly convex) are considered for the properties of the objective function $f_i(x)$ , and different values of $\gamma$ are selected for these two cases. Parameters $L$ and $\mu$ are unknown for most problems, so ADProx-SAGA will works well in practical.

In this section, we show that ADProx-SAGA is actually a combination of Point-SAGA and DR splitting operators, and is a generalization of the Point-SAGA while establishing a connection to fast Douglas–Rachford splitting.