Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications

I Introduction

Consider the min-max (a.k.a. saddle point) problem below:

Problem (1) is quite generic, and it arises in a wide range of signal processing and communication (SPCOM) applications. We list of few of these applications below.

Distributed non-convex optimization: Consider a network of $K$ agents defined by a connected graph $\mathcal{G}\>=\{\mathcal{V},\mathcal{E}\}$ with $|\mathcal{V}|=K$, where each agent $i$ can communicate with its neighbors. A generic problem formulation that captures many distributed machine learning and signal processing problems can be formulated as follows :

The above problem can be equivalently expressed as:

See Sec. III-A for detailed discussion on this reformulation and its relationship with (2). Clearly (3) is in the form of (1).

Power control and transceiver design problem: Consider a problem in wireless transceiver design, where $K$ transmitter-receiver pairs transmit over $N$ channels to maximize their minimum rates. User $k$ transmits messages with power $x_{k}:=[x^{1}_{k};\cdots;x^{N}_{k}]$, and its rate is given by (assuming Gaussian signaling):

A closely related problem is the coordinated beamforming design in a (multiple input single output) MISO interference channel. In this case the target is to find the optimal beamforming vector for each user in order to maximize some system utility function under the total power and outage probability constraints . When the min-rate utility is used, this problem can be formulated as

where $x_{i}$ is the transmit beamformer, $N_{t}$ is the number of antennas. Also, $R_{i}(\{x_{k}\})=\log_{2}(1+\xi_{i}(\{x_{k}\}_{k\neq i})x_{i}^{H}Q_{ii}x_{i})$, where $\xi_{i}$ incorporates the outage constraints and the cross-link interference, while $Q_{ii}$ denotes the covariance matrix of the channel between the $i$th transmitter-receiver pair.

For other setups, similar min-max problems can be formulated, some of which can be solved optimally (e.g., power control , transmitter density allocation , or certain MISO beamforing ). But for general multi-channel and/or MIMO interference channel, the corresponding problem is NP-hard . Many heuristic algorithms are available for these problems , but they are all designed for special problems, and often require repeatedly invoking computationally expensive general purpose solvers. For computational tractability, a common approach is to perform the following approximation of the min-rate utility :

However such an approximation procedure can introduce significant rate losses, as will be seen in Sec. IV.

Power control in the presence of a jammer: Consider an extension of the power control problem, where a jammer participates in a $K$-user $N$-channel interference channel transmission . Differently from a regular user, the jammer’s objective is to reduce the sum-rate of other users by properly transmitting noises. Let $y^{n}$ denote the jammer’s transmission on the $n$th channel, then one can formulate the following sum-rate maximization-minimization problem:

where $x_{k}$ and $y$ are the power allocation of user $k$ and the jammer, respectively; the set $\mathcal{X}:=\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{K}$, where $\mathcal{X}_{k}$ are defined similarly as before.

I-B Related Work

Motivated by these applications, it is of interest to develop efficient algorithms for solving these problems with theoretical convergence guarantees. In the optimization community, there has been a long history of studying min-max optimization problems. When the problem is convex in $x$ and concave in $y$, algorithms have been developed which can solve the convex-concave saddle problem optimally; see and the references therein. However, when the problem is non-convex, the convergence behavior of such alternating type algorithms has not been well understood.

Although there are many recent works on the non-convex minimization problems , only a few of them have been focused on the non-convex min-max problems. An optimistic mirror descent algorithm is proposed in , and its convergence to a saddle point is established under certain strong coherence assumptions. In , algorithms for robust optimization are proposed, where the $x$ problem is unconstrained, and $y$ linearly couples with a non-convex function of $x$ [cf. (4)]. In , a proximally guided stochastic mirror descent method (PG-SMD) is proposed, which provably converges to an approximate stationary point of the outer minimization problem. An oracle based non-convex stochastic gradient descent for generative adversarial networks (GAN) is proposed in , where the algorithms solve the maximization subproblem up to some small error. Moreover, in a multi-step GDA scheme is introduced, where the maximization problem is approximately solved using a number of gradient ascent steps. In the convergence of a primal-dual algorithm to a first-order stationary point is established for a class of GAN problems formulated as a special min-max optimization problem where the coupling term is linear w.r.t the discriminator. More recently, in it has been shown that GDA can converge to a stationary point of the outer minimization problem in the (strongly) concave case, under certain conditions. Under the same optimality criterion and assuming that the inner problem is concave, proves convergence using a proximal dual implicit accelerated gradient method.

It is worth noting that, in the works discussed above, different optimality criteria are often utilized. Since these conditions are not equivalent to each other, one cannot directly compare the convergence guarantees of algorithms that reach these criteria. On the other hand, these optimality criteria often share some interesting implicit connections. For example, it can be shown that, no matter if the inner maximization problem is strongly concave or concave, as long as a point $(x^{\ast},y^{\ast})$ is an (exact or approximate) stationary point defined in this current work [see (17)], then it is also an (exact or approximate, respectively) stationary point in the sense defined in ; see for detailed discussions. In Table I we provide a summary of some algorithms discussed above, including the complexity and the respective optimality criterion.

I-C Contribution of this work

In this work, we design effective algorithms for the min-max problem by adopting the popular block alternating minimization/maximization strategy. The studied problems allow non-convexity and non-smoothness in the objective, as well as non-linear coupling between variables. The algorithm proposed in this work is named the Hybrid Block Successive Approximation (HiBSA) algorithm, because it updates the variables block by block, where each block is optimized using a strategy similar to the idea of successive convex approximation (SCA) – except that to update the $y$ block, a concave approximation is used (hence the name “hybrid”). Despite the fact that such a block-wise alternating optimization strategy is simple and easy to implement [for example it has been used in the popular block successive upper bound minimization (BSUM) framework for minimization-only problem], it turns out that having the maximization subproblem invalidates all the previous analysis for minimization-only algorithms.

The main contributions of this paper are listed as follows. First, a number of applications in SPCOM have been formulated in the framework of non-convex, one-sided min-max problem (1). Second, based on different assumptions on how $x$ and $y$ variables are coupled, as well as whether the $y$ problem is strongly concave or merely concave, three different types of min-max problems are studied. For each of the problem class, a simple single loop algorithm is presented, together with its convergence guaranteesIn addition to the algorithm presented in the main text, we also provide an alternative double-loop algorithm for the case where the $y$ problem is concave, in the supplementary document of this article .. The major benefits of using the block successive approximation strategy are twofold: 1) each subproblem can be solved effectively, and 2) it is relatively easy to integrate many existing algorithms that are designed for only solving minimization problems (such as those based on the BSUM framework ). Finally, extensive numerical experiments are conducted for selected applications from SPCOM to validate the proposed algorithms.

Overall, to the best of our knowledge this is the first time that the convergence of the alternating block successive approximation type algorithm is rigorously analyzed for the (one-sided) non-convex min-max problem (1).

II The Proposed Algorithms and Analysis

In this section, we present our main algorithm. Towards this end, we will first make a number of blanket assumptions on problem (1), and then present the HiBSA algorithm in its generic form. We will then discuss in detail about various algorithmic choices, as well as major challenges in the analysis.

Throughout the paper, we will assume that problem (1) satisfies the following blanket assumption.

Assumption A. The following conditions hold for (1):

$h_{i}(\cdot)$’s and $g(\cdot)$ are convex and non-smooth functions;

$f$ has Lipschitz continuous gradient with respect to (w.r.t.) $x_{i}$ for every $i$ with constant $L_{x_{i}}$, that is:

Furthermore, $f$ has Lipschitz continuous gradient w.r.t. $y$ with constant $L_{y}$, that is:

Next we describe the proposed HiBSA algorithm.

Hybrid Block Successive Approximation (HiBSA) Algorithm At each iteration $r=1,2,3,\cdots$ [S1]. For $i=1,\cdots,K$, perform the following update: $\displaystyle x_{i}^{r+1}=$ $\displaystyle\arg\min_{x_{i}\in\mathcal{X}_{i}}U_{i}(x_{i};w^{r+1}_{i},y^{r})+h_{i}(x_{i})+\frac{\beta^{r}}{2}\|x_{i}-x_{i}^{r}\|^{2}$ (12) [S2]. Perform the following update for the $y$-block: $\displaystyle y^{r+1}=$ $\displaystyle\arg\max_{y\in\mathcal{Y}}\;{U_{y}(y;x^{r+1},y^{r})}-g(y)-\frac{\gamma^{r}}{2}\|y\|^{2};$ (13) [S3]. If converges, stop; otherwise, set $r=r+1$, go to [S1].

Assumption B. Each $U_{i}(\cdot)$ satisfies the following conditions:

(Strong convexity). Each $U_{i}(\cdot;w,y)$ is strongly convex with modulus $\mu_{i}>0$:

(Gradient consistency). Each $U_{i}(\cdot;w,y)$ satisfies:

(Tight upper bound). Each $U_{i}(\cdot;w,y)$ satisfies:

(Lipschitz gradient). Each $U_{i}(\cdot;w,y)$ satisfies:

Clearly, the $x$ update step [S1] closely resembles the BSUM algorithm , which is designed for minimization problems. Similarly as in BSUM, approximation functions are used to simplify the update for each subproblem; see for a number of such functions often used in signal processing applications.

However, a key difference from the BSUM, or for that matter, all successive convex approximation (SCA) based algorithms such as the inexact flexible parallel algorithm (FLEXA) , the concave-convex procedure (CCCP) , is the presence of the ascent step in [S2]. [Songtao: Too long consider to revise] This step is needed to deal with the inner maximization problem, but unfortunately the use of it invalidates the existing analyses for SCA-type algorithms, because all of them critically depend on consistently achieving some form of descent as the algorithms progress. As a result, how to properly implement and analyze the proposed algorithm represents a major challenge.

We note that it is not straightforward to design algorithms for one-sided non-convex min-max problem, as compared with non-convex minimization problems. For the former problem, simple algorithms like gradient descent-ascent can diverge (see Example 1 or ), but if we specialize such an algorithm to the latter problem (which becomes the well-known gradient descent), then it will converge to a second-order stationary solution . We refer the readers to a few recent works for more discussions.

Letting $\gamma^{r}=0$ and $\beta^{r}=0$ for all $r$, the HiBSA becomes an alternating gradient descent-ascent algorithm

Unfortunately, one can verify that for almost any $A$, regardless the choices of $\eta,\lambda$, (14) will not converge to the desired solution satisfying: $A^{T}y^{*}=0$ and $Ax^{*}=0$; see Fig. 1. This is because the linear system describing the dynamics of the vector $(x^{r},y^{r})$ is always unstable. $\blacksquare$

The above example motivates us to introduce both the proximal term ${\beta^{r}}/{2}\|x-x^{r}\|^{2}$ in [Step 1] of HiBSA, and the penalty term $-\frac{\gamma^{r}}{2}\|y^{r}\|^{2}$ in [Step 2]. By properly selecting the sequences $\{\beta^{r},\gamma^{r}\}$, we will show in the next section, that the HiBSA will converge for a wide class of problems (including Example 1 as a special case).

III Theoretical Properties of HiBSA

First, let us elaborate on the type of solutions we would like to obtain for problem (1). Because of the non-convexity involved in the minimization problem, we will not be able to use the classical measure of optimality for saddle point problems (i.e., the distance to a saddle point). Instead, we will adopt some kind of first-order stationarity conditions. To precisely state our condition, let us define the proximity operator for $x$ and $y$ blocks as follows:

Moreover, we define the stationarity gap for problem (1) as:

We say that a tuple $(x^{*},y^{*})$ is a first-order stationary solution for problem (1) if it holds that:

Following the above definition, we will say that $(x^{*},y^{*})$ is an $\epsilon$-stationary solution if the following holds

First, consider the case where $f$ is strongly concave in $y$. Then, it can be shown that if $(x^{\ast},y^{\ast})$ is an $\epsilon$-stationary point in the sense of (18), then it is also an $\mathcal{O}(\epsilon)$ stationary point in the sense defined in , that is:

For more details the interested reader can refer to .

Based on the above definition of first-order stationarity, we establish the equivalence between a few optimization formulations discussed in Section I.

Problems (2) and (3) are equivalent, in the sense that every KKT point for problem (2) is a first-order stationary solution of (3) [in the sense of (17)], and vice versa.

Proof. For simplicity of notation we assume $N=1$. Consider the following KKT conditions for problem (2)

The optimality conditions for these problems imply

Clearly, the conditions (23) – (24) imply (21).

Consider the problem: $\max\limits_{x\in\mathcal{X}}\min\limits_{k}R_{k}(x)$, and its reformulation (5). They are equivalent in the sense that, an equivalent smooth reformulation of the former has the same first-order stationary solutions as those of the latter [in the sense of (17)].

Proof. A well-known equivalent smooth formulation of the min-utility maximization problem is given below (equivalent in that the global optimal of these two problems are the same)

The partial KKT conditions of the above problem are

where $\{\hat{y}_{i}\}_{i=1}^{K}$ are the respective Lagrange multipliers, which together with $(\hat{\lambda},\hat{x})$ satisfy the KKT condition.

Now consider a stationary point $(x^{\ast},y^{\ast})$ of problem (5). Then the optimality conditions (17) imply that

where $R(x^{\ast}):=[R_{1}(x^{\ast});\ldots;R_{K}(x^{\ast})]$. Let us define

so it holds that $R_{i}(x^{\ast})\geq\lambda^{*},\;\forall~{}i$.

Plugging $(x^{*},y^{*})$ into the optimality conditions of (27a), (27b), we obtain:

For all $i$ such that $R_{i}(x^{\ast})=\lambda^{*}$ obviously it holds that $y_{i}^{*}(\lambda^{*}-R_{i}(x^{*}))=0$. Let $i,j$ be indices such that $R_{i}(x^{*})>\lambda^{*}$ and $R_{j}(x^{*})=\lambda^{*}$. Then, plugging $y_{i}=0,y_{j}=y_{i}^{\ast}+y_{j}^{\ast}$ and $y_{k}=y_{k}^{\ast},k\neq i,j$ into (28b) yields $y_{i}^{\ast}(R_{j}(x^{\ast})-R_{i}(x^{\ast}))\geq 0$. Because $R_{j}(x^{\ast})-R_{i}(x^{\ast})<0$ and $y_{i}^{\ast}\geq 0$ it must necessarily hold $y_{i}^{\ast}=0$ and thus $y_{i}^{\ast}(\lambda^{*}-R_{i}(x^{\ast}))=0$. As a result the conditions (26) are satisfied.

Conversely, assume $(x^{\ast},y^{\ast})$ satisfies conditions (26). Note that $R_{i}(x^{*})y_{i}\geq\lambda^{*}y_{i}$ for any $y\in\Delta$, so

for all $y\in\Delta,y^{\ast}\in\Delta$. It is not difficult to see that $(x^{\ast},y^{\ast})$ satisfy the rest of the conditions in (28a) – (28b). As a result the opposite direction also holds. Q.E.D.

III-B Convergence analysis: f​(x,y)𝑓𝑥𝑦f(x,y) strongly concave in y𝑦y

Starting this subsection, we will analyze the convergence of HiBSA algorithm. For the ease of presentation, we relegate all the details of the proof to the appendix.

We will first consider a subset of problem (1), where $f(x,y)$ is strongly concave in $y$. Specifically, we assume the following.

Assumption C-1. For any $x\in X$, $f(\cdot)$ satisfies the following:

where $\theta>1$ is the strong concavity constant. Further assume:

where $\rho>0$ is some fixed constant. $\blacksquare$

We note that it can be verified that the jamming problem (8) satisfies Assumption C-1. Next we will present a series of lemmas which lead to our main result in this subsection. The detailed proof can be found in Appendix Sec. -A – -D.

(Descent Lemma on $x$) Suppose that Assumptions A, B and C-1 hold. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA, with $\gamma^{r}=0$, and $\beta^{r}=\beta>0,\;\forall~{}r$. Then we have the following descent estimate:

(Descent Lemma on $y$) Suppose that Assumptions A, B and C-1 hold. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA, with $\gamma^{r}=0$, and $\beta^{r}=\beta>0,\;\forall~{}r$. Then we have the following descent estimate:

Suppose that Assumptions A, B and C-1 hold. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA, with $\gamma^{r}=0$, and $\beta^{r}=\beta>0,\;\forall~{}r$. Let us define a potential function as

When the following conditions are satisfied:

then there exist positive constants $c_{1},\{c_{2i}\}_{i=1}^{N}$ such that:

Combining the above analysis, we can obtain the following convergence guarantee for the HiBSA algorithm.

Suppose that Assumptions A, B, C-1 hold. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA, with $\gamma^{r}=0$, and $\beta^{r}=\beta>0,\;\forall~{}r$, satisfying (31). For a given $\epsilon>0$, let $T(\epsilon)$ denote the first iteration index, such that the following holds:

Then, $T(\epsilon)=\mathcal{O}\left(\frac{1}{\epsilon^{2}}\right)$.

III-C Convergence analysis: f​(x,y)𝑓𝑥𝑦f(x,y) concave in y𝑦y

Next, we consider the following assumptions for (1).

Assumption C-2. Assume that $f(\cdot)$ in (1) satisfies:

That is, it is concave in $y$. Further, assume that

That is, the $y$ update directly maximizes a regularized version of the objective function. Note that $U_{y}(u;x;y)$ is strongly concave in $u$, which satisfies the counterpart of Assumption B.1 for $U_{y}(\cdot)$. $\blacksquare$

Despite the fact that $f(x,y)$ is no longer strongly concave in $y$, the $y$-update in [S2] is still relatively easy since it maximizes a strongly concave function. However, the absence of strong concavity of $f(x,y)$ in $y$ poses significant challenge in the analysis. In fact, from Example 1 it is clear that directly utilizing the alternating gradient type algorithm may fail to converge to any interesting solutions. Towards resolving this issue, we specialize the HiBSA algorithm, by using a novel diminishing regularization plus increasing penalty strategy to regularize the $y$ and $x$ update, respectively (by using a sequence of diminishing $\{\gamma^{r}\}$, and increasing $\{\beta^{r}\}$).

We have the following convergence analysis. The proofs of the results below can be found in Appendix Sec. -E – -G.

(Descent lemma) Suppose that Assumptions A, B and C-2 hold. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA, with $\gamma^{r}>0$ and $\beta^{r}>L_{x_{i}},\;\forall~{}r,i$. Then we have:

Next we show that there exists a potential function, given below, which decreases consistently

Suppose that Assumptions A, B and C-2 are satisfied. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA. Suppose the following conditions are satisfied for all $r$,

then the change of potential function can be bounded through

Before proving the main result in this section, we make the following assumptions on the parameter choices.

Assumption C-3. Suppose that the following conditions hold:

Note that the above assumption on $\{\gamma^{r}\}$ can be satisfied, for example, when $\gamma^{r}=\frac{1}{\rho r^{1/4}}$; see the discussion after (69). $\blacksquare$

Suppose that Assumptions A, B, C-2 and C-3 hold. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA. For a given $\epsilon>0$, let $T(\epsilon)$ be defined similarly as in Theorem 1. Then, $T(\epsilon)=\widetilde{\mathcal{O}}\left(\frac{1}{\epsilon^{4}}\right).$

It is important to note that, when the problem is only concave in $y$, the condition (33) asserts that in each step a strongly concave problem has to be solved exactly. However, for a generic objective function, this step does not involve closed-form solution. In the supplementary material accompanying this paper , we extend this algorithm to the case where the maximization problem is solved by performing a finite number of gradient ascent steps.

III-D Convergence analysis: f​(x,y)𝑓𝑥𝑦f(x,y) linear in y𝑦y

Finally, we briefly discuss the case where the coupling term in (1) is linear in $y$. The derivation of the results in this section largely follows from what we have presented in Section III-C, therefore we choose to omit it.

Assumption C-4. Assume that problem (1) simplifies to:

Note that (40) contains the robust learning problem (4), the min utility maximization problem (5), and Example 1 as special cases. It is worth noting that, due to the use of the strongly concave approximation function $U_{y}(u;x,y)$ as defined in (33), we are able to perform a simple gradient step to update $y$, while in the algorithm proposed in the previous section, each iteration has to solve an optimization problem involving $y$.

It is worth mentioning that, in this case the analysis steps are similar to those in Sec. III-C. In particular, we can show that the potential function (35) has the same behavior as in Lemma 5. Therefore, we state our convergence result in the following corollary.

Suppose that Assumptions A, B, C-3 and C-4 hold. Let $(x^{r},y^{r})$ be a sequence generated by HiBSA. For a given $\epsilon>0$, let $T(\epsilon)$ be defined as in Theorem 1. Then, $T(\epsilon)=\widetilde{\mathcal{O}}\left(\frac{1}{\epsilon^{4}}\right).$

IV Numerical Results

We test our algorithms on three applications: a robust learning problem, a rate maximization problem in the presence of a jammer and a coordinated beamforming problem.

Robust learning over multiple domains. Consider a scenario where we have datasets from two different domains and adopt a neural network model in order to solve a multi-class classification problem. The neural network consists of two hidden layers with 50 neurons, each endowed with sigmoid activations, except from the output layer where we adopt the softmax activation. We aim to learn the model parameters using the following two approaches:

Robust Learning : Apply the robust learning model (4) and optimize the cost function using the HiBSA algorithm with $\gamma^{r}=\frac{1}{r^{1/4}}$ and the Multi-step GDA algorithm with one gradient descent and five gradient ascent steps per iteration. Note that we treat the minimization variable as one block and use the first-order Taylor expansion of the cost function as the approximation function.

Mutltitask Learning : Apply a multitask learning model , where we optimize the sum of the respective empirical risks correspsonding to the two domains/tasks; the weights associated with each task are fixed to 1/2. The problem is optimized using gradient descent.

Moreover, we evaluate the above algorithms by using the minimum accuracy across the two domains, over both training and test datasets. That is, accuracy = $\min\{$accuracy on domain 1, accuracy on domain 2$\}$.

In our experiments we use the MNIST dataset whose data points are images of handwritten digits of dimensions $28\times 28$. We select two different parts of the MNIST dataset as the two different domains we mentioned above. The first part consists of the digits from 0 to 4, while the second one contains the rest. Moreover, for the first domain we use $5000$ images for training and $1000$ for testing, while in the second one we employ $25000$ and $5000$ images respectively. Finally, we average the results over $5$ iterations.

Note that we do not perform extensive parameter tuning, since the purpose of this experiment is not to support the superiority of the robust model, but merely to illustrate that the proposed HiBSA computes a reasonable model similar to what can be computed by multistep GDA, and to what can be obtained by multi-task learning. Indeed, the results presented in Fig. 2 support this view, since different approaches achieve approximately the same accuracy on the test set.

Power control in the presence of a jammer. Consider the multi-channel and multi-user formulation (8) where there are $N$ channels, $K$ collaborative users and one jammer. We can verify that the jammer problem (i.e., the maximization problem over $y$) has a strongly concave objective function over the feasible set.

We compare HiBSA with the classic interference pricing algorithm , and the WMMSE algorithm , which are designed for solving sum-rate optimization problem without the jammer. Our problem is tested using the following setting. We construct a network with $K=10$, and the interference channel among the users and the jammer is generated using uncorrelated fading channel model with channel coefficients generated from the complex zero-mean Gaussian distribution with unit covariance . All users’ power budget is fixed at $P=10^{\rm SNR/10}$. For test cases without a jammer, we set $\sigma^{2}_{k}=1$ for all $k$. For test cases with a jammer, we set $\sigma^{2}_{k}=1/2$ for all $k$, and let the jammer have the rest of the noise power, i.e., $p_{0,\max}=N/2$. Note that by splitting the noise power we intend to achieve some fair comparison between the cases with and without the jammer. However, it is not possible to be completely fair because even though the total noise budgets are the same, the noise power transmitted by the jammer has to go through the random channel, so the total received noise power could be different. Nevertheless, this setting is sufficient to demonstrate the behavior of the HiBSA algorithm.

From the Fig. 3 (top), it is clear that the pricing algorithm monotonically increases the sum rate (as is predicted by theory), while HiBSA behaves differently: after some initial oscillation, the algorithm converges to a value that has a lower sum-rate. Further in Fig. 3 (bottom), we do see that by using the proposed algorithm, the jammer is able to effectively reduce the total sum rate of the system.

Coordinated MISO beamforming design. Consider the coordinated beamforming design problem described in Sec. I over a MISO interference channel. In this problem we experiment with the scenario where there are $K=10$ transmitter-receiver pairs, each transmitter is equipped with $N=6$ antennas. We adopt the min-rate utility, i.e., $U(\{R_{i}(x)\}_{i=1}^{K})=\min_{i=1,\ldots,K}\{R_{i}(x)\}$. Moreover, the transmission is performed over a complex Gaussian channel, and we set the power budget to be $\bar{p}=1$. The channel covariance matrices $\{C_{ij}\},i,j=1,\ldots,10$ are generated at random and their maximum eigenvalues are normalized to 1, if $i=j$, and to some constant $\lambda>0$, if $i\neq j$. Thus, the parameter $\lambda$ quantifies the level of intereference.

The problem of interest is to design the users’ beamformers in order to maximize the system’s utility function under constraints in power and outage probability. We approach the solution of the problem using two different algorithms :

BSUM-LSE : Substitute the min-rate utility function with a popular log-sum-exp approximation, i.e.,

Note that $\nu$ specifies the level of approximation with higher $\nu$’s corresponding to tighter bounds for the approximation error. Then following what is suggested in [14, Section C], we formulate the respective problem using the surrogate function, and solve the resulting problem iteratively using the projected gradient descent.

HiBSA: We apply the HiBSA to solve the formulation in (5). The $x$-subproblem is solved similarly as in BSUM-LSE. Moreover, in the maximization problem we use $\gamma^{r}=1/r^{1/4}$.

We run both algorithms for $1000$ complete iterations (one complete iteration involves one update of all the block variables, and $1000$ iterations are sufficient for both algorithms to converge in all scenarios), set the stepsizes $\beta$ and $\rho$ of HiBSA and the respective stepsize of BSUM-LSE all equal to $10^{-2}$. We also average the final results over $10$ independent random problem instances. Moreover, in order to evaluate the effect of the log-sum approximation we show the achieved min-rate utility of BSUM-LSE, by using 3 different values of $\nu\in\{1,5,7\}$.

In Fig. 4 we plot the min-rate utility for 7 different values of the noise variance and 2 different levels of interference. Notice that the HiBSA algorithm achieves higher utility than BSUM-LSE, while as expected the larger the value of $\nu$ the higher the utility achieved by the latter algorithm.

Furthermore, since large values of the parameter $\nu$ lead to low approximation error bounds, it is of interest to consider experiments with large $\nu$ for the BSUM-LSE algorithm. Intuitively, we expect the resulting objective to be very close to the min-rate utility and thus the achieved min-rate of the BSUM-LSE algorithm should approach the respective min-rate of HiBSA. In order to determine the behavior of BSUM-LSE in that range of $\nu$’s we consider an experiment with $K=10,N=6$ and $\lambda=0.6$. Regarding the stepsizes we keep them constant across the different values of $1/\sigma^{2}$, however an effort was made to select the optimal ones for all algorithms in order to ensure fair comparisons. Moreover, we terminate both algorithms when the relative successive differences of the min-rate utility becomes small, i.e., $|r_{min}(x^{r+1})-r_{min}(x^{r})|/|r_{min}(x^{r})|\leq 10^{-7}$, or the number of iterations becomes larger than $5,000$. Finally, the results are provided in Fig. 5.

Note that, for large value of $\nu$, i.e. $\nu=50,100,1000$, the achieved rate of BSUM-LSE is close but still inferior to that of HiBSA. Additionally, for the same $\nu$’s the HiBSA is faster than BSUM-LSE; in fact the larger the $\nu$ the longer the runtime. On the other hand, the former algorithm is in general slower than BSUM-LSE with $\nu=5$, however in that case HiBSA achieves higher min-rate utility. Overall, note that even though large $\nu$ leads (in most cases), to improvements in the attained min-rate utility, it also incurs longer runtimes. This can be attributed to the fact that for high $\nu$ the log-sum-exp objective approaches a non-smooth function, which is difficult to optimize. In conclusion, HiBSA in general outperforms BSUM-LSE in terms of runtime and attained min-rate utility.

V Conclusions

In this paper, motivated by the min-max problems arising in the areas of signal processing and wireless communications, we propose an algorithm called HiBSA. By leveraging the (strong) concavity of the maximization problem, we conduct analysis on the convergence behavior of the proposed algorithm. Numerical results show the effectiveness of the proposed algorithms of solving the min-max problems in robust machine learning and wireless communications. There are many potential future research directions we plan to explore. For example, it will be interesting to develop algorithms for more challenging problems where the $y$ problem is also non-convex. Further, it will also be interesting to establish some lower complexity bounds for non-convex and/or non-concave min-max problems, which characterizes the best performance one can achieve when optimizing such a family of problems.

VI Acknowledgement

The authors would like to thank Dr. Tsung-Hui Chang and Dr. Wei-Chiang Li for helpful discussion on the MISO beamforming problem, and for providing their codes.

References

-A Proof of Lemma 1

By using the assumption that $f$ has Lipschitz gradient, $h_{i}$ is convex (cf. Assumption A), and by noticing that $w^{r+1}_{i}=(x^{r}_{i},w^{r+1}_{-i})$, we obtain the following:

for some $\vartheta^{r+1}_{i}\in\partial h_{i}(x^{r+1}_{i})$.

Second, the optimality condition for the $x_{i}$ update step (12) is

So adding and subtracting $\langle\nabla_{x_{i}}U_{i}(x_{i}^{r};w_{i}^{r+1},y^{r}),x_{i}^{r}-x_{i}^{r+1}\rangle$ in (-A), and by applying assumptions B.1 (strong convexity) and B.2 (gradient consistency), we obtain the following:

Then, combining the above expression with (41) results in

Summing over $i\in[K]$ we obtain the desired result. Q.E.D.

-B Proof of Lemma 2

where $(a)$ follows from the optimality conditions of the $y$-step (13) at iterations $r+1$ and $r$; in $(b)$ we apply the following identity:

in $(c)$ we add and subtract a term $\langle\nabla_{y}f(x^{r},y^{r}),y^{r+1}-y^{r}\rangle$, and apply the Young’s inequality and obtain:

where ${L_{y}}$ is defined in (11a). By applying the strong concavity of $f(x,y)$ in $y$, the Young’s inequality and the Lipschitz condition w.r.t $y$, we can have the following bound for the inner product term in (44):

Combining the above with (44) completes the proof. Q.E.D.

At this point, by simply combining Lemmas 1 - 2, it is not clear how the objective value behaves after each $x$ and $y$ update. To capture the essential dynamics of the algorithm, the key is to identify a proper potential function, which decreases after each round of $x$ and $y$ updates.

-C Proof of Lemma 3

According to (43), the optimality condition of $y$-problem (13) at iterations $r+1$ and $r$ are given by:

where $\xi^{r}\in\partial(\mathcal{I}_{\mathcal{Y}}(y^{r})+g(y^{r}))$. We subtract these two equalities, multiply both sides by $y^{r+1}-y^{r}$, utilize the defining property of subgradient vectors: $\langle\xi^{r+1}-\xi^{r},y^{r+1}-y^{r}\rangle\geq 0,$ and we obtain:

where $v^{r+1}$ is defined in (46). Applying (45) to the LHS to the above expression, and using similar techniques as in (47), (48) for the RHS of the above expression [note that this time we use a constant $\theta$ instead of $\rho$, when applying (47)], we obtain the following:

Multiplying both sides of (-C) by $4/(\theta\rho)$, and adding the resulting inequality to the above expression, we have

Finally, adding in both sides the term $\left({\frac{1}{2\rho}}-4\left(\frac{1}{\rho}-\frac{L^{2}_{y}}{2\theta}\right)\right)\|y^{r+1}-y^{r}\|^{2}$ and using the definition of the potential function (30), we obtain the following

In the inequality above we do not include $\theta-\rho L^{2}_{y}/2$ (from RHS of the descent estimate in Lemma 1) because by the choice of $\rho$ this term is positive. Therefore, when

we have sufficient descent of the potential function $\mathcal{P}^{r+1}$. This completes the proof. Q.E.D.

-D Proof of Theorem 1

We first bound the $i$th block of the optimality gap (16) by

where in $(a)$ we use the optimality conditions w.r.t to $x_{i}$ in (12); in $(b)$ we use the nonexpansiveness of the proximal operator, $\nabla_{x_{i}}U_{i}(x_{i}^{r};w_{i}^{r+1},y^{r})=\nabla_{x_{i}}f_{i}(w_{i}^{r+1},y^{r})$ (Assumption B2), Assumption B4 (Lipschitz gradient), as well as the following identity

Moreover, utilizing the same argument for the optimality condition w.r.t to $y$ problem (13), we obtain:

where in $(a)$ we use the optimality conditions w.r.t $y$, in $(b)$ we use the nonexpansiveness of the proximal operator and finally in (c) the Assumption A.3. Combining (32) and the above two inequalities, we see that there exist constants $\sigma_{1}>0$ and $\sigma_{2}>0$ such that the following holds:

Summing the above inequality over $r\in[T]$, we have

Dividing both sides by $\epsilon^{2}$, the desired result is obtained. Q.E.D.

-E Proof of Lemma 4

Following similar steps as in Lemma 1 and using the assumption $\beta^{r}>L_{x_{i}},\forall i$ we obtain

where $\mu:=\min\limits_{i\in[K]}\mu_{i}$. To analyze the $y$ update, define

The optimality condition for the $y$ update is

where $\xi^{r+1}\in\partial(\mathcal{I}_{\cal{Y}}(y^{r+1})+g(y^{r+1}))$. Using this, we have the following series of inequalities:

Combining (55) and (57), we obtain the desired result. Q.E.D.

-F Proof of Lemma 5

To simplify notation, define $f^{r+1}:=f(x^{r+1},y^{r+1})$. The optimality conditions of $y$ problem are given by

for all $y\in\mathcal{Y}$, where $\vartheta^{r+1}\in\vartheta g(y^{r+1})$.

Plugging in $y=y^{r}$ in (58a), $y=y^{r+1}$ in (58b), adding them together and utilizing the defining property of subgradient vectors, i.e $\langle\vartheta^{r+1}-\vartheta^{r},y^{r+1}-y^{r}\rangle\geq 0$, we obtain

where $v^{r+1}$ is defined in (46). In the following, we will use the above inequality to analyze the recurrence of the size of the difference between two consecutive iterates. First, we have

Substituting (60) and (45) into (-F), we have

where $(a)$ is true because of the fact that $0<\gamma^{r}<\gamma^{r-1}$, which implies that $-\frac{\gamma^{r-1}-\gamma^{r}}{2}<0$ and $-\frac{\gamma^{r-1}+\gamma^{r}}{2}<-\gamma^{r}$, and the concavity of function $f(x,y)$ in $y$; in $(b)$ we use the Young’s inequality. Next, let us define

Furthermore, adding (34) and (61), and ignoring the negative term -$\frac{\gamma^{r-1}}{2}\|y^{r+1}-y^{r}\|^{2}$ we have

Finally, by adding to both sides the term $\frac{2}{\rho}\left(\frac{1}{\rho\gamma^{r+1}}-\frac{1}{\rho\gamma^{r}}\right)\|y^{r+1}-y^{r}\|^{2}$, using the definition $\{\mathcal{P}^{r}\}$ in (35), we obtain

According to the above, to achieve descent in $\|y^{r+1}-y^{r}\|^{2}$ we need to ensure that the following holds:

Note that, (62) is equivalent to the condition $\frac{1}{\gamma^{r+1}}-\frac{1}{\gamma^{r}}\leq{\rho}/{4}.$ which holds by condition (36). This completes the proof. Q.E.D.

-G Proof of Theorem 2

For simplicity, let $\mathcal{G}^{r}_{i}:=(\mathcal{G}^{\beta^{r}}_{\rho}(x^{r},y^{r}))_{i}$. Similarly as in the proof of Theorem 1, we have

For the corresponding bound for $y$ we have

where in $(a)$ we use the optimality conditions w.r.t $y$; in $(b)$ we use the nonexpansiveness of the proximal operator, as well as the the Lipschitz gradient condition w.r.t $y$ two times. Combining the above two bounds we obtain

where we defined $L:=\max\limits_{i\in[K]}(L_{u_{i}}+L_{x_{i}})$. Moreover, we choose

where $\kappa$ is chosen to satisfy $\kappa>2,\quad\beta^{0}>L_{x_{i}},\;\forall i$.

By condition (38), it is clear that $\beta^{r+1}\geq\beta^{r}$. Combining this with the choice of $\kappa$ we have: $\beta^{r}\geq\beta^{0}>L_{x_{i}},\;\forall i,r$. Thus, this choice of $\beta^{r}$ satisfies Assumption C-3.

Using these properties in (63), the constants in front of $\|x^{r+1}-x^{r}\|^{2}$ becomes

in $(a)$ we use the identity shown in (65); $(b)$ always holds for some $d_{1}>1$ (which are both independent of $r$), since $\alpha^{r}$ is an increasing sequence, and $\alpha^{0}$ is bounded away from zero. Note that since $y$ lies in a bounded set, there exists $\sigma_{y}$ such that $\|y^{r+1}\|^{2}\leq\sigma^{2}_{y},\forall~{}r$. Using (66), setting $z:=3\left(L_{y}+\frac{1}{\rho}\right)^{2}$, we obtain

Furthermore, when $\beta^{r}=\rho{L^{2}_{y}}+\frac{{2\kappa L^{2}_{y}}}{\rho(\gamma^{r})^{2}}-2\mu$ and since $\frac{1}{\gamma^{r+1}}-\frac{1}{\gamma^{r}}\leq{\frac{\rho}{5}}$, the bound of the potential function (37) becomes

Because $\{\alpha^{r}\}$ is increasing and $\|y^{r}\|^{2}\leq\sigma^{2}_{y}$, the above relation implies the following

Then by combining (68) and (67), we obtain

Summing both sides from $r=1$ to $T$, and noting that condition (38) implies $\frac{\gamma^{r}}{\gamma^{r+1}}\leq 1.2,\;\forall r$, we obtain

where $d_{4}:=\min\left\{\frac{1}{10\rho},1\right\}$. Also, there exists $d_{5}>\max\left\{\frac{d_{1}^{2}}{d_{4}},\frac{z}{d_{4}a^{0}}\right\}$ such that $d_{2}^{r}\geq\frac{1}{d_{5}\alpha^{r}}$.

By utilizing the definition of $T(\epsilon)$ and the above bounds, we know that

Moreover, when $\gamma^{r}=\frac{1}{\rho r^{1/4}}$, it can be verified that the following holds:

because $(r+1)^{1/4}-(r)^{1/4}$ is a monotonically decreasing function and its maximum value is achieved at $r=1$. We can plug in this choice of $\gamma^{r}$ into (65), and obtain

Using these choices of $\{\gamma^{r},\alpha^{r}\}$, and by utilizing the bounds that $\sum_{r=1}^{T}1/r\leq c\ln(T)$ (for some $c>0$), and $\sum_{r=1}^{T}1/\sqrt{r}\geq\sqrt{T}$, the relation (69) becomes:

where $C>0$ is some constant independent of the iteration. Then, the desired result follows directly from (70). Q.E.D.