# Coordinate Descent for Variance-Component Models
## 3 Parameter-Expanded CD
### Updating Regime  
We now consider an alternative to the cyclic ordering of updates. Suppose we update the block \(\widetilde{\mathbf{\gamma}}\) after every co-ordinate update--that is, the updating order of one complete cycle is  
\[\gamma_{0}\to\widetilde{\mathbf{\gamma}}\to\gamma_{1}\to\widetilde{\mathbf{\gamma}}\to \ldots\to\gamma_{m}\to\widetilde{\mathbf{\gamma}}.\]  
This ordering regime satisfies the \"essentially cyclic\" condition whereby, in every stretch of \(2(m+1)\) updates, each component is updated at least once. We refer to CD with this ordering as parameter expanded-immediate coordinate descent (PXI-CD). In practice, this ordering implies updating the matrix \(\mathbf{C}\) after every update made to each \(\gamma_{k}\). Since the expression for \(h^{\prime}_{k}(x)\) requires one to evaluate \(\operatorname{tr}(\mathbf{C}^{-1}\mathbf{V}_{k})\) and \(\mathbf{C}\) is updated after every coordinate, we must re-compute \(\mathbf{C}^{-1}\) for each \(k\). This implies that each cycle in PXI-CD will be more expensive than PX-CD. However, we observe that in situations where \(\mathbf{V}_{i}\) is full rank and \(n\) is sufficiently large, the number of cycles needed to converge is significantly less than that required for PX-CD and basic CD. This results in PXI-CD being the most time-efficient algorithm when the scale of the problem is large. In Section 3.3, we show that, when \(\mathbf{V}_{i}\) is low-rank, re-computing \(\operatorname{tr}\bigl{(}\mathbf{C}^{-1}\mathbf{V}_{k}\bigr{)}\) comes at no additional-cost through the use of the Woodbury matrix identity. However, in this particular scenario, where \(\mathbf{V}_{k}\) are low-rank, the performance gain from PXI-CD is not as significant as when \(\mathbf{V}_{i}\) are full rank, and both PXI-CD and PX-CD show similar performance. Algorithm 2 summarizes both PX-CD and PXI-CD methods to obtain \(\hat{\mathbf{\gamma}}\). ```
input:\(\mathbf{y}\) and \([\mathbf{V}_{0},\mathbf{V}_{1},\ldots,\mathbf{V}_{m}]\) where \(\mathbf{V}_{0}=\mathbf{I}_{n}\)
1 Choose \(\gamma_{l}\in\{\mathbf{u}\in\mathbb{R}^{m+1}\mid u_{i}>0\}\)
2\(\mathbf{\Omega}\leftarrow\gamma_{0}\mathbf{I}+\sum_{i=1}^{m}\gamma_{i}\mathbf{V}_ {i}\)
3 repeat
4\(\mathbf{C}\leftarrow\mathbf{\Omega}\)
5 for\(k=0,1,\ldots,m\)do
6\(\operatorname{T}\leftarrow\operatorname{tr}\bigl{(}\mathbf{C}^{-1}\mathbf{V} _{k}\bigr{)}\)
7\(\mathbf{\Omega}_{-k}\leftarrow\mathbf{\Omega}-\gamma_{k}\mathbf{V}_{k}\)
8\(\gamma_{k}\leftarrow\operatorname*{arg\,min}_{x\geq 0}\left[\mathbf{y}^{ \top}(\mathbf{\Omega}_{-k}+x\mathbf{V}_{k})^{-1}\mathbf{y}+x\operatorname{T}\right]\) via Newton's Method
9\(\mathbf{\Omega}\leftarrow\mathbf{\Omega}_{-k}+\gamma_{k}\mathbf{V}_{k}\)
10 ifPXI-CDthen
11\(\mathbf{C}\leftarrow\mathbf{\Omega}\)
12
13 until termination test satisfied return\(\mathbf{\gamma},\mathbf{\Omega}\)
```  
**Algorithm 2** PX-CD and PXI-CD for \(G(\mathbf{\Omega})\)  
As mentioned previously, the novel parameter-expanded coordinate-descent algorithms, PX-CD and PXI-CD, are both amenable to standard convergence analysis. **Theorem 1** (PX-CD and PXI-CD Limit Points). : _For both PX-CD and PXI-CD in Algorithm 2, let \(\{\mathbf{\gamma}^{(t)},\hat{\mathbf{\gamma}}^{(t)}\}_{t\geq 0}\) be the coordinate-descent sequence. Then, either \(G(\sum_{k}\gamma_{k}^{(t)}\mathbf{V}_{k})\to-\infty\), or every limit-point of \(\{\mathbf{\gamma}^{(t)}\}_{t\geq 0}\) is a coordinate-wise minimum of (3). If we further assume that \(\mathbf{y}\
ot\in\operatorname{span}\{\mathbf{V}_{1},\ldots,\mathbf{V}_{m}\}<n\), then the sequence \(\{\mathbf{\gamma}^{(t)}\}_{t\geq 0}\) is bounded and \(G(\sum_{k}\gamma_{k}^{(t)}\mathbf{V}_{k})\to-\infty\) is ruled out._  
Proof. : Recall that \(\mathbf{\Omega}=\sum_{i=0}^{m}\gamma_{i}\mathbf{V}_{i}\) and \(\mathbf{C}=\sum_{i=0}^{m}\widetilde{\gamma}_{i}\mathbf{V}_{i}\). Denote \((x_{1},\ldots,x_{m+1}):=\mathbf{\gamma}\) and \(\mathbf{x}_{m+2}:=\widetilde{\mathbf{\gamma}}\in\mathbb{R}^{m+1}\) as well as \(\mathbf{x}:=(x_{1},\ldots,x_{m+1},\mathbf{x}_{m+2})\in\mathbb{R}^{2(m+1)}\).