Article Contents
Article Contents

# Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization

• * Corresponding author: Xin-Wei Liu
• We study the problem of minimizing the sum of two functions. The first function is the average of a large number of nonconvex component functions and the second function is a convex (possibly nonsmooth) function that admits a simple proximal mapping. With a diagonal Barzilai-Borwein stepsize for updating the metric, we propose a variable metric proximal stochastic variance reduced gradient method in the mini-batch setting, named VM-SVRG. It is proved that VM-SVRG converges sublinearly to a stationary point in expectation. We further suggest a variant of VM-SVRG to achieve linear convergence rate in expectation for nonconvex problems satisfying the proximal Polyak-Łojasiewicz inequality. The complexity of VM-SVRG is lower than that of the proximal gradient method and proximal stochastic gradient method, and is the same as the proximal stochastic variance reduced gradient method. Numerical experiments are conducted on standard data sets. Comparisons with other advanced proximal stochastic gradient methods show the efficiency of the proposed method.

Mathematics Subject Classification: Primary: 90C06; Secondary: 90C30.

 Citation:

• Figure 1.  Comparison of VM-SVRG with different mini-batch sizes

Figure 2.  Comparison of VM-SVRG and other modern methods for solving LR problem

Figure 3.  Comparison of VM-SVRG with different mini-batch sizes

Figure 4.  Comparison of VM-SVRG and mS2GD for solving SVM problem

 Algorithm 2 PL-VM-SVRG($w^0,m,b,U_0$) Input: Number of inner iterations $m$, initial point $\tilde{w}_0=w^0 \in \mathbb{R}^d$, initial metric $U_0$, mini-batch size $b\in \{1,2,\ldots,n\}$; 1: for $s=0,1,\ldots,S-1$ do2:    $w^{s+1} =$ VM-SVRG($w^s,m,b,U_0$).3: end forOutput: $w^S$.

Table 1.  Comparison of the SFO and PO complexity.

 Complexity Prox-GD Prox-SGD Prox-SVRG VM-SVRG SFO $\mathcal{O}(n/\epsilon)$ $\mathcal{O}(1/\epsilon^2)$ $\mathcal{O}(n+(n^{2/3}/\epsilon))$ $\mathcal{O}(n+(n^{2/3}/\epsilon))$ PO $\mathcal{O}(1/\epsilon)$ $\mathcal{O}(1/\epsilon)$ $\mathcal{O}(1/\epsilon)$ $\mathcal{O}(1/\epsilon)$ SFO(PL) $\mathcal{O}(n\kappa\log(1/\epsilon))$ $\mathcal{O}(1/\epsilon^2)$ $\mathcal{O}((n+\kappa n^{2/3})\log(1/\epsilon))$ $\mathcal{O}((n+\kappa n^{2/3})\log(1/\epsilon))$ PO(PL) $\mathcal{O}(\kappa \log(1/\epsilon))$ $\mathcal{O}(1/\epsilon)$ $\mathcal{O}(\kappa \log(1/\epsilon))$ $\mathcal{O}(\kappa \log(1/\epsilon))$

Table 2.  The information of data sets

 Data sets $n$ $d$ ijcnn1 49, 990 22 rcv1 20, 242 47, 236 real-sim 72, 309 20, 958 covtype 581, 012 54

Table 3.  Best choices of parameters for the methods

 Data sets mS2GD$(m,\eta)$ mS2GD-BB mSARAH$(m,\eta)$ mSARAH-BB VM-SVRG ijcnn1 $(0.02n,\frac{4}{L})$ $0.04n$ $(0.05n,\frac{1.8}{L})$ $0.04n$ $0.04n$ rcv1 $(0.1n,\frac{4}{L})$ $0.11n$ $(0.1n,\frac{3.5}{L})$ $0.09n$ $0.25n$ real-sim $(0.12n,\frac{0.6}{L})$ $0.15n$ $(0.07n,\frac{2}{L})$ $0.06$ $0.11n$ covtype $(0.07n,\frac{21}{L})$ $0.03n$ $(0.07n,\frac{25}{L})$ $0.008n$ $0.01n$

Figures(4)

Tables(4)