NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization

Introduction

Consider the following nonconvex and nonsmooth constrained optimization problem

In this work we solve (1) in a stochastic and distributed manner. We consider the setting in which $N$ distributed agents each having the knowledge of one smooth function $\{g_{i}\}_{i=1}^{N}$, and they are connected to a cluster center which handles $g_{0}$ and $p$. At any given time, a randomly selected agent is activated and performs computation to optimize its local objective. Such distributed computation model has been popular in large-scale machine learning and signal processing . Such model is also closely related to the (centralized) stochastic finite-sum optimization problem , in which each time the iterate is updated based on the gradient information of a random component function. One of the key differences between these two problem types is that in the distributed setting there can be disagreement between local copies of the optimization variable $z$, while in the centralized setting only one copy of $z$ is maintained.

where $h(z):=\iota_{Z}(z)+p(z)$, $x:=[x_{1};\cdots;x_{N}]$. Our algorithm uses the Lagrangian relaxation of the equality constraints, and at each iteration a (possibly non-uniformly) randomly selected primal variable is optimized, followed by an approximate dual ascent step. Note that such splitting scheme has been popular in the convex setting , but not so when the problem becomes nonconvex.

Our work also reveals a fundamental connection between primal-dual based algorithms and the primal only average-gradient based algorithm such as SAGA/SAG/IAG . With the key observation that the dual variables in NESTT serve as the “memory” of the past gradients, one can specialize NESTT to SAGA/SAG/IAG. Therefore, NESTT naturally generalizes these algorithms to the nonconvex nonsmooth setting. It is our hope that by bridging the primal-dual splitting algorithms and primal-only algorithms (in both the convex and nonconvex setting), there can be significant further research developments benefiting both algorithm classes.

Related Work. Many stochastic algorithms have been designed for (2) when it is convex. In these algorithms the component functions $g_{i}$’s are randomly sampled and optimized. Popular algorithms include the SAG/SAGA , the SDCA , the SVRG , the RPDG and so on. When the problem becomes nonconvex, the well-known incremental based algorithm can be used , but these methods generally lack convergence rate guarantees. The SGD based method has been studied in , with $\mathcal{O}(1/\epsilon^{2})$ convergence rate. Recent works and develop algorithms based on SVRG and SAGA for a special case of (1) where the entire problem is smooth and unconstrained. To the best of our knowledge there has been no stochastic algorithms with provable, and non-trivial, convergence rate guarantees for solving problem (1). On the other hand, distributed stochastic algorithms for solving problem (1) in the nonconvex setting has been proposed in , , in which each time a randomly picked subset of agents update their local variables. However there has been no convergence rate analysis for such distributed stochastic scheme. There has been some recent distributed algorithms designed for (1) , but again without global convergence rate guarantee.

Preliminaries. The augmented Lagrangian function for problem (1) is given by:

where $\lambda:=\{\lambda_{i}\}_{i=1}^{N}$ is the set of dual variables, and $\eta:=\{\eta_{i}>0\}_{i=1}^{N}$ are penalty parameters.

We make the following assumptions about problem (1) and the function (3).

The function $f(z)$ is bounded from below over $Z\cap\hbox{int}(\hbox{dom }f)$: $\underline{f}:=\min_{z\in Z}f(z)>-\infty.$ $p(z)$ is a convex lower semi-continuous function; $Z$ is a closed convex set.

The $g_{i}$’s and $g$ have Lipschitz continuous gradients, i.e.,

Clearly $L\leq 1/N\sum_{i=1}^{N}L_{i}$, and the equality can be achieved in the worst case. For simplicity of analysis we will further assume that $L_{0}\leq\frac{1}{N}\sum_{i=1}^{N}L_{i}.$

Each $\eta_{i}$ in (3) satisfies $\eta_{i}>L_{i}/N$; if $g_{0}$ is nonconvex, then $\sum_{i=1}^{N}\eta_{i}>3L_{0}$.

Assumption A-(c) implies that $L\left(x,z;\lambda\right)$ is strongly convex w.r.t. each $x_{i}$ and $z$, with modulus $\gamma_{i}:=\eta_{i}-L_{i}/N$ and $\gamma_{z}=\sum_{i=1}^{N}\eta_{i}-L_{0}$, respectively [31, Theorem 2.1].

We then define the prox-gradient (pGRAD) for (1), which will serve as a measure of stationarity. It can be checked that the pGRAD vanishes at the set of stationary solutions of (1) .

The proximal gradient of problem (1) is given by (for any $\gamma>0$)

The NESTT-G Algorithm

Algorithm Description. We present a primal-dual splitting scheme for the reformulated problem (2). The algorithm is referred to as the NESTT with Gradient step (NESTT-G) since each agent only requires to know the gradient of each component function. To proceed, let us define the following function (for some constants $\{\alpha_{i}>0\}_{i=1}^{N}$):

Note that $V_{i}(\cdot)$ is related to $L(\cdot)$ in the following way: it is a quadratic approximation (approximated at the point $z$) of $L(x,y;\lambda)$ w.r.t. $x_{i}$. The parameters $\alpha:=\{\alpha_{i}\}_{i=1}^{N}$ give some freedom to the algorithm design, and they are critical in improving convergence rates as well as in establishing connection between NESTT-G with a few primal only stochastic optimization schemes.

The algorithm proceeds as follows. Before each iteration begins the cluster center broadcasts $z$ to everyone. At iteration $r+1$ a randomly selected agent $i_{r}\in\{1,2,\cdots N\}$ is picked, who minimizes $V_{i_{r}}(\cdot)$ w.r.t. its local variable $x_{i_{r}}$, followed by a dual ascent step for $\lambda_{i_{r}}$. The rest of the agents update their local variables by simply setting them to $z$. The cluster center then minimizes $L(x,z;\lambda)$ with respect to $z$. See Algorithm 1 for details.

We remark that NESTT-G is related to the popular ADMM method for convex optimization . However our particular update schedule (randomly picking $(x_{i},\lambda_{i})$ plus deterministic updating $z$), combined with the special $x$-step (minimizing an approximation of $L(\cdot)$ evaluated at a different block variable $z$) is not known before. These features are critical in our following rate analysis.

To proceed, let us define $r(j)$ as the last iteration in which the $j$th block is picked before iteration $r+1$. i.e.$r(j):=\max\{t\mid t<r+1,j=i(t)\}.$ Define $y_{j}^{r}:=z^{r(j)}$ if $j\neq i_{r}$, and $y_{i_{r}}^{r}=z^{r}$. Define the filtration $\mathcal{F}^{r}$ as the $\sigma$-field generated by $\{i(t)\}_{t=1}^{r-1}$.

A few important observations are in order. Combining the $(x,z)$ updates (4) – (7), we have

​​ The key here is that the dual variables serve as the “memory” for the past gradients of $g_{i}$’s. To proceed, we first construct a potential function using an upper bound of $L(x,y;\lambda)$. Note that

​​ where ${\rm(i)}$ uses (8b) and applies the descent lemma on the function $1/Ng_{i}(\cdot)$; in ${\rm(ii)}$ we have used (5) and (8b). Since each $i$ is picked with probability $p_{i}$, we have

Then the following descent estimate holds true for NESTT-G

Sublinear Convergence. Define the optimality gap as the following:

Suppose Assumption A holds, and pick (for $i=1,\cdots,N$)

Then every limit point generated by NESTT-G is a stationary solution of problem (2). Further,

Note that Part (1) is useful in the centralized finite-sum minimization setting, as it shows the sublinear convergence of NESTT-G, measured only by the primal optimality gap evaluated at $z^{r}$. Meanwhile, part (2) is useful in the distributed setting, as it also shows that the expected constraint violation, which measures the consensus among agents, shrinks in the same order. We also comment that the above result suggests that to achieve an $\epsilon$-stationary solution, the NESTT-G requires about \mathcal{O}\left(\bigg{(}\sum_{i=1}^{N}\sqrt{L_{i}/N}\bigg{)}^{2}/\epsilon\right) number of gradient evaluations (for simplicity we have ignored an additive $N$ factor for evaluating the gradient of the entire function at the initial step of the algorithm).

It is interesting to observe that our choice of $p_{i}$ is proportional to the square root of the Lipschitz constant of each component function, rather than to $L_{i}$. Because of such choice of the sampling probability, the derived convergence rate has a mild dependency on $N$ and $L_{i}$’s. Compared with the conventional gradient-based methods, our scaling can be up to $N$ times better. Detailed discussion and comparison will be given in Section 4.

Note that similar sublinear convergence rates can be obtained for the case $\alpha_{i}=1$ for all $i$ (with different scaling constants). However due to space limitation, we will not present those results here.

2 Linear Convergence.

In this section we show that the NESTT-G is capable of linear convergence for a family of nonconvex quadratic problems, which has important applications, for example in high-dimensional statistical learning . To proceed, we will assume the following.

Each function $g_{i}(z)$ is a quadratic function of the form $g_{i}(z)=1/2z^{T}A_{i}z+\langle b,z\rangle$, where $A_{i}$ is a symmetric matrix but not necessarily positive semidefinite;

The feasible set $Z$ is a closed compact polyhedral set;

The nonsmooth function $p(z)=\mu\|z\|_{1}$, for some $\mu\geq 0$.

Suppose Assumptions A and B hold. Let $Z^{*}$ denotes the set of stationary solutions of problem (1), and $\mbox{dist\,}(z,Z^{*}):=\min_{u\in Z^{*}}\|z-u\|$. Then we have the following

(Error Bound Condition) For any $\xi\geq\min_{z}f(z)$, exists a positive scalar $\tau$ such that the following error bound holds

for all $z\in(Z\cap{\rm dom}~{}h)$ and $z\in\{z:f(z)\leq\xi\}$.

(Separation of Isocost Surfaces) There exists a scalar $\delta>0$ such that

We note that the first statement holds true largely due to [29, Theorem 4], and the second statement holds true due to [20, Lemma 2.1]; see detailed discussion after [29, Assumption 2]. Here the only difference with the statement [29, Theorem 4] is that the error bound condition (15) holds true globally. This is by the assumption that $Z$ is a compact set. The proof will be provided in the Appendix.

Utilizing the above result, we have the following linear convergence claim.

Linear convergence of this type for problems satisfying Assumption B has been shown for (deterministic) proximal gradient based methods [29, Theorem 2, 3]. To the best of our knowledge, this is the first result that shows the same linear convergence for a stochastic and distributed algorithm. There has been some recent works showing linear convergence for nonconvex problems satisfying certain quadratic growth condition . However the problems considered in are smooth unconstrained problems, and every stationary point is a global minimum, therefore they do no cover our nonconvex quadratic problems, whose stationary solutions are not global minimizers.

The NESTT-E Algorithm

In this section, we present a variant of NESTT-G, which is named NESTT with Exact minimization (NESTT-E). Our motivation is the following. First, in NESTT-G every agent should update its local variable at every iteration [cf. (4) or (6)]. In practice this may not be possible, for example at any given time a few agents can be in the sleeping mode so they cannot perform (6). Second, in the distributed setting it has been generally observed (e.g., see [9, Section V]) that performing exact minimization (whenever possible) instead of taking the gradient steps for local problems can significantly speed up the algorithm. The NESTT-E algorithm to be presented in this section is designed to address these issues.

To proceed, let us define a new function as follows:

Note that if $\alpha_{i}=1$ for all $i$, then the $L(x,z;\lambda)=U(x,z;\lambda)+p(z)+h(z)$. The algorithm details are presented in Algorithm 2. The algorithm proceeds as follows. At each iteration the cluster center minimizes $L(x,z;\lambda)$ with respect to $z$. Then the updated $z$ is sent to a randomly selected agent $i_{r}\in\{1,2,\cdots N\}$, who minimizes $U(x,z;\lambda)$ w.r.t. its local variable $x_{i_{r}}$, followed by a dual ascent step for $\lambda_{i_{r}}$.

2 Convergence Analysis

We begin analyzing NESTT-E. The proof technique is quite different from that for NESTT-G, and it is based upon using the expected value of the Augmented Lagrangian function as the potential function. For the ease of description we define the following quantities:

To measure the optimality of NESTT-E, define the prox-gradient of $L(x,z;\lambda)$ as:

It can be verified that $H(w^{r})\to 0$ implies that $w^{r}$ reaches a stationary solution for problem (2). We have the following theorem regarding the convergence properties of NESTT-E.

Suppose Assumption A holds, and that $(\eta_{i},\alpha_{i})$ are chosen such that $c_{i}<0$ . Then for some constant $\underline{f}$, we have

Further, almost surely every limit point of $\{w^{r}\}$ is a stationary solution of problem (2). Finally, for some function of $\alpha$ denoted as $C(\alpha)={\sigma_{1}(\alpha)}/{\sigma_{2}(\alpha)}$, we have the following:

We remark that the above result shows the sublinear convergence of NESTT-E to the set of stationary solutions. Note that $\gamma_{i}=\eta_{i}-L_{i}/N$, to satisfy $c_{i}<0$, a simple derivation yields

Further, the above result characterizes the dependency of the rates on various parameters of the algorithm. For example, to see the effect of $\alpha$ on the convergence rate, let us set $p_{i}=\frac{L_{i}}{\sum_{i=1}^{N}L_{i}}$, and $\eta_{i}=3L_{i}/N$, and assume $L_{0}=0$, then consider two different choices of $\alpha$: $\widehat{\alpha}_{i}=1,\;\forall~{}i$ and $\widetilde{\alpha}_{i}=4,\;\forall~{}i$. One can easily check that applying these different choices leads to following results:

The key observation is that increasing $\alpha_{i}$’s reduces the constant in front of the rate. Hence, we expect that in practice larger $\alpha_{i}$’s will yield faster convergence. This phenomenon will be later confirmed by the numerical results.

Next let us briefly present the linear convergence of NESTT-E algorithm under Assumption B. The proof again utilizes the error bound condition in Lemma 2.2.

Connections and Comparisons with Existing Works

In this section we compare NESTT-G/E with a few existing algorithms in the literature. First, we present a somewhat surprising observation, that NESTT-G takes the same form as some well-known algorithms for convex finite-sum problems. To formally state such relation, we show in the following result that NESTT-G in fact admits a compact primal-only characterization.

The NESTT-G can be written into the following compact form:

​ Based on this observation, the following comments are in order.

Suppose $h\equiv 0$, $g_{0}\equiv 0$ and $\alpha_{i}=1$, $p_{i}=1/N$ for all $i$. Then (23) takes the same form as the SAG presented in . Further, when the component functions $g_{i}$’s are picked cyclically in a Gauss-Seidel manner, the iteration (23) takes the same form as the IAG algorithm .

Suppose $h\neq 0$ and $g_{0}\neq 0$, and $\alpha_{i}=p_{i}=1/N$ for all $i$. Then (23) is the same as the SAGA algorithm , which is design for optimizing convex nonsmooth finite sum problems.

Note that SAG/SAGA/IAG are all designed for convex problems. Through the lens of primal-dual splitting, our work shows that they can be generalized to nonconvex nonsmooth problems as well.

Secondly, NESTT-E is related to the proximal version of the nonconvex ADMM [14, Algorithm 2]. However, the introduction of $\alpha_{i}$’s is new, which can significantly improve the practical performance but complicates the analysis. Further, there has been no counterpart of the sublinear and linear convergence rate analysis for the stochastic version of [14, Algorithm 2].

In Table 1 we list the comparison of the number of gradient evaluations for NESTT-G and GD, in the worst case (in the sense that $\sum_{i=1}^{N}L_{i}/N=L$). For simplicity, we omitted an additive constant of $\mathcal{O}(N)$ for computing the initial gradients.

Numerical Results

Due to the existence of noise, $\hat{\Gamma}$ is not positive semidefinite hence the problem is not convex. Note that this problem satisfies Assumption A– B, then by Theorem 2.2 NESTT-G converges Q-linearly.

To facilitate the following derivation, in this section we collect some key properties of NESTT-G.

First, from the optimality condition of the $x$ update we have

Then using the update scheme of the $\lambda$ we can further obtain

Therefore, using the definition of $y^{r}_{i}$ we have the following compact forms

Second, let us look at the optimality condition for the $z$ update. The $z$-update (7) is given by

Note that this problem is strongly convex because we have assumed that $\sum_{i=1}{\eta_{i}}>3L_{0}$; cf. Assumption [A-(c)].

where in ${\rm(i)}$ we have defined $\beta:=1/\sum_{i=1}^{N}\eta_{i}$; in ${\rm(ii)}$ we have defined

Clearly if we pick $\alpha_{i}=p_{i}$ for all $i$, then we have

Using the definition of $u^{r+1}$, it is easy to check that

The optimality condition for the $z$ subproblem is given by:

where, $\xi^{r+1}\in\partial h(z^{r+1})$ is a subgradient of $h(z^{r+1})$. Using the definition of $v_{i_{r}}$ in (32), we obtain

Third, if $\alpha_{i}=p_{i}$, then we have:

where $(a)$ is true because whenever $\alpha_{i}=p_{i}$ for all $i$, then

2 Proof of Lemma 2.1

Step 1). Using the definition of potential function $Q^{r}$, we have:

where in ${\rm(i)}$ we have used the Lipschitz continuity of the gradients of $g_{i}$’s as well as the convexity of $h$; in ${\rm(ii)}$ we have used the fact that

Overall we have the following bound for the first term in (38):

Step 3). We bound the second term in (38) in the following way:

where in ${\rm(i)}$ we have used the fact that the randomness of $z^{r-1}$ comes from $i_{r-2}$, so fixing $\mathcal{F}^{r-1}$, $z^{r-1}$ is deterministic; we have also applied the following inequality:

The equality ${\rm(ii)}$ is true because the randomness of $y^{r-1}_{i}$ comes from $i_{r-1}$, and for each $i$ there is a probability $p_{i}$ such that $x^{r}_{i}$ is updated, so that $\nabla g_{i}(y^{r-1}_{i})=\nabla g_{i}(z^{r-1})$, otherwise $x_{i}$ is not updated so that $\nabla g_{i}(y^{r-1}_{i})=\nabla g_{i}(y^{r-2}_{i})$.

Step 4). Applying (42) and set $\alpha_{i}=p_{i}$, the second part of (38) can be bounded as

Combining (41) and (43) eventually we have

Recall that $\beta=\frac{1}{\sum_{i=1}^{N}\eta_{i}}$.These values yield the following

To show that $\hat{c}\leq-\sum_{i=1}^{N}\frac{\eta_{i}}{8}$ let us assume that $\eta_{i}=d_{i}L_{i}$ for some $d_{i}>0$. Note that by assumption we have

Therefore we have the following expression for $\hat{c}$:

As a result, to have $\hat{c}<-\sum_{i=1}^{N}\frac{\eta_{i}}{8}$, we need

By finding the root of the above quadratic inequality, we need $d_{i}\geq\frac{9}{Np_{i}}$, which is equivalent to choosing the following parameters

3 Proof of Theorem 2.1

First, using the fact that $f(z)$ is lower bounded [cf. Assumption A-(a)], it is easy to verify that $\{Q^{r}\}$ is a bounded sequence. Denote its lower bound to be $\underline{Q}$. From Lemma 2.1, it is clear that $\{Q^{r}-\underline{Q}\}$ is a nonnegative supermartingale. Apply the Supermartigale Convergence Theorem [4, Proposition 4.2] we conclude that $\{Q^{r}\}$ converges almost surely (a.s.), and that

The first inequality implies that $\|\lambda_{i_{r}}^{r}-\lambda_{i_{r}}^{r-1}\|\to 0$. Combining this with equation (5) yields $\|x_{i_{r}}^{r}-z^{r-1}\|\to 0$, which further implies that $\|z^{r}-z^{r-1}\|\to 0$. By utilizing (8b) – (8c), we can conclude that

That is, almost surely the successive differences of all the primal and dual variables go to zero. Then it is easy to show that every limit point of the sequence $(x^{r},z^{r},\lambda^{r})$ converge to a stationary solution of problem (2) (for example, see the argument in [14, Theorem 2]. Here we omit the full proof.

Part 1). We bound the gap in the following way (where the expectation is taking over the nature history of the algorithm):

where $\rm(a)$ is due to (5.1); $\rm(b)$ is true due to the nonexpansivness of the prox operator, and the Cauchy-Swartz inequality; in $\rm(c)$ we have used the definition of $u$ in (31) and the fact that $3L_{0}\leq\sum_{i=1}^{N}\eta_{i}=\frac{1}{\beta}$ [cf. Assumption A-(c)]. In the last inequality we have applied (45), which implies that

Note that $\eta_{i}$’s has to satisfy (48). Let us follow (11) and choose

So plugging the expression of $\beta$ into (52) and (53), we conclude

After plugging in the above inequity into (13), we obtain:

If we sum both sides over $r=1,\cdots,R$, we obtain:

Part 2). In order to prove the second part let us recycle inequality in (57) and write

Combining the above two inequalities, we conclude

where in the first equality we have used the relation $\frac{\alpha_{i}}{\beta}=\eta_{i}$ [cf. (52)]. Using a similar argument as in first part, we conclude that

4 Proof of Theorem 2.2

The first statement holds true largely due to [29, Theorem 4], and the second statement holds true due to [20, Lemma 2.1]; see detailed discussion after [29, Assumption 2]. Here the only difference with the statement [29, Theorem 4] is that the error bound condition (15) holds true globally. This is by the assumption that $Z$ is a compact set. Below we provide a brief argument.

From [29, Theorem 4], we know that when Assumption B is satisfied, we have that for any $\xi\geq\min_{z}f(z)$, there exists scalars $\tau$ and $\epsilon$ such that the following error bound holds

From Theorem 2.1 we know that $(x^{r},z^{r},\lambda^{r})$ converges to the set of stationary solutions of problem (2). Let $(x^{*},z^{*},\lambda^{*})$ be one of such stationary solution. Then by the definition of the $Q$ function and the fact that the successive differences of the gradients goes to zero (cf. (49)), we have

where $\bar{z}^{r}=\arg\min_{z\in Z^{*}}\|z^{r}-z\|.$ Therefore, combining the fact that $\|x^{r+1}-x^{r}\|\to 0$, $\|z^{r+1}-z^{r}\|\to 0$, $\|x^{r+1}_{i}-z^{r+1}\|\to 0$ and $\|\lambda^{r+1}-\lambda^{r}\|\to 0$ (cf. (87), (88)), it is easy to see that

where $\bar{x}^{r},\bar{\lambda}^{r}$ are defined similarly as $\bar{z}^{r}$.

Now we prove that the expectation of $\Delta^{r+1}:=Q^{r+1}-\bar{v}$ diminishes Q-linearly. All the expectation below is w.r.t. the natural history of the algorithm. The proof consists of the following steps: Step 1: There exists $\sigma_{1}>0$ such that

Step 3: There exists $\sigma_{2}>0$ such that

Step 4: There exists $\sigma_{3}>0$ such that the following relation holds true for all $r\geq\bar{r}$

These steps will be verified one by one shortly. But let us suppose that they all hold true. Below we show that linear convergence can be obtained.

Combining step 4 and step 2 we conclude that there exists $\sigma_{3}>0$ such that for all $r\geq\bar{r}$

which further implies that for $\sigma_{5}=\frac{\sigma_{4}}{\sigma_{1}}>0$, we have

Now let us verify the correctness of each step. Step 1 can be directly obtained from equation (12). Step 2 is exactly Lemma (2.2). Step 3 can be verified using a similar derivation as in (5.3)We simply need to replace $-z^{r-1}+\mbox{prox}_{h}^{1/\beta}[u^{r-1}-\beta\nabla g_{0}(z^{r-1})]$ in step (a) of (5.3) by $-z^{r}+\mbox{prox}_{h}^{1/\beta}[u^{r}-\beta\nabla g_{0}(z^{r})]$ and using the same derivation..

Below let us prove the step 4, which is a bit involved. From (7) we know that

The first term in RHS can be bounded as follows:

where $(a)$ is true due to the descent lemma; and $(b)$ comes from the Lipschitz continuity of the $\nabla g_{i}$.

Plugging the above bound into (5.4), we further have:

where in the first inequality we have used the fact that $\lambda^{r}_{i}=-\frac{1}{N}\nabla g_{i}(y^{r-1}_{i})$; cf . (27). Applying the Cauchy-Schwartz inequality we further have:

Now let us bound $\sum_{i=1}^{N}\frac{\eta_{i}}{2}\|x_{i}^{r+1}-\bar{z}^{r}\|^{2}$ in the above inequality:

Using the fact that $x_{i}^{r+1}=z^{r}$ when $i\neq i_{r}$ we further have:

Take expectation on both sides of the above equation and set $p_{i}=\alpha_{i}$, we obtain:

Combining equations (68) and (69), eventually one can find $\sigma_{3}>0$ such that

In summary, we have shown that Step 1 - 4 all hold true. Therefore we have shown that the NESTT-G converges Q-linearly. Q.E.D.

5 Some Key Properties of NESTT-E

To facilitate the following derivation, in this section we collect some key properties of NESTT-E.

First, for $i=i_{r}$, using the optimality condition for $x_{i}$ update step (18) we have the following identity:

Combined with the dual variable update step (19) we obtain

Second, the optimality condition for the $z$-update is given by:

6 Proof of Theorem 3.1

To prove this result, we need a few lemmas.

For notational simplicity, define new variables $\{\hat{x}^{r+1}_{i}\}$, $\{\hat{\lambda}_{i}^{r+1}\}$ by

These variables are the virtual variables generated by updating all variables at iteration $r+1$. Also define:

First, we need the following lemma to show that the size of the successive difference of the dual variables can be upper bounded by that of the primal variables. This is a simple consequence of (71); also see [R2, Lemma 2.1]. We include the proof for completeness.

Suppose assumption A holds. Then for NESTT-E algorithm, the following are true:

Proof. We only show the first inequality. The second one follows an analogous argument.

To prove (75a), first note that the case for $i\neq i_{r}$ is trivial, as both sides of (75a) are zero. For the index $i_{r}$, we have a closed-form expression for $\lambda^{r}_{i_{r}}$ following (71). Notice that for any given $i$, the primal-dual pair $(x_{i},\lambda_{i})$ is always updated at the same iteration. Therefore, if for each $i$ we choose the initial solutions in a way such that $\lambda_{i}^{0}=-\nabla g_{i}(x_{i}^{0})$, then we have

Combining (76) with Assumption A-(a) yields the following:

Second, we bound the successive difference of the potential function.

Suppose Assumption A holds true. Then the following holds for NESTT-E

Proof. First let us split $L^{r+1}-L^{r}$ in the following way:

The first two terms in (78) can be bounded by

where in $\rm(a)$ we have used (19), and the fact that $\lambda_{i}^{r+1}-\lambda_{i}^{r}=0$ for all variable blocks except $i_{r}$th block; $\rm(b)$ is true because of Lemma 5.1.

The last two terms in (78) can be written in the following way:

The first two terms in (80) characterizes the change of the Augmented Lagrangian before and after the update of $x$. Note that $x$ updates do not directly optimize the augmented Lagrangian. Therefore the characterization of this step is a bit involved. We have the following:

$\rm(a)$ is true because $L(x,z,\lambda)$ is strongly convex with respect to $x_{i}$.

$\rm(b)$ is true because when $i\neq i_{r}$, we have $x^{r+1}_{i}=x_{i}^{r}$.

$\rm(c)$ is true because $x^{r+1}_{i_{r}}$ is optimal solution for the problem $\min U_{i_{r}}(x_{i_{r}},z^{r+1},\lambda_{i_{r}}^{r})$ (satisfying (70)), and we have used the optimality of such $x^{r+1}_{i_{r}}$.

$\rm(d)$ and $\rm(e)$ are due to Lemma 5.1.

Similarly, the last two terms in (80) can be bounded using equation (70) and the strong convexity of function $L$ with respect to the variable $z$. Therefor We have:

Combining equations (79), (81) and (82), eventually we have:

Taking expectation on both side of this inequality with respect to $i_{r}$, we can conclude that:

where $p_{i}$ is the probability of picking $i$th block. The lemma is proved. Q.E.D.

Suppose that Assumption A is satisfied, then $L^{r}\geq\underline{f}$.

Proof. Using the definition of the augmented Lagrangian function we have:

where $\rm(a)$ is true because of equation (71); $\rm(b)$ follows Assumption A-(b); $\rm(c)$ follows Assumption A-(d). The desired result is proven. Q.E.D.

Proof of Theorem 3.1. We first show that the algorithm converges to the set of stationary solutions, and then establish the convergence rate.

Step 1. Convergence to Stationary Solutions. Combining the descent estimate in Lemma 5.2 as well as the lower bounded condition in Lemma 5.3, we can again apply the Supermartigale Convergence Theorem [4, Proposition 4.2] and conclude that

From Lemma 5.1 we have that the constraint violation is satisfied

The rest of the proof follows similar lines as in [14, Theorem 2.4]. Due to space limitations we omit the proof.

Step 2. Convergence Rate. We first show that there exists a $\sigma_{1}(\alpha)>0$ such that

From the optimality condition of the $z$ update (73) we have:

Using this, the first term in equation (90) can be bounded as:

where in the last inequality we have used the nonexpansiveness of the proximity operator.

Similarly, the optimality condition of the $x_{i}$ subproblem is given by

Applying this identity, the second term in equation (90) can be written as follows:

where $\rm(a)$ holds because of equation (92); $\rm(b)$ holds because of Lemma 5.1.

Finally, combining (91) and (93) leads to the following bound for proximal gradient

The two inequalities (94) – (95) imply that:

Let us set $C(\alpha)=\frac{\sigma_{1}(\alpha)}{\sigma_{2}(\alpha)}$ and take expectation on both side of the above equation to obtain:

Summing both sides of the above inequality over $r=1,\cdots,R$, we obtain:

Using the definition of $w^{m}=(x^{m},z^{m},\lambda^{m})$, and following the same line of argument as Theorem (2.1) we eventually conclude that

7 Proof of Theorem 3.2

where $\bar{z}^{r}=\arg\min_{z\in Z^{*}}\|z^{r}-z\|.$ Therefore, combining the fact that $\|x^{r+1}-x^{r}\|\to 0$, $\|z^{r+1}-z^{r}\|\to 0$, $\|x^{r+1}_{i}-z^{r+1}\|\to 0$ and $\|\lambda^{r+1}-\lambda^{r}\|\to 0$ [cf. (87), (88)], it is easy to see that

where $\bar{x}^{r},\bar{\lambda}^{r}$ are defined similarly as $\bar{z}^{r}$.

In what follows we will show that $\Delta:=L^{r+1}-\bar{v}$ decreases Q-linearly.

From the optimality condition for $z$ subproblem (73), we know that:

In what follows we bound $L(z^{r+1},x^{r},\lambda^{r})-\bar{v}$. Assume that $r>\bar{r}$, therefore $\bar{z}^{r+1}=\arg\min_{z\in Z^{*}}\|z^{r+1}-z\|$ satisfies $f(\bar{z})=\bar{v}$. We have the following

From the optimality condition of the $z$ subproblem we know that:

Rearranging the terms in the previous equation we have:

Plugging in (110) in (108) yields the following:

Overall, there exists $\sigma_{2}>0$ such that

where the inequality comes from the fact that $L^{r+1}-L(z^{r+1},x^{r},\lambda^{r})\leq 0$ [by (83) and the fact that $c_{i}<0$ for all $i$]. Considering the above equations we obtain:

Let us set $\rho=\frac{\sigma_{3}}{1+\sigma_{3}}<1$. Thus concluding the proof. Q.E.D.

8 Proof of Proposition 4.1

Applying the optimality condition on $z$ subproblem in (5.1) we have:

where the variable $u^{r+1}$ is given by (cf. (31))

Now from one of the key properties of NESTT-G [cf. Section 5.1, equation (30)], we have that

References