{'fraction_non_alphanumeric': 0.058562285017634, 'fraction_numerical': 0.013279923368311054, 'mean_word_length': 4.153242091092663, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stochastic Primal-Dual Coordinate Method for Nonlinear Convex Cone Programs

Block coordinate descent (BCD) methods and their variants have been widely used in coping with large-scale nonconstrained optimization problems in many fields such as imaging processing, machine learning, compress sensing and so on. For problem with coupling constraints, Nonlinear convex cone programs (NCCP) are important problems with many practical applications, but these problems are hard to solve by using existing block coordinate type methods. This paper introduces a stochastic primal-dual coordinate (SPDC) method for solving large-scale NCCP. In this method, we randomly choose a block of variables based on the uniform distribution. The linearization and Bregman-like function (core function) to that randomly selected block allow us to get simple parallel primal-dual decomposition for NCCP. The sequence generated by our algorithm is proved almost surely converge to an optimal solution of primal problem. Two types of convergence rate with different probability (almost surely and expected) are also obtained. The probability complexity bound is also derived in this paper.


Introduction.
Recently, block coordinate descent (BCD) methods and their variants have been widely used in coping with large-scale optimization problems in many fields such as imaging processing, machine learning, compress sensing and so on (See [11,22,32,33]). In each iteration of these methods, one block of coordinates is selected to reduce the objective value, simultaneously the other blocks are keeping fixed. The main advantage of BCD is to reduce the complexity and memory requirements per iteration. These benefits are increasingly important for very-large scale problem.
For problem without constraints, there are two variations of BCD discussed the most by researchers. The first variation is on block choosing strategy. One common approach for block choosing is cyclic strategy. Tseng [29] proved the convergence of a BCD of cyclic strategy. Luo and Tseng [15] and Wang and Lin [30] proved local and global linear convergence under specific assumptions respectively. The other approach is randomized strategy. Nesterov [17] studied the convergence rate of randomized BCD for convex smooth optimization. Richtárik and Takáč [23] and Lu and Xiao [14] extend Nesterov's technique to composite optimization. The point read to evaluate the gradient in each iteration is the second variation of BCD. If the read point have different "ages", this type of BCD called asynchronous BCD, otherwise it is called synchronous BCD. All the variants of BCD reviewed above are synchronous BCD. Liu and Wright [12] and Liu et. al. [13] established the convergence rate of asynchronous BCD for composite optimization and convex smooth optimization without constraints respectively.
For problem with constraints, there are only a few works. Gao et. al. [8] proposed a coordinate type method for problem with linear coupling constraints. Necoara and Patrascu [16] proposed a random coordinate descent algorithm for optimization problem with one linear constraint. To the best of our knowledge, there is no primal-dual coordinate convergence and convergence rate results for optimization problem with nonlinear inequality constraints.
In the big data era, there is one class of optimization problem with nonlinear inequality constraints which has received much attention in the compressed sensing and machine learning fields, such as least absolute shrinkage and selection operator (LASSO) problem, basis pursuit denoising (BPDN) problem and support vector machine (SVM) problem. Actually, the LASSO problem is a least-squares problem with a 1-norm constraint (Tibshirani [28]) and BPDN is a sparse optimization problem with a least-squares constraint (Chen et. al. [4]). In the field of SVM, Oneto et. al. [19] states that the Ivanov regularization scheme allows more effective control of the learning hypothesis space, while the Morozov regularization scheme is useful when an effective estimate of the noise in the data is available. All these problems are problem with one smooth or nonsmooth inequality constraint.
In this paper, we consider the following nonlinear convex cone programs (NCCP): (1.1) where G is a convex smooth function on closed convex subset U ⊂ R n , J is a convex but possibly nonsmooth function on U ⊂ R n , and Θ(u) is a possibly nonsmooth C-convex mapping from R n to R m . C is a nonempty closed convex cone in R m with vertex at the origin, that is αC+βC ⊂ C, for α, β ≥ 0. It is obvious that whenC (the interior of C) is nonempty, the constraint Θ(u) ∈ −C corresponds to an inequality constraint. The case C = {0} corresponds to an equality constraint. C * denotes the conjugate cone. Assume that both J(u) = (1.2) U = U 1 × U 2 · · · × U N , u i ∈ U i ⊂ R ni and N i=1 n i = n.
In order to cope with separable or nonseparable, smooth or nonsmooth NCCP, Cohen and Zhu [6] proposed a fairly general first-order primal-dual decomposition method, Auxiliary Problem Principle of augmented Lagrangian methods (APP-AL), based on linearization of the augmented Lagrangian. Recently, Zhao and Zhu [35] extend APP to a more flexible framework, Variant Auxiliary Problem Principle methods (VAPP), with an O(1/t) convergence rate on average for primal suboptimality, feasibility, and dual suboptimality. Moreover, they propose a backtracking scheme to treat the case where the Lipschitz constants are not known or computable.
In this paper, we propose a stochastic primal-dual coordinate (SPDC) method based on auxiliary problem principle (Cohen and Zhu [6]) for NCCP. In this method, we randomly choose a block of variables based on the uniform distribution. The linearization and Bregman-like function (core function) to that randomly selected block allow us to get simple parallel primal-dual decomposition for problem (P). The sequence generated by our algorithm is proved almost surely converge to an optimal solution of problem (P). The almost surely O(1/t 1−α 2 ) convergence rate and expected O(1/t 1−α ) result with 1/2 < α < 1 are also obtained for problem (P) under the convexity assumptions. The probability complexity bound is also derived in this paper.
The rest of this paper is organized as follows. Section 2 is devoted to technical preliminaries. The updating scheme of SPDC for (P) is presented in Section 3. In Section 4 we establish the convergence. Almost surely O(1/t 1−α 2 ) sub-linear convergence rate is proposed in Section 5. In Section 6 expected O(1/t 1−α ) sub-linear convergence rate and the probability complexity bound is established. In Section 7, we compute an example to show the efficiency of our algorithm.

Preliminaries.
In this section, we first provide some preliminaries which are useful for our further discussions and then summarize some notations and assumptions to be used. We denote · and · as the inner product and Euclidean norm of vector, respectively.
2.1. Notations and assumptions. Throughout this paper, we make the following standard assumptions for Problem (P): J is subgradientiable and has linear bounded subgradients in U, that is (ii) G is a convex and differentiable with its derivative Lipschitz of constant B G .
(v) Constraint Qualification Condition. WhenC = ∅, we assume that Furthermore, the following lemma gives some properties of G which satisfies Assumption 1. 2.2. Augmented Lagrangian and first-order primal-dual decomposition algorithm. In this subsection, the Lagrangian of (P) is defined as: and a saddle point (u * , p * ) ∈ U × C * is such that This manuscript is for review purposes only.
Under Assumption 1, there exist saddle points of L on U × C * . The dual function ψ is defined as The function ψ is concave and sub-differentiable. Using dual function ψ(p), we consider the primal-dual pair of nonlinear convex cone optimization: The following theorem characterizes a saddle point optimality condition for the primal and dual problem.
or the following variational inequality holds: is a saddle point if and only if u * and p * are, respectively, optimal solutions to the primal and dual problems (P) and (D) with no duality gap, that is, with (G + J)(u * ) = ψ(p * ). Now we take a trick by introducing slack variables which help problem (P) come back to problem with equality constraints. Namely, the problem (P) is converted into the equivalent problem with equality constraints as follows (P 1 ): min The augmented Lagrangian for this problem is The augmented Lagrangian associated with problem (P) is defined as where ϕ(Θ(u), p) = [ Π p + γΘ(u) 2 − p 2 ]/2γ and Π is a projection on to C * . The augmented Lagrangian dual function is as following: This manuscript is for review purposes only.
Using ψ γ (p), we obtain new primal-dual pair of nonlinear convex cone optimization The following theorem shows that function ϕ(θ, p), dual function ψ γ (p) and augmented Lagrangian L γ (u, p) have some useful properties.
Theorem 2.3. Suppose Assumption 1 holds for problem (P). Then we have (i) The function ϕ(θ, p) is convex in θ and concave in p.
(ii) ϕ is differentiable in θ and p and one has ∇ θ ϕ(θ, p) = Π(p + γθ), (iv) L and L γ have the same sets of saddle points U * × P * respectively on U × C * and U × R m .
For the general NCCP, the augmented Lagrangian method is an approach which can overcome the instability and nondifferentiability of the dual function of the Lagrangian. Furthermore, the augmented Lagrangian of a constrained convex program has the same solution set as the original constrained convex program. The augmented Lagrangian approach for equality-constrained optimization problems was introduced in Hestenes [9] and Powell [21], then extended to inequality-constrained problems by Buys [3].
Although the augmented Lagrangian approach (Uzawa algorithm) has several advantages, it does not preserve separability, even when the initial problem is separable. One way to decompose the augmented Lagrangian is ADMM (Fortin and Glowinski [7]). ADMM can only handle convex problems with linear constraints and is not easily parallelizable. Another way to overcome this difficulty is the Auxiliary Problem Principle of augmented Lagrangian methods (APP-AL) (Cohen and Zhu [6]), which is a fairly general first-order primal-dual decomposition method based on linearization of the augmented Lagrangian in separable or nonseparable, smooth or nonsmooth NCCP. Cohen and Zhu (1984) [6] propose first-order primal-dual augmented Lagrangian methods for NCCP as Algorithm 2.1. Cohen and Zhu (1984) shows the sequence {(u k , p k )} generated by APP-AL Initialize u 0 ∈ U and p 0 ∈ C * for k = 0, 1, · · · , do Update u k+1 = arg min u∈U ∇G(u k ), u + J(u) + Π p k + γΘ(u k ) , Θ(u) + 1 D(u, u k ) Update p k+1 = Π p k + γΘ(u k+1 ) end for convergence to (u * , p * ) saddle point of L over U × C * . If we choose the following additive K(u) respect to the space decomposition 1.2, K(u) = N i=1 K i (u i ), then the primal problem split to N small optimization subproblem only for u i . [6] In the era of big data, there has been a surge of interest in redesign of APP-AL suitable for solving the huge optimization with available computing performance.
2.3. The properties of projection on convex cone. In this subsection, we introduce some properties of projection on convex sets (resp. convex cone) as preparations. These properties are used in the following sections.
Let S be a nonempty closed convex set of R m . For x ∈ R m , we propose the projection Π S (x) as a projection on S. Then Π S (x) is characterized by the following two conditions [5]: Furthermore, the following proposition gives another property of projection operator which is used for convergence and convergence rate analysis.
Next, we consider the properties for projection on convex cone. Let C be a nonempty closed convex cone in R m with vertex at the origin. C * denotes the conjugate cone. Let Π denote the projection on C * and Π −C denote the projection on −C. The projection is characterized by the following conditions. (see Wierzbicki [31]): 2.4. The boundness of multiplier sets and application. Noted that under Assumption 1, the dual optimal solution set of Lagrangian for (P) is bounded [6]. Here we denote the bound is µ 0 i.e., p * ≤ µ 0 . Moreover, we set µ = µ 0 + 1. The estimate of dual optimal bound µ is required in constructing new coordinate descent method. In this section, we will provide the estimate of dual optimal bound for problem (P) with special convex cone C = R m , Hiriart-Urruty and Lemaréchal gives a dual optimal bound as follows. (See section 2.3 Chapter VII of [10]) whereû is one Slater vector. In many cases, we can easy to getû and prior to estimate the lower bound G + J of (G + J)(u * ), then we obtain one bound µ for the dual optimal set as following: This manuscript is for review purposes only.
For constrained optimization problem Nedić and Ozdaglar [18] recently use these bounds to design a dual algorithm that projects on a set containing the dual optimal solution. Shefi and Teboulle [27] also use these bounds to derive the rate of convergence results for the proximal method of multipliers for convex minimization.
When C = K m ν , Zhao and Zhu [35] gives a dual optimal bound, and the following lemma shows that µ 0 is computable.
Lemma 2.5. If there exists a pointû satisfying CQC condition for problem (P) and C = K m+1 Such bound plays a key role in our subsequence development. In particular, we use this bound to construct a new coordinate descent method by augmented Lagrangian to solve the nonlinear convex cone program. In order to treat the nonseparability of constraints, the dual update is need to compute a projection onto an intersection to the nonnegative orthant and a ball B µ with radius µ. However, this projection is very easy to implement as: P µ (y) = [min(1, µ/ y )]y.
In the following sections, we propose a Stochastic Primal-Dual Coordinate method (SPDC) to solve NCCP, analyse the convergence and convergence rate of our method.
3. Stochastic primal-dual coordinate method. In this section, we propose a stochastic primal-dual coordinate descent algorithm to solve (P). Firstly, we introduce the core function K(·) satisfying the following assumption: Assumption 2. K is strongly convex with parameter β and differentiable with its gradient Lipschitz continuous with parameter B on U. [1,6]. From Assumption 2 we have: Moreover, we assume that the sequence of parameter { k } is non-increasing and satisfies: Then we introduce Stochastic Primal-Dual Coordinate Method (SPDC) for solving (P) in Algorithm 3.1.
In this algorithm, P µ denotes the projection on the ball B µ which is computed easily. For the sake of brevity, let us set that q k = Π p k + γΘ(u k ) , q k+1/2 = Π p k + γΘ(u k+1 ) . Noted that the primal problem of algorithm can be expressed as and the dual problem of algorithm is expressed as Note that if we choose an additive Bregman like function (or core function) respect to the space decomposition (1.2) that is Then problem (AP k ) is just a small optimization problem for selected block i(k).
for (AP k ), we perform only a block proximal gradient update for block i(k), where we linearize the coupled function G(u) and augmented Lagrangian term ϕ(Θ(u), p) and add the proximal term to it. In next sections, we will establish the convergence and convergence rate and probability complexity bounds of SPDC.
4. Convergence analysis. In this section, we will establish results about convergence of SPDC. Before proceeding, we first give the generalized equilibrium reformulation of saddle point formulation (2.5): Obviously, bifunction L(u , p)−L(u, p ) is convex in u and linear in p for given u ∈ U, p ∈ C * . In algorithm SPDC, the indices i(k), k = 0, 1, 2, . . . are random variables. After k iterations, SPDC method generates a random output (u k+1 , p k+1 ). We denote by F k is a filtration generated by the random variable i(0), i(1), . . . , i(k), i.e., This manuscript is for review purposes only.
. . , i(k − 1)}, for given u ∈ U, we have: For the sequence {(u k , p k )} generated by algorithm SPDC, the following function provides one upper bound for u k − u * 2 : The boundness of the sequence {(u k , p k )} generated by SPDC will play an important role. To obtain this boundness, we need the following lemma.
Proof. (i) Firstly, for all u ∈ U, the unique solution u k+1 of the primal problem (3.2) is characterized by the following variational inequality: which follows that The simple algebraic operation follows that (4.10) Combining (4.9) and (4.10) with u = u * , we obtain that (4.11) Take expectation with respect to i(k) on both side of (4.11), together the conditional expectation (4.2)-(4.4), we get This manuscript is for review purposes only.
Furthermore, we have that (from (4.12)) Then statement (i) is provided.
(ii) By simple operations the following equality holds for all p ∈ C * : From the property of projection (2.9) with x = p k + γΘ(u k+1 ) and y = p, the first term of right hand side of (4.13) is negative: Second, using Proposition 2.4 with x = γΘ(u k+1 ), y = γΘ(u k ), z = p k , we obtain one upper bound of the third term of (4.13): Thus from (4.13), for any p ∈ C * ∩ B µ , we have (since p k+1 = P µ (q k+1/2 ) and by property (2.10) of projection) Therefore, we have Then, (4.17) yields that Then statement (ii) is provided.
(iii) First, we observe that (from the Hölder's inequality xy ≤ (κx 2 + y 2 κ )/2, κ > 0) For statement (ii), let p = p * , and take the expectation of i(k) on both sides, we have This manuscript is for review purposes only.
(ii) Since lim k→+∞ Λ k (u k , p k ) almost surely exists, then Λ k (u k , p k ) is almost surely bounded. From (4.5), we have Λ k (u k , p k ) ≥ β 2 u k − u * 2 , which implies the sequence {u k } is almost surely bounded.
Before the study of the convergence of SPDC, we start with following lemma about augmented Lagrangian L γ , which will be used in the forthcoming convergence analysis.
Proof. (i) By the convexity of ϕ(θ, p) in θ, we have This manuscript is for review purposes only.
(iii) Note that L γ (u * , p * ) ≥ L γ (u * , p k ), we have that Together statement (i) and (ii) of this lemma, we have To estimate the term E i(k) u k − u k+1 , we consider (4.6) with u = u k , it follows that This manuscript is for review purposes only.
Next convergence theorem is derived by Proposition 4.2 and Robbins-Siegmund Inequality [24].
(ii) Every cluster point of {u k } is almost surely an optimal solution of (P).
Definition 5.1. Given the desired accuracy ε > 0, the primal point u ε ∈ U is an ε-optimal solution for (P) if it satisfies Bound on primal suboptimality: Bound on feasibility: This section devotes to analyse the convergence rate for SPDC of (P). Before the convergence rate analysis, we again study the augmented Lagrangian function. Define the value function associated with (P 1 ) as From the convexity of G + J and the C-convexity of Θ, it easy to show v(ζ) is convex in ζ. Then we write following problem which is equivalent to (P) and (P 1 ). The augmented Lagrangian function of (P 2 ) is The dual function for (P 2 ) is ψ γ (p) = min ζ∈R m γ (ζ, p). We also show that ψ γ (p) is coincide with the dual function ψ γ (p) for (P). Therefore, the optimal multiplier p * ∈ C * achieves the maximum ofψ γ (p). From the stability of augmented Lagrangian of (P 2 ), we haveζ p * = arg min γ (ζ, p * ) = 0 and γ (ζ p * , p * ) = L γ (u * , p * ) = ψ γ (p * ). From (5.4), γ (ζ, p) is strongly convex with constant γ, it yields (5.5) The following lemma furnishes the important character of augmented Lagrangian which will be used to derive the convergence rate.
Lemma 5.2. (Inequalities for primal suboptimality and feasibility) Suppose Assumption 1 holds, then for any given u ∈ U and p * ∈ P * , we have This manuscript is for review purposes only.
Together with statement (i) of this proposition, we have Π Θ(u) 2 Noted that the augmented Lagrangian has the stability or it furnishes an exact penalty function for (P), i.e. the solution of the following exact penalty problem is also one solution for (P).
Now we start the convergence rate analysis with above exact penalty problem (P 3 ) and the primal suboptimality and feasibility for problem (P).
By the definitionū t , the convexity of L γ (u, p) for u and k = 1 k α , 1 2 < α ≤ 1, it follows that (5.12) (ii) Together statement (ii) of Lemma 5.2 and statement (i) of this theorem, we have that (iii) From the statement (iii) of Lemma 5.2 and statement (i) of this theorem, it follows Remark 5.4. Theorem 5.3 showsū t produced by Algorithm SPDC almost surely satisfies the suboptimality and feasibility condition (5.1) and (5.2). The convergence rate is O(1/t 1−α 2 ) in this case, i.e. given a desired accuracy ε > 0 the SPDC produces an ε-solution of (P) in O(1/ε 2 1−α ) iterations with probability 1.
Next section we will propose an expected convergence rate generated by algorithm SPDC.
6. Expected Convergence rate. In this section we prove expected convergence rate for SPDC. Before proceeding, we need following lemma for the bifunction value at (u k , q k ). Lemma 6.1. (Monotonicity of expected distance like function) Suppose Assumption 1 and 2 hold, {(u k , p k )} is generated by SPDC, the parameter sequence { k } satisfies condition (3.1). Then for any t > k > 0 and p ∈ C * ∩ B µ , it holds that where and p could possibly be random.
Proof. From (i) of Lemma 4.1, we obtain k N L(u k , q k ) − L(u * , q k ) (6.1) Taking expectation with respect to F t , t > k, for inequality (6.1), we obtain that Taking expectation with respect to F t for (ii) of Lemma 4.1, it follows that, ∀p ∈ This manuscript is for review purposes only.
Summing (6.2) and (6.3), it follows that Noted that the above derivation is valid even though p is a random vector. Then, we have the claimed results.
For the sequence {(u k , p k )} generated from Algorithm SPDC, and any t > 0 we define k . Then we have the following proposition.
Proposition 6.2. (Global estimate of expected bifunction values in (ū t ,p t )) Let Assumption 1 and 2 hold, k = 1 k α . Then we have d 2 > 0 such that where p could possibly be random.
7. Numerical Experiments. In this section, we test the proposed SPDC method on solving the Elastic Net Support Vector Machine problem (EN-SVM) [34]: The elements of A ∈ R m×n are selected i.i.d. from a Gaussian N (0, 1) distribution. To construct a sparse true solution u * ∈ R n , given the dimension n and sparsity s, we select s entries of u * at random to be nonzero and N (0, 1) normally distributed, and set the rest to zero. The measurement vector b ∈ R m is obtained by b = Au * , λ ∈ [0, 1] and δ ∈ R + .
The left-hand graph in each figure shows the number of blocks and plots suboptimality versus iteration count. The right-hand graph indicates the number of blocks and plots feasibility value versus iteration count.