Sparse Optimization for Green Edge AI Inference

The study of inducing sparsity generally falls into the sparse optimization category [27, 28]. In particular, sparse optimization, emerging as a powerful tool, has recently contributed to the effective design of wireless networks, e.g., group sparse beamforming for energy-efficient cloud radio access networks [29, 30], and sparse signal processing for Internet-of-Things (IoT) networks [31, 32]. In particular, to induce the group sparsity structure of the beamforming vector, the work of [22, 23] adopted the mixed $\ell_{1,2}$-norm. As illustrated in [27], the mixed $\ell_{1,q}$-norms ($q>1$) can induce the group sparsity structure of the interested solution. Moreover, the mixed $\ell_{1,2}$-norm and $\ell_{1,\infty}$-norm [33] are commonly adopted. However, the effectiveness of sparsity based on convex sparsity-inducing norms is not satisfactory since there always exists some small nonzero elements in the obtained solutions [34]. In contrast to these works, some works applied nonconvex sparsity-inducing functions to seek sparser solutions [35]. Notably, the work [34] reported the capability of log-sum function for enhancing the sparsity of the solutions.

Motivated by their superior performance on inducing sparsity, we adopt log-sum functions to promote the sparsity pattern in the solutions. However, adopting the log-sum function to enhance sparsity usually makes the problem difficult to compute and analyze. In [34], the authors first proposed an iteratively reweighted $\ell_{1}$ algorithm (IRL1) for tackling the nonconvex and nonsmooth log-sum functions with linear constraints. Nonetheless, they did not further conduct the convergence analysis for the proposed method. Under reasonable assumptions, the work of [36] established the convergence results for a class of unconstrained nonconvex nonsmooth problems based on the limiting-subgradient tool. In particular, these results could apply to the log-sum model in an unconstrained setting. In [37], they proposed a proximal iteratively reweighted algorithm and proved that any accumulation point is a critical point. The work of [38] further showed that, for any starting feasible points, the sequence generated by their proximal iteratively reweighted algorithm could converge to a critical point under the Kurdyka-Łojasiewicz (KL) property [39]. However, these works focused on the unconstrained formulation or linearly constrained cases when the log-sum model is involved. The theoretical analysis for the log-sum function with general convex-set constraints has not been investigated.

The remainder of this paper is organized as follows. Section II presents the system model of the edge AI inference, followed by the problem formulation and analysis. Section II-C provides the group sparse beamforming formulation. The log-sum function based three-stage GSBF approach is proposed in  Section III. Section IV provides the global convergence and convergence rate analysis of the proposed proximal iteratively reweighted algorithm. Section V demonstrates the performance of the proposed approach. The conclusion remark is made in Section VI. To keep the main text coherent and free of technical details, we divert most of the mathematic proofs to the Appendices.

Throughout this paper, we subsume the notation used as follows. We use $\mathbb{C}^{n}$ and $\mathbb{R}^{n}$ to denote the complex vector space and the real Euclidean $n$-space $\mathbb{R}^{n}$, respectively. Boldface lower-case letters and upper case letters to represent vectors (e.g., $\bm{x}$) and matrices (e.g., $\bm{I}$) with an appropriate size, respectively. The inner product between $\bm{x},\bm{y}\in\mathbb{C}^{n}$ is denoted as $\langle\bm{x},\bm{y}\rangle$. $\|\cdot\|_{1}$ and $\|\cdot\|_{2}$ is the conventionally defined $\ell_{1}$-norm and $\ell_{2}$-norm for any vectors in $\mathbb{C}^{n}$, respectively. In addition, we use $(\cdot)^{\sf{H}}$ and $(\cdot)^{\sf{T}}$ to denote the Hermitian and transpose operators, respectively. $\mathfrak{R}(\cdotp)$ is the real part of a complex scalar. $\bm{1}$ is a vector with all components equal to 1 and $\bm{0}$ denotes the zero vector with an appropriate size. In particular, $\|\bm{v}\|_{\mathcal{G}_{2}}=\left[\|\bm{v}_{1}\|_{2},\cdots,\|\bm{v}_{n}\|_{2}\right]^{\sf{T}}\in\mathbb{R}^{n}$ represents a vector whose $n$th element is the $\ell_{2}$-norm of a structured vector $\bm{v}_{n}\in\mathbb{C}^{n}$. We use $\circ$ to denote composition operation between two functions and symbol $\odot$ defines the elementwise product for any two vectors $\bm{x},\bm{y}\in\mathbb{C}^{n}$.

For any closed convex set $\mathcal{C}\subset\mathbb{C}^{n}$, we use $\delta_{\mathcal{C}}(\bm{c})$ to denote the characteristic function associated with $\mathcal{C}$, which is defined as

Similarly, $\mathbb{I}(\cdot)$ defines a indicator function associated with the given condition $\cdot$, i.e., if condition $\cdot$ is met, then return the value $1$; otherwise, return the value $0$. Moreover, $z\sim\mathcal{CN}(\mu,\sigma^{2})$ corresponds to the complex random variable $z$ with mean $\mu$ and variance $\sigma^{2}$.

We consider an edge computing system consisting of $N$ $L$-antenna BSs collaboratively serving $K$ single-antenna mobile users (MUs), as illustrated in Fig. 1. These deployed BSs are used as dedicated edge nodes and have access to the enormous computation and storage resources [8]. For convenience, define $\mathcal{K}=\{1,\dots,K\}$ and $\mathcal{N}=\{1,\dots,N\}$ as the index sets of MUs and BSs, respectively. MUs have inference computing tasks, and the results can be inferred from task-related DNNs. For ease of expression, we use $\bm{d}_{k}$ to denote the raw input data collected from MU $k$, and the corresponding inference results are represented as $\phi_{k}(\bm{d}_{k})$. As performing intelligent tasks on DNNs are typically resource-demanding, it is usually impractical to perform the tasks on resource-constrained mobile devices locally. In the proposed edge AI inference system, by exploiting the computation replication [25], we consider the scenario that each neighboring edge BS has collected the raw input data $\{\bm{d}_{k}\}$ from all MUs. Then the edge BSs process the data $\{\bm{d}_{k}\}$ for model inference. After the edge BSs complete the model inference, the inference results $\{\phi_{k}(\bm{d}_{k})\}$ are returned to the corresponding MUs via the downlink channels. We assume that all edge BSs have been equipped with the pre-trained deep network models for all inference tasks [23].

In the downlink transmission, the edge BSs, which perform the inference tasks for the same MU cooperatively, return the inference results to the MU. We assume perfect channel state information (CSI) is available to all edge BSs to enable cooperative transmission for the inference results [24]. Let $\mathcal{A}_{n}\subseteq\mathcal{K}$ denote the indexes of MUs whose tasks are selectively performed by BS $n$, and $\mathcal{A}=(\mathcal{A}_{1},\cdots,\mathcal{A}_{N})$ represents task selection strategy.

Note that there is a fundamental trade-off between transmission and computation power consumption. To be specific, more edge BSs performing the same task for MUs can significantly reduce the transmission power by exploiting higher transmit beamforming gains. However, this inevitably increases the computation power consumption for performing inference tasks. Therefore, the goal of an energy-efficient edge inference system can be achieved by minimizing the overall network power consumption to reach a balance between these two parts of power consumption.

Let $\{\gamma_{k}\}$ be the target SINR for MUs to receive the reliable AI inference results in the downlink successfully. In our proposed energy-efficient edge AI inference system, the overall power minimization problem is thus formulated as

where $P_{n}^{\sf{max}}>0$ denotes the maximum transmit power of edge BS $n$.

Unfortunately, problem (7) turns out to be a mixed combinatorial optimization problem due to the presence of combinatorial variable $\mathcal{A}$, which makes it computationally intractable [45]. On the other hand, the nonconvex SINR constraints also pose troublesome challenges for solving (7). To address these issues, we recast problem (7) into a tractable formulation by inducing the group sparsity of the beamforming vector in the following section.

One naive approach to cope with the combinatorial variable $\mathcal{A}$ is the exhaustive search. However, it is often computationally prohibitive owing to the exponential complexity. As a practical alternative, there is a critical observation that such a combinatorial variable $\mathcal{A}$ can be eliminated by exploiting the inherent connection between task selection and the group sparsity structure of beamforming vectors. Specifically, if edge BS $n$ does not perform the inference tasks from MU $k$ (i.e., $k\notin\mathcal{A}_{n}$), then it will not deliver the inference result $\phi_{k}(\bm{d}_{k})$ in the downlink transmission (i.e., $\bm{v}_{nk}=\bm{0}$). In other words, if $k\notin\mathcal{A}_{n}$, all coefficients in the beamforming vector $\bm{v}_{nk}$ are zero simultaneously. Mathematically, we have $\mathcal{A}_{n}=\{k\mid\bm{v}_{nk}\neq\bm{0},~{}k\in\mathcal{K}\}$, for all $n\in\mathcal{N}$, meaning the task selection strategy $\mathcal{A}$ can be uniquely determined by the group sparsity structure of $\bm{v}_{nk}$. In this respect, the overall network power consumption problem (7) can rewritten as

By considering the sparsity structure in the beamforming vectors, the SINR expression (3) is transformed into

where $\bm{h}_{k}=\left[\bm{h}_{1k}^{\sf{H}},\dots,\bm{h}_{Nk}^{\sf{H}}\right]^{\sf{H}}$ and $\bm{v}_{k}\!=\!\left[\bm{v}_{1k}^{\sf{T}},\dots,\bm{v}_{Nk}^{\sf{T}}\right]^{\sf{T}}$ are the aggregated channel vector and downlink transmit beamforming vector for MU $k$, respectively.

On the other hand, since an arbitrary phase rotation of the transmit beamforming vectors $\{\bm{v}_{nk}\}$ does not affect the downlink SINR constraints and the objective function value, we can always find proper phases to equivalently transform the SINR constraints in (7) into convex second-order cone constraints [46]. We thus have the following convex-constrained sparse optimization framework for network power minimization

However, problem (10) is still nonconvex due to the indicator function in the objective function. As presented in [29, Proposition 1], a weighted mixed $\ell_{1,2}$-norm can be served as the tightest convex surrogate of the objective in (10), i.e.,

In this paper, we instead propose to adopt a new group sparsity inducing function for inference tasks selection via enhancing sparsity, thereby further reducing the network power consumption.

Let $\bm{v}=\!\left[\bm{v}_{11}^{\sf{T}},\cdots,\bm{v}_{1K}^{\sf{T}},\cdots,\bm{v}_{N1}^{\sf{\sf{T}}},\cdots,\bm{v}_{NK}^{\sf{T}}\right]^{\sf{T}}\!\in\!\mathbb{C}^{LNK}$ denote the aggregated beamforming vector $\bm{v}$. To promote the group sparsity for the beamforming vector $\bm{v}_{nk}$, in this paper, we propose to use the following weighted nonconvex log-sum function as an approximation for the objective $P_{\textrm{sparse}}(\bm{v})$

where $\rho_{nk}=\sqrt{P^{\sf{c}}_{nk}/\eta_{n}}>0$ is a weight coefficient and $p>0$ is a tunable parameter. The main motivation for adopting such a log-sum penalty among various types of sparsity-inducing functions [27] is based on the following considerations:

• •

  The mixed $\ell_{1,2}$-norm is similar as an $\ell_{1}$-norm of vector $\bm{v}$ and thereof offers the tightest convex relaxation to the $\ell_{0}$-norm. In contrast to the mixed $\ell_{1,2}$-norm, it has been reported that the log-sum function can significantly enhance the sparsity of the solution than the conventional $\ell_{1}$-norm [27, 34].

• •

  From the perspective of performance and theoretical analysis of the designed algorithm, a log-sum function brings more practicability due to its coercivity and boundedness of its first derivative.

We present the proposed log-sum based three-stage GSBF framework. Specifically, the first stage is to solve the log-sum convex-constrained problem via the proposed proximal iteratively reweighted algorithm to obtain a solution $\bm{v}_{\textrm{sparse}}$; the second stage prioritizes the tasks in progress based on the obtained solution $\bm{v}_{\textrm{sparse}}$ and system parameters, followed by obtaining the optimal task selection strategy $\mathcal{A}^{*}$; with fixed $\mathcal{A}^{*}$, we refine the $\bm{v}$ in the third stage. Details are depicted as follows.

Stage 1: Log-sum Function Minimization. In this first stage, we obtain the group sparsity structure of beamformer $\bm{v}$ by solving the following nonconvex program

where $\mathcal{C}$ denotes the convex-constraints in (10).

However, the nonconvex and nonsmooth objective in (13) and the presence of the convex constraints usually pose challenges in computation and analysis. Inspired by the work of [34], we can iteratively minimize the objective by solving a sequence of tractable convex subproblems. The main idea of our presented algorithm is to solve a well-constructed convex surrogate subproblem instead of directly solving the original nonconvex problem.

Let $f_{p}(\bm{v}_{nk}):=\log(1+p\|\bm{v}_{nk}\|_{2})$. First observe that $f_{p}(\bm{v}_{nk})$ is a composite function with $\bm{z}(\bm{v}_{nk})=\|{\bm{v}}_{nk}\|_{2}$ convex and $f_{p}(\bm{z})=\log(1+pz_{nk})$ nonconvex. At the $i$th iterate $\bm{v}_{nk}^{[i]}$, for any feasible $\tilde{\bm{v}}_{nk}$, we have

where $\bm{w}^{[i]}\in\partial(f_{p}(\bm{z}(\bm{v}_{nk}^{[i]})))$ is the subgradient of $f_{p}(\bm{z})$ at $\bm{z}=\bm{z}(\bm{v}_{nk}^{[i]})$ and $\beta>0$ is the prescribed proximity parameter, and the first inequality holds by the definition of the subgradient of the convex function. Hence, a convex subproblem is derived as an approximation of $f_{p}(\bm{v}_{nk})$ at current iterate $\bm{v}_{nk}^{[i]}$, which reads

with weights

As presented in [34], a smaller $\|\bm{v}_{nk}^{[i]}\|_{2}$ causes larger $w_{nk}^{[i]}$, then drive the nonzero components of $\bm{v}_{nk}$ towards zero aggressively. Overall, to enhance the group sparsity structure of the beamforming vector, the proposed proximal iteratively reweighted algorithm is illustrated in Algorithm 1.

Stage 2: Tasks Selection. In this second stage, an ordering guideline is applied to determine the priority of inference tasks, which is guided by the solution obtained in Stage 1. For ease of notation, let $\mathcal{S}=\{(n,k)\mid n\in\mathcal{N},k\in\mathcal{K}\}$ denote the set of all tasks. By considering the key system parameters (e.g., $\bm{h}_{nk}$, $P_{nk}^{\sf{c}}$ and $\eta_{n}$), the priority of task $(n,k)$ is heuristically given as

Intuitively, if edge BS $n$ is with a lower aggregative beamformer gain, lower power amplifier efficiency, lower channel power gain, but a higher computation power consumption for MU $k$, task $(n,k)$ has a lower priority. A lower $\theta_{nk}$ indicates that the tasks from MU $k$ have lower priority and may not be performed by BS $n$. Thus, tasks are arranged in light of the rule (17) with descending order. That is, the task’s priority is $\theta_{\pi_{1}}\geq\theta_{\pi_{2}}\dots\geq\theta_{\pi_{NK}}$, where $\pi$ denotes the permutation of task indexes.

We then solve a sequence of convex feasibility detection problems to obtain task selection strategy $\mathcal{A}$,

where $\pi^{(t)}=\{\pi_{t+1},\cdots,\pi_{NK}\}$ and $t$ increases from $K$ to $NK$ until (18) is feasible. Here $\bm{v}_{\pi^{(t)}}=\bm{0}$ are convex constraints, meaning that all $\bm{v}_{nk}$’s coefficients are zeros for task $(n,k)\in\pi^{(t)}$. The support set of beamformer $\bm{v}$ is defined as $\mathcal{T}(\bm{v})=\{(n,k)\mid\|\bm{v}_{nk}\|_{2}\neq 0,n\in\mathcal{N},k\in\mathcal{K}\}$, then the optimal task selection strategy $\mathcal{A}^{*}$ can be derived from $\mathcal{T}(\bm{v})=\{\pi_{1},\dots,\pi_{t}\}$.

Stage 3: Solution Refinement. At this point, we have determined tasks selection for each BS. Then, fix the obtained task index set, we solve the following convex program to refine the beamforming vectors

Overall, our proposed log-sum function based three-stage GSBF framework for solving (7) can be presented in Algorithm 2.

In this subsection, we derive the first-order necessary conditions to characterize the optimal solution of (13). Problem (13) is equivalently rewritten as

Similarly, for the derived subproblem (15), we have

Due to the nonconvex and nonsmooth nature of the log-sum function, we make use of the Fréchet subdifferential as the major tool in our analysis. Its definition is introduced as follows.

Several important properties of the Fréchet subdifferential [26] are listed below, which are used to characterize the optimal solution of (13).

The following Fermat’s rule [47] describes the necessary optimality condition of problem (13).

We next investigate the properties of $\partial_{F}\Omega(\bm{v})$ in the following Proposition 2, indicating that the Fréchet subdifferentials of $f_{p}(\cdot)$ at $\bm{0}$ is bounded.

To explore the behavior of the proposed proximal iteratively reweighted algorithm, based on Theorem 1 and Proposition 2, we define the optimality residual associated with (20) at a point $\bm{v}^{[i]}$ as

where $\bm{x}^{[i]}\in\partial\|\bm{v}^{[i]}\|_{\mathcal{G}_{2}}=\left[(\partial\|\bm{v}_{11}^{[i]}\|_{2})^{\sf{T}},\cdots,(\partial\|\bm{v}_{NK}^{[i]}\|_{2})^{\sf{T}}\right]^{\sf{T}}$ and $\bm{u}^{[i]}\in\mathcal{N}_{\mathcal{C}}(\bm{v}^{[i]})$. Since $\bm{r}^{[i]}\in\partial_{F}J(\bm{v}^{[i]})$, it implies that if $\bm{r}^{[i]}=\bm{0}$ then $\bm{v}^{[i]}$ satisfies the first-order necessary optimality condition (22). We adopt $\bm{r}^{[i]}$ to measure the convergence rate of our algorithm.

Moreover, we provide the first-order optimality condition of the subproblem (21) as follows

where $\bm{v}^{[i+1]}=\operatornamewithlimits{arg\,min}_{\bm{v}}G(\bm{v};\bm{v}^{[i]})$, $\bm{x}^{[i+1]}\in\partial\|\bm{v}^{[i+1]}\|_{\mathcal{G}_{2}}$ and $\bm{u}^{[i+1]}\in\mathcal{N}_{\mathcal{C}}(\bm{v}^{[i+1]})$. Note that the existence of optimal solution to (21) simply follows from the convexity and the coercivity of the objective $G(\cdot;\bm{v}^{[i]})$.

Now we show that an optimal solution of (21) also satisfies the first-order necessary optimality condition of (20) in the following lemma.

Define the model reduction caused by $\bm{v}^{[i+1]}$ at a point $\bm{v}^{[i]}$ as

The new iterate $\bm{v}^{[i+1]}$ causes a decrease in the objective $J(\bm{v})$, and this model reduction (25) converges to zero in the limit, both results are revealed in the following Lemma 2.

We now provide our main result in the following Theorem 2.

In this subsection, we show that the presented proximal iteratively reweighted algorithm has $O(1/t)$ ergodic worst-case convergence rate in terms of the optimality residual. In the following Lemma, it states that the optimality residual has an upper bound with the displacement of the iterates.

The subproblem (21) is referred to as the primal problem, and by exploiting the conjugate function [47], the associated Fenchel-Rockafellar dual is constructed as

where the dual objective is given as $Q(\bm{\lambda},\bm{\mu};\bm{v}^{[i]})=-\frac{1}{2\beta}\|\bm{\lambda}\odot\bm{w}^{[i]}+\bm{\mu}-\beta\bm{v}^{[i]}\|_{2}^{2}+\frac{\beta}{2}\|\bm{v}^{[i]}\|_{2}^{2}-\delta_{\mathcal{C}}^{*}(\bm{\mu})$, and the technical details to construct (26) is provided in Appendix E.

The Fenchel-Rockafellar duality theorem [47] states that the solution to (26) provides a lower bound on the minimum value to the solution of (21). Moreover, the gap between the primal objective function value of (21) and the corresponding dual objective function value of (26) at the $i$th iterate is defined as

If this gap $g(\bm{v},\bm{\lambda},\bm{\mu};\bm{v}^{[i]})$ is zero, then the strong duality holds. That is, at the optimal solution $(\bm{v}^{[i+1]};\bm{\lambda}^{[i+1]},\bm{\mu}^{[i+1]})$, we have

We now show that the duality gap vanish asymptotically in the following Theorem.

The goal in this subsection is to illustrate the convergence behavior of the proposed proximal iteratively reweighted algorithm. The presented result is obtained in a typical channel realization. Fig. 3 illustrates the convergence of the proximal iteratively reweighted algorithm. We can see that $\Omega(\bm{v})$ steadily decreases along with the iterations, which is consistent with our analysis in Lemma 2. Interestingly, we observe that the objective value of $\Omega(\bm{v})$ drops quickly in the first few iterations (less $5$ iterations), which indicates that the proposed proximal iteratively reweighted algorithm converges very fast. In view of this, we may suggest early terminating the Algorithm 1 in practice to obtain an approximate solution to speed up the entire algorithm while guaranteeing the overall performance.

We evaluate the performance of the three algorithms in terms of the overall network power consumption, the transmit power consumption and the number of computation tasks. The presented results are averaged over $100$ randomly and independently generated channel realizations.

Fig. 4 depicts the overall network power consumption of three approaches with different target SINRs. First, we observe that all three approaches have higher total power consumption as the required SINR becomes more stringent. This is because more edge BSs are required to transmit the inference results for higher QoS. In addition, we can see that CB approach has the highest power consumption among three approaches and the relative power difference between CB and the other two approaches can achieve approximately $67\%$ when SINR is $2$dB and approximately $18\%$ when SINR is $8$dB, indicating the effectiveness of joint task selection strategy and group sparse beamforming approach to minimize the overall network power consumption. On the other hand, we can see that the proposed log-sum function based three-stage GSBF approach outperforms the mixed $\ell_{1,2}$ GSBF approach, which demonstrates that enhance the group sparsity further reduces the overall network power consumption. In particular, we also observe that the performance gap between the blue and the red curve approximately remains at $9\%$ when SINR ranges from $4$dB to $8$dB, which indicates that the proposed log-sum function based three-stage GSBF approach is still attractive in the high SINR regime.

Tables I and II further demonstrate the number of inference tasks performed by edge BSs and the transmission power consumption, respectively. To be specific, in Table I, we observe that the number of performed inference tasks among three approaches is different under various SINRs, which shows the existence of the task selection strategy. Besides, it is observed that the log-sum function based three-stage GSBF approach always achieves a less number of performed inference tasks compared to the mixed $\ell_{1,2}$ GSBF approach for target SINRs, which indicates that the log-sum function based three-stage GSBF approach can enhance the group sparsity pattern in the beamforming vector. Meanwhile, as observed in Table II, the CB approach has the lowest transmission power compared to the other two approaches because the CB approach only optimizes the power consumption in transmission with performing all inference tasks. On the other hand, the transmission power consumption of the log-sum function based three-stage GSBF approach is slightly higher compared to the mixed $\ell_{1,2}$ GSBF approach under most SINRs. This is because more edge BSs participate in performing inference tasks in the mixed $\ell_{1,2}$ GSBF approach, resulting in a higher transmit beamforming gain for reducing transmission power. In other words, less number of performed inference tasks further reduces the computation power consumption of edge BSs but increases the transmission power consumption. Observe the Fig. 4 and Tables I-II together, it indicates that the proposed joint task selection strategy and GSBF approach find a good balance between computation power consumption and transmission power consumption, yielding lowest network power consumption.