A Stochastic Variance-reduced Proximal Difference-of-convex Method for Nonconvex and Nonsmooth Optimization Problems

What the paper says

(Communicated by Jie Sun) Consider the nonconvex and nonsmooth optimization problem $\min\limits_{x\in \mathbb{R}^n }\ \psi(x)= \frac{1}{m} \sum \limits_{i=1}^m f_i(x)+r_1(x)-r_2(x),$ (1) where for each $ i \in \{1, 2, \ldots, m\} $, the function $f_i: \mathbb{R}^n \to (-\infty, \infty] $ is smooth. The functions $r_1: \mathbb{R}^n \to (-\infty, \infty] $ and $ r_2: \mathbb{R}^n \to (-\infty, \infty] $ are nonsmooth convex functions. In this paper, we propose a stochastic variance-reduced proximal difference-of-convex algorithm (SVRPDCA) for $(1)$, i.e. Algorithm 1 Stochastic Variance Reduced Proximal Difference-of-Convex Algorithm (SVRPDCA) Input: Let $S$ be an arbitrary positive integer, initial point $x_0\in \mathbb{R}^n$, set $q = b = [m^{\frac 1 2}]$, $N = Sq$, $\alpha=\frac{1}{2L}.$ for $k=1:N-1$ do S1 if $\mod(k,q)==0$, calculate the full gradient $v_k = \nabla f(x_k),$ S2 else S3 Randomly select a subset $\mathcal{M}_k\subseteq \{1,2,\ldots,n\}$ such that $|\mathcal{M}_k|=b$, and compute $v_{k}=\frac{1}{b} \sum_{i \in \mathcal{M}_{k}} \nabla f_{i}(x_{k})-\nabla f_{i}(x_{k-1})+v_{k-1},$ S4 end if S5 Compute $\xi_{k} \in \partial r_{2}(x_{k})$ and update $x_{k+1}$ by $x_{k+1}=\arg\min _{x \in \mathbb{R}^{n}}\left\langle x-x_{k}, v_{k}-\xi_{k}\right\rangle+r_{1}(x)+\frac{1}{2 \alpha}\|x-x_{k}\|^{2}.$ (2) end for Output: Return $x_{R}$, where $R$ is chosen uniformly at random from $\{1,\cdots, N-1\}$. We also establish that the proposed method attains an $\epsilon$-equilibrium point with a gradient complexity bounded by $O(\sqrt{m}\epsilon^{-2} + m)$ under conditions, where $m$ represents the number of data samples. Numerical experiments validate the efficiency and practical relevance of the proposed algorithm.