Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence

Difference of convex (DC) functions cover a broad family of non-convex and possibly non-smooth and non-differentiable functions, and have wide applications in machine learning and statistics. Although deterministic algorithms for DC functions have been extensively studied, stochastic optimization that is more suitable for learning with big data remains under-explored. In this paper, we propose new stochastic optimization algorithms and study their first-order convergence theories for solving a broad family of DC functions. We improve the existing algorithms and theories of stochastic optimization for DC functions from both practical and theoretical perspectives. On the practical side, our algorithm is more user-friendly without requiring a large mini-batch size and more efficient by saving unnecessary computations. On the theoretical side, our convergence analysis does not necessarily require the involved functions to be smooth with Lipschitz continuous gradient. Instead, the convergence rate of the proposed stochastic algorithm is automatically adaptive to the H\"{o}lder continuity of the gradient of one component function. Moreover, we extend the proposed stochastic algorithms for DC functions to solve problems with a general non-convex non-differentiable regularizer, which does not necessarily have a DC decomposition but enjoys an efficient proximal mapping. To the best of our knowledge, this is the first work that gives the first non-asymptotic convergence for solving non-convex optimization whose objective has a general non-convex non-differentiable regularizer.


Introduction
In this paper, we consider a family of non-convex non-smooth optimization problems that can be written in the following form: where g(·) and h(·) are real-valued lower-semicontinuous convex functions, r(·) is a proper lower-semicontinuous function. We include the component r in order to capture nondifferentiable functions that usually plays the role of regularization, e.g., the indicator function of a convex set X where r(x) = δ X (x) is zero if x ∈ X and infinity otherwise, and a non-differential regularizer such as the convex 1 norm x 1 or the non-convex 0 norm and p norm x p p with p ∈ (0, 1). We do not necessarily impose smoothness condition on g(x) or h(x) and the convexity condition on r(x).
A special class of the problem (1) is the one with r(x) being a convex function -also known as difference of convex (DC) functions. We would like to mention that even the family of DC functions is broader enough to cover many interesting non-convex problems that are well-studied, including an additive composition of a smooth non-convex function and a non-smooth convex function, weakly convex functions, etc. We postpone this discussion to Section 2 after we formally introduce the definitions of smooth functions and weakly convex functions.
In the literature, deterministic algorithms for DC problems have been studied extensively since its introduction by Pham Dinh Tao in 1985 and are continuously receiving attention from the community (Khamaru and Wainwright, 2018;Wen et al., 2018). Please refer to (Thi and Dinh, 2018) for a survey on this subject. Although stochastic optimization (SO) algorithms for the special cases of DC functions mentioned above (smooth non-convex functions, weakly convex functions) have been well studied recently (Davis and Grimmer, 2017;Davis and Drusvyatskiy, 2018b,a;Drusvyatskiy and Paquette, 2018;Chen et al., 2018b;Lan and Yang, 2018;Allen-Zhu, 2017;Chen and Yang, 2018;Allen-Zhu and Hazan, 2016;Reddi et al., 2016b,a;Zhang and He, 2018), a comprehensive study of SO algorithms with a broader applicability to the DC functions and the problem (1) with a non-smooth nonconvex regularizer r(x) still remain rare. The papers by Nitanda and Suzuki (2017) and Thi et al. (2017) are the most related works dedicated to the stochastic optimization of special DC functions. Thi et al. (2017) considered a special class of DC problem whose objective function consists of a large sum of nonconvex smooth functions and a regularization term that can be written as a DC function. They reformulated the problem into (1) such that h is a sum of n convex functions, and g is a quadratic function and r is the first component of the DC decomposition of the regularizer. Regarding algorithm and convergence, they proposed a stochastic variant of the classical DCA (Difference-of-Convex Algorithm) and established an asymptotic convergence result for finding a critical point. To our knowledge, the paper by Nitanda and Suzuki (2017) is the probably the first result that gives non-asymptotic convergence for finding an approximate critical point of a special class of DC problem, in which both g and h can be stochastic functions and r = 0. Their algorithm consists of multiple stages of solving a convex objective that is constructed by linearizing h(x) and adding a quadratic regularization. However, their algorithm and convergence theory have the following drawbacks. First, at each stage, they need to compute an unbiased stochastic gradient denoted by v(x) of ∇h(x) such that E[ v(x) − ∇h(x) 2 ] ≤ 2 , where is the accuracy level imposed on the returned solution in terms of the gradient's norm. In reality, one has to resort to mini-batching technique by using a large number of samples to ensure this condition, which is impractical and not user-friendly. An user has to worry about what is the size of the mini-batch in order to find a sufficiently accurate solution while keeping the computational costs minimal. Second, for each constructed convex subproblem, their theory requires running a stochastic algorithm that solves each subproblem to the accuracy level of , which could waste a lot of computations at earlier stages. Third, their convergence analysis requires that r(x) = 0 and g(x) is a smooth function with a Lipchitz continuous gradient.
Our Contributions -I. In Section 3, we propose new stochastic optimization algorithms and establish their convergence results for solving the DC class of the problem (1) that improves the algorithm and theory in Nitanda and Suzuki (2017) from several perspectives. It is our intension to address the aforementioned drawbacks of their algorithm and theory. In particular, (i) our algorithm only requires unbiased stochastic (sub)-gradients of g(x) and h(x) without a requirement on the small variance of the used stochastic (sub)-gradients; (ii) we do not need to solve each constructed subproblem to the accuracy level of . Instead, we allow the accuracy for solving each constructed subproblem to grow slowly without sacrificing the overall convergence rate; (iii) we improve the convergence theory significantly. First, our convergence analysis does not require g(x) to be smooth with a Lipchitz continuous gradient. Instead, we only require either g(x)+r(x) or h(x) to be differentiable with a Hölder continuous gradient, under the former condition h(x) can be a non-smooth non-differentiable function and under the later condition r(x) and g(x) can be non-smooth non-differentiable functions. Second, the convergence rate is automatically adaptive to the Hölder continuity of the involved function without requiring the knowledge of the Hölder continuity to run the algorithm. Third, when adaptive stochastic gradient method is employed to solve each subproblem, we establish an adaptive convergence similar to existing theory of AdaGrad for convex problems (Duchi et al., 2011;Chen et al., 2018a) and weakly convex problems (Chen et al., 2018b).
Our Contributions -II. Moreover, in Section 4 we extend our algorithm and theory to the more general class of non-convex non-smooth problem (1), in which r(x) is a general nonconvex non-differentiable regularizer that enjoys an efficient proximal mapping. Although such kind of non-smooth non-convex regularization has been considered in literature (Attouch et al., 2013;Bolte et al., 2014;Bot et al., 2016;Li and Lin, 2015;Yu et al., 2015;Yang, 2018;Liu et al., 2018;An and Nam, 2017;Zhong and Kwok, 2014), existing results are restricted to deterministic optimization and asymptotic or local convergence analysis. In addition, most of them consider a special case of our problem with g − h being a smooth non-convex function. To the best of our knowledge, this is the first work of stochastic optimization with a non-asymptotic first-order convergence result for tackling the non-convex objective (1) with a non-convex non-differentiable regularization and a smooth function g and a possibly non-smooth function h with a Hölder continuous gradient. Our algorithm and theory are based on using the Moreau envelope of r(x) that can be written as a DC function, which then reduces to the problem that is studied in Section 3. By using the algorithms and their convergence results established in Section 3 and carefully controlling the approximation parameter, we establish the first non-asymptotic convergence of stochastic optimization for solving the original non-convex problem with a non-convex non-differentiable regularizer. This non-asymptotic convergence result can be also easily extended to the deterministic optimization, which itself is novel and could be interesting to a broader community. A summary of our results is presented in Table 1.

Preliminaries
In this section, we present some preliminaries. Let · p denote the standard p-norm with p ≥ 0. For a non-convex function f (x) : R d → R, let∂f (x) denote the Fréchet subgradient and ∂f (x) denote the limiting subgradient, i.e., When f is convex, the Fréchet and the limiting subgradient reduce to the subgradient in the sense of convex analysis: For simplicity, we use · to denote the Euclidean norm (aka. 2-norm) of a vector. Let dist(S 1 , S 2 ) denote the distance between two sets.
A function f (x) is smooth with a L-Lipchitz continuous gradient if it is differentiable and the following inequality holds Next, let us characterize the critical points of the considered problem (1) that are standard in the literature (Hiriart-Urruty, 1985;Horst and Thoai, 1999;Thi and Dinh, 2018;An and Nam, 2017), and introduce the convergence measure for an iterative optimization algorithm. First, let us consider the DC problem: where g : R d → R ∪ {∞} is a proper lower semicontinuous convex function and h : R d → R is convex. Ifx is a local minimizer of f (x), then ∂h(x) ⊂ ∂g(x). Any pointx that satisfies the condition ∂h(x) ⊂ ∂g(x) is called a stationary point of (2) and any pointx such that ∂h(x) ∩ ∂g(x) = ∅ is called a critical point of (2). If h(x) is further differentiable, the stationary points and the critical points coincide. For an iterative optimization algorithm, it is hard to find an exactly critical point in a finite-number of iterations. Therefore, one is usually concerned with finding an -critical point x that satisfies Similarly, we can extend the above definitions of stationary and critical points to the general problem (1) with r(x) being a proper and lower semi-continuous (possibly non-convex) function (An and Nam, 2017). In particular,x is called a stationary point of the considered problem (1) if it satisfies ∂h(x) ⊂∂(g + r)(x), and any pointx such that ∂h(x) ∩∂(g + r)(x) = ∅ is called a critical point of (1). When g is differentiable,∂(g + r)(x) = ∇g(x) + ∂r(x) (Rockafellar and Wets, 1998)[Exercise 8.8], and when both g and r are convex and their domains cannot be separated∂(g + r)(x) = ∂g(x) + ∂r(x) (Rockafellar and Wets, 1998)[Corollary 10.9]. An -critical point of (1) is a point x that satisfies dist(∂h(x),∂(g + r)(x)) ≤ . It is notable that when g + r is non-differentiable, finding an -critical point could become a challenging task for an iterative algorithm even under the condition that r is a convex function. Let us consider the example of g = h = 0, r = |x|. As long as x = 0, we have dist(0, ∂|x|) = 1. To address this challenge when g + r is non-differentiable, we introduce the notion of nearly -critical points. In particular, a point x is called a nearly -critical point of the problem (1) if there existsx such that A similar notion of nearly critical points for non-smooth and non-convex optimization problems have been utilized in several recent works (Davis and Grimmer, 2017;Davis and Drusvyatskiy, 2018b,a;Chen et al., 2018b).
Examples and Applications of DC functions. Before ending this section, we present some examples of DC functions and their applications in machine learning and statistics. Example 1: Additive composition of a smooth loss function and a non-smooth convex regularizer. Let us consider where r(x) is a convex function and g(x) is an L-smooth function. For an L-smooth function, it is clear thatĝ(x) = g(x) + L 2 x 2 is a convex function. Therefore, the above objective function can be written asĝ(x) + r(x) − L 2 x 2 -a DC function. Example 2: Weakly convex functions. Weakly convex functions have been recently studied in numerous papers (Davis and Grimmer, 2017;Davis and Drusvyatskiy, 2018b,a;Chen et al., 2018b;Zhang and He, 2018). A function f (x) is called ρ-weakly convex if f (x)+ ρ 2 x 2 is a convex function. More generally, f (x) is called ρ-relative convex with respect to a strongly convex function ω(x) if f (x) + ρω(x) is convex (Zhang and He, 2018). It is obvious that a weakly convex function f (x) is a DC function. Examples of weakly convex functions can be found in deep neural networks with a smooth active function and a non-smooth loss function (Chen et al., 2018b), robust learning (Xu et al., 2018), robust phase retrieval (Davis and Drusvyatskiy, 2018a), etc.
Example 3: Non-Convex Sparsity-Promoting Regularizers. Many non-convex sparsitypromoting regularizers in statistics can be written as a DC function, including log-sum penalty (LSP) (Candès et al., 2008), minimax concave penalty (MCP) (Zhang, 2010a), smoothly clipped absolute deviation (SCAD) (Fan and Li, 2001), capped 1 penalty (Zhang, 2010b), transformed 1 norm Zhang and Xin (2014). For detailed DC composition of these regularizers, please refer to (Wen et al., 2018;Gong et al., 2013). It is notable that for LSP, MCP and SCAD, the second function in their DC decomposition can be a smooth function. In particular, if one consider regression or classification with LSP, MCP, SCAD or transformed 1 norm regularizer, the problem is a special case of (1) with r(x) being a convex function and h(x) being a smooth convex function. Here we give one example by considering learning with MCP as a regularization, where the problem is where (a i , b i ), i = 1, . . . , n denote a set of data points (feature vector and label pairs), (·, ·) is a convex loss function with respect to its first argument, θ > 0 is a constant and λ > 0 is a regularization parameter. We can write P (x) as a difference of two convex functions where h(x) is continuously differentiable with 1 θ -Lipchitz continuous gradient . Example 4: Least-squares Regression with 1−2 Regularization. Recently, a non-convex regularization in the form of λ( x 1 − x 2 ) was proposed for least-squares regression or compressive sensing (Yin et al., 2015), which is naturally a DC function.
Example 5: Positive-Unlabeled (PU) Learning. A standard learning task is to find a model denoted by x that minimizes the expected risk based on a convex surrogate loss , i.e., where z ∈ R m denotes the feature vector of a random data and y ∈ {1, −1} denotes its corresponding label. In practice one observes a finite set of i.i.d training data {z i , y i }, i = 1 . . . , n, which leads to the well-known empirical risk (ERM) minimization problem, i.e., min x∈R d 1 n n i=1 (x; z i , y i ). However, if only positive data {z i , +1, i = 1, . . . , n + }, are observed, ERM becomes problematic. A remedy to address this challenge is to use unlabeled data for computing an unbiased estimation of E z,y [ (x; z, y)]. In particular, the objective in the following problem is an unbiased risk (Kiryo et al., 2017): where {z u i , i = 1, . . . , n u } is a set of unlabeled data, and π p = Pr(y = 1) is the prior probability of the positive class. It is obvious that if (x; ·) is a convex loss function in terms of x, the above objective function is a DC function. In practice, an estimation of π p is used.

Examples of Non-Convex Non-Smooth
Regularizers. Finally, we present some examples of non-convex non-smooth regularizers r(x) that cannot be written as a DC function or whose DC composition is unknown. Thus, the algorithms and theories presented in Section 3 are not directly applicable, but the algorithms discussed in Section 4 are applicable when the proximal mapping of each component of r(x) is efficient to compute. Examples include 0 norm (i.e., the number of non-zero elements of a vector) and p norm regularization for p ∈ (0, 1) (i.e., d i=1 |x i | p ), whose proximal mapping can be efficiently computed (Attouch et al., 2013;Bolte et al., 2014). For another example, let us consider a penalization approach for tackling non-convex constraints. Consider a non-convex optimization problem with domain constraint x ∈ C, where C is a non-convex set. Directly handling a nonconvex constrained problem could be difficult. An alternative solution is to convert the domain constraint into a penalization λ 2 x − P C (x) 2 with λ > 0 in the objective, where P C (·) denotes the projection of a point to the set C. Note that when C is a non-convex set, r(x) = λ 2 x − P C (x) 2 is a non-convex non-smooth function in general, and its proximal mapping enjoys a closed-form solution (Li and Pong, 2016).
As a final remark, it is worth mentioning that even if r(x) can be written as a DC function such that the two components in its DC decomposition are both non-smooth nondifferntiable (e.g., 1−2 regularization, capped 1 norm d i=1 min(|x i |, θ)), the theory presented in Section 4 can be still useful to derive a non-asymptotic first-order convergence in terms of finding a close critical point, while the theory in Section 3 is not directly applicable.

New Stochastic Algorithms of DC functions
In this section, we present new stochastic algorithms for solving the problem (1) when r(x) is a convex function and their convergence results. We assume both g(x) and h(x) have a large number of components such that computing a stochastic gradient is much more efficient than computing a deterministic gradient. Without loss of generality, we assume , and consider the following problem: where g, h : R d → R d are real-valued lower-semicontinuous convex functions and r is a proper lower-semicontinuous convex function. It is notable that a special case of this problem is the finite-sum form: which will allows us to develop faster algorithms for smooth functions by using variance reduction techniques. Since we do not necessarily impose any smoothness assumption on g(x) and h(x), we will postpone the particular assumptions for these functions in the statements of later theorems. For all algorithms presented below, we assume that the proximal mapping of r(x) can be efficiently computed, i.e., the solution to the following problem can be easily computed for any η > 0: min x∈R d 1 2η x − y 2 + r(y).
A basic assumption that will be used in the analysis is the following.
Assumption 1 For a given initial solution x 1 ∈ dom(r), assume that there exists ∆ > 0 such that Algorithm 1 A Stagewise Stochastic DC Algorithm: SSDC-A 1: Initialize: x 1 ∈ dom(r) 2: for k = 1, . . . , K do 3: The basic idea of the proposed algorithm is similar to the stochastic algorithm proposed in (Nitanda and Suzuki, 2017). The algorithm consists of multiple stages of solving convex problems. At the k-th stage (k ≥ 1), given a point x k , a convex majorant function F γ where γ > 0 is a constant parameter. Then a stochastic algorithm is employed to optimize the convex majorant function. The key difference from the previous work lies at how to solve each convex majorant function. An important change introduced to our design is to make the proposed algorithms more efficient and more practical. Roughly speaking, we only require solving each function F γ x k (x) up to an accuracy level of c/k for some constant c > 0, i.e., finding a solution x k+1 such that In contrast, the algorithm and anlysis presented in (Nitanda and Suzuki, 2017) requires solving each convex problem up to an accuracy level of , which is the expected accuracy level on the final solution. This change not only makes our algorithms more efficient by saving a lot of unnecessary computations but also more practical without requiring to run the algorithm. We present a meta algorithm in Algorithm 1, in which A refers to an appropriate stochastic algorithm for solving each convex majorant function. The Step 4 means that A is employed for finding x k+1 such that (9) is satisfied (or a more fine-grained condition is satisfied for a particular algorithm as discussed later), where Θ k denotes the algorithm dependent parameters (e.g., the number of iterations). There are three issues that deserve further discussion in order to fully understand the proposed algorithm. First, how many outer iterations k is needed to ensure finding a (nearly) -stationary point of the original problem under the condition that (9) is satisfied for each problem. Second, how to ensure the condition (9) to be satisfied for a stochastic algorithm. Third, what is the overall complexity (iteration complexity or gradient complexity) taking into account the complexity of the stochastic algorithm A for solving each convex majorant function. Note that the last two issues are closely related to the particular algorithm employed. We emphasize that the last two issues are important not only in theory but also in practice. Related factors such as how to initialize the algorithm A, how to set the step size and how many iterations for each call of A suffice have dramatic effect on the practical performance. Next, we first present a general convergence analysis of Algorithm 1 under the condition that (9) is satisfied for solving each problem. Then, we present several representative stochastic algorithms for solving each convex majorant function and derive their overall iteration complexities.
Our convergence analysis also has its merits compared with the previous work (Nitanda and Suzuki, 2017). We will divide our convergence analysis into three parts. First, in subsection 3.1 we introduce a general convergence measure without requiring any smoothness assumptions of involved functions and conduct a convergence analysis of the proposed algorithm. Second, we analyze different stochastic algorithms and their convergence results in subsection 3.2, including an adaptive convergence result for using AdaGrad. Finally, we discuss the implications of these convergence results for solving the original problem in terms of finding a (nearly) -stationary point in subsection 3.3.

A General Convergence Result
For any γ > 0, define It is notable that P γ (z) is well defined since the above problem is strongly convex. The following proposition shows that when z = P γ (z), then z is a critical point of the original problem.
Since z = P γ (z), we have which implies that z is a critical point of the original minimization problem.
The above proposition implies that G γ (z) = γ P γ (z) − z can serve as a measure of convergence of an algorithm for solving the considered minimization problem. In subsection 3.3, we will discuss how the convergence in terms of γ P γ (z) − z implies that the standard convergence measure in terms of the (sub)gradient norm of the original problem. The following theorems are the main results of this subsection.
Theorem 1 Suppose Assumption 1 holds and there exists an stochastic algorithm A that when applied to F γ x k (x) can find a solution x k+1 satisfying (9), then with a total of K stages we have where τ ∈ {1, . . . , K} is uniformly sampled.
Remark: It is clear that when K → ∞, γ x τ − P γ (x τ ) → 0 in expectation, implying the convergence to a critical point. Note that the log(K) factor will lead to an iteration complexity of O(log(1/ )/ 4 ) for using stochastic (sub)gradient method. This seems to be slightly worse than that presented in (Nitanda and Suzuki, 2017) by a logarithmic factor. However, practically our algorithms can perform much better. This is because that if we simply run a stochastic algorithm A at each stage to find a solution x k+1 such that one can obtain a convergence upper bound of O(1/K) without a logarithmic factor. However, the stochastic algorithm A will need much more iterations at each stage, leading to a worse performance in practice.
A simple way to get rid of such a logarithmic factor without sacrificing the practical performance is by exploiting non-uniform sampling under a slightly stronger condition of the problem.
Theorem 2 Suppose there exists an stochastic algorithm A that when applied to F γ x k (x) can find a solution x k+1 satisfying (9), and there exists . . , K} is slightly stronger than Assumption 1. However, it can be easily satisfied if x k ∈ dom(r) resides in a bounded set (e.g., when r(x) is the indicator function of a bounded set), or if E[F (x k )] is non-increasing (e.g., when using variance-reduction methods for the case that g(x) is smooth). Proof [of Theorem 2] The proof of Theorem 1 can be obtained by a slight change of the following proof. Define the following notations.
By the assumption of (9), we have Rearranging the terms, we have where the last inequality follows the convexity of h(·). Multiplying both sides by w k = k α and taking summation over k = 1, . . . , K, we have The second term in the R.H.S of the above inequality can be easily bounded using simple calculus. For the first term, we use similar analysis as that in the proof of Theorem 1 in (Chen et al., 2018b): where we use w 0 = 0. Taking expectation on both sides, we have which can complete the proof by multiplying both sides by 2γ. The result in Theorem 1 for the uniform sampling can be easily derived from the equality (23) by using the fact K k=1 1/k ≤ (1 + log K).

Convergence Results of Different Stochastic Algorithms
In this section, we will present the convergence results of Algorithm 1 for employing different stochastic algorithms for minimizing F k (x) at each stage. In particular, we consider three representative algorithms, namely stochastic proximal subgradient (SPG) method (Duchi et al., 2010;Zhao and Zhang, 2015), adaptive stochastic gradient (AdaGrad) method (Duchi et al., 2011;Chen et al., 2018a), and proximal stochastic gradient method with variance reduction (SVRG) (Xiao and Zhang, 2014). SPG is a simple stochastic method, AdaGrad allows us to derive adaptive convergence to the history of learning, and SVRG allows us to leverage the finite-sum structure and the smoothness of the problem to improve the convergence rate.
Compute stochastic subgradients ∂g(x t ; ξ t ) and ∂h(x 1 ; ς t ) 4: Option 1: Option 2: Stochastic Proximal Subgradient Method. We make the additional assumptions about the problem for developing SPG.
Assumption 2 Assume one of the following conditions hold: , and either r = δ X (x) for a closed convex set X or ∂r(x) ≤ G for x ∈ dom(r).
Remark: The first assumption is typically used in the analysis of stochastic gradient method when the involved function is smooth (Zhao and Zhang, 2015), and the second assumption is typically used when the involved function is non-smooth (Duchi et al., 2010). Note that the condition ∂r(x) (x − y) ≥ 0, ∀x, y ∈ dom(r) is to capture the indicator function of a convex set. When r(x) is the indicator function of a convex set X , we have dom(r) = X and ∂r(x) corresponds to the normal cone of X , implying ∂r( We present the SPG algorithm in Algorithm 2 with two options to handle smooth and non-smooth g separately. The constraint x−x 1 ≤ 3G/γ at Step 5 is added to accommodate the proximal mapping of r(x) when g(x) is non-smooth. When using the subgradient of r(x) instead of the proximal mapping of r(x) in the update or r(x) is the indicator function of a bounded convex set, the constraint x − x 1 ≤ 3G/γ can be removed.
Proposition 2 Suppose Assumption 2(i) hold, then by setting η t = 3/(γ(t+1)) and γ ≥ 3L, Algorithm 2 with Option 1 guarantees that Suppose Assumption 2(ii) hold, then by setting η t = 4/(γt), Algorithm 2 with Option 2 guarantees that , We present a proof the above Proposition in the Appendix, which mostly follows existing analysis of SPG or related algorithms. By applying the above results (e.g., the second result in Proposition 2) to the k-th stage, we have where T k denotes the number of iterations used by SPG for the k-th stage. One might directly use the above result to argue that the condition (9) holds by assuming that x k −z k is bounded, which is true in the non-smooth case due to the domain constraint x ∈ Ω in the update. In the smooth case, the upper bound is not directly available for setting T k such that the condition (9) holds. Fortunately, when we apply the above result in the convergence analysis of Algorithm 1, we can utilize the strong convexity of F k to cancel the ) by setting T k to be larger than a constant. Let us summarize the convergence of Algorithm 1 when using SPG to solve each subproblem.
Theorem 3 Suppose Assumption 2 (i) holds and Algorithm 2 is employed for solving F k with parameters given in Proposition 2 and with γ ≥ 3L and T k = 3Lk/γ + 3, and there exists . . , K}, then with a total of K stages Algorithm 1 guarantees Similarly, Suppose Assumption 2 (ii) holds and Algorithm 2 is employed for solving F k with parameters given in Proposition 2 and with T k = k/γ + 1, and there exists ∆ > 0 such that . . , K}, then with a total of K stages Algorithm 1 guarantees where τ ∈ {1, . . . , K} is sampled according to probabilities p(τ = k) = k α K k=1 k α with α ≥ 1. Remark: Let us consider the iteration complexity of using SPG for finding a solution that satisfies E G γ (x τ ) 2 ≤ 2 . In both cases, we need a total number of stages K = O(γ/ 2 ) and total iteration complexity K k=1 T k = K k=1 O(k/γ + 1) = O(γ/ 4 ). One can also derive similar results for using the uniform sampling under Assumption 1, which are worse by a logarithmic factor.
Update g 1:t = [g 1:t−1 , g t ], s t,i = g 1:t,i 2 5: AdaGrad. AdaGrad (Duchi et al., 2011) is an important algorithm in the literature of stochastic optimization, which uses adaptive step size for each coordinate. It has potential benefit of speeding up the convergence when the cumulative growth of stochastic gradient is slow. Next, we show that AdaGrad can be leveraged to solve each convex majorant function and yield adaptive convergence for the original problem. Similar to previous analysis of AdaGrad (Duchi et al., 2011;Chen et al., 2018a), we make the following assumption.
The convergence analysis of using AdaGrad is build on the following proposition about the convergence AdaGrad for minimizing F γ x , which is attributed to Chen et al. (2018a).
Proposition 3 Let H 0 = 2GI with 2G ≥ max t g t ∞ , and iteration number T be the smallest integer satisfying T ≥ M max{a(2G + max i g 1:T,i ), d i=1 g 1:T,i /a, G r x 1 − x T +1 /η} for any a > 0. Algorithm 3 returns an averaged solution x T such that where x * = arg min x F γ x 1 (x), g 1:t = (g 1 , . . . , g t ) and g 1:t,i denotes the i-th row of g 1:t .
The convergence result of Algorithm 1 by using AdaGrad to solve each problem is described by following theorem.

Theorem 4 Suppose Assumption 3 hold and Algorithm 3 is employed for solving
. . , K}, then with a total of K stages Algorithm 1 guarantees where g k 1:t,i denotes the cumulative stochastic gradient of the i-th coordinate at the k-th stage, and τ ∈ {1, . . . , K} is sampled according to probabilities p(τ = k) = k α K k=1 k α with α ≥ 1.
Algorithm 4 SVRG(F γ x 1 , x 1 , T , S) 1: Input: x 1 ∈ dom(r), the number of inner initial iterations T 1 , and the number of outer loops S.

5:
for t = 1, 2, . . . , T do 6: Remark: It is obvious that the total number of iterations K k=1 T k is adaptive to the data. Next, let us present more discussion on the iteration complexity.
, therefore T k in the order of O(k) will satisfy the condition in Theorem 4. Thus in the worst case, the iteration complexity for finding We can show the potential advantage of adaptiveness similar to that in (Chen et al., 2018b). In particular, let us consider r = δ X and thus G r = 0 in the above result. When the cumulative growth of stochastic gradient is slow, e.g., assuming g k 1:T k ,i ≤ O(T k β ) with β < 1/2. Then T k = O(k 1/(2(1−β)) ) will work, and then the total number of iterations , which is better than O(1/ 4 ). SVRG. Next, we present SVRG for solving each subproblem when it has a finite-sum form and g is a smooth function. In particular, we consider the following problem: and make the following assumption.
It is notable that the smoothness of h is not necessary for developing the SVRG algorithm since at each stage we linearize h(x). Each subproblem is of the following form: We use the proximal SVRG proposed in (Xiao and Zhang, 2014) to solve the above problem, which is presented in Algorithm 4. Its convergence result for solving F γ x 1 is given below.
Proposition 4 By setting η < 1/(4L) and T is large enough such that ρ = In particular, if we set Remark: The gradient complexity of SVRG is (n + T )S, where n = n 1 + n 2 .
Theorem 5 Suppose Assumption 1 and Assumption 4 hold, and Algorithm 4 is employed for solving F k with η k = 0.05/L, T k ≥ max(2, 200L/γ), S k = log 2 (k) , then with a total of K stages Algorithm 1 guarantees , the total number of stages K = O(γ/ 2 ) and the total gradient complexity is O((nγ + L)/ 2 ).

Convergence results for finding a (nearly) -critical point
In this subsection, we will discuss the convergence results of the proposed algorithms for finding a nearly -critical point. The key is to connect the convergence in terms of G γ (x) to the convergence in terms of (sub)gradient. To this end, we present the following result.
Proposition 5 If g(x) + r(x) is differentiable and has L g+r -Hölder continuous gradient, we have If h(x) is differentiable and has L h -Hölder continuous gradient, we have Proof From the proof of Proposition 1, we have When g(x) + r(x) is differentiable and has L-Hölder continuous gradient, there exists v ∈ ∂h(x) such that Similarly, we can prove the case when h is differentiable and had Hölder continuous gradient.
Next, we present a general result that can be used to derive the convergence rate for the proposed algorithms.
Theorem 6 Assume Algorithm 1 returns a solution x τ such that under appropriate conditions. Then if g(x) + r(x) is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], we have If h(x) is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], we have where z τ = P γ (x τ ).
Remark: In the above results, the value of γ is set to be a constant. We can see that the convergence of SPG and AdaGrad can be automatically adaptive to the Hölder continuous of the involved functions without requiring the value of L and ν for running the algorithm. Both algorithms have an iteration complexity (in the worst-case) of O(1/ 4/ν ) for finding a (nearly) -critical point. When the problem has a finite-sum structure (13) and g(x) is smooth, SVRG has a gradient complexity of O(n/ 2/ν ) for finding a (nearly) -critical point.

Improved Convergence results when ν is known
In this subsection, we present some improved convergence results when ν is known. The key idea is by using an increasing sequence of regularization parameters γ that depend on ν.
Lemma 1 Suppose Assumption 2 (i) holds and Algorithm 2 is employed for solving F k with parameters given in Proposition 2 and with γ k = 3Lk 1−ν 1+ν and T k = 3Lk/γ k + 3, and there exists . . , K}, then with a total of K stages Algorithm 1 guarantees where τ ∈ {1, . . . , K} is sampled according to probabilities p(τ = k) = k α K k=1 k α with α ≥ 1. Similarly, Suppose Assumption 2 (ii) holds and Algorithm 2 is employed for solving F k with parameters given in Proposition 2 and with γ k = ck 1−ν 1+ν and T k = k/γ k + 1, and there exists . . , K}, then with a total of K stages Algorithm 1 guarantees Corollary 7 Suppose the same conditions as in Lemma 1 hold. If g(x) + r(x) is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], by setting

and the total iteration complexity is
is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], by setting Remark: The iteration complexity O(1/ 1+3ν ν ) in the above Corollary is an improved one compared with O(1/ 4/ν ) derived from Theorem 6 for SPG. Proof By the analysis of Proposition 5, if g(x) + r(x) is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], we have where we use the concavity of x s for s < 1 and x ≥ 0. By setting K = O(1/ 1+ν ν ) and γ K = O(K 1−ν 1+ν ), and using the results in Lemma 1, we have Similarly, if h(x) is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], by the analysis of Proposition 5 we have We can finish the proof using similar analysis.
Next, we develop the results for AdaGrad by using the following lemma.

Lemma 2 Suppose Assumption 3 hold and Algorithm 3 is employed for solving
T k +1 /η k } and M k η k ≥ 4/(aγ k ) with c and a being constants, and there exists ∆ > 0 such that E[F (x k ) − min x F (x)] ≤ ∆ for all k ∈ {1, . . . , K}, then with a total of K stages Algorithm 1 guarantees where g k 1:t,i denotes the cumulative stochastic gradient of the i-th coordinate at the k-th stage, and τ ∈ {1, . . . , K} is sampled according to probabilities p(τ = k) = k α K k=1 k α with α ≥ 1.
Corollary 8 Suppose the same conditions as in Lemma 2 hold. If g(x) + r(x) is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], by setting

and the total iteration complexity is
is differentiable and has L-Hölder continuous gradient with ν ∈ (0, 1], by setting Remark: The worst-case iteration complexity can be derived as following. According to the setting Nevertheless, the convergence of SSDC-AdaGrad is adaptive to the data. Lemma 3 Suppose Assumption 1 and Assumption 4 hold, and Algorithm 4 is employed for solving F k with γ k = ck 1−ν 1+ν with a constant c > 0, η k = 0.05/L, T k ≥ max(2, 200L/γ k ), S k = log 2 (k) , then with a total of K stages Algorithm 1 guarantees where τ ∈ {1, . . . , K} is sampled according to probabilities p(τ = k) = k α K k=1 k α with α ≥ 1.
The proofs of Corollary 8 and 9 are similar to that of Corollary 7 and hence are omitted. The proofs of Lemma 2 and Lemma 3 are presented in the Appendix.

Tackling Non-Smooth Non-Convex Regularization
In this section, we consider the more general class of problems where r(x) is non-smooth and non-convex that is not necessarily a DC function (e.g., 0 norm). Even if r(x) is a DC function such that both components in its DC decomposition r(x) = r 1 (x) − r 2 (x) are non-differentiable functions without Hölder continuous gradients (e.g., 1−2 regularization, capped 1 norm), the theories presented in this section are useful to derive non-asymptotic convergence results in terms of finding an -critical point. Please note that in this case the results presented in section 3.3 are not applicable. In particular, we consider the following class of problems: where g(x) and h(x) are real-valued lower-semicontinuous convex functions, g has a Lipchitz continuous gradient, and r(x) is a proper non-smooth and non-convex lower-semicontinuous function. Both g and h can be stochastic functions as in (6). We assume r(x) is simple such that its proximal mapping exisits and can be efficiently computed, i.e., prox µr (x) = arg min y∈R d 1 2µ y − x 2 + r(y).
The problem is challenging due to the presence of non-smooth non-convex functions r. To tackle this function, we introduce the Moreau envelope of r: where µ > 0. A nice property of the Moreau envelope function is that it can be written as a DC function: where R µ (x) is a convex function because it is the max of convex functions of x. We also have several nice properties about the Moreau envelope function that will be useful for our analysis.
The proof of the first fact can be found in (Liu et al., 2018)[Eqn. 7], and the second fact follows (Rockafellar, 1970)[Theorem 10.1]. Given the Moreau envelope of r, the key idea is to solve the following DC problem: By carefully controlling the value of µ and combining the results presented in previous section, we are able to derive non-asymptotic convergence results for the original problem. It is worth mentioning that using the Moreau envelope of r and its DC decomposition for handling non-smooth non-convex function is first proposed in (Liu et al., 2018). However, their algorithms are deterministic and convergence results are only asymptotic. To formally state our non-asymptototic convergence results, we make the following assumptions.
Assumption 5 Assume one of the following conditions holds: (i) r is Lipchitz continuous.
(ii) r is lower bounded and finite-valued over R d .
(ii) f (x) + r µ (x) is level bounded for a small µ < 1, and r is finite-valued on a compact set, and lower bounded over R d .

Remark:
The above assumptions on r capture many interesting non-convex non-smooth regularizers. For example, 1−2 regularization and capped 1 norm satisfy Assumption 5 (i). The 0 norm satisfies Assumption 5 (ii). A coersive function r usually satisfies Assumption 5 (iii), e.g., p norm r(x) = d i=1 |x| p for p ∈ (0, 1). When employing the presented algorithms in last section to solve the problem (17), we let r = 1 2µ x 2 , g = g and h =ĥ. It is also notable that the new component R µ (x) in h is deterministic, whose subgradient can be computed according to Lemma 4. Thus the condition in Assumption 2 (i) is sufficient for running SPG (option 1), and the condition in Assumption 4 is sufficient for running SVRG.

Basic Results with constant γ
In this subsection, we present the basic results by using a constant regularization parameter γ. In next subsection, we present improved complexities by using an increasing sequence of regularization parameters. It will exhibit how an increasing sequence of γ reduces the complexities.
We first present the results under the smoothness condition h, i.e., the following condition hold.
Assumption 6 Assume h is L-smooth.
Theorem 10 Regarding the problem (14), we have the following results: a. If Assumption 6, Assumption 5 (i) and Assumption 2 (i) hold, then we can use Algorithm 1 with a constant γ and with Algorithm 2 (option 1) to solve (17) with µ = , which returns a solution x τ after K = O(1/ 4 ) stages satisfying where w τ = prox µr (x τ ).
c. If g and h have a finite-sum form, Assumption 6 and Assumption 4 hold, then we can use Algorithm 1 with a constant γ and with Algorithm 4 to solve (17). We can set µ = if Assumption 5 (i) holds or µ = 2 if Assumption 5 (ii) or (iii) holds. The algorithm will return a solution x τ after K = O(1/ 4 ) (corresponding to Assumption 5 (i)) or K = O(1/ 6 ) (corresponding to Assumption 5 (ii) or (iii)) stages satisfying where w τ = prox µr (x τ ).

Remark:
The above result establishes that w τ is an -critical point. Under Assumption 5 (i), the iteration complexity of using SPG is O(1/ 8 ) and the gradient complexity of using SVRG is O(n/ 4 ); and under Assumption 5 (ii), the iteration complexity of using SPG is O(1/ 12 ) and the gradient complexity of using SVRG is O(n/ 6 ). Under Assumption 5 (iii), the only provable interesting result is by using SVRG, which gives a gradient complexity of O(n/ 6 ). Proof In the following proof,∂r(x) means there exists v ∈∂r(x). By applying the stochastic algorithms for DC functions in last section, at each stage the following problem is solved approximately Then we have for any τ ∈ {1, . . . , K}. Denote by w τ = prox µr (x τ ). It is notable that 1 µ x τ − prox µr (x τ ) ∈ ∂r(w τ ). Then we have ∇ĝ(x τ ) − ∇h(x τ ) − 1 µ prox µr (x τ ) = ∇g(x τ ) − ∇h(x τ ) +∂r(w τ ) and which implies that where uses the facts that g and h are smooth. Next, we need to show that E[ x τ − w τ ] is small. The argument will be different for part (a), part (b) and part (c). For part (a), using where the second inequality with an appropriate G > 0 follows the Lipchitz continuity of r. Then By setting µ = and K = O(1/ 4 ) and τ randomly sampled, we have E[ x τ − z τ ] ≤ 2 and hence For part (b), using we have where M > 0 exists due to Assumption 5(ii). Then By setting µ = 2 and K = O(1/ 6 ) and τ randomly sampled, we have E[ x τ − z τ ] ≤ 3 and hence For part (c) under Assumption (5) (iii), we take expectation over the above inequality giving Since using the SVRG, we can show E[f (x τ ) + r µ (x τ )] is bounded above, i.e., x τ is in a bounded set (in expectation), which together with the assumption r is lower bounded implies that there exists a constant M > 0 such that E[r(x τ ) − min x∈R d r(x)] ≤ M for τ = 1, . . . , K. Then By setting µ = 2 and K = O(1/ 6 ) and τ randomly sampled, we have E x τ − z τ ≤ 3 and hence For part (c) under Assumption (5) (i) and Assumption (5) (ii), we can use similar analysis as for part (a) and (b).
Next, we extend the results to the case that h has a Hölder continuous gradient, i.e, the following conditions hold.
Proof In the following proof,∂r(x) means there exists v ∈∂r(x). By applying the stochastic algorithms for DC functions in last section, at each stage the following problem is solved approximately Then we have which implies that where uses the facts that g is L-smooth and h has L-Hölder-continuous gradient with parameter ν ∈ (0, 1]. Next, we need to show that E[ x τ − w τ ] is small. The argument will be different for part (a), part (b) and part (c). For part (a), using where the second inequality with an appropriate G > 0 follows the Lipchitz continuity of r. Then By setting µ = and K = O(1/ 2(1+ν) ) and τ randomly sampled, we have E[ x τ − z τ ] ≤ 1+ν and hence For part (b), using we have where M > 0 exists due to Assumption 5(ii). Then By setting µ = 2 and K = O(1/ 2(2+ν) ) and τ randomly sampled, we have For part (c) under Assumption 5 (iii), we take expectation over the above inequality giving Since using the SVRG, we can show E[f (x τ ) + r µ (x τ )] is bounded above, i.e., x τ is in a bounded set (in expectation), which together with the assumption r is lower bounded implies that there exists a constant M > 0 such that E[r(x τ ) − min x∈R d r(x)] ≤ M for τ = 1, . . . , K. Then By setting µ = 2 and K = O(1/ 2(2+ν) ) and τ randomly sampled, we have E x τ −z τ ≤ 2+ν and hence For part (c) under Assumption (5) (i) and Assumption (5) (ii), we can use similar analysis as for part (a) and (b).

Improved Complexities with Increasing γ
In this subsection, we present improved complexities by simply changing the value of γ across stages. The key idea is to use an increasing sequence of γ across stages. In particular, at the k-stage, we use γ k = O(k β ) with 0 < β < 1. Let us abuse the notations F, F k defined by wherer(x) = 1 2µ x 2 . Similar to Lemma 1, we have the following result for the convergence of x τ − z τ when SPG (option 1) is employed at each stage.
Theorem 12 (Improved Complexities of SSDC-SPG) Regarding the problem (14), we have the following results: a. If Assumption 6, Assumption 5 (i) and Assumption 2 (i) hold, then we can use Algorithm 1 with Algorithm 2 (option 1) to solve (17) with µ = , γ k = 3Lk 1/3 and T k = 3Lk/γ k + 3, which returns a solution x τ after K = O(1/ 3 ) stages satisfying where w τ = prox µr (x τ ). The total iteration complexity is b. If Assumption 6, Assumption 5 (ii) and Assumption 2 (i) hold, then we can use Algorithm 1 with Algorithm 2 (option 1) to solve (17) with µ = 2 , γ k = 3Lk 1/2 and T k = 3Lk/γ k + 3, which returns a solution x τ after where w τ = prox µr (x τ ). The total iteration complexity is Remark: We note that after the first version of this paper was posted online, Metel and Takeda (2019) also considered a special setting of our problem (14) where g is a smooth and non-convex, h = 0, r is non-smooth non-convex and Lipchitz continuous, which is covered in part (a) of the above theorem by noting that a smooth function g can be written as a DC decomposition of two smooth convex functions. In terms of iteration complexity, they obtained the same complexity of O(1/ 5 ) but with a large mini-batch size equal to O(1/ ). When using a mini-batch size of 1, their algorithm has a worse complexity of O(1/ 6 ). In contrast, our algorithm does not need a large mini-batch size. In addition, the step size in their algorithm is also small in the order of O( 2 ) or ( 3 ) for finding an -critical point, while the step size in our algorithm is decreasing in a stagewise manner. Proof This proof is similar to the proof of Theorem 10. Following the analysis of Theorem 10 we know for any τ ∈ {1, . . . , K}, For part (a), by the setting of γ τ = 3Lτ 1/3 , we know γ τ ≤ 3LK 1/3 so that By using where the second inequality with an appropriate G > 0 follows the Lipchitz continuity of r. Then By setting µ = and K = O(1/ 3 ) and τ randomly sampled, we have E[ x τ − z τ ] ≤ 2 by Lemma 5 with β = 1/3 and hence For part (b), by the setting of γ τ = 3Lτ 1/2 , we know γ τ ≤ 3LK 1/2 so that By using we have where M > 0 exists due to Assumption 5(ii). Then By setting µ = 2 and K = O(1/ 4 ) and τ randomly sampled, we have E[ x τ − z τ ] ≤ 3 by Lemma 5 with β = 1/2 and hence We can also solve the subproblem by using SVRG (Algorithm 4) when g and h are of finite-sum form. Similar to Lemma 3, we have the following result for the convergence of x τ − z τ .
Remark: Metel and Takeda (2019) also considered a special setting of our problem (14) where g is a finite-sum smooth and non-convex function, h = 0, r is non-smooth non-convex and Lipchitz continuous, which is covered in part (a) of the above theorem. In terms of iteration complexity, they obtained a gradient complexity of O(n 2/3 / 3 ) but with a large mini-batch size equal to n 2/3 . Their gradient complexity is better than the result of part (a) in the above theorem. However, their algorithm needs to use a large mini-batch size and a small step size. In contrast, our algorithm does not need a large mini-batch size, and the step size in SVRG is a constant. In addition, we also emphasize that our algorithm SSDC is a general framework, which allows one to employ any suitable stochastic algorithms for smooth and strongly convex functions. It therefore gives us much more flexibility in practice. However, it is an interesting question whether one can obtain a better dependence on n in our framework.
Proof Similar to the proof of Theorem 12, we know for any τ ∈ {1, . . . , K}, For part (a), using where the second inequality with an appropriate G > 0 follows the Lipchitz continuity of r.
Then by the setting of γ K = 3LK 1/3 , By setting µ = and K = O(1/ 3 ) and τ randomly sampled, we have E[ x τ − z τ ] ≤ 2 by Lemma 6 with β = 1/3 and hence For part (b), if Assumption 5(ii) holds, then using we have If Assumption 5(iii) holds, we take expectation over the above inequality giving Since using the SVRG, we can show E[f (x τ ) + r µ (x τ )] is bounded above, i.e., x τ is in a bounded set (in expectation), which together with the assumption r is lower bounded implies that there exists a constant M > 0 such that E[r(x τ ) − min x∈R d r(x)] ≤ M for τ = 1, . . . , K. For both cases, by the setting of γ K = 3LK 1/2 we have By setting µ = 2 and K = O(1/ 4 ) and τ randomly sampled, we have E x τ − z τ ≤ 3 by Lemma 6 and hence Next, we present the results under the Hölder continuous gradient condition of h. These results are simple extension of that in Theorems 12, and Theorem 13.
d. If g and h have a finite-sum form, Assumption 7, Assumption 4 and Assumption 5 (ii) or (iii) hold, then we can use Algorithm 1 with Algorithm 4 to solve (17). We can set µ = 2 , γ k = ck 1/2 , T k ≥ max(2, 200L/γ k ), S k = log 2 (k) . The algorithm will return a solution x τ after where w τ = prox µr (x τ ). The total gradient complexity for such convergence guarantee ).
Proof This proof is similar to the proof of Theorem 11 and Theorems 12 and 13. Following the analysis of Theorem 11 we know for any τ ∈ {1, . . . , K}, For part (a), by the setting of γ τ = 3Lτ 1/3 , we know γ τ ≤ 3LK 1/3 so that By using where the second inequality with an appropriate G > 0 follows the Lipchitz continuity of r. Then By setting µ = and K = O(1/

Improved Complexities when ν of h is known
Similar to the case when r is convex, we can also improve the complexity for solving problems with non-smooth non-convex r and h with a Hölder continuous gradient under the condition that ν is known.

Remark:
The above results can be easily proved as Theorem 14.
Deterministic Methods for (14) with a Non-smooth Non-convex Regularizer.
Finally, we note that for the problem (14) with a non-smooth non-convex regularizer, a non-asymptotic convergence result for a deterministic optimization method is novel and interesting of its own. In particular, SVRG can be replaced by deterministic gradient based methods (e.g., accelerated gradient methods (Nesterov, 1983;Beck and Teboulle, 2009;Nesterov, 2013)) to enjoy a similar non-asymptotic convergence in terms of . From this perspective, we can also generalize the results to the case when both g and h have Hölder continuous gradients by using a universal gradient method (Nesterov, 2015) that can adapts to the actual level of smoothness of the objective function for solving each subproblem.

Numerical Experiments
In this section, we perform some experiments for solving different tasks to demonstrate effectiveness of proposed algorithms by comparing with different baselines. We use very large-scale datasets from libsvm website in experiments, including real-sim (n = 72309) and rcv1 (n=20242) for classification, million songs (n = 463715) for regression. For all algorithms, the initial stepsizes are tuned in the range of {10 −6:1:4 }, and the same initial solution with all zero entries is used. The initial iteration number T 0 of SSDC-SPG is tuned in {10 1:1:4 }. For SSDC algorithms, we use a constant parameter γ and also tune its value in {10 −7:1:3 }. First, we compare SSDC algorithms with SDCA (Thi et al., 2017), SGD (Davis and Drusvyatskiy, 2018b), SVRG (Reddi et al., 2016c), GIST (Gong et al., 2013) and GPPA (An and Nam, 2017) for learning with a DC regularizer: minimizing logistic loss with a SCAD regularizer for classification and huber loss with a MCP regularizer for regression. The parameter in Huber loss is set to be 1. The value of regularization parameter is set to be 10 −4 . Note that since these regularizers are weakly convex, SGD with step size η 0 / √ t is applicable (Davis and Drusvyatskiy, 2018b). We set the inner iteration number of SVRG as # gradient n following (Reddi et al., 2016c) and the same value is used as the inner iteration number T of SSDC-SVRG. We set the values of parameters in GIST with their suggested BB rule (Gong et al., 2013). Similar to (Thi et al., 2017), we tune the batch size of SDCA in a wide range and choose the one with the best performance. GIST and GPPA are two deterministic algorithms that use the all data points in each iteration. For fairness of comparison, we plot the objective in log scale versus the number of gradient computations in Figure 1. Second, we consider minimizing 0 regularized non-linear least square loss function 1 n n i=1 (y i − σ(w x i )) 2 + λ w 0 with a sigmod function σ(s) = 1 1+e −s for classification and 0 regularized truncated least square loss function 1 2n n i=1 α log(1 + (y i − w x i ) 2 /α) + λ w 0 (Xu et al., 2018) for regression. We compare the proposed algorithms with GPPA, APG (Li and Lin, 2015) and proximal version of SGD (proxSGD), where GPPA and APG are deterministic algorithms. We fix the truncation value as α = √ 10n. The loss function in these two tasks are smooth and non-convex. The value of regularization parameter is fixed as 10 −6 . For APG, we implement both monotone and non-monotone versions following (Li and Lin, 2015), and then the better one is reported. Although the convergence guarantee of proxSGD remains unclear for the considered problems, we still include it for comparison. The results on two data sets are plotted in Figure 2.
The results of these two experiments indicate that the proposed stochastic algorithms outperform all deterministic baselines (GITS, GPPA, APG) on all tasks, which verify the necessity of using stochastic algorithms on large datasets. In addition, our algorithms especially SSDC-AdaGrad and SSDC-SPG also converge faster than stochastic algorithms SGD, SDCA, and non-convex SVRG verifying that our stochastic algorithms are more practical for the considered problems. We also see that in most cases SSDC-AdaGrad is more effective than SSDC-SPG and SSDC-SVRG.
Finally, we compare SSDC algorithms with two baselines AdaSPD (Nitanda and Suzuki, 2017) and SGD (Davis et al., 2018) for solving two 2 regularized positive-unlabeled (PU) learning problems (Du Plessis et al., 2015) with non-smooth losses, i.e., hinge loss and absolute loss. The 2 regularization parameter is set to be 10 −4 . For SGD, we use the standard stepsize η = η 0 / √ t (Ghadimi and Lan, 2013) with η 0 tuned. The mini-batch size and the number of iterations of each stage of AdaSPD are simply set as 10 4 . The results on two classification datasets are plotted in Figure 3, which show that SSDC-SPG and SSDC-AdaGrad outperforms SGD and AdaSPD.

Conclusions
In this paper, we have presented stochastic optimization algorithms for solving a broad family of DC functions with convex or non-convex non-smooth regularizer. We consider several stochastic algorithms and presented their convergence results in terms of finding an approximate critical point. The proposed stochastic optimization algorithms and their analysis for solving DC functions are improvements over an existing work by making the algorithms more efficient and practical and the theories more broad and general. For the first time, we provide non-asymptotic convergence for solving non-convex problems with non-smooth non-convex regularizer.
Appendix A. Proof of Proposition 2 Option 1. Let us first prove the case of smooth g.
Lemma 7 Under the same assumptions in Proposition 2, we have The proof of this lemma is similar to the analysis to proof of Lemma 1 in (Zhao and Zhang, 2015). For completeness, we will include its proof later in this section. Let's continue the proof by following Lemma 7 and letting w t = t, then Option 2. Next, we prove the case when g is non-smooth. First, we need to show that x * = arg min F γ x 1 (x) in the set x − x 1 ≤ 3G/γ. By the optimality condition of x * we have Plugging x = x 1 into the above inequality, we have where the first inequality uses Assumption 2 (ii). Let us recall the update x t+1 = arg min By the optimality condition of x t+1 and the strong convexity of above problem, we have for any Rearranging the terms, we have Taking expectation on both sides, we have Multiplying both sides w t and taking summation over t = 1, . . . , T and expectation, we have Thus, Plugging the value w t = t, η t = 4/(γt), and using the fact wt 2ηt − w t−1 /η t−1 +w t−1 γ 2 ≤ 0, ∀t ≥ 2, we have Thus,

A.1. Proof of Lemma 7
First, we need the following lemma, which is attributed to Zhao and Zhang (2015).

Lemma 8 Ifr(x) is convex and
Proof of Lemma 8. The proof can be found in the analysis of Lemma 1 in (Zhao and Zhang, 2015), but we still include it here for completeness. By the optimilaty of u and v we have Sincer(x) is convex, then Then, let's start the proof of Lemma 7. Since f ( Recall that a stochastic gradient of f (x) is given by ∂f (x; ξ, ς) = ∇g(x; ξ) − ∂h(x 1 , ς), which has a variance of G 2 according to the assumption, and η t = 1/(L(t + 1)) ≤ 1/L. By the convexity of f (x) and strong convexity ofr(x) we have By the smoothness of f (x), we also have Combing the above two inequalities, we have where the last second equality is due to the update and optimilaty of x t+1 (Option 1 in Algorithm 2); the last equality uses the fact that 2 x−y, y−z = x−z 2 − x−y 2 − y−z 2 . To deal with the term ∂f (x t )−∂f (x t ; ξ t , ς t ), x t+1 −x , we define x t+1 = arg min x x ∂f (x t )+ r(x) + 1 2ηt x − x t 2 , which is independent of ∂f (x t ; ξ t , ς t ). Taking expectation over ξ t and ς t over this term we get where the third equality is due to E[ ∂f (x t ) − ∂f (x t ; ξ t , ς t ), x t+1 − x |x t ] = 0; the last third inequality uses Cauchy-Schwartz inequality; the last second inequality is due to Lemma 8; the last inequality uses Assumption 2 (i). With above inequality, taking the expectation on both sides of (18) and using the fact that η t ≤ 1/L, we get

Appendix B. Proof of Theorem 3
Let us use the same notations as in the proof of Theorem 2 and prove the case of smooth g. By Proposition 2, we have To continue the analysis, we have where we use F k (x k ) ≥ F k (z k ) + γ 2 x k − z k 2 due to the strong convexity of F (x), and T k ≥ 2. On the other hand, we have that where the inequality follows from the Young's inequality with 0 <α < 1. Thus we have that On the other hand, by the convexity of h(·) we have By the strong convexity of F k (x), we also have where we use the fac T k ≥ 3. It then gives us By setting T k = 3Lk/γ + 3, we have Following similar analysis to the proof of Theorem 2, we can finish the proof. For completeness, we include the remaining analysis here. Multiplying both sides by w k = k α and taking summation over k = 1, . . . , K, we have Similar to proof of of Theorem 2, we have which can complete the proof by multiplying both sides by 8γ.
Similarly, we can prove the case of non-smooth g(x). For completeness, we include the details here. By Proposition 2 we have where we use F k (x k ) ≥ F k (z k ) + γ 2 x k − z k 2 due to the strong convexity of F (x), and T k ≥ 1. On the other hand, we have that where the inequality follows from the Young's inequality with 0 <α < 1. Thus we have that .
On the other hand, by the convexity of h(·) we have By the strong convexity of F k (x), we also have 4T k (T k + 1) + 28G 2 γ(T k + 1) 4T k (T k + 1) + 28G 2 γ(T k + 1) + 28G 2 γ(T k + 1) where we use the fact T k ≥ 1. It then gives us By setting T k = k/γ + 1, we have Multiplying both sides by w k = k α and taking summation over k = 1, . . . , K, we have Similar to proof of of Theorem 2, we have Then, by K k=1 k α ≥ K 0 x α dx = K α+1 α+1 and K k=1 k α−1 ≤ K α , (α ≥ 1), we have which can complete the proof by multiplying both sides by 8γ.

Appendix E. Proof of Theorem 5
Recall that F (x) = 1 n 1 n 1 i=1 g i (x) + r(x) − 1 n 2 n 2 j=1 h j (x) and F k (x) = 1 For any x, by the convexity of h(x) we know F k (x) ≥ F (x) + γ 2 x − x k 2 . By applying the result in Proposition 4 to the k-th stage, we have as a result, we have To continue the analysis, we have where we use F k (x k ) ≥ F k (z k ) + γ 2 x k − z k 2 due to the strong convexity of F (x), and F k (x k ) = F (x k ). On the other hand, we have that Wenliang Zhong and James T. Kwok. Gradient descent with proximal average for nonconvex and composite regularization. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada., pages 2206-2212, 2014.