# Coordinate Descent for Variance-Component Models
## 3 Parameter-Expanded CD  
Since the basic CD Algorithm 1 is both expensive per coordinate update and is not amenable to standard convergence analysis [16; 17], we consider an alternative called the parameter-expanded CD or PX-CD. We argue that our novel coordinate-descent algorithm is both faster to converge and also amenable to simple convergence analysis because the existence and uniqueness assumption holds. This constitutes our main contribution. In the PX-CD, we use the supporting hyper-plane (first-order Taylor approximation) to the concave matrix function \(f(\mathbf{A})=\ln\det\mathbf{A}\), where \(\mathbf{A}\succ\mathbf{0}\). The supporting hyper-plane gives the bound [9]:  
\[\ln\det\mathbf{A}\leq\ln\det\mathbf{C}+\operatorname{tr}\Bigl{(}\mathbf{C}^{- 1}(\mathbf{A}-\mathbf{C})\Bigr{)},\]  
where \(\mathbf{C}\in\mathbb{R}^{n\times n}\) is an arbitrary PSD matrix, and equality is achieved if and only if \(\mathbf{C}=\mathbf{A}\). Replacing the log-determinant term in \(G\) with the above upper bound, we obtain the surrogate function,  
\[H(\mathbf{\Omega},\mathbf{C}):=\boldsymbol{y}^{\top}\mathbf{\Omega}^{-1} \boldsymbol{y}+\sum_{i=0}^{m}\gamma_{i}\operatorname{tr}(\mathbf{C}^{-1} \mathbf{V}_{i})+\ln\det(\mathbf{C})-n\geq G(\mathbf{\Omega}). \tag{9}\]  
The surrogate function \(H\) has \(\mathbf{C}\) as an extra variable in our optimization, which we set to be of the form:  
\[\mathbf{C}=\sum_{i=0}^{m}\tilde{\gamma}_{i}\mathbf{V}_{i},\]  
where \(\widetilde{\boldsymbol{\gamma}}=(\widetilde{\gamma}_{0},\widetilde{\gamma}_{ 1},\ldots,\widetilde{\gamma}_{m})\) are latent parameters. Similar to the MM algorithmic recipe [9], we then jointly minimize the surrogate function \(H\) with respect to both \(\boldsymbol{\gamma}\) and \(\widetilde{\boldsymbol{\gamma}}\) using CD. The most apparent way of selecting our coordinates is to cyclically update in the order:  
\[\gamma_{0}\to\gamma_{1}\to\ldots\to\gamma_{m}\to\widetilde{\boldsymbol{\gamma}},\]  
where the last update is a block update of the entire block \(\widetilde{\boldsymbol{\gamma}}\). In other words, the expanded parameters \(\widetilde{\boldsymbol{\gamma}}\) are treated as a block of coordinates that is updated in each cycle by searching through the coordinate hyper-plane rather than the single-coordinate directions. We refer to a full completion of updates in a single ordering as a \"cycle\" of updates. Suppose the initial guess for the parameters are \(\bigl{(}\boldsymbol{\gamma}^{(0)},\widetilde{\boldsymbol{\gamma}}^{(0)}\bigr{)}\), then, at the end of cycle \(t\), we denote the updated parameters as \((\boldsymbol{\gamma}^{(t)},\widetilde{\boldsymbol{\gamma}}^{(t)})\). In Theorem 1, we state that under certain conditions, the sequence \(\{(\boldsymbol{\gamma}^{(t)},\widetilde{\boldsymbol{\gamma}}^{(t)})\}_{t\geq 0}\) generated by PX-CD has limit-points, which are coordinate-wise minima for \(G\). Let \(\mathbf{\Omega}^{(t)}=\sum_{i=0}^{m}\gamma_{i}^{(t)}\mathbf{V}_{i}\) be the updated covariance matrix after the \(m+1\) original parameters have been updated in cycle \(t\). Then, as the inequality in (9) achieves equality if and only if \(\mathbf{C}=\mathbf{\Omega}\) the update for the expanded block parameters \(\widetilde{\boldsymbol{\gamma}}\) in cycle \(t\) is,  
\[\widetilde{\boldsymbol{\gamma}}^{(t)}=\operatorname*{arg\,min}_{\widetilde{ \boldsymbol{\gamma}}}H(\mathbf{\Omega}^{(t)},\sum_{i=0}^{m}\tilde{\gamma}_{i} \mathbf{V}_{i})=\boldsymbol{\gamma}^{(t)}.\]  
In practice, we simply store \(\mathbf{C}^{(t)}=\mathbf{\Omega}^{(t)}\) at the end of each cycle.