## 1 Introduction  
In this paper, we consider the following structured convex optimization problem  
\[F_{*}:=\min_{x\in\mathbb{R}^{n}}\ \left\{F(x):=f(x)+h(x)\right\}, \tag{1}\]  
where \(f:\ \text{dom}\ h\to\mathbb{R}\) and \(h:\ \mathbb{R}^{n}\to(-\infty,\infty]\) are closed proper convex functions, but not necessarily differentiable, and \(\text{dom}\ h:=\{x:\ h(x)<\infty\}\) is the effective domain of \(h\). Problems of this type frequently arise in practice, such as compressed sensing [1], image reconstruction [2], machine learning [3], optimal control [4] and power system [5; 6; 7; 8], and so forth. The following are three interesting examples. **Example 1**. : _(\(\ell_{1}\) minimization in compressed sensing). The signal recovery problems in compressed sensing [1] usually take the following form_  
\[\min_{x\in\mathbb{R}^{n}}\ \frac{1}{2}\|Ax-b\|^{2}+\lambda\|x\|_{1}, \tag{2}\]  
_where \(A\in\mathbb{R}^{m\times n}\), \(b\in\mathbb{R}^{m}\), \(\lambda>0\) and \(\|x\|_{1}:=\sum_{i=1}^{n}|x_{i}|\), which aims to get a sparse solution \(x\) of the linear system \(Ax=b\). Note that by defining \(f(x)=\frac{1}{2}\|Ax-b\|^{2}\) and \(h(x)=\lambda\|x\|_{1}\), (2) is of the form of (1)._  
**Example 2**. : _(Regularized risk minimization). At the core of many machine learning problems is to minimize a regularized risk function [9; 10]:_  
\[\min\limits_{x\in\mathbb{R}^{n}}\ R_{\mathrm{emp}}(x)+\lambda\Omega(x), \tag{3}\]  
_where \(R_{\mathrm{emp}}(x):=\frac{1}{m}\sum\limits_{i=1}^{m}l(u_{i},v_{i},x)\) is the empirical risk, \(\{(u_{i},v_{i}),\ i=1,\cdots,m\}\) is a training set, and \(l\) is a convex loss function measuring the gap between \(v\) and the predicted values generated by using \(x\). In general, \(R_{\mathrm{emp}}(x)\) is a nondifferentiable and computationally expensive convex function, whereas the regularization term \(\Omega(x)\) is a simple convex function, say \(\Omega(x)=\frac{1}{2}\|x\|_{2}^{2}\) or \(\Omega(x)=\|x\|_{1}\). By defining \(f(x)=R_{\mathrm{emp}}(x)\) and \(h(x)=\lambda\Omega(x)\), (3) is also of the form of (1)._  
**Example 3**. : (_Unconstrained transformation of a constrained problem). Given a constrained problem_  
\[\min\ \{f(x):\ x\in X\}, \tag{4}\]  
_where \(f\) is a convex function and \(X\subseteq\mathbb{R}^{n}\) is a convex set. By introducing the indicator function \(\delta_{X}\) of \(X\), that is, \(\delta_{X}(x)\) equals \(0\) on \(X\) and infinity elsewhere, problem (4) can be written equivalently as_  
\[\min\limits_{x\in\mathbb{R}^{n}}\ f(x)+\delta_{X}(x). \tag{5}\]  
_Clearly, by setting \(h(x)=\delta_{X}(x)\), (5) becomes the form of (1). We note that such transformation could be very efficient in practice if the set \(X\) has some special structure [11; 12]._  
The design of methods for solving problems of the form (1) has attracted the attention of many researchers. We mention here four classes of these methods--operator splitting methods [13; 14; 15], alternating direction methods of multipliers [5; 16; 17; 18; 19], alternating linearization methods [20; 21], and alternating linearization bundle method [22]. They all fall within the well-known class of first-order black-box methods, that is, it is assumed that there is an _oracle_ that can return the (approximate) function value and one arbitrary (approximate) subgradient at any given point. Regarding the above methods, we are concerned about the following three points:  
* Smoothness of one or both functions in the objective has been assumed for many of the methods. * Except for Reference [22], they all require the exact computation of the function values and (sub)gradients. * The alternating linearization methods [20; 21] essentially assume that both functions \(f\) and \(h\) are \"simple\" in the sense that minimizing the function plus a separable convex quadratic function is easy.