Linear convergence of SDCA in statistical estimation
Chao Qu Huan Xu

	
	Mapping the Milky Way with LAMOST I: Method and overview
    Chao Liu
      1
   Yan Xu
      1
   Jun-Chen Wan
      1,2
   Hai-Feng Wang
      1,2
   Jeffrey L. Carlin
   3
   Li-Cai Deng
      1
   Heidi Jo Newberg
      4
   Zihuang Cao
      1
    Yonghui Hou
       5
    Yuefei Wang
       5
    Yong Zhang
       5
   
    Received  2017 month day; accepted  2017  month day
=============================================================================================================================================================================================================================================================================


	In this paper, we consider stochastic dual coordinate (SDCA) without strongly convex assumption or convex assumption. We show that SDCA converges linearly under mild conditions termed restricted strong convexity. This covers a wide array of popular statistical models including  Lasso, group Lasso, and logistic regression with ℓ_1 regularization, corrected Lasso  and linear regression with SCAD regularizer. This significantly improves previous convergence results on SDCA for problems that are not strongly convex. As a by product, we derive a dual free form of SDCA that can handle general regularization term, which is of interest by itself.
	
	
	


	
	

§ INTRODUCTION

	First order methods have again become a central focus of research in optimization and particularly in machine learning in recent years, thanks to its ability to address very large scale empirical risk minimization problems that are ubiquitous in machine learning, a task that is often challenging for other algorithms such interior point methods.  The randomized (dual) coordinate version of the first order method samples one data point and updates the objective function at each time step, which avoids the computations of the full gradient and  pushes the speed to a higher level. Related methods have been implemented in various software packages <cit.>. In particular, the randomized dual coordinate method considers the following problem.
	
    min_w∈Ω F(w)   :=1/n∑_i=1^n f_i (w)+λ g(w) 
       = f(w)+λ g(w),

	where f_i(w) is a convex loss function of each sample and g(w) is the regularization, Ω is a convex compact set.
	Instead of directly solving the primal problem it look at the dual problem
	
    D(α)=1/n∑_i=1^n-ψ_i^* (-α_i)-λ g^*( 1/λ n∑_i=1^nX_iα_i ),

	where it assumes the loss function f_i(w) has the form ψ_i(X_i^Tw).  <cit.> consider this dual form and proved linear convergence of the stochastic dual coordinate ascent method (SDCA) when g(w)=w_2^2. They further extend the result into a general form, which allows the regulerizer g(w)
	to be a general strongly convex function <cit.>. <cit.> propose the AdaSDCA, an adaptive variant of SDCA, to allow the method to adaptively change the probability distribution over the dual variables through the iterative process. Their experiment results outperform the non-adaptive methods. <cit.> consider a primal-dual frame work and extend SDCA to the non-strongly convex case with sublinear rate. <cit.> further improve the convergece speed using a novel non-uniform sampling that selects each coordinate with a probability proportional to the square root of the smoothness parameter. Other acceleration techniques <cit.>,  as well as mini-batch and distributed variants on coordinate method <cit.> have been studied in literature. See <cit.> for a review on the coordinate method. 
	
	Our goal is to investigate how to extend SDCA to non-convex statistical problems. Non-convex optimization problems attract fast growning attentions due to the rise of numerous applications, notably non-convex M estimators (e.g.,SCAD <cit.>, MCP <cit.>),  deep learning <cit.> and robust regression <cit.>. <cit.> proposes a dual free version of SDCA and proves the linear convergence of it, which addresses the case that each individual loss function f_i(w) may be non-convex, but their sum f(w) is strongly convex.  This extends the applicability of SDCA.  
	From a technical perspective, due to non-convexity of f_i(w), the paper avoids explicitly using its dual (hence the name “dual free”), by introducing pseudo-dual variables.
	
	In this paper, we consider using SDCA to solve M-estimators that are not strongly convex, or even non-convex. We show that under the restricted strong convexity condition, SDCA converges linearly. This setup includes well known formulations such as   Lasso, Group Lasso, Logistic regression with ℓ_1 regularization, linear regression with SCAD regularizer <cit.>, Corrected Lasso <cit.>, to name a few. This significantly improves upon existing theoretic results <cit.> which only established sublinear convergence on convex objectives.
	
	
	
	To this end, we first adapt  SDCA <cit.> into  a  generalized dual free form in  Algorithm <ref>. This is because to apply SDCA in our setup, we need to introduce a non-convex term and thus demand a dual free analysis.
	We remark that the theory about dual free SDCA established in <cit.> does  not apply to our setup for the following reasons:
	
		
  * In <cit.>, F(w) needs to be strongly convex, thus does not apply to Lasso or non-convex M-estimators.
		
  * <cit.> only studies the special case where g(w)=1/2w_2^2, while the M-estimators we consider include non-smooth regularization such as ℓ_1 or ℓ_1,2 norm.
	
	
	
	
	
	
	
	We   illustrate the update rule of  Algorithm <ref> using an example. While our main focus  is for   non-strongly convex problems, we start with a strongly convex example to obtain some intuitions. Suppose f_i(w)=1/2(y_i-w^T x_i)^2 and g(w)=1/2w_2^2+ w_1. It is easy to see ∇ f_i(w)= x_i(w^T x_i-y_i) and w_t=min_w∈Ω1/2w-v_t_2^2+ w_1.
	
	
	
	
	
	
	
	It is then clear that to apply SDCA  g(w) needs to be strongly convex, or otherwise the proximal step w_t=max_w∈Ω w^Tv^t-w_1 becomes ill-defined: w_t may be infinity (if Ω is unbounded) or not unique. This observation motivates the following preprocessing step: if g(·) is not strongly convex, for example Lasso where  f_i(w)=1/2(y_i-w^T x_i)^2 and g(w)=w_1, we redefine the formulation by adding a strongly convex term to g(w) and subtract it from f(w).
	More precisely, for i=1,...,n, we define ϕ_i(w)=n+1/2ny_i-w^Tx_i_2^2, ϕ_n+1(w)=-λ̃ (n+1)/2w_2^2, g̃(w)= 1/2w_2^2+λ/λ̃w_1,
	
	
	
	
	
	and apply Algorithm <ref> on 1/n+1∑_i=1^n+1ϕ_i(w)+λ̃g̃(w) (which is equivalent to Lasso), where the value of λ̃ will be specified later. Our analysis  is thus focused on this alternative representation. The main challenge arises from the  non-convexity of the newly defined ϕ_n+1, which precludes the use of the dual method as in <cit.>. While in <cit.>, a dual free SDCA algorithm is proposed and analyzed, the results do not apply to out setting for reasons discussed above.  
	
	Our contributions are two-fold. 1. We prove   linear convergence  of SDCA for a class of problem that are not strongly convex   or even non-convex, making use of the concept  restricted strong convexity (RSC). To the best of our knowledge, this is the first work to prove  linear convergence   of SDCA under this setting which includes several statistical model such as Lasso, Group Lasso, logistic regression, linear regression with SCAD regularization, corrected Lasso, to name a few.  2. As a byproduct,  we derive a dual free from SDCA that extends the work of <cit.> to account for more general regularization g(w).
	
	
	
	Related work.   <cit.> prove  linear convergence  of the batched gradient and composite gradient method in Lasso, Low rank matrix completion problem  using the RSC condition. <cit.> extend this to a class of non-convex M-estimators. In spirit, our work can be thought as a stochastic counterpart. Recently, <cit.> consider SVRG and SAGA in the similar setting as ours, but they look at the primal problem. <cit.> considers dual free SDCA, but the analysis does not apply to the case where F(·) is not strongly convex.  Similarly, <cit.>  consider the non-strongly convex setting in SVRG (^++), where F(w) is convex, each individual f_i(w) may be non-convex, but only establish sub-linear convergence. Recently, <cit.> consider SVRG with a zero-norm constraint and prove   linear convergence for this specific formulation. In comparison,  our results hold more generally,  covering not only sparsity model but also corrected Lasso with noisy covariate, group sparsity model, and beyond. 
	
	
	

§ PROBLEM SETUP

	In this paper we consider two setups, namely, (1) convex but not strongly convex F(w)  and (2) non-convex F(w).
	For the convex case, we consider 
	
    min_g(w)≤ρ F(w)   :=f(w)+λ 
    	g(w)
       :=1/n∑_i=1^n f_i (w)+λ g(w),

	where ρ>0 is some pre-defined radius, f_i(w) is the loss function for  sample i, and g(w) is a norm.
	Here we assume each f_i(w) is convex and L_i-smooth.
	
	
	
	For the non-convex F(w) we consider
	
    min_d_λ(w)≤ρF(w):   =f(w)+d_λ,μ(w)
       =1/n∑_i=1^n f_i(w)+d_λ,μ(w) ,

	where ρ>0 is some pre-defined radius, f_i(w) is convex and L_i smooth, d_λ,μ(w) is a non-convex regularizer depending on a tuning parameter λ  and a parameter μ explained in section <ref>. This M-estimator includes a side constraint depending on d_λ (w), which needs to be a convex function and admits a lower bound d_λ(w)≥w_1. It is also closed w.r.t. to d_λ,μ(w),  more details are deferred to section <ref>.
	
	We list some examples that belong to these two setups.
	
		
  * Lasso: F(w)=∑_i=1^n1/2(y_i-w^Tx_i)^2+λw_1.
		
  * Logistic regression with ℓ_1 penalty:
		
    F(w)=∑_i=1^nlog (1+exp (-y_ix_i^Tw))+λw_1.

		
  * Group Lasso F(w)=∑_i=1^n1/2(y_i-w^Tx_i)^2+λw_1,2.
		
  * Corrected Lasso <cit.>:
		F(w)=∑_i=1^n1/2n (⟨ w,x_i ⟩-y_i)^2-1/2w^TΣ w+λw_1, where Σ is some positive definite matrix.
		
  * linear regression with SCAD regularizer <cit.>: F(w)=∑_i=1^n1/2n (⟨ w,x_i ⟩-y_i)^2+SCAD(w).
	  
	
	The first three examples belong to first setup while the last two belong to the second setup.
	
	

 §.§ Restricted Strongly Convexity

	
	Restricted Strongly Convexity (RSC) is proposed in <cit.> and has been explored in several other work <cit.>. We say the loss function f(w) satisfies the RSC condition with curvature κ and the tolerance parameter τ with respect to the norm g(w) if 
	
    Δ f(w_1,w_2)≜ f(w_1)-f(w_2)-⟨∇ f(w_2),w_1-w_2 ⟩
       ≥κ/2w_1-w_2_2^2-τ g^2(w_1-w_2).

	When f(w) is γ strongly convex,  then it is RSC with  κ=γ and τ=0. However in many case,  f(w) may not be strongly convex, especially in the high dimensional case where the ambient dimension p>n. On the other hand, RSC is easier to be satisfied.  Take Lasso as an example, under some mild condition, it is shown that <cit.> 
	Δ f(w_1,w_2)≥ c_1 w_1-w_2_2^2-c_2log p/nw_1-w_2_1^2,
	where c_1, c_2 are some  positive constants. Besides Lasso, the RSC condition holds for a large range of statistical models including log-linear model, group sparsity model, and low-rank model. See <cit.> for more detailed discussions. 
	

 §.§ Assumption on convex regularizer g(w)

	Decomposability is the other ingredient needed to analyze the algorithm.
	
	 A regularizer is decomposable with respect to a pair of subspaces 𝒜⊆ℬ if 
	
    g(α+β)=g(α)+g(β)   for all  α∈𝒜, β∈ℬ^⊥,
 where ⊥ means the orthogonal complement.
	
	
	
	A concrete example is l_1 regularization for sparse vector supported on subset S. We define the subspace pairs with respect to the subset S⊂{1,...,p}, 
	𝒜(S)={w∈ℝ^p| w_j=0  for all  j∉ S } and ℬ(S)=𝒜(S). The decomposability is thus easy to verify. Other widely used examples include non-overlap group norms such as·_1,2, and the nuclear norm | ·|_* <cit.>. In the rest of the paper, we denote w_ℬ as the projection of w on the subspace ℬ.
	
	

  §.§.§ Subspace compatibility constant

	For any subspace 𝒜 of ℝ^p, the subspace compatibility constant with respect to the pair (g,·_2) is give by 
	
    Ψ (𝒜)=sup_u∈𝒜\{0}g(u)/u_2.

	That is, it is the Lipschitz constant of the regularizer restricted in 𝒜. For example, for the above-mentioned sparse vector with cardinality s, Ψ(𝒜)=√(s) for g(u)=u_1.
	
	

 §.§ Assumption on non-convex regularizer d_λ,μ (w)

	We consider  regularizers that are separable across coordinates, i.e., d_λ,μ(w)=∑_j=1^pd̅_λ,μ (w_j).
	Besides the separability, we make further assumptions on the univariate function d̅_λ,μ (t):
	
		
  * d̅_λ,μ(·) satisfies d̅_λ,μ(0)=0 and is symmetric about zero (i.e., d̅_λ,μ(t)=d̅_λ,μ(-t)).
		
  * On the nonnegative real line, d̅_λ,μ (·) is nondecreasing.
		
  * For t>0,  d̅_λ,μ (t)/t is nonincreasing in t.
		
  * d̅_λ,μ(·) is differentiable for all t≠0 and subdifferentiable at t=0, with lim_t→0^+d̅_λ,μ'(t)=λ L_d.
		
  * d̅_λ(t):= (d̅_λ,μ(t)+μ/2t^2)/λ is convex.	
	
	For instance, SCAD satisfying these assumptions.
	
	𝐒𝐂𝐀𝐃_λ,ζ (𝐭)= 
	
    λ |t|,        for  |t|≤λ,
    
    	-(t^2-2ζλ|t|+λ^2)/(2(ζ-1)),      for λ<|t|≤ζλ,
    
    	(ζ+1)λ^2/2,    for |t|>ζλ,

	where ζ>2 is a fixed parameter. It satisfies the assumption with L_d=1 and μ=1/ζ-1 <cit.>.

	
	
	

 §.§ Applying SDCA

	

  §.§.§ Convex F(w)

	Following a similar line as we did for Lasso, to apply the SDCA algorithm, we define
	ϕ_i(w)=n+1/n f_i(w)   for  i=1,...,n , ϕ_n+1(w)=-λ̃ (n+1)/2w_2^2 , g̃(w)= 1/2w_2^2+λ/λ̃g(w).
	
	
	
	
	
	Correspondingly, the new smoothness parameters are L̃_i=n+1/nL_i   for   i=1,...,n and  L̃_n+1=λ̃(n+1). Problem (<ref>) is thus equivalent to the following
	
    min_w∈Ω  1/1+n∑_i=1^n+1ϕ_i(w)+ λ̃g̃(w).

	This enables us to apply Algorithm <ref> to the problem with ϕ_i, g̃, L̃_i, λ̃.  In particular, while ϕ_n+1 is not convex, g̃ is still convex (1-strongly convex). We exploit this property in the proof and define g̃^*(v)=max_w∈Ω⟨ w,v⟩-g̃(w), where Ω is a convex compact set. Since g̃(w) is 1-strongly convex, g̃^*(v) is 1-smooth <cit.>.
	

  §.§.§ Non-convex F(w)

	Similarly, we define 
	
    ϕ_i(w)=n+1/n f_i(w)   for   i=1,...,n, 
       ϕ_n+1(w)=- (λ̃+μ) (n+1)/2w_2^2,
       g̃(w)= 1/2w_2^2+λ/λ̃d_λ(w),

	and then apply Algorithm <ref> on  
	
    min_w∈Ω  1/1+n∑_i=1^n+1ϕ_i(w)+ λ̃g̃(w).

	The update rule of proximal step  for different g(·),d_λ(·) (such as SCAD and MCP) can be found in <cit.>.	

	
	
	

§  THEORETICAL RESULT

	In this section, we present the main theoretical results, and  some corollaries that instantiate the main results in several well known statistical models.
	

 §.§ Convex F(w)

	To begin with, we define several terms related to the  algorithm. 		
	
		
  * w^* is true unknown parameter. g^*(·) is the dual norm of g(·). Conjugate function g̃^*(v)=max_w∈Ω⟨ w,v ⟩-g̃(w), where Ω={ w| g(w)≤ρ}.
		
  * ŵ is the optimal solution to problem <ref>, and we assume ŵ is in the interior of Ω w.l.o.g. by choosing Ω large enough. 
  * (ŵ,v̂) is an optimal solution pair satisfying g̃(ŵ)+g̃^*(v̂)=⟨ŵ,v̂⟩. 
		
  * A_t=∑_j=1^n+11/q_ja_j^t-â_j_2^2, where â_j=-∇ϕ_j(ŵ). B_t=2(g̃^*(v^t)-⟨∇g̃^*(v̂),v^t-v̂⟩-g̃^*(v̂)).
	
	We remark that our definition on the first potential A_t is the same as in <cit.>, while the second one B_t is different. If g̃ (w)=1/2w_2^2, our definition on B_t reduces to that in <cit.>, i.e.,  w^t-ŵ_2^2.  To see this, when g̃ (w)=1/2w_2^2, g̃^*(v)=1/2v_2^2 and v^t=w^t, v̂=ŵ. We then define another potential C_t, which is a combination of A_t and B_t. C_t=η/(n+1)^2 A_t +λ̃/2 B_t. Notice that using smoothness of g̃^*(·) and Lemma <ref> and <ref> in the appendix, it is not hard to show B_t≥ w^t-ŵ_2^2. Thus if C_t converges, so does w^t-ŵ_2^2.
	
	For notational simplicity, we  define the following two terms used in the theorem.
	
		
  * Effective RSC parameter: κ̃=κ-64τΨ^2 (ℬ). 
		
  * Tolerance: δ=c_1τδ_stat^2, where δ_stat^2=(Ψ(ℬ)ŵ-w^* _2+g (w^*_𝒜^⊥))^2, c_1 is a universal positive constant.
	
	
	
	
	
		Assume each f_i(w) is L_i smooth and convex, f(w) satisfies the RSC condition with parameter (κ,τ), w^* is feasible, the regularizer is decomposable w.r.t ( 𝒜, ℬ ) such that κ̃≥ 0,  and the Algorithm <ref> runs with η≤min{1/16 (λ̃+L̅),1/4λ̃ (n+1)}, where L̅=1/n∑_i=1^n L_i, λ̃ is chosen such that  0<λ̃≤κ̃.  If we choose the regularization parameter λ such that λ≥max(2g^*(∇ f(w^*)),  c τρ) where c is some universal positive constant, then we have 
		
    𝔼(C_t)≤ (1-ηλ̃)^t C_0,

		until F(w^t)-F(ŵ)≤δ, where the expectation is for the randomness of sampling of i in the algorithm. 
	
	Some remarks are in order for interpreting the theorem.
	
	
		
  * In several statistical models, the requirement of κ̃> 0 is easy to satisfy under mild conditions. For instance, in Lasso  we have Ψ^2 (ℬ)=s. τ≃log p/n, κ=1/2 if the feature vector x_i is sampled from N(0,I). Thus, if  128 slog p/n≤ 1, we have κ̃≥1/4.  
		
  * In some models, we can choose the pair of subspace (𝒜, ℬ) such that w^*∈𝒜 and thus δ=c_1 τΨ^2(ℬ) ŵ-w^*_2^2. In Lasso, as we mentioned above τ≃log p/n, thus δ≃ c_1s log p/nŵ-w^*_2^2, i.e., this tolerance is dominated by statistical error if s is small and n is large. 
		
  * We know B_t≥w^t-ŵ_2^2 and A_t≥ 0, thus C_t≥λ̃/2w^t-ŵ_2^2 , thus, if C_t converge, so does w^t-ŵ_2^2. 
		When F(w^t)-F(ŵ)≤δ, using Lemma <ref> in the supplementary material, it is easy to get w^t-ŵ_2^2≤4δ/κ̃.  
	
	Combining these remarks, Theorem <ref> states that the optimization error decreases geometrically until it achieves the tolerance δ/κ̃ which is  dominated by the statistical error ŵ-w^*_2^2, thus can be ignored from the statistical view. 
	
	
	
	If g(w) in Problem (<ref>) is indeed 1-strongly convex, we have the following proposition, which extends dual-free SDCA <cit.> into the general regularization case. Notice we now directly apply the Algorithm <ref> on Problem (<ref>) and change the definitions of A_t and B_t correspondingly. In particular, A_t=∑_j=1^n1/q_ja_j^t-â_j_2^2, B_t=2(g^*(v^t)-⟨∇ g^*(v̂),v^t-v̂⟩-g^*(v̂)), where â_j=-∇ f_j(ŵ). C_t is still defined in the same way, i.e., C_t=η/n^2 A_t +λ/2 B_t.
	
	
	
		Suppose each f_i (w) is L_i smooth, f(w) is convex, g(w) is 1- strongly convex,  ŵ is the optimal solution of  Problem (<ref>), and L̅=1/n∑_i=1^nL_i. Then we have:
		(I) If each f_i(x) is convex, we run the Algorithm 
		<ref>  with η≤min{1/4L̅,1/4λ n}, then
		𝔼(C_t)≤ (1-ηλ )^t C_0.  (II) Otherwise, we run the Algorithm <ref> with  η≤min{λ/4L̅^2,1/4λ n}, and 𝔼(C_t)≤ (1-ηλ )^t C_0. Note that B_t≥w^t-ŵ_2^2, A_t≥ 0, thus w^t-ŵ_2^2 decreases geometrically.
	
	In the following we present several corollaries that instantiate Theorem <ref> with several concrete statistical models. This essentially requires to choose appropriate subspace pair (𝒜,ℬ) in these models and check the RSC condition.
	
	

  §.§.§ Sparse linear regression

	Our first example is Lasso, where f_i(w)=1/2(y_i-w^Tx_i)^2 and  g(w)=w_1. We assume each feature vector x_i is generated from  Normal distribution N(0,Σ) and the true parameter w^* ∈ℝ ^p is sparse with cardinality s. The observation y_i is generated by y_i=(w^*)^T x_i+ξ_i, where ξ_i is a Gaussian noise with mean 0 and variance  σ^2. We denote the data matrix by X∈ℝ^n× p and X_j is the jth column of X. Without loss of generality,  we assume X is column normalized, i.e., X_j_2/√(n)≤ 1  for all j=1,2,...,p.  We denote σ_min (Σ) as the smallest eigenvalue of Σ, and ν (Σ)=max_i=1,2,..,pΣ_ii.  
	
		Assume w^* is the true parameter supported on a subset with cardinality at most s, and we choose the parameter λ,λ̃ such that λ≥max(6σ√(log p /n),  c_1  ρν (Σ) log p/n) and 0< λ̃≤κ̃  hold, where  κ̃=1/2σ_min(Σ)-c_2ν (Σ) s log p/n, where c_1,c_2 are some universal positive constants. Then we run the Algorithm <ref> with η≤min{1/16(λ̃ +L̅),1/4λ̃ (n+1)} and have 
		
    𝔼(C_t)≤ (1-ηλ̃)^t C_0

		with probability at least 1-exp(-3log p)-exp (-c_3 n),
		until F(w^t)-F(ŵ)≤δ, where   δ=c_4 ν(Σ) slog p /nŵ-w^*_2^2. c_1,c_2,c_3,c_4 are some universal positive constants.
	
	The  requirement λ≥ 6σ√(log p /n) is documented in literature  <cit.> to ensure that Lasso is statistically consistent. And λ≥ c_1  ρν (Σ) log p/n is needed for fast convergence of optimization algorithms, which is similar to the condition proposed in   in <cit.> for batch optimization algorithm. When slog p/n=o(1), which is necessary for statistical consistency of Lasso, we have 1/2σ_min (Σ)-c_2 ν (Σ) s log p/n≥ 0 , which guarantees the existence of  λ̃.  Also notice under this condition,  δ= c_3ν(Σ)slog p/nŵ-w^*_2^2  is of a lower order of ŵ-w^*_2^2. Using remark 3 in Theorem <ref>, we have  w^t-ŵ_2^2≤4δ/κ̃, which is dominated by the statistical error ŵ-w^*_2^2 and hence  can be ignored from the statistical perspective. Thus to sum up, Corollary <ref> states the optimization error decreases geometrically until it achieves the statistical limit of Lasso.
	
	
	
	
	

  §.§.§ Group Sparsity Model

	<cit.> introduce the group Lasso to allow predefined groups of covariates  to be selected together into or out of a model together. The most commonly used regularizer to encourage group sparsity is ·_1,2. In the following, we define group sparsity formally. We assume groups are disjointed, i.e., 𝒢={G_1,G_2,...,G_N_𝒢} and G_i ∩ G_j=∅. The regularization is w_𝒢,q≜∑_g=1^N_gw_g_q. When q=2, it reduces to the commonly used group Lasso <cit.>, and another popularly used case is q=∞ <cit.>. 	We require the following condition, which  generalizes the column normalization condition in the Lasso case. Given a group G of size m and X_G∈ℝ^n× m , the associated operator norm ||| X_G_i|||_q → 2≜max_w_q=1X_Gw_2 satisfies
	
    ||| X_G_i|||_q→ 2/√(n)≤ 1   for all   i=1,2,...,N_𝒢.
 
	The condition reduces to the column normalized condition when each group contains only one feature (i.e., Lasso).
	
	We now define the subspace pair (𝒜,ℬ) in the group sparsity model. For a subset S_𝒢⊆{1,...,N_𝒢} with cardinality s_𝒢= |S_𝒢|, we define the subspace 
	
    𝒜 (S_𝒢)={w|w_G_i=0   for all    i∉ S_𝒢} ,
and 𝒜=ℬ.
	The orthogonal complement is 
	
    ℬ^⊥(S_𝒢) = {w|w_G_i=0   for all    i∈ S_𝒢}.
 We can easily verify that 
	
    α +β_𝒢,q=α_𝒢,q+β_𝒢,q,

	for any α∈𝒜(S_𝒢) and β∈ℬ^⊥ (S_𝒢).
	
	In the following corollary, we use q=2, i.e., group Lasso, as an example. We assume the observation y_i is generated by y_i=x_i^T w^*+ξ_i, where x_i∼ N(0,Σ), and ξ_i∼ N(0,σ^2).
	
		Assume w∈ℝ^p and each group has m parameters, i.e.,  p=m N_𝒢. Denote by s_𝒢  the cardinality of non-zero group,  and we choose   parameters λ, λ̃ such that  
		
    λ   ≥max(4σ (√(m/n)+√(log N_𝒢/n)), c_1ρσ_2(Σ) (√(m/n)+√(3 log N_𝒢/n) )^2);
       0    < λ̃≤κ̃,     κ̃=σ_1(Σ)-c_2σ_2(Σ)s_𝒢 (√(m/n)+√(3 log N_𝒢/n) )^2;

		where  σ_1 (Σ) and σ_2 (Σ) are   positive constant  depending only on Σ. If we run the Algorithm 1 with η≤min{1/16(λ̃ +L̅),1/4λ̃ (n+1)}, then we have
		
		
    𝔼(C_t)≤ (1-ηλ̃)^t C_0
  with probability at least 1-2exp (-2 log N_𝒢)-c_2 exp(-c_3n) ,
		until F(w^t)-F(ŵ)≤δ, where   δ=c_3σ_2 (Σ)s_𝒢(√(m/n)+√(3 log N_𝒢/n))^2 ŵ-w^*_2^2. 
		
	
	We offer some discussions to interpret the corollary.
	To satisfy the requirement κ̃≥ 0, it suffices to have
	
    s_𝒢(√(m/n)+√(3 log N_𝒢/n))^2=o(1).
 This is a mild condition, as it is needed to guarantee the statistical consistency of group Lasso <cit.>. Notice that the condition is easily   satisfied  when s_𝒢 and m are small. Under this same condition, since 
	δ=c_3σ_2(Σ)s_𝒢(√(m/n)+√(3 log N_𝒢/n))^2 ŵ-w^*_2^2,
	we conclude that δ is dominated by ŵ-w^*_2^2.
	Again, it implies the optimization error decrease geometrically up to the scale o(ŵ-w^*_2^2) which is dominated by the statistical error of the model.
	
		

  §.§.§ Extension to generalized linear model 

		We consider the generalized linear model  of the following form,
		
    min_w∈Ω1/n∑_i=1^n (Φ (w ,x_i)-y_i⟨ w,x_i ⟩)+λw_1,
 which covers such  case  as Lasso (where Φ (θ)=θ^2/2) and logistic regression (where Φ(θ)=log (1+exp (θ))). In this model, we have 
    Δ f(w_1,w_2)=1/n∑_i=1^nΦ” (⟨ w_t,x_i ⟩) ⟨ x_i, w_1-w_2 ⟩^2,
 where w_t=t w_1+(1-t)w_2 for some t∈ [0,1 ].
		The RSC condition   thus is equivalent to:
		
    1/n∑_i=1^nΦ” (⟨ w_t,x_i ⟩)⟨ x_i, w_1-w_2 ⟩ ^2 
    ≥   κ/2w_1-w_2_2^2-τ g^2 (w_1-w_2)   for   w_1,w_2∈Ω.

		Here we require Ω to be a bounded set <cit.>. This requirement is essential since in some generalized linear model Φ”(θ) approaches to zero as θ diverges. For instance, in logistic regression, Φ”(θ)=exp (θ)/(1+exp(θ))^2, which tends to zero as θ→∞ . For a broad class of generalized linear models, RSC holds with τ=clog p/n, thus the same result as that of Lasso holds, modulus change of constants.
	
	
	
	
	

 §.§ Non-convex F(w)

	In the non-convex case, we assume the following RSC condition: 
	
    Δ f(w_1,w_2)≥κ/2w_1-w_2_2^2-τw_1-w_2_1^2

	with τ=θlog p/n for some constant θ. We again define the potential A_t ,B_t and C_t in the same way with convex case. The main difference  is that now we have ϕ_n+1=-(λ̃+μ)(n+1)/2w_2^2  and the effective RSC parameter κ̃ is different. The necessary notations for presenting the theorem are listed below:
	
		
  * w^* is  the unknown true parameter that is s-sparse. Conjugate function g̃^*(v)=max_w∈Ω⟨ w,v ⟩-g̃(w), where Ω={ w| d_λ(w)≤ρ}. Note Ω is convex due to convexity of d_λ(w).
		
  * ŵ is the global optimum of Problem (<ref>), we assume it is in the interior of Ω w.l.o.g.   
		
  * (ŵ,v̂) is an optimal solution pair satisfying g̃(ŵ)+g̃^*(v̂)=⟨ŵ,v̂⟩. 
		
  * A_t=∑_j=1^n+11/q_ja_j^t-â_j_2^2, B_t=2(g̃^*(v^t)-⟨∇g̃^*(v̂),v^t-v̂⟩-g̃^*(v̂)), C_t=η/(n+1)^2 A_t +λ̃/2 B_t, where â_j=-∇ϕ_j(ŵ).
		
  * Effective RSC parameter: κ̃=κ-μ-64τ s, where τ=θlog p/n for some constant θ. Tolerance: δ=c_1τ s ŵ-w^*_2^2, where c_1 is a universal positive constant.
	
	
	
		Suppose w^* is s sparse, ŵ is the global optimum of Problem (<ref>). Assume each f_i(w) is L_i smooth and convex, f(w) satisfies the RSC condition with parameter (κ,τ), where τ=θlog p/n for some constant θ, d_λ,μ (w) satisfies the Assumption in section <ref>,   λ L_d≥max{ cρθlog p /n , 4 ∇ f (w^*)_∞} where c is some universal positive constant, and κ̃-μ≥λ̃> 0, the Algorithm <ref> runs with η≤min{1/16 (λ̃+L̅),1/4λ̃ (n+1)}, where L̅=1/n∑_i=1^n L_i, then we have
		
		
    𝔼(C_t)≤ (1-ηλ̃)^t C_0,

		until F(w^t)-F(ŵ)≤δ, where the expectation is for the randomness of sampling of i in the algorithm.
		
	
	Some remarks are in order to interpret the theorem.
	
		
  * We require λ̃ to satisfy 0<λ̃≤κ-2μ-64θlog p/n s.  Thus if the non-convex parameter μ is too large, we can not find such λ̃.
		
  * Note that δ=c_1sθlog p/nŵ-w^*_2^2 is dominated by ŵ-w^*_2^2 when the model is sparse and n is large. Similar as the convex case, by B_t≥w^t-ŵ_2^2, the theorem says the optimization error deceases linearly up to the fundamental statistical error of the model.
	
	The first non-convex model we consider is  linear regression with SCAD.  Here f_i(w)=1/2 (⟨ w, x_i ⟩-y_i)^2 and d_λ,μ(·) is SCAD(·) with parameter λ and ζ. The  data (x_i,y_i) are generated similarly as in the Lasso case.  
		
		Suppose we have n i.i.d. observations { (x_i,y_i) }, w^* is s sparse , ŵ is global optima and we choose λ and λ̃ such that λ≥max{ c_1ρν (Σ) log p /n , 12σ√(log p/n)}, κ̃ -1/ζ-1≥λ̃>0, then we run the algorithm with η≤min{1/16 (λ̃+L̅),1/4λ̃ (n+1)}, where L̅=1/n∑_i=1^n L_i, then  have	
		
    𝔼(C_t)≤ (1-ηλ̃)^t C_0,

		with 1-exp(-3log p)-exp (-c_2 n),  until F(w^t)-F(ŵ)≤δ, where κ̃=1/2σ_min(Σ)-c_3 ν(Σ) s log p/n-1/ζ-1, δ=c_4ν (Σ)slog p/nŵ-w^*_2^2.  Here c_1, c_2, c_3,c_4 are universal positive constants.
	
	
	If the non-convex parameter 1/ζ-1 is small, s is sparse, n is large, then we can choose a positive λ̃ to guarantee the convergence of algorithm. Under this setting, we have the tolerance δ dominated by ŵ-w^*_2^2.
	
	
	The second example is the corrected Lasso. In many applications, the covariate may be observed subject to corruptions. 	In this section, we consider corrected Lasso proposed by <cit.>. Suppose data are generated according to a   linear model y_i=x_i^Tw^*+ξ_i, where ξ_i is a random zero-mean sub-Gaussian noise with variance σ^2; and   each data point x_i is i.i.d.  sampled from a zero-mean normal distribution, i.e., x_i∼ N(0,Σ). We denote the data matrix by X∈ℝ^n× p , the smallest eigenvalue of Σ by σ_min (Σ), and the largest eigenvalue of Σ by σ_max (Σ) . 
	
	The observation z_i of x_i is corrupted by addictive noise, in particular,   z_i=x_i+ς_i, where ς_i∈ℝ^p is a random vector independent of x_i, say zero-mean with known covariance matrix Σ_ς. Define Γ̂=Z^TZ/n-Σ_ς and γ̂=Z^Ty/n. Our goal is to estimate w^* based on y_i and z_i (but not x_i which is not observable), and the corrected Lasso proposes to solve the following: 
	
    ŵ∈min_w_1≤ρ1/2 w^T Γ̂ w-γ̂ w+ λw_1.

	Equivalently, it solves 
	
    min_w_1≤ρ1/2n∑_i=1^n (y_i-w^Tz_i)^2-1/2w^TΣ_ς w +λw_1 .

	Notice that due to the term -1/2w^TΣ_ς w, the optimization problem is non-convex.
	
		Suppose we are given i.i.d. observation {(z_i,y_i)   } from the linear model with additive noise,  w^* is s sparse, and Σ_ς=γ_ς I. Let ŵ be the global optima.  We choose λ≥max{ c_0ρlog p /n , c_1 φ√(log p/n)} , and positive λ̃ such that κ̃-γ_ς≥λ̃>0, where φ=(√(σ_max (Σ))+√(γ_ς))(σ+√(γ_ς)w^*_2), and  
    κ̃=1/2σ_min(Σ)-c_2 σ_min(Σ)max( (σ_max (Σ)+γ_ς/σ_min(Σ))^2,1 )  slog p/n-γ_ς,
then if we run the algorithm with η≤min{1/16(λ̃ +L̅),1/4λ̃ (n+1)},  we have 
		
    𝔼(C_t)≤ (1-ηλ̃)^t C_0,

		with probability at least  1-c_3 exp(-c_4 nmin( σ^2_min (Σ)/( σ_max(Σ)+γ_ς)^2,1 )    )-c_5exp(-c_6 log p) , until F(w^t)-F(ŵ)≤δ, where δ=c_7 σ_min(Σ)max( (σ_max (Σ)+γ_ς/σ_min(Σ))^2,1 )slog p/nŵ-w^*_2^2, and c_0 to c_7 are some universal positive constants.
	
	Some remarks of the corollary are in order.
	
		
  * The result can be easily extended to more general Σ_ς≼γ_ς I.
		
  * The requirement of λ is similar with its batch counterpart <cit.>.
		
  * Similar to the setting in Lasso, we need slog p/n=o(1).  To ensure the existence of such λ̃, the non-convex parameter γ_ς can not be too large, which is similar to the result in <cit.>.
	
	
	
		

§ EXPERIMENT RESULT

		We report numerical experiment results to validate our theoretical findings, namely, without strong convexity, SDCA still   achieves linear convergence   under our setup.   The setup of  experiment is similar to that in <cit.>.  On both synthetic and real datasets we report results of SDCA and compare with several other algorithms.  These algorithms  are Prox-SVRG <cit.>, SAGA <cit.>, Prox-SAG an proximal version of the algorithm in <cit.>, proximal stochastic gradient (Prox-SGD), regularized dual averaging method (RDA) <cit.> and the proximal full gradient method (Prox-GD) <cit.>. For the algorithms with a constant learning rate (i.e., Prox-SAG, SAGA, Prox-SVRG, SDCA, Prox-GD), we tune the learning rate from an exponential grid  { 2, 2/2^1,...,2/2^12} and chose the one with best performance. Below are some further remarks. 
		
		
			
	    
  * Convergence rates of Prox-SGD and RDA are sub-linear according to the analysis in <cit.>. The stepsize of Prox-SGD is set as η_k=η_0/√(k) as suggested in <cit.> and that of RDA is β_k=β_0 √(k) as suggested in <cit.>. η_0  and β_0 are chosen as the one that attains the best performance among powers of 10.
		
  * <cit.> prove that  Prox-GD converges linearly in the setting of our experiment.
	   
  * The convergence rate of Prox-SVRG and SAGA is linear in our setting, shown recently in <cit.>.
	   
  * To the best of our knowledge, linear convergence of  Prox-SAG in our setting has not been established, although in practice it works well.  
			
	
	

 §.§ Synthetic dataset

	In this section we test algorithms above on Lasso, Group Lasso, Corrected Lasso and  SCAD .
	
	

  §.§.§ Lasso

	We generated the feature vector x_i∈ℝ^p independently from N(0,Σ), where we set Σ_ii=1,   for   i=1,...,p and Σ_ij=b,   for   i≠ j.  The responds y_i is generated by follows: y_i=x_i^T w^*+ξ_i.  w^*∈ℝ^p is a sparse vector with cardinality s,  where the non-zero entries are ± 1 drawn from the Bernoulli distribution with probability 0.5. The noise ξ_i follows the standard normal distribution. We set λ=0.05 in Lasso and choose λ̃=0.25 in SDCA. In the following experiment, we set p=5000, n=2500 and try different settings on s and b.
	
	
	
	Figure <ref> presents simulation results on Lasso. Among all four settings, SDCA, SVRG and SAG converge with linear rates.  When b=0.4 and s=100, SDCA outperforms the other two.  When b=0, the Prox-GD works although with slower rate. While b is nonzero, the Prox-GD does not works well due to the large condition number. RDA and SGD converges slowly in all setting because of the large variance in gradient. 
	
	

  §.§.§ Group Lasso

	
	We report the experiment result on Group Lasso in Figure <ref>. Similarly as Lasso, we generate the observation y_i=x_i^T w^*+ξ_i with the feature vectors independently sampled from N(0,Σ), where Σ_ii=1 and Σ_ij=b, i≠ j. The cardinality of non-zero group is s_𝒢, and the non-zero entries are sampled uniformly from [-1, 1].  In the following experiment, we try different setting on b, group size m and group sparsity s_𝒢.
	
	
	
	
	Similar with the result in Lasso, SDCA, SVRG and SAG performs well in all settings. When m=20 and s_𝒢=20, SDCA outperforms the other two.  The Prox-GD converges with linear rate when m=10, s_G=10, b=0 but does not work well in the other three setting. SGD and RDA converge slowly in all four settings. 
	
	

  §.§.§ Corrected Lasso

	
	We generate data as follows: y_i=x_i^Tw^*+ξ_i, where each data point x_i∈ℝ^p is drawn from normal distribution N(0,I), and the noise ξ_i is   drawn from N(0,1). The coefficient w^* is sparse with cardinality s, where the non-zero coefficient equals to ± 1 generated from the Bernoulli distribution with probability 0.5. We set covariance matrix Σ_ς=γ_ς I. We choose λ=0.05 in the formulation and λ̃=0.1 in SDCA. The result is presented in Figure <ref>.  
	
	
	
	
	In both setting, we see κ̃> λ̃+γ_ς, thus according to our theory, SDCA converges linearly.  In both figures (a) and (b), SDCA, Prox-SVRG, Prox-SAG and Prox-GD converge linearly. SDCA performs better in the second setting.  SGD and RDA converge slowly due to the large variance in gradient.
	
	

  §.§.§ SCAD

	The way to generate data is same with Lasso. Here  x_i∈ℝ^p is drawn from normal distribution N(0,2I) to satisfy the requirement of on κ̃, γ_ς and λ̃.  We set λ=0.05 in the formulation and choose λ̃=0.1  in SDCA.   We present the result in Figure <ref>. We try two different settings on n, p, s, ζ. In both case, SDCA, Prox-SVRG, Prox-SAG, converge linearly with similar performance. Prox-GD also converges linearly but with slower rate. According to our theory,  κ̃≥ 1 and λ̃+μ≤ 0.5 in both cases, thus SDCA can converge linearly and the simulation results verify our theory.
	
	 
	
	

 §.§ Real dataset

	
	
	

  §.§.§ Sparse Classification Problem 

	In this section, we evaluate the performance of the algorithms when solving the logistic regression with ℓ_1 regularization: min_w∑_i=1^nlog (1+exp (-y_ix_i^Tw))+λw_1.
	We conduct experiments on two real-world data sets, namely, rcv1 <cit.> and sido0 <cit.>.  The regularization parameters are set as λ=2· 10^-5 in rcv1 and λ=10^-4 in sido0, as suggested in <cit.>.  For SDCA, we choose λ̃=0.002 and λ̃=0.001 in these two experiments, respectively.
	
	
	
	
	
	
	
	
	
	In Figure <ref> and <ref> we report the performance of different algorithms.  In Figure <ref> , Prox-SVRG performs best, and closely followed by SDCA, SAGA, and then Prox-SAG. We observe that Prox-GD converges much slower, albeit in theory it should converges with a linear rate <cit.>, possibly because its contraction factor is close to one. Prox-SGD and RDA converge slowly due to the variance in the stochastic gradient. The objective gaps of them remain significant even after 1000 passes of the whole dataset. In Figure <ref>, similarly as before, Prox-SVRG, SAGA, SDCA and Prox-SAG (some part of Prox-SAG  overlaps with SDCA)  perform well. On this dataset, SAGA performs best followed by SDCA , Prox-SAG and then Prox-SVRG. The performance of  Prox-GD is even worse   than   Prox-SGD.   RDA converges the slowest.
	
	

  §.§.§ Sparse Regression Problem 

	
	In Figure <ref>, we present the result of Lasso on IJCNN1 dataset (n=49990,p=22)  <cit.> with λ=0.02. It is easy to see, the performance of SDCA is best and then followed by SAGA, Prox-SAG, SVRG and Prox-GD. Prox-SGD and RDA does not work well. 
		We apply the linear regression with SCAD regularization on IJCNN1 dataset <cit.> and present the result in Figure <ref>. In this dataset, SAGA and SDCA have almost identical performance, then followed by Prox-SVRG, Prox-SAG and Prox-GD. Prox-SGD converge fast at beginning, but has a large optimality gap (10^-4). RDA does not work at all.
		  In Figure <ref>,  we consider a group sparse regression problem on the Boston Housing dataset (n=506,p=13)  <cit.>.  As suggested in <cit.>, to take into account the non-linear relationship between variables and response, up to third-degree polynomial expansion is applied on each feature. In particular, terms x, x^2 and x^3 are grouped together. We consider group Lasso model on this problem with λ=0.1. We choose the setting m=2n in SVRG and λ̃=0.1 in SDCA. 	Figure <ref> shows the objective gap of various algorithms versus the number of passes over the dataset. Prox-SVRG, SDCA, SAGA and Prox-SAG have almost same performance. Prox-SGD does not converge: the objective gap oscillates between 0.1 and 1. Both the Prox-GD and RDA converge, but with much slower rates.
	
	
	
	
	
	

§ CONCLUSION AND FUTURE WORK

	
	In this paper, we adapt SDCA into a dual-free form to solve  non-strongly convex problems  and non-convex problems. Under the condition of RSC, we prove that this dual-free SDCA　 converges with linear rates which covers several important statistical models. 
	From a high level, our results re-confirmed a well-observed  phenomenon that statistically easy problems   tend to be more computationally friendly. We believe this  intriguing fact indicates that there are fundamental relationships between statistics and optimization,  and understanding such relationships may shed deep insights.

	

	
	

§ PROOFS

	
	To begin with, we present a technical Lemma that will be used repeatedly in the following proofs.
	
		Suppose function f(x) is convex and L smooth then we have
		
    f(x)-f(y)-⟨∇ f(y),x-y ⟩≥1/2L∇ f(x)-∇ f(y)_2^2.

	
	
		Define p(x)=f(x)-⟨∇ f(x_0),x⟩. It is obvious that p(x_0) is the optimal value of p(x)  due to convexity. 
		Since f(x) is L smooth, so is p(x), and we have
		
    p(x_0)≤ p(x-1/L∇ p(x))≤ p(x)-1/2L∇ p(x)_2^2.

		That is	
		
    f(x_0)-⟨∇ f(x_0),x_0 ⟩≤ f(x)-⟨∇ f(x_0),x ⟩-1/2L∇ f(x)-∇ f(x_0)_2^2.
	
		Rearrange the terms, we have
		
    f(x)-f(x_0)-⟨ f(x_0),x-x_0 ⟩≥1/2L∇ f(x)-∇ f(x_0)_2^2.

	
	The following Lemma presents a well-known fact on conjugate function of a strongly convex function. We extract it from Theorem 1 of <cit.>.
	
		Define p^*(v)=max_w∈Ω⟨ w,v⟩-p(w), where Ω is a convex compact set, p(w) is a 1-strongly convex function, then p^*(v) is 1-smooth and ∇ p^*(v)=w̅ where w̅=max_w∈Ω⟨ w,v⟩-p(w).
	
	

 §.§ Proof of results for Convex F(w)

	In this section we establish the results for convex F(w), namely, Theorem <ref>. 
	Recall the problem we want to optimize is
	
    min_w∈Ω F(w):=f(w)+λ 
    	g(w):=1/n∑_i=1^n f_i (w)+λ g(w),

	where Ω is {w∈ℝ^p  | g(w)≤ρ}.
	Remind that instead of directly minimizing the above objective function, we look at the following form.
	
    min_w∈Ω F(w):=ϕ(w)+λ̃g̃(w)= 1/1+n∑_i=1^n+1ϕ_i(w)+ λ̃g̃(w).
 
	Also remind that L̃_i is the smooth parameter of ϕ_i(w) and we define L̃≜1/n+1∑_i=1^n+1L̃_i.
	
	
	
	Notice the Algorithm 1  keeps the  following relation v^t-1=1/λ̃ (n+1)∑_i=1^n+1a_i^t-1, and thus we have: 
	
    E (η_i  (∇ϕ_i(w^t-1)+a_i^t-1))   =η/n+1∑_i=1^n+1 (∇ϕ_i(w^t-1)+a_i^t-1)
       =η (1/n+1∑_i=1^n+1∇ϕ_i(w^t-1)+λ̃ v^t-1)
        =η (∇ϕ(w^t-1)+λ̃ v^t-1).

	
	
	
	Before we start the proof of the main theorem , we present several technical lemmas.  The following two lemmas are similar to its batched counterpart in <cit.>.
	
		Suppose f(w) is convex and g(w) is decomposable with respect to (𝒜,ℬ), g(w^*)≤ρ, if we choose λ≥ 2g^*(∇ f(w^*)), define the error term Δ^*=ŵ-w^*, then we have the following condition holds 
		
    g(Δ^*_ℬ^⊥)≤ 3 g(Δ^*_ℬ)+4g(w^*_𝒜^⊥),

		which implies g (Δ^*)≤ g(Δ^*_ℬ^⊥)+g(Δ^*_ℬ)≤ 4 g(Δ^*_ℬ)+4g(w^*_𝒜^⊥).
	
	
	
	
	
		Using the optimality of ŵ, we have
		
		
    f(ŵ)+λ g(ŵ)-f(w^*)-λ g(w^*)≤ 0.

		So we get
		
    λ g(w^*)-λ g(ŵ)≥ f(ŵ)-f(w^*)≥⟨∇ f(w^*), ŵ-w^*  ⟩≥ -g^*(∇ f(w ^*)) g (Δ^*),

		where the second inequality holds from the convexity of f(w), and the third one holds by Holder's inequality. Using triangle inequality, we have
		g(Δ^*)≤ g(Δ^*_ℬ)+g(Δ^*_ℬ^⊥), which leads to
		
    λ g(w^*)-λ g(ŵ)≥ -g^*(∇ f(w ^*)) (g(Δ^*_ℬ)+g(Δ^*_ℬ^⊥) ).

		Notice 
    ŵ=w^*+Δ^*= w^*_𝒜+w^*_𝒜^⊥+Δ^*_ℬ+Δ^*_ℬ^⊥.

		Now we obtain
		
    g  (ŵ)-g(w^*)   (a)≥  g (w^*_𝒜+Δ^*_ℬ^⊥)-g(w^*_𝒜^⊥)-g(Δ^*_ℬ)-g(w^*)
       (b)= g (w^*_𝒜)+g (Δ^*_ℬ^⊥)-g(w^*_𝒜^⊥)-g(Δ^*_ℬ)-g(w^*)
       (c)≥ g (w^*_𝒜)+g (Δ^*_ℬ^⊥)-g(w^*_𝒜^⊥)-g(Δ^*_ℬ)-g(w^*_𝒜)-g(w^*_𝒜^⊥)
       ≥ g (Δ^*_ℬ^⊥)-2g(w^*_𝒜^⊥)-g(Δ^*_ℬ),

		where (a) and (c) hold from the triangle inequality, and (b) uses the decomposability of g(·).
		
		
		
		Substitute  the above to  (<ref>), and  and use the assumption that λ≥ 2g^*(∇ f(w^*)), we obtain
		
    -λ/2 (g(Δ^*_ℬ)+g(Δ^*_ℬ^⊥) )+λ (g (Δ^*_ℬ^⊥)-2g(w^*_𝒜^⊥)-g(Δ^*_ℬ))≤ 0,

		which implies 
		
    g(Δ^*_ℬ^⊥)≤ 3  g(Δ^*_ℬ)+4g(w^*_𝒜^⊥).

	
	
	
	
	
	
	
	
	
		Suppose	f(w) is convex and g(w) is decomposable with respect to (𝒜,ℬ). If we choose λ≥ 2g^*(∇ f(w^*)),  and suppose there exist a given tolerance ξ and T such that F(w^t)-F(ŵ)≤ξ for all t> T ,  then for the error term Δ^t=w^t-w^* we have
		
    g(Δ^t_ℬ^⊥)≤ 3 g(Δ^t_ℬ)+4g(w^*_𝒜^⊥)+ 2min{ξ/λ, ρ},

		which implies 
    g(Δ^t)≤ 4 g(Δ^t_ℬ)+4g(w^*_𝒜^⊥)+ 2 min{ξ/λ,ρ}.

	
	
		First notice F(w^t)-F(w^*)≤ξ holds by assumption since F(w^*)≥ F(ŵ).
		So we have
		
    f(w^t)+λ g(w^t)-f(w^*)-λ g(w^*)≤ξ.

		Follow the same steps as those in the proof of Lemma <ref>, we have
		
    g(Δ^t_ℬ^⊥)≤ 3 g(Δ^t_ℬ)+4g(w^*_𝒜^⊥)+ 2ξ/λ.

		Using the fact that w^* and w^t both belong to Ω={w∈ℝ^p  | g(w)≤ρ},    we have  g(Δ^t)≤ g (w^*)+g(w^t)≤ 2ρ. This leads to
		
    g(Δ^t_ℬ^⊥)≤ g(Δ^t_ℬ)+2ρ,

		by triangle inequality g(Δ^t_ℬ^⊥)≤ g(Δ^t_ℬ)+g(Δ^t).
		Combine this with the above result we have
		
    g(Δ^t_ℬ^⊥)≤ 3 g(Δ^t_ℬ)+4g(w^*_𝒜^⊥)+ 2min{ξ/λ,ρ}.

		The second statement follows immediately from g(Δ^t)≤ g(Δ^t_ℬ)+g(Δ^t_ℬ^⊥).	
	
	
	
	
		Under the same assumption of Lemma <ref>, we have
		
    F(w^t)-F(ŵ)≥(κ/2-32τΨ^2(ℬ ))Δ̂^t _2^2- ϵ^2(Δ^*,𝒜,ℬ),

		and 
		
    ϕ(ŵ)-ϕ(w^t)-⟨ŵ-w^t,∇ϕ(w^t)⟩
       ≥[(κ-λ̃/2-32τΨ^2(ℬ ))Δ̂^t _2^2- ϵ^2(Δ^*,𝒜,ℬ)],
	
		where Δ̂^t=w^t-ŵ, ϵ^2(Δ^*,𝒜,ℬ)=2τ (δ_stat+δ)^2, δ=2min{ξ/λ, ρ}, and δ_stat= 8Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥).
	 
	
	
		We begin the proof by establishing a simple fact on Δ̂^t=w^t-ŵ. We adapt the argument in Lemma <ref> (which is on  Δ^t)  to Δ̂^t:
		
    g(Δ̂^t)   ≤ g (Δ^t)+g(Δ^*)
       ≤  4 g(Δ^t_ℬ)+4g(w^*_𝒜^⊥)+ 2min{ξ/λ, ρ}+4 g(Δ^*_ℬ)+4g(w^*_𝒜^⊥)
       ≤ 4 Ψ(ℬ)Δ^t_2+4Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥)+2min{ξ/λ,ρ},

		where the first inequality holds from the triangle inequality, the second inequality uses Lemma <ref> and <ref>, the third holds because of the definition of subspace compatibility. 
		
		
		We know 
    f(w^t)-f(ŵ)-⟨∇ f(ŵ), Δ̂^t  ⟩≥κ/2Δ̂^t _2^2-τ g^2(Δ̂^t)

		which implies F(w^t)-F(ŵ)≥κ/2Δ̂^t _2^2-τ g^2(Δ̂^t), since ŵ is the optimal solution to the problem <ref> and g(w) is convex.
		Notice that
		
    g(Δ̂^t)   ≤ 4 Ψ(ℬ)Δ^t_2+4Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥)+2min{ξ/λ,ρ}
       ≤  4 Ψ(ℬ)Δ̂^t_2+8Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥)+2min{ξ/λ,ρ},

		where the second inequality uses the triangle inequality.
		Using the inequality (a+b)^2≤ 2 a^2+2b^2, we can upper bound g^2 (Δ̂^t).
		
    g^2 (Δ̂^t)≤ 32Ψ^2(ℬ)Δ̂^t_2^2+2[8Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥)+2min{ξ/λ,ρ}]^2.

		We now use above result to rewrite the RSC condition. 
		
		
		Substitute this upper bound in the RSC, we have
		
    F(w^t)-F(ŵ)≥(κ/2-32τΨ^2(ℬ ))Δ̂^t _2^2-2τ[8Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥)+2min{ξ/λ,ρ}]^2.

		Notice by δ=2min{ξ/λ,ρ}, δ_stat= 8Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥),  and	ϵ^2(Δ^*,𝒜,ℬ)=2τ(δ_stat+δ)^2,  we obtain
		
    ϵ^2(Δ^*,𝒜,ℬ)=2τ(8Ψ(ℬ)Δ^*_2+8g(w^*_𝒜^⊥)+2min{ξ/λ,ρ})^2.

		We thus conclude
		
    F(w^t)-F(ŵ)≥(κ/2-32τΨ^2(ℬ ))Δ̂^t _2^2- ϵ^2(Δ^*,𝒜,ℬ).

		Recall ϕ(w)= f(w)-λ̃/2w_2^2, and hence we have
		
    ϕ(ŵ)-ϕ(w^t)-⟨ŵ-w^t,∇ϕ(w^t)⟩
    
    		=    f(ŵ)-f(w^t)-⟨∇ f(w^t), ŵ-w^t⟩-λ̃/2ŵ-w^t_2^2 
    ≥   κ/2Δ̂^t_2^2-τ g^2 (Δ̂^t)-λ̃/2Δ̂^t_2^2,

		where the inequality is due to the RSC condition.
		Now we plug in  the upper bound of g^2(Δ̂^t) in Equation  (<ref>), and arrange the terms to establish Equation (<ref>).	
	
	
	
	
		Recall we define two potentials
		
    A_t   =∑_j=1^n+11/q_ia_j^t-â_j_2^2, 
    
    		B_t    =2(g̃^*(v^t)-⟨∇g̃^*(v̂),v^t-v̂⟩-g̃^*(v̂)).

		Notice using   Theorem 1 in <cit.>,  we know  g̃^* (v) is 1- smooth and w=∇g̃^* (v).
		
		
		We remark that the potential A_t is defined the same as in <cit.> while we define B_t   differently to solve the problem with general regularization g(w). When g̃(w)=1/2w_2^2, B_t reduce to v^t-v̂_2^2=w^t-ŵ_2^2, which is same as  in <cit.>.
		
		
		
		 Step 1. The first step is to lower bound A_t-1-A_t, in particular, to establish that 
		
    𝔼[A_t-1-A_t]=ηλ̃( A_t-1+∑_i=1^n+11/q_i (-u_i-â_i_2^2+(1-β_i)m_i_2^2)  ).

		This step is indeed same as <cit.>, which we present for the completeness. Define u_i=-∇ϕ_i(w^t-1), β_i=η_iλ̃ (n+1) and m_i=-u_i+a_i^t-1 for notational simplicity. Suppose coordinate i is picked up at time t, then we have 
		
    A_t-1-A_t=    -1/q_ia_i^t-â_i_2^2+1/q_ia_i^t-1-â_i_2^2
       =-1/q_i(1-β_i) (a_i^t-1-â_i)+β_i(u_i-â_i) _2^2+1/q_ia_i^t-1-â_i_2^2
       ≥ -1/q_i(  (1-β_i)a_i^t-1-â_i _2^2+β_i u_i-â_i_2^2-β_i (1-β_i) a_i^t-1-u_i_2^2)
               + 1/q_ia_i^t-1-â_i_2^2
        =β_i/q_i(a_i^t-1-â_i_2^2-u_i-â_i_2^2+(1-β_i)m_i_2^2).

		Taking expectation on both sides with respect to the random sampling of i at time step t, we established Equation (<ref>).
		
		Step 2. We now look at the evolution of B_t. In particular, we will prove that
		
    𝔼(B_t-1-B_t)=2⟨ w^t-1-ŵ, η ( ∇ϕ(w^t-1)+λ̃ v^t-1) ⟩- η^2/(n+1)^2∑_i=1^n+11/q_im_i_2^2.

		To this end, notice that
		
    1/2(B_t-1-B_t)
       =g̃^*(v^t-1)-⟨∇g̃^*(v̂),v^t-1-v̂⟩-g̃^*(v̂)- (g̃^*(v^t)-⟨∇g̃^*(v̂),v^t-v̂⟩-g̃^*(v̂))
       =g̃^*(v^t-1)-g̃^*(v^t)-⟨∇g̃^*(v̂),v^t-1-v^t ⟩
       ≥⟨∇g̃^*(v^t-1), v^t-1-v^t⟩-1/2v^t-1-v^t_2^2-⟨∇g̃^*(v̂),v^t-1-v^t ⟩
       = ⟨∇g̃^*(v^t-1)- ∇g̃^*(v̂),v^t-1-v^t ⟩-1/2v^t-1-v^t_2^2
       =⟨ w^t-1-ŵ, v^t-1-v^t ⟩-1/2v^t-1-v^t_2^2,

		where the inequality  holds because 
    g̃^*(v^t)-g̃^*(v^t-1)≤⟨∇g̃^* (v^t-1),v^t-v^t-1⟩+1/2v^t-v^t-1_2^2,
  which results from g̃^*(v) being 1-smooth; and
		the last equality holds from the fact that ∇g̃^* (v^t-1)=w^t-1 using Lemma <ref>.
		
		
		Take  expectation on both sides of Equation (<ref>), we established Equation (<ref>),
		where we use result in Equation (<ref>).
		
		Step 3. We define a new potential  C_t=c_a A_t+c_b B_t, and prove in this step that 
    𝔼(C_t-1-C_t)≥  c_aηλ̃ A_t-1-c_aηλ̃∑_i=1^n+11/q_iu_i-â_i_2^2+c_bηλ̃  B_t-1
                +2c_bη(F(w^t-1)-F(ŵ))
    		+2c_bη ( ϕ(ŵ)-ϕ(w^t-1)-⟨ŵ-w^t-1,∇ϕ(w^t-1) ).

		From the definition of C_t, and using Equation (<ref>) and (<ref>), we have
		
    𝔼(C_t-1-C_t)≥    c_aηλ̃ A_t-1-c_aηλ̃∑_i=1^n+11/q_iu_i-â_i_2^2+2c_bη⟨ w^t-1-ŵ,∇ϕ(w^t-1)+λ̃v^t-1⟩
         +∑_i=1^n+11/q_im_i_2^2 (c_aηλ̃ (1-β_i)-c_b η^2/(n+1)^2).

		We next show that 
		
    ⟨ w^t-1-ŵ,∇ϕ(w^t-1)+λ̃v^t-1⟩ -λ̃/2B_t-1-(F(w^t-1)-F(ŵ))=ϕ(ŵ)-ϕ(w^t-1)-⟨ŵ-w^t-1,∇ϕ(w^t-1)⟩.

		This holds by directly verifying as follows:
		
    ⟨ w^t-1-ŵ,∇ϕ(w^t-1)+λ̃v^t-1⟩ -λ̃/2B_t-1-(F(w^t-1)-F(ŵ))
    
    		=   ⟨ w^t-1-ŵ,∇ϕ(w^t-1)+λ̃v^t-1⟩-λ̃ (g̃^*(v^t-1)-⟨∇g̃^*(v̂),v ^t-1-v̂⟩-g̃^*(v̂))-F(w^t-1)+F(ŵ)
    
    		=   ⟨ w^t-1,λ̃ v^t-1⟩-λ̃g̃^*(v^t-1) -⟨ŵ,λ̃v̂⟩+λ̃g̃^*(v̂)+⟨ŵ,-∇ϕ(w^t-1) ⟩-F(w^t-1)+F(ŵ)
         + ⟨ w^t-1,∇ϕ(w^t-1) ⟩
    
    		=   λ̃g̃(w^t-1)-λ̃g̃(ŵ)-F(w^t-1)+F(ŵ)+⟨ w^t-1-ŵ,∇ϕ(w^t-1)⟩
    
    		=   λ̃g̃(w^t-1)-λ̃g̃(ŵ)-λ̃g̃(w^t-1)-ϕ(w^t-1)+λ̃g̃(ŵ)+ϕ(ŵ)+⟨ w^t-1-ŵ,∇ϕ(w^t-1) ⟩
    
    		=   ϕ(ŵ)-ϕ(w^t-1)-⟨ŵ-w^t-1,∇ϕ(w^t-1)⟩,

		where the second equality uses the fact that ŵ=∇g̃^*(v̂), and the third equality holds using the definition of g̃^*(v).
		Thus, substituting the equation into (<ref>), we get
		
    𝔼(C_t-1-C_t)≥  c_aηλ̃ A_t-1-c_aηλ̃∑_i=1^n+11/q_iu_i-â_i_2^2+c_bηλ̃  B_t-1+2c_bη(F(w^t-1)-F(ŵ))
       +∑_i=1^n+11/q_im_i_2^2 (c_aηλ̃ (1-β_i)-c_b η^2/(n+1)^2)+2c_bη [ ϕ(ŵ)-ϕ(w^t-1)-⟨ŵ-w^t-1,∇ϕ(w^t-1) ].

		We can choose η≤q_i/2λ̃ and c_b/c_a=λ̃ (n+1)^2/2η so that β_i≤ 1/2, and the term ∑_i=1^n+11/q_im_i^2 (c_aηλ̃ (1-β_i)-c_b η^2/(n+1)^2) is non-negative. Since q_i≥1/2(n+1) for every i, we can choose η≤1/4λ̃ (n+1).
		Using these condition, we established (<ref>).
		
		
		Step 4  We now bound ∑_i=1^n+11/q_iu_i-â_i_2^2.  
		Notice that for i=1,...,n, since ϕ_i is convex, we can apply Lemma <ref>, and the fact that ξ+∇ f(ŵ)=0, for ξ∈λ∂  g(ŵ).
		
    ∑_i=1^n1/q_iu_i-â_i_2^2     =∑_i=1^n1/q_i∇ϕ_i(w^t-1)-∇ϕ_i(ŵ) _2^2
       ≤(2maxL̃_i/q_i) ∑_i=1^n(ϕ_i(w^t-1)-ϕ_i(ŵ)-⟨∇ϕ_i(ŵ),w^t-1-ŵ⟩)
       =n+1/n(2maxL̃_i/q_i) ∑_i=1^n(f_i(w^t-1)-f_i(ŵ)-⟨∇ f_i(ŵ),w^t-1-ŵ⟩) 
       ≤n+1/n(2maxL̃_i/q_i) n( f(w^t-1)-f(ŵ)+λ g(w^t-1)-λ g(ŵ) ) 
       ≤(2maxL̃_i/q_i)(n+1) (F(w^t-1)-F(ŵ)).

		As for i=n+1, we have
		
    1/q_n+1∇ϕ_n+1(w^t-1)-∇ϕ_n+1(ŵ)_2^2   ≤λ̃^2 (n+1)^2/q_n+1w^t-1-ŵ_2^2
       =2(n+1)L̃_n+1/q_n+1λ̃/2w^t-1-ŵ_2^2.

		
			Step 5 We now analyze the progress of the potential by induction.		
		We  need to relate λ̃/2w^t-1-ŵ_2^2 to F(w^t-1)-F(ŵ). In high level, we divide the time steps t=1,2,... into several epochs, i.e., ([ T_0,T_1), [T_1,T_2),...). At the end of  each epoch j,  we prove that C_t decreases with linear rate until the optimality gap F(w^t)-F(ŵ) decrease to some tolerance ξ_j. We then prove that (ξ_1,ξ_2,ξ_3,...) is a decreasing sequence and finish the proof.
		
		Assuming that time step t-1 is in the epoch j, we use Equation (<ref>) in Lemma <ref> and the fact that λ̃≤κ̃  to obtain
		
    1/q_n+1∇ϕ_n+1(w^t-1)-∇ϕ_n+1(ŵ)_2^2≤ 2(n+1)L̃_n+1/q_n+1 (F(w^t-1)-F(ŵ)+ϵ_j^2 (Δ^*,𝒜,ℬ)).

		Combining the above two results on ϕ_i(·) together, we have
		
    ∑_i=1^n+11/q_iu_i-â_i_2^2≤    4(n+1) (max_ i∈{1,..,n+1 }L̃_̃ĩ/q_i ) (F(w^t-1)-F(ŵ)+1/2ϵ_j^2 (Δ^*,𝒜,ℬ))
    ≤    8(n+1)^2L̃ (F(w^t-1)-F(ŵ))+4(n+1)^2L̃ϵ_j^2 (Δ^*,𝒜,ℬ),

		where we use the fact  L̃_i/q_i=2(n+1)L̃L̃_i/L̃_i+L̃≤ 2(n+1) L̃.
		
		
		
		
		Replace the corresponding term in equation (<ref>), we have
		
    𝔼(C_t-1-C_t)≥  c_aηλ̃ A_t-1-8c_aηλ̃(n+1)^2L̃  (F(w^t-1)-F(ŵ))-4c_aηλ̃  (n+1)^2L̅ϵ_j^2 (Δ^*,𝒜,ℬ)
           +c_bηλ̃  B_t-1+2c_bη(F(w^t-1)-F(ŵ))+2c_bη ( ϕ(ŵ)-ϕ(w^t-1)-⟨ŵ-w^t-1,∇ϕ(w^t-1) )
       ≥ηλ̃ C_t-1+η(2c_b-8c_aλ̃ (n+1)^2L̃)(F(w^t-1)-F(ŵ)) -4c_aηλ̃(n+1)^2L̃ϵ_j^2 (Δ^*,𝒜,ℬ)
          +(c_bη (κ̃-λ̃) w^t-ŵ_2^2 -2c_bηϵ_j^2 (Δ^*,𝒜,ℬ)),

		where the second inequality is due to Lemma <ref>.
		We choose 2c_b=16c_a λ̃ (n+1)^2L̃, and use the fact that c_b/c_a=λ̃ (n+1)^2/2η, we have η=1/16L̃ and 
		
    𝔼(C_t-1-C_t)≥ηλ̃ C_t-1+ η c_b (F(w^t-1)-F(ŵ))-3c_bηϵ_j^2 (Δ^*,𝒜,ℬ),

		where we use the assumption that κ̃≥λ̃ and the assumption n>4.
		
		Remind that in   epoch j, we have
		
    ϵ_j^2(Δ^*,𝒜,ℬ)   =2τ (δ_stat+δ_j-1)^2, δ_j-1=2min{ξ_j-1/λ,ρ},
        δ_stat   = 8Ψ(ℬ)Δ^*+8g(w^*_𝒜^⊥).

		The epoch is determined by the comparison between F(w^t)-F(ŵ) and 3ϵ_j^2 (Δ^*,𝒜,ℬ)
		
		
		
		
		
		
		In the first epoch, we choose δ_0=2ρ. 
		Thus ϵ_1^2 (Δ^*,𝒜,ℬ)=2τ (δ_stat+2ρ)^2.
		We choose T_1 such that 
		
		
    F(w^T_1-1)-F(ŵ)≥ 3ϵ_1^2 (Δ^*,𝒜,ℬ)   and   F(w^T_1)-F(ŵ)≤ 3ϵ_1^2 (Δ^*,𝒜,ℬ).
 
		
		If no such T_1 exists, that means F(w^t)-F(ŵ)≥ 3ϵ_1^2 (Δ^*,𝒜,ℬ) always holds and we have 𝔼(C_t)≤ (1-ηλ̃) C_t-1 for all t and get the geometric convergence rate. It is a contradiction with F(w^t)-F(ŵ)≥ 3ϵ_1^2 (Δ^*,𝒜,ℬ).
		
		Now we know F(w^T_1)-F(ŵ)≤ 3ϵ_1^2 (Δ^*,𝒜,ℬ),  and hence we choose ξ_1= 6τ (δ_stat+δ_0)^2.
		
		In the second epoch we use the same argument:
		
    ϵ_2^2 (Δ^*,𝒜,ℬ)=2τ_σ (δ_stat+δ_1)^2   where  δ_1=2 min{ξ_1/λ,ρ}.

		We choose T_2 such that 
		
    F(w^T_2-1)-F(ŵ)≥ 3ϵ_2^2 (Δ^*,𝒜,ℬ)   and   F(w^T_2)-F(ŵ)≤ 3ϵ_2^2 (Δ^*,𝒜,ℬ).
 
		Then we choose ξ_2= 6τ (δ_stat+δ_1)^2.
		
		Similarly in epoch j, we choose T_j such that
		
    F(w^T_j-1)-F(ŵ)≥ 3ϵ_j^2 (Δ^*,𝒜,ℬ)   and   F(w^T_j)-F(ŵ)≤ 3ϵ_j^2 (Δ^*,𝒜,ℬ),
 
		and ξ_j= 6τ (δ_stat+δ_j-1)^2.
		
		In this way, we arrive at recursive equalities of the tolerance {ξ_j}_j=1^∞ where 
		
    ξ_j= 6τ_σ (δ_stat+δ_j-1)^2   and  δ_j-1=2 min{ξ_j-1/λ,ρ}.

		We claim that following holds, until δ_j=δ_stat. 
		
    (I)     ξ_k+1≤ξ_k/ (4^2^k-1) 
        (II)       ξ_k+1/λ≤ρ/4^2^k   for    k=1,2,3,...

		
		The proof of Equation (<ref>) is same with Equation (60) in <cit.>, which we present here for  completeness.
		
		We assume δ_0≥δ_stat (otherwise the statement is true trivially), so ξ_1≤ 96 τρ^2. We make the assumption that λ≥ 384τρ, so ξ_1/λ≤ρ/4 and ξ_1≤ξ_0. 
		
		In the second epoch we have 
    ξ_2 (1)≤ 12τ (δ^2_stat+δ^2_1)≤ 24τδ_1^2≤96 τξ_1^2/λ^2(2)≤96τξ_1/4λ(3)≤ξ_1/4,

		where (1) holds from the fact that (a+b)^2≤ 2a^2+2b^2, (2) holds using ξ_1/λ≤ρ/4, (3) uses the assumption on λ. Thus,
		
    ξ_2/λ≤ξ_1/4λ≤ρ/16.

		In i+1th step, with similar argument, and by induction assumption we have
		
    ξ_j+1≤96τξ_j^2/λ^2≤96τξ_j/4^2^jλ≤ξ_j/4^2^k-1

		and 
		
    ξ_j+1/λ≤ξ_j/4^2^j-1λ≤ρ/4^2^j.

		Thus we know ξ_j is a decreasing sequence, and 𝔼 (C_t)≤ (1-ηλ̃) C_t-1 holds until F(w^t)-F(ŵ)≤ 6τ (2δ_stat)^2, where η is set to satisfy η≤min (1/16L̃, 1/4λ̃(n+1)).  
		
		Observe that (n+1)L̃=n+1/n(∑_i=1^nL_i)+λ (n+1)=(n+1) (λ +1/n∑_i=1^n L_i), we establish the theorem.
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

 §.§ Strongly convex F(w)

	
	
		
		If g(w) is 1 strongly convex, we can directly apply the algorithm on Equation (<ref>). In this case,  RSC is not needed and the proof is significantly simpler. As the main road map of the proof is similar, we just mention the difference in the following.
		We define the potential,
		
    A_t    =∑_j=1^n1/q_ia_j^t-â_j_2^2, 
    
    		B_t     =2(g^*(v^t)-⟨∇ g^*(v̂),v^t-v̂⟩-g^*(v̂)).

		Notice in this setup, the potential B_t is defined on g rather than g̃.
		
		
		The evolution of A_t follows from the same analysis of Step 1 in the proof of Theorem <ref> , except that we replace λ̃ by λ and we only have n terms rather than n+1 terms. This gives
		
    𝔼[A_t-1-A_t]=ηλ ( A_t-1+∑_i=1^n1/q_i (-u_i-â_i_2^2+(1-β_i)m_i_2^2)  ).

		Note that g^*(v) is 1-smooth, follow the same analysis of Step 2  in the proof of Theorem <ref>, specifically the derivation in (<ref>), we obtain
		
    1/2(B_t-1-B_t)≥⟨ w^t-1-ŵ, v^t-1-v^t ⟩-1/2v^t-1-v^t_2^2.

		Combining the above two equations, we have
		
    𝔼(C_t-1-C_t)≥    c_aηλ A_t-1-c_aηλ∑_i=1^n1/q_iu_i-â_i_2^2+2c_bη⟨ w^t-1-ŵ,∇ f(w^t-1)+λ v^t-1⟩
       +∑_i=1^n1/q_im_i_2^2 (c_aηλ (1-β_i)-c_b η^2/n^2).

		We can choose η≤q_i/2λ and c_b/c_a=λ n^2/2η so that β≤ 1/2, and the term ∑_i=1^n1/q_im_i_2^2 (c_aηλ (1-β_i)-c_b η^2/n^2) is non-negative. According to the definition of q_i, we know q_i ≥1/2n, thus we can choose  η≤1/4n to ensure that η≤q_i/2λ. 
		
		We can show that 
		
    ⟨ w^t-1-ŵ,∇ f(w^t-1)+λ v^t-1⟩ -λ/2B_t-1-(F(w^t-1)-F(ŵ))
    
    		=   f(ŵ)-f(w^t-1)-⟨ŵ-w^t-1,∇ f(w^t-1)⟩≥ 0

		This follows from the same derivation as in Equation (<ref>) , modulus replacing λ̃, g̃(w) and ϕ_i(w) by λ, g(w) and f_i(w) correspondingly. The last step follows immediately from the convexity of f(w).
		
		The proof now proceed with discussing two cases separately: (1). each f_i(w) is convex. And (2). f_i(w) is not necessarily convex, but the sum f(w) is convex.
		
		Case 1: Since each f_i(w) is convex in this case,
		to bound ∑_i=1^n1/q_iu_i-â_i_2^2 is easier, via the following. 
		
    ∑_i=1^n1/q_iu_i-â_i_2^2     = ∑_i=1^n1/q_i∇ f_i(w^t-1)-∇ f_i(ŵ) _2^2
       ≤ (2 max_i L_i/q_i)∑_i=1^n (f_i(w^t-1)-f(ŵ)-⟨∇ f_i(ŵ),w^t-1-ŵ⟩  )
       ≤ (2 max_i L_i/q_i) n (F (w^t-1)-F(ŵ)),

		where the first inequality follows from Lemma <ref>, and the second one follows from convexity of g(w) and optimality condition of ŵ.
		
		The definition of q_i in the Algorithm 1  implies that for every i,
		
    L_i/q_i=2nL̅L_i/L_i+L≤ 2n L̅.

		Substitute this into the corresponding terms in (<ref>), we have
		
    𝔼(C_t-1-C_t)
    ≥   c_a ηλ A_t-1+ c_b ηλ B_t-1 +2c_bη (F(w^t-1)-F(ŵ))-4c_aηλ  n^2L̅ (F(w^t-1)-F(ŵ)).

		Remind c_b=c_a λ n^2/2η, using the choice η≤1/4 L̅, we have
		
    E(C_t)≤ (1-ηλ) C_t-1,

		where η=min{1/4L̅,1/4λ n}.
		
		Case 2:  Using  strong convexity of F(·), we have 
		
    c_aηλ∑_i^n1/q_iu_i-â_i_2^2=c_aηλ∑_i=1^n1/q_i∇ f_i(w^t-1)-∇ f_i(ŵ)_2^2 
    ≤    c_aηλ∑_i=1^nL_i^2/q_iw^t-1-ŵ_2^2≤ 2c_aη(F(w^t-1)-F(ŵ)) ∑_i=1^nL^2_i/q_i,
 
		where the first inequality uses the smoothness of f_i(·), and the second one holds from the strong convexity of F(·) and optimal condition of ŵ.
		
		Using Equation (<ref>), we have 
		
    ⟨ w^t-1-ŵ,∇ f(w^t-1)+λ v^t-1⟩≥λ/2B_t-1+(F(w^t-1)-F(ŵ)).

		Then replace the corresponding terms in (<ref>) we have
		
    𝔼 (C_t-1-C_t)≥ηλ C_t-1 + 2η(c_b- c_a ∑_i=1^nL_i^2/q_i)(F(w^t-1)-F(ŵ)).

		Since we know L_i/q_i≤ 2nL̅, we have
		
    𝔼 (C_t-1-C_t)≥ηλ C_t-1+2η (c_b-2n^2L̅^2 c_a) (F(w^t-1)-F(ŵ)).

		
		The last term is no-negative if c_b/c_a≥ 2n^2L̅^2. Since we choose c_b/c_a=λ n^2/2η, this condition is satisfied as we choose η≤λ/4L̅^2.
	
	
	
	
	
	
	
	
	

 §.§ Proof on non-convex F(w)

	The proof of the non-convex case follows a similar line as that of the convex case. To avoid redundancy,  we focus on pointing out the difference in the proof. We start with some technical lemmas. The following lemma is adapted from Lemma 6 of <cit.>, which  we present for completeness.
	
		For any vector w∈ R^p, let A denote the index set of its s largest elements in magnitude, under assumption of d_λ,μ in Section <ref> in the main body of paper, we have 
		
    d_λ,μ(w_A)-d_λ,μ (w_A^c)≤λ L_d (w_A_1-w_A^c_1)  .
 
		Moreover, for an arbitrary vector w∈ℝ^p, we have
		
    d_λ,μ (w^*)-d_λ,μ (w)≤λ L_d (ν_A_1-ν_A^c_1),

		where ν=w-w^* and w^* is s sparse.
	
	The next  lemma is non-convex counterparts of Lemma <ref> and Lemma <ref>. 
	
		Suppose d_λ,μ(·) satisfies the assumptions in Section <ref>  in the main body of paper, w^* is feasible,   λ L_d≥8ρθlog p /n,  λ≥4/L_d∇ f (w^*)_∞, and there exists ξ, T such that 
		
    F(w^t)-F(ŵ)≤ξ, ∀ t> T.

		Then for any t> T, we have	
		
    w^t-ŵ_1≤ 4√(s)w^t-ŵ_2+8√(s)w^*-ŵ_2+2min(ξ/λ L_d, ρ).

	
	
		For an arbitrary feasible w, define Δ=w-w^*.
		Suppose we have F(w)-F(ŵ)≤ξ, since we know F(ŵ)≤ F(w^*) so we have F(w)≤ F(w^*)+ξ, which implies 
		
    f(w^*+Δ)+d_λ,μ (w^*+Δ)≤ f(w^*)+d_λ,μ(w^*) +ξ .

		Subtract ⟨∇ f(w^*),Δ⟩ and use the RSC condition (Recall we have τ=θlog p/n in the assumption of Theorem 2) we have
		
    κ/2Δ_2^2-θlog p/nΔ_1^2+d_λ,μ (w^*+Δ)-d_λ,μ(w^*)
    ≤   ξ-⟨∇ f(w^*),Δ⟩
    ≤   ξ+∇ f(w^*)_∞Δ_1,

		where the last inequality holds from Holder's inequality.
		
		
		
		
		Rearranging terms and use the fact that Δ_1≤ 2ρ (by feasibility of w and w^*) and  we assume that λ L_d≥ 8ρθlog p /n , λ≥4/L_d∇ f (w^*)_∞,   we get
		
    ξ+1/2λ L_dΔ_1+d_λ,μ(w^*)-d_λ,μ(w^*+Δ)≥κ/2Δ_2^2≥ 0.

		By Lemma <ref>, we have
		
    d_λ,μ (w^*)-d_λ,μ (w)≤λ L_d (Δ_A_1-Δ_A^c_1) ,

		where A is the set of indices of the top s components of Δ in magnitude, which thus leads to
		
    3λ L_d/2Δ_A_1-λ L_d/2Δ_A^c_1+ξ≥ 0.

		Consequently 
		
    Δ_1≤Δ_A_1+Δ_A^c_1≤ 4Δ_A_1+2ξ/λ L_d≤ 4√(s)Δ_2 +2ξ/λ L_d.

		
		Combining with the fact Δ_1≤ 2ρ , we obtain
		
    Δ_1≤ 4√(s)Δ_2 +2min{ξ/λ L_d, ρ}.

		So we have w^t-w^*_1≤ 4√(s)w^t-w^*_2+2min{ξ/λ L_d, ρ}.
		
		Notice F(w^*)-F(ŵ)≥ 0, so following same steps and set ξ=0 we have ŵ-w^*_1≤ 4√(s)ŵ-w^*_2.
		
		Combining the two together, we get 
		
    w^t-ŵ_1≤w^t-w^*_1+w^*-ŵ_1≤  4√(s)w^t-ŵ_2+8√(s)w^*-ŵ_2+2min (ξ/λ L_d, ρ).
	
	
	Now we provide a counterpart of Lemma <ref> in the non-convex case.
	
		Under the same assumptions as those of Lemma <ref>, we  have
		
    F(w^t)-F(ŵ)≥κ̃/2w^t-ŵ_2^2-ϵ^2 (Δ^*,s );
         ϕ(ŵ)-ϕ(w^t)-⟨∇ϕ(w^t), ŵ-w^t ⟩≥   [κ̃-λ̃/2w^t-ŵ_2^2-ϵ^2 (Δ^*,s )],

		where κ̃=κ-μ-64sτ, Δ^*=ŵ-w^*, and ϵ^2 (Δ^*,s )=2τ (8√(s)ŵ-w^*_2+2min(ξ/λ L_d,ρ))^2.
	
	 Notice that
		
    F(w^t)-F(ŵ)
    
    		=     f(w^t)-f(ŵ)-μ/2w^t_2^2+μ/2ŵ_2^2+ λ d_λ(w^t)-λ d_λ(ŵ)
    ≥   ⟨∇ f(ŵ),w^t-ŵ⟩+κ/2w^t-ŵ_2^2- ⟨μŵ, w^t-ŵ⟩-μ/2w^t-ŵ_2^2
       + λ d_λ(w^t)-λ d_λ(ŵ)-τw^t-ŵ_1^2
    ≥   ⟨∇ f(ŵ),w^t-ŵ⟩+κ/2w^t-ŵ_2^2- ⟨μŵ, w^t-ŵ⟩-μ/2w^t-ŵ_2^2
       + λ⟨∂ d_λ(ŵ),w^t-ŵ⟩-τw^t-ŵ_1^2 
    
    		=    κ-μ/2w^t-ŵ_2^2-τw^t-ŵ_1^2,

		where the first inequality uses RSC condition, the second inequality uses the convexity of d_λ(w), and the last equality holds from the optimality condition of ŵ.
		
		
		
		Using Lemma <ref>, and the inequality (a+b)^2≤ 2a^2+2b^2, we have
		
    w^t-ŵ_1^2≤   (4√(s)w^t-ŵ_2+8√(s)w^*-ŵ_2+2min (ξ/λ L_d, ρ))^2 
    ≤   32 s w^t-ŵ_2^2+2 (8√(s)ŵ-w^*_2+2min(ξ/λ L_d,ρ))^2.

		Substitute this into Equation (<ref>), we obtain
		
    F(w^t)-F(ŵ)≥ (κ-μ/2-32sτ)w^t-ŵ_2^2-2τ (8√(s)ŵ-w^*_2+2min(ξ/λ L_d,ρ))^2.

		
		
		Recall 
		
    ϕ(w)= f(w)-λ̃/2w_2^2
    		-μ/2w_2^2.
	 
		So we have
		
    ϕ(ŵ)-ϕ(w^t)-⟨ŵ-w^t,∇ϕ(w^t)⟩
    
    		=    f(ŵ)-f(w^t)-⟨∇ f(w^t), ŵ-w^t⟩-λ̃+μ/2ŵ-w^t_2^2 
    ≥   κ/2ŵ-w^t_2^2-τŵ-w^t_1^2-λ̃+μ/2ŵ-w^t_2^2.

		Then use the upper bound of w^t-ŵ_1^2 in (<ref>) and rearrange terms we establish the lemma.
	
	
	
	
	We are now ready to prove the main theorem of the non-convex case, i.e., Theorem 2.
		
		Remind in the non-convex case, for i=1,...,n, the definition of ϕ_i(x) is the same as in the convex case.  
		The difference is for ϕ_n+1(w), where ϕ_n+1(w) is defined as follows:
		
    ϕ_n+1(w)=-(n+1) (λ̃+μ)/2w_2^2.

		Recall the definition of g̃(w) is as follows
		
    g̃(w)=1/2w_2^2+λ/λ̃d_λ (w).

		
		
		Following similar steps  as in the proof of Theorem <ref>, we have 
		
    E(C_t-1-C_t)≥  c_aηλ̃ A_t-1-c_aηλ̃∑_i=1^n+11/q_iu_i-â_i_2^2+c_bηλ̃  B_t-1+2c_bη(F(w^t-1)-F(ŵ))
       +∑_i=1^n+11/q_im_i_2^2 (c_aηλ̃ (1-β_i)-c_b η^2/(n+1)^2)+2c_bη [ ϕ(ŵ)-ϕ(w^t-1)-⟨ŵ-w^t-1,∇ϕ(w^t-1) ].

		
		
		Following the same steps as in Equation (<ref>), and replace λ̃ by λ̃+μ we have
		
    1/q_n+1∇ϕ_n+1(w^t-1)-∇ϕ_n+1(ŵ)_2^2
    		   ≤ 2(n+1)L̃_n+1/q_n+1λ̃+μ/2w^t-1-ŵ_2^2.

		Similar as the convex case we then divide the time step t=1,2,... into several epochs, i.e., ([ T_0,T_1), [T_1,T_2),...). At the end of  each epoch j,  we prove that C_t decreases with a linear rate until the optimality gap F(w^t)-F(ŵ) decrease to some tolerance ξ_j.
		
		
		We then apply Lemma <ref> and using the assumption that κ̃≥λ̃+μ to relate w^t-1-ŵ_2^2 to F(w^t)-F(ŵ):
		
    1/q_n+1∇ϕ_n+1(w^t-1)-∇ϕ_n+1(ŵ)_2^2≤ 2(n+1)L̃_n+1/q_n+1 (F(w^t-1)-F(ŵ)+ϵ_j^2 (Δ^*,s)).

		Thus
		
    ∑_i=1^n+11/q_iu_i-â_i_2^2≤  8(n+1)^2L̃ (F(w^t-1)-F(ŵ))+4(n+1)^2L̃ϵ_j^2 (Δ^*,s).

		We choose 2c_b=16c_a λ̃ (n+1)^2L̃, and use the fact that c_b/c_a=λ̃ (n+1)^2/2η, we have η=1/16L̃. Combine all pieces together we get
		
    𝔼(C_t-1-C_t)≥  c_aηλ̃ A_t-1-8c_aηλ̃(n+1)^2L̃  (F(w^t-1)-F(ŵ))-4c_aηλ̃  (n+1)^2L̅ϵ_j^2 (Δ^*,s)
           +c_bηλ̃  B_t-1+2c_bη(F(w^t-1)-F(ŵ))+2c_bη ( ϕ(ŵ)-ϕ(w^t-1)-⟨ŵ-w^t-1,∇ϕ(w^t-1) )
       ≥ηλ̃ C_t-1+η(2c_b-8c_aλ̃ (n+1)^2L̃)(F(w^t-1)-F(ŵ)) -4c_aηλ̃(n+1)^2L̃ϵ_j^2 (Δ^*,s)
         +(c_bη (κ̃-λ̃) w^t-ŵ_2^2 -2c_bηϵ_j^2 (Δ^*,s))
       ≥ηλ̃ C_t-1+ η c_b (F(w^t-1)-F(ŵ))-3c_bηϵ_j^2 (Δ^*,s),

		where the second inequality uses Lemma <ref> and the assume κ̃≥λ̃.
		
		The rest of the proofs are almost identical to the convex one. In the first epoch, we have
		
    ϵ_1^2 (Δ^*,s)=2τ (δ_stat+2ρ)^2 ,  ξ_1= 6τ (δ_stat+2ρ)^2

		Then we choose T_1 such that 
		
    F(w^T_1-1)-F(ŵ)≥ 3ϵ_1^2 (Δ^*,s)   and   F(w^T_1)-F(ŵ)≤ 3ϵ_1^2 (Δ^*,s).
 
		In the second epoch we can use the same argument.
		
    ϵ_2^2 (Δ^*,s)=2τ_σ (δ_stat+δ_1)^2   where  δ_1=2ξ_1/λ L_d.

		Repeat this strategy on every epoch. The only difference from the proof of the convex case is that we now replace λ by λ L_d. 
		
		We use the same argument to prove ξ_k is a decreasing sequence and conclude the proof.
	
	
	
	
	
	

 §.§ Proof of Corollaries

	We now prove the corollaries that instantiate our main theorems to different statistical estimators.
	
		To begin with, we present the following  lemma of the RSC  proved in <cit.> and then use it in the case of Lasso.
		
			If each data point x_i is i.i.d randomly sampled from the distribution N(0,Σ), then there exist universal constants c_0 and c_1 such that
			
    XΔ_2^2/n≥1/2Σ^1/2Δ_2^2-c_1ν(Σ)log p/nΔ_1^2,     Δ∈ℝ^p,

			with probability at least 1-exp(-c_0n). Here X is the data matrix where each row is data point x_i.
		
		Since  w^* is supported on a subset S with cardinality s,  we choose 
    ℬ(S)={ w∈ℝ^p | w_j=0  for all   j∉ S   }.
 It is straightforward to choose 𝒜(S)=ℬ(S) and notice that w^*∈𝒜(S).
		
		In Lasso, f(w)=1/2ny-Xw_2^2,  and it is easy to verify that
		
    f(w+Δ)-f(w)-⟨∇ f(w),Δ⟩≥1/2nXΔ_2^2≥1/4Σ^1/2Δ_2^2-c_1/2ν(Σ)log p/nΔ_1^2.

		Notice that g(·) is ·_1 in Lasso, thus Ψ(ℬ)=sup_w∈ℬ\{0}w_1/w_2=√(s). So we have 
		
    κ̃=1/2σ_min (Σ)-64c_1 ν(Σ) slog p/n .

		On the other hand, the tolerance is 
		
    δ   =24τ(8Ψ(ℬ)ŵ-w^*_2+8g(w^*_𝒜^⊥))^2
       =c_2ν (Σ)slog p/nŵ-w^*_2^2,

		where we use the fact that w^*∈𝒜(S) which implies  g(w^*_𝒜^⊥)=0. 
		
		The last piece to check is that λ≥ 2g^*(∇ f(w^*)). In Lasso we have g^*(·)=·_∞. Using the fact that y_i=x_i^Tw^*+ξ_i, this is equivalent to require λ≥2/nX^Tξ_∞. Thus, by our choice of λ that λ≥ 6σ√(log p/n), the condition is satisfied invoking the following inequality which holds by applying the tail bound on the Gaussian variable and the union bound to get
		
    ℙ(2/nX^Tξ_∞≤ 6σ√(log p/n)) ≥ 1-exp(-3log p).

	
	
	
		We use the following fact on the RSC condition of the Group Lasso <cit.><cit.>. As each data point x_i is i.i.d random sampled from the distribution N(0,Σ), then  there exists strictly positive constant  (σ_1,σ_2) which just depends on Σ such that 
		
    XΔ_2^2/2n≥σ_1(Σ) Δ_2^2-σ_2(Σ) (√(m/n)+√(3 log N_𝒢/n) )^2 Δ^2_𝒢,2,     Δ∈ℝ^p

		with probability at least 1-c_3exp (-c_4n).
		
		Recall we define the subspace 
		
    𝒜 (S_𝒢)={w|w_G_i=0   for all    i∉ S_𝒢} ,
and 𝒜(𝒮_𝒢)=ℬ (𝒮_𝒢), where S_𝒢 corresponds to non-zero group of w^*. The subspace compatibility can be computed by  
    Ψ(ℬ)=sup_w∈ℬ\{0}w_𝒢,2/w_2=√(s_𝒢).

		The effective RSC parameter is given by		
		
    κ̃=σ_1(Σ)-64σ_2(Σ)s_𝒢(√(m/n)+√(3 log N_𝒢/n))^2  .

		We then check the requirement on λ holds.  Since  Group lasso is ℓ_1,2 grouped norm, its dual norm of it is (∞,2) grouped norm.
		So we need 
    λ≥ 2 max_i=1,...,N_𝒢1/n(X^Tξ)_G_i_2.

		Using Lemma 5 in <cit.>, we know 
		
    max_i=1,...,N_𝒢1/n(X^Tξ)_G_i_2≤ 2σ(√(m/n)+√(log N_𝒢/n))

		with probability at least 1-2exp (-2log N_𝒢). 	Thus it suffices to choose λ≥ 4σ (√(m/n)+√(log N_𝒢/n)), as suggested in the corollary.
		
		Finally, the tolerance can be computed as
		
    δ=c_3 s_𝒢σ_2(Σ)(√(m/n)+√(3 log N_𝒢/n))^2 ŵ-w^*_2^2.

	
	
	
	
		The proof is similar to that of Lasso. Recall in the proof of the Lasso example we have 
		
    ∇ f(w^*)_∞=1/nX^Tξ_∞≤ 3 σ√(log p/n),
 
		and the RSC condition is 
		
    XΔ_2^2/n≥1/2Σ^1/2Δ_2^2-c_1ν(Σ)log p/nΔ_1^2.

		Recall μ=1/ζ-1 and L_d=1, we establish the result. 
	
	
	
	
		Notice
		
    ∇ f(w^*)_∞=Γ̂w^*-γ̂_∞=γ̂-Σ w^* +(Σ-Γ̂)w^*_∞≤γ̂-Σ w^*_∞+(Σ-Γ̂)w^*_∞.

		As shown in Lemma 2 of <cit.>, both terms are bounded by
		c_1 φ√(log p/n) with probability at least 1-c_1exp(-c_2log p )., where φ=(√(σ_max (Σ))+√(γ_ς)) (σ+√(γ_ς)w^*_2).
		
		
		To obtain the RSC condition,  we apply Lemma 1 in <cit.>, to get
		
    1/nΔ^TΓ̂Δ≥σ_min (Σ)/2Δ_2^2-c_3 σ_min(Σ)max( (σ_max (Σ)+γ_ς/σ_min(Σ))^2,1 ) log p/nΔ_1^2,

		with probability at least 1-c_4 exp(-c_5 nmin( σ^2_min (Σ)/( σ_max(Σ)+γ_ς)^2,1 )    ).
		
		Combine these pieces together, we establish the result.
	
	
	
	
	
	
	
	plainnat
