# Coordinate Descent for Variance-Component Models
## 2 Basic Coordinate Descent
### Convergence  
An interesting question is whether the sequence generated in Algorithm 1 converges to a local minimum of the objective function (3) (which is assumed to have a global minimum). To make a general point about the convergence theory, take \(\mathcal{C}\) to be the set of limit points of a coordinate-descent sequence \(\{\mathbf{\gamma}^{(t)}\}\). It is well-known [16; 17] that the following existence and uniqueness assumption:  
\[g_{k}(x)=G(\mathbf{\Omega}_{-k}+x\mathbf{V}_{k})\text{ has a unique (global) minimizer for }x\geq 0 \tag{8}\]  
is one of the simplest sufficient conditions that ensures the set \(\mathcal{C}\) is not empty and contains only singletons. Assuming that the existence and uniqueness assumption holds for a given coordinate-descent algorithm and \(\mathbf{\gamma}^{*}\in\mathcal{C}\) then, by construction, \(\mathbf{\gamma}^{*}\) is a global _coordinate-wise minimum_ of (3)--that is, one cannot reduce the value of the objective function by moving along each of the coordinate directions (that is, \(G(\mathbf{\Omega}_{-k}+x\mathbf{V}_{k})\geq G(\mathbf{\Omega}_{-k}+\mathbf{\gamma}_{k}^{*} \mathbf{V}_{k})\) for each \(k\) and all \(x\geq 0\)). Even if \(\gamma^{*}\in\mathcal{C}\) is a coordinate-wise minimum, it may not be a local minimum of (3). It may well be a saddle point of (3). For example, the function \(f(\gamma_{1},\gamma_{2})=\gamma_{1}^{2}+\gamma_{2}^{2}-5\gamma_{1}\gamma_{2}\) does not have a local minimum at zero (\(f(\gamma,\gamma)=-3\gamma^{2}\) indicating that a minimum does not even exist); however, it has a coordinate-wise minimum at \((\gamma_{1},\gamma_{2})=(0,0)\). Thus, it is important to remember that the set of local minima of the optimization problem (3) is a subset of \(\mathcal{C}\) because \(\mathcal{C}\) may contain coordinate-wise minima, which are still saddle points of (3). One positive aspect is that the saddle points found by any coordinate-descent algorithm (under the existence and uniqueness assumption) are a subset of all the saddle points of (3) because they are constrained to be coordinate-wise minima. Stated another way, the set \(\mathcal{C}\) consists of either local minimizers or saddle points that look like coordinate-wise minimizers. Either way, there is simply no guarantee that any of our coordinate-descent procedures in this paper will converge to a strict local minimum of (3), see [16; 18] for more in-depth discussions. Of course, this is an issue for any of the existing optimization algorithms for (3) (MM and EM algorithms simply being a special case of coordinate descent, and [PERSON]'s method known for convergence only when initialized near a local minimum), and thus it should not be viewed as a particular disadvantage of our proposals. Unfortunately, the existence and uniqueness assumption (8) cannot be used to deal with the convergence of the basic CD Algorithm 1. This is because \(g_{k}(x)\) can exhibit multiple local minima, as illustrated next. Suppose \(n=2\), then from Equation (7), we have  
\[g_{k}(x)=\frac{\alpha_{k,1}^{2}}{d_{k,1}x+1}+\ln(1+d_{k,1}x)+\frac{\alpha_{k,2 }^{2}}{d_{k,2}x+1}+\ln(1+d_{k,2}x)+\text{const.}\]  
In Figure 1, we observe two minimizers for \(g_{k}(x)\) when \(\alpha_{k}=(1.2,3)\) and \(\mathbf{d}_{k}=(10,0.2)\), respectively. This implies that the existence and uniqueness assumption does not hold for the basic implementation of CD, and we cannot ensure that accumulation points of the sequence \(\{\gamma^{(t)}\}\) are coordinate-wise minima of \(G\). **Example 1** (Sufficient Conditions for a Unique Minimum). : _In this example, we show that strong conditions are needed for the existence and uniqueness assumption to hold, making the basic CD Algorithm 1 less than attractive. Suppose \(\delta:=\frac{1}{n}\sum_{j=1}^{n}\alpha_{k,j}^{2}>1\) and there is a constant \(d>0\) such that \(d_{k,j}=d\) for all \(j=1,\ldots,n\).