s2fieldsofstudy:
Computer Science
Mathematics

text:
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.


extfieldsofstudy:
Physics
Computer Science

text:
Research on Text Mining of Railway Safety Supervisors Performance Based on BiLSTM and CRF

In the era of big data with unstructured data, the potential value of unstructured data mining is an effective way to solve the industry problem. Based on a large number of data recorded from the actual text of the performance plan of railway security supervisors, this paper proposes a text similarity calculation method based on text mining technology to calculate whether the personnel performance plan matches the reality. First, the text Named Entity Recognition(NER) is realized by using the combination of Bi-directional Long Short Term Memory (BiLSTM) and the Conditional Random Fields (CRF). Then based on the concept similarity calculation of HowNet, we designed the method of calculating the similarity between the same named entity. After that, different weights are given according to the importance of named entity, and a method of computing similarity between named entities is designed.. Finally, according to the given threshold, to obtain whether planning and realistic matching, and the actual personnel working situation, provide the basis for personnel assessment for the management personnel.

INTRODUCTION
The performance of railway security supervisors includes: (1) performance projects and plans. According to the method of "monthly safety performance appraisal form for managers", managers first input post performance items into the system, and maintain monthly work plan and quantitative indicators according to performance items. (2) Realistic performance. When the manager inspects or finds problems on the spot, he chooses the corresponding work plan in the system to input realistic information. In such a long period of work, a large number of text data have been accumulated. It is of great significance to match the actual work of the analysts with the monthly plan. These data rely on manual analysis for a long time. Data analysis is usually not timely and unreliable because of the large amount of data and human factors. It has important research and practical significance to use text similarity computing technology based on text mining, automatically calculating the semantic similarity between two texts, and judge whether the plan and the reality match.
Text mining technology aims to express, understand and extract words, grammar, semantics and other information contained in unstructured text strings through computer technology. Through mining and analyzing the facts and implicit positions, viewpoints and values, it can infer the intention and purpose of the text generator [1]. Text similarity calculation is to calculate the similarity between two texts. There are three kinds of methods for calculating text similarity. One is the traditional calculation method. Character matching is used to determine whether the text is similar or not, but because of the general content of the monthly plan of railway security supervisors, the actual content is more detailed, and it is difficult to match the characters. Second, the character representation is mapped to vector space, using cosine similarity calculation or other distance calculation methods, such as TF-IDF, word 2vec. However, the existing algorithms remain in the representation similarity, and fail to achieve real semantic similarity. Third is based on the construction of semantic computation. Ontology-based semantic similarity calculation [2], Because the complexity of ontology construction, it is a relatively large project to build ontology or knowledge map based on the semantic similarity computation of [2].
Based on the analysis of the characteristics of data, this paper applies the method of named entity recognition and concept similarity calculation to realize text similarity calculation. Named Entity Recognition (NER) refers to the recognition of text entities with specific meanings, usually including names, places, institutions and so on. NER tasks include entity boundaries and entity types. It can be regarded as a classification problem, so we can use methods such as Bayesian model based on classification [3], Support Vector Machine (SVM) [4], Maximum Entropy (ME) [5]. It can also be considered as a serialization problem, so Hidden Markov Model (HMM)[6], Maximum Entropy Markov Model (MEMM) and Conditional Random Field (CRF) model can be used [7]. Lin B Y et al. [8] proposed that the word representation of multi-channel information and traditional CRF are embedded into LSTM network. The synthetic word contains character-level information and syntactic features. The model is similar to the model in this paper, but there are differences in word representation. The similarity calculation of the same named entity is based on the similarity calculation of words or phrases. The text similarity calculation based on words is based on the method of synonym word forest [9]. Chinese word similarity is based on semantic resource Hownet and concept similarity calculation method based on Hownet. These methods are based on a large corpus to calculate the similarity between words.

COMPUTATION OF TEXT SIMILARITY
In this paper, the process of calculating the similarity between plan and realistic content mainly includes text preprocessing, named entity recognition, concept similarity calculation and final comprehensive analysis. The overall process is shown in Figure 1.  Figure 1 Text Similarity Computing Flow Text preprocessing process. First of all, the original personnel performance plan and performance realism are divided into multiple tasks according to line change and period respectively. Each task is clearly numbered. According to the content characteristics of task record, the named entity extracted is defined as time, place, task and problems found. Then the named entity is labeled by BIOES.
Named entity recognition process. The process of named entity recognition is divided into two steps: model training and model application. Model training is based on the combination of BiLSTM and CRF. The tagged corpus is applied to the model and the model is trained to achieve high accuracy. The application of the model is to put the original performance plan and realistic content into the trained model separately, and automatically extract the time, place, person and key elements of the problem for the use of conceptual similarity.
Conceptual similarity calculation process. Conceptual similarity calculation is to calculate the similarity between the entity of performance plan and the corresponding entity of performance reality, and to get the entity similarity between the two texts. According to the importance of the entity, the corresponding weight of the entity is given. For example, in defined entities, time is less important, because it is written in the monthly plan and filled in the month's realism, so time is not so important. On the contrary, task and location are more important concepts, because the matching between tasks and locations is similar, it can be basically identified as a task, which can be considered as a match between the plan and reality. Finally, given the threshold, the similarity between texts is considered to be similar if the similarity is higher than 0.8. As shown in Conceptual similarity calculation process Comprehensive analysis process. After getting the similarity of the two texts, we can analyze the personnel performance data. The main analysis of the actual implementation of the staff's work plan.

NAMED ENTITY RECOGNITION MODEL
The neural network model in this paper consists of embedding layer, BiLSTM layer and CRF layer. Figure 3 shows the entire network structure. The embedding layer is applied to construct the feature representation of Chinese in each sentence. Then, the feature representation vectors are put into the BiLSTM layer. Therefore, a hidden state is obtained at BiLSTM level, which is considered as the character feature vector. In the last CRF layer, the final prediction label of the input sentence is decoded. The whole neural network is implemented by tensorflow, a deep learning framework.

Tagging Data
Generally speaking, supervised deep learning algorithms need a lot of labeled data. So before the experiment, we need to annotate a lot of text data. Firstly, four named entities are defined according to the analysis requirements and the text characteristics of personnel planning and realistic records. Entity categories are shown in Table 1. Secondly, in order to distinguish a complete entity, we use B (start), I (internal), O (other), E (End), S (single) tags and named entity definitions to tag data. B, I and E represent the beginning of a multi-character entity, the middle part of a multi-character entity, and the end of a multi-character entity, respectively. S means that there is only one character entity. O represents other characters, not entities we define. For example, the first character of a time entity is marked as B-TIM, the remaining characters are marked as I-TIM, and the last character is automatically marked as E-TIM by the program. The average length of sample sentences is about 30 characters.

Character Embedding Layer
Character embedding layer is the high-dimensional representation of words. Characters are represented in two ways. One is to use genism based on Chinese wiki corpus to represent vectors. Each character is represented by a 100-dimensional vector. The second is the use of dictionary representation based on stuttering participle. If each character after word segmentation is composed of a single character, it is expressed as 0. The representation of two characters is 1 and 3. The representation of three characters is 1, 2 and 3. Define a 20-dimensional vector to represent each character vector. Then the representations of both modes are input into the BiLSTM layer.

Bidirectional Long-term and Short-term Memory Network
Long-term and short-term memory network (LSTM) is a special recurrent neural network (RNN). It can learn to rely on information for a long time, especially the relevance of information. Because it has three gates to protect and control neurons. controls what information can be discarded. Input gate control requires new information to be stored. The output gate controls the information that needs to be output. The specific workflow of the LSTM unit is shown in Figure 4.
it, ft ,ot , Ct represent the unit states of the input gate, the forgetting gate and the output gate at T time, respectively. xt and ht represent the vector of the input vector and the hidden layer at time t. σ refers to sigmoid activation function.Wi and bi represent the weight vector and the bias vector, respectively.
BiLSTM has two LSTMs. An LSTM processing sequence from left to right contains the past information of data, which is called forward hiding layer. Another LSTM processes data from right to left, containing future information of the data, called a backward hiding layer. So the final hidden state of BiLSTM is the connection between the front and back hidden layers, as follows.

Conditional Random Field Algorithms
In the final prediction sequence, it is necessary to consider the correlation between the final tags. For example, in the input sequence, I-TIM cannot be behind I-LOC. These restriction information can be learned automatically by CRF layer in the training process. So conditional random field model is added to the model. If we use the softmax layer to predict the final tag, these constraints may be broken.

CONCEPTUAL SIMILARITY CALCULATION
This paper uses the concept similarity calculation based on HowNet. This paper takes the concepts represented by Chinese and English words as descriptive objects, and reveals the relationship between concepts and concepts, as well as the attributes of concepts as the basic content of the knowledge base [11]. It is a concept consisting of "sememe". Its similarity calculation method is a calculation method based on world knowledge. "sememe" is the smallest unit to describe a concept. It describes each concept with a series of original meanings. HowNet uses more than 1500 sememes and is divided into 10 categories: Event, entity, attribute, aValue, quantity, qValue, SecondaryFeature, syntax, EventRole, EventFeatures. These sememes are divided into four groups. "Basic semantics" are used to describe the semantic characteristics of a single concept. "Grammatical sememe" is used to describe grammatical features. "Relational sememe" is used to describe the relationship between concepts and concepts. It also includes "Other sememe ". Since the extracted words belong to notional words after extracting the named entity of the text, some of them are phrases, so there is a problem that the phrase or word is not included in the original

Yes No
Computing the similarity of notional words.
The unlisted words are segmented into concepts to form a linear list of multiple concepts, and organized in reverse order. The last three concepts are selected.
Combination concepts between computational concepts.
Is the second concept a function word?
Direct addition of concepts.
Return to the first concept.
No Yes Figure 5 Unregistered Word Processing When the words or phrases to be calculated are not included in the HowNet corpus, the unlisted words are segmented into concepts to form a linear list of multiple concepts and organized in reverse order. For example, after the segmenting of "signal machine", it can be stored as: [machine]→[signal]. Take the last three concepts. Then the concepts in the concept list are merged in order. Between the two concepts, if the second concept is a function word, the first concept is taken directly, otherwise the two concepts are added together. Entities processed by unlisted words belong to notional words, so the similarity between notional words is only considered here.
The basic idea of calculating the similarity between notional words is that the overall similarity should be based on partial similarity. A complex whole is decomposed into parts, and the global similarity is obtained by calculating the similarity between parts. [11] We divide the semantic expression of notional concept into four parts: independent sememe description, other independent sememe description, relational sememe description and symbolic sememe description. Independent sememe description: Compute the similarity between two independent sememes, expressed as Sim(S1,S2) P1 and P2 denote two sememes. l denotes the equal position of two sememes, and is the path length of A and A in the hierarchical system of sememes. Mean operation is used to calculate the similarity among other independent sememes, relational sememes and symbolic sememes. Among them, S1 and S2 denote the two sememes computed.
Computing the similarity between two concepts is expressed as follows

EXPERIMENTAL RESULTS
In the experiment, from July 2017 to January 2018, more than 60,000 data were used as the experimental data. Among them, 1000 were used as training samples and 200 were used as testing samples to train named entity models. Then the model is applied to all data and named entities are extracted automatically. The results are shown in Table 2. Conlleval CRF++ tool is used to calculate the accuracy and recall rate. From the experimental results, we can find that "time", "place" and "task" have higher accuracy. This is because the content and format of these types of named entity records are more standardized. However, the accuracy of the "discovered problem" is not very high because of the diversity of its own problems and the different habits of personnel records.
The results of personnel performance plan and realistic matching calculated by named entity extraction and concept similarity are compared artificially, and the accuracy is 94%.

CONCLUSION
In this paper, we use classical application scenarios and techniques in text mining field to realize long text similarity calculation step by step, which has been well applied in railway personnel performance analysis. Named entity recognition itself is also a typical application scenario of text analysis. In the process of analysis, converting unstructured text data into structured data can provide more dimensions of mining personnel performance information.