This work was supported by SNSF grant
407540_167212 through the NRP 75 Big Data program. Also, MD thanks
the NSF for funding via the NSF TRIPODS program.

Supplementary Material:
Convergence Analysis of Block Coordinate Algorithms
with Determinantal Sampling
PROOFS
DPPs
[Proof of Theorem REF ]
First, assume that \(\alpha =1\) . Since \(\succ \mathbf {0}\) , we have \(\det (_{SS})>0\)  for
all \(S\subseteq [d]\) . We will next use the following
standard determinantal formula which holds for any \(v\in ^d\)  and any
invertible matrix \(\) :

()v-1v = (+vv)
- ().

Applying this formula to the submatrices of \(\)  and denoting by \(v_S\) 
the sub-vector of \(v\)  indexed by \(S\) , we show that for any \(v\in ^d\) :

v[(S)+
]v =
S[d](SS)(+)vSSS-1vS
(REF ) =S[d](SS+vSvS)-(SS)(+)
=S ([+vv]SS) - S(SS)(+)
(Lemma ) =(++vv) - (+)(+)
(REF ) =(+) v(+)-1v(+)
=
v(+)-1v.

Since the above holds for all \(v\) , the equality also holds for the pd.
matrices. To obtain the result with \(\alpha \ne 1\) , it suffices to
replace \(\)  with \(\frac{1}{\alpha }\) .
[Proof of Lemma ]
The eigenvalues of \((\alpha +)^{-1}\)  are
\(\frac{\lambda _i}{\lambda _i+\alpha }\)  so

[|S|]  = i=1d ii +  =
i=1d ii + jk j
 = i < kd ii +
jk j  + i kd
ii + jk j
< (k-1)+ 1 = k,

which concludes the proof.

Convergence Analysis
[Proof of Theorem ]
\(\sigma _1 & \stackrel{(\ref {eq:sigma_1})}{=} & \lambda _{\min }\left( ^{1/2} \left({\alpha }+ \right)^{-1} ^{1/2} \right) \\& = & \lambda _{min} \left( \left( {\alpha }^{-1} + \right)^{-1} \right)\\& = & \frac{1}{\lambda _{\max }\left({\alpha } ^{-1} + \right)} = \frac{1}{1 + {\alpha }\lambda _{\max }(^{-1})} \\& = & \frac{ \mu }{ \mu + \alpha } \\\) 
where \(\mu = \lambda _{\min }()\) .
[Proof of Proposition ]
By definition,
\( \frac{1}{\sigma (k+1)} = 1 + \frac{\sum _{i>k}^{d}\lambda _i}{\lambda _d} = 1 + \frac{\sum _{i>{k-1}}^{d}\lambda _i - \lambda _{k}}{\lambda _d} = \frac{1}{\sigma (k)} - \frac{\lambda _{k}}{\lambda _d} \) 
Rearranging,
\( \frac{1}{\sigma (k)} = \frac{1}{\sigma (k+1)} + \frac{\lambda _{k}}{\lambda _d} \Rightarrow \sigma (k) = \frac{\sigma (k+1)\lambda _d}{\lambda _d + \lambda _k \sigma (k+1)} \) 
Dividing the denominator and the numerator by \(\lambda _d\)  finishes the proof.

Dual convergence rate
The dual convergence rate established in [1]} relies on the
notion of expected separable over-approximation. Namely, the existence of
\(v \in ^d\)  s.t. \([_S] \preceq (p \circ v)\) , where \(p\)  is
the vector of marginal probabilities. In case of DPP sampling, one can
choose \(v = ()\circ ((+ \alpha )^{-1})^{-1}\) ,
and apply dual convergence results established in this literature. By
\(\circ \)  we denote element-wise product.

LEVERAGE SCORE SAMPLING VS DPP SAMPLING
We perform a simple experiment on the Gaussian Mixtures dataset where the matrix has a sparse spectrum. In Figure REF  we see that the optimization process is influenced minimally.
<FIGURE>
RELATIVE SMOOTHNESS AND RELATIVE STRONG CONVEXITY
Recent works such as [2]} and [3]} introduce the concepts of relative-smoothness, relative strong convexity and \(c\) -stability. These are weaker conditions than assumed in this paper. With these conditions, the proof techniques used to analyze coordinate descent algorithms are applicable to Newton-like algorithms, where instead of a fixed matrix \(\) , the actual Hessian \((x)\)  can be used. The extension to \(c-\) stability is done trivially in Theorem 2 of [3]}, here we focus on a slightly more elaborate connection with relative smoothness and relative strong-convexity.
[[2]}]
There exists a constant \(\tilde{L}\ge \tilde{\mu }\)  such that for all \(x,y \in \subseteq ^d\) , where \(:=\lbrace x \in ^d : f(x)\le f(x_0)\rbrace \) :
\(f(x) \le f(y) + {\nabla f(y),x} + \frac{\tilde{L}}{2}{x-y}_{(y)}\) 
and
\(f(x) \ge f(y) + {\nabla f(y),x} + \frac{\tilde{\mu }}{2}{x-y}_{(y)}.\) 
Now the task is to analyze the algorithm with the following update rule, which is identical to general Newton rule when \(S = [d]\) ,
\(x_{k+1} = x_k - \gamma ((x_k)_{S_k})^+ \nabla f(x_k).\) 
We fix a particular choice of \(\gamma = 1/\tilde{L}\) . This should be contrasted with the update rule \((\ref {eq:update})\) .
Now given these assumption, we are able to show that the constant akin to \(\sigma (\hat{S})\)  appears in the analysis of this algorithm by utilizing the notions from [2]}. We sacrifice generality for the sake of brevity, and assume that range of \((x)\)  spans whole \(^d\)  for each \(x \in \) . Then, the following quantities resembling \(\sigma (\hat{S})\)  appear in the convergence analysis of the update rule (REF )
\(\hat{\sigma }(\hat{S},x) = \lambda _{\min } \left( _{\hat{S}} \left[ ^{1/2}(x)((x)_{\hat{S}})^+ (x)^{1/2} \right] \right)\) 
and
\(\hat{\sigma }(\hat{S}) = \min _{x\in } \hat{\sigma }(\hat{S},x) \) 
[Theorem 3.1 of [2]}, modified]
Let \(f\)  satisfy Assumption , and let \((x)\)  be the Hessian at \(x\)  having range that spans whole \(^d\)  for all \(x\) . Then
\( _{\hat{S}}[ f(x_{k+1}) - f(x^*) ] \le \left( 1 - \frac{\hat{\sigma }(\hat{S},x_k)\mu }{L} \right) (f(x_k) - f(x^*), \) 
and
\( _{\hat{S}}[ f(x_{k}) - f(x^*) ] \le \left( 1 - \frac{\hat{\sigma }(\hat{S})\mu }{L} \right)^k (f(x_0) - f(x^*), \) 
where \( \hat{\sigma }(\hat{S}) = \min _{x\in } \hat{\sigma }(\hat{S},x)\)  as in Equation (REF ).
Minimizing the upper bound in (REF ) restricted to coordinates in \(S_k\) , we arrive at,
\(f(x_{k+1}) - f(x_k) & \stackrel{(\ref {eq:smooth})}{\le }& - \frac{1}{2\tilde{L}} {\nabla f(x_k), ((x_k)_{S_k})^+ \nabla f(x_k)} \\[f(x_{k+1}) - f(x_k)] & \le & - \frac{1}{2\tilde{L}} {\nabla f(x_k),_{\hat{S}}[((x_k)_{S_k})^+] \nabla f(x_k)}\\& \stackrel{(\ref {eq:rconvex}), (\ref {eq:sigmahat})}{\le }& -\frac{\mu }{L}\hat{\sigma }(\hat{S},x) (f(x_k) - f(x^*))\\& \le & -\frac{\mu }{L}\hat{\sigma }(\hat{S}) (f(x_k) - f(x^*))\\\) 
rearranging finishes the proof.
The following corollary states that with DPP sampling, the update rule in (REF ) can have a more interpretable convergence rate than stated in the Theorem .
[of Theorem ]
Under the assumption of Theorem , let additionally \(S_k\)  be a sample from sampling \(\hat{S}_k \sim (\frac{1}{\alpha } (x_k))\) , then
\( _{\hat{S}_k}[ f(x_{k+1}) - f(x^*) ] \le \left( 1 - \left(\frac{\lambda (x_k) }{\lambda (x_k) + \alpha }\right)\frac{\mu }{L} \right) (f(x_k) - f(x^*), \) 
where \(\lambda (x_k) = \lambda _{\min }((x_k))\) .
The following lemma relates the complexity quantity defined above to the definition of \(\sigma (\hat{S})\)  used in the main body of this paper. Note that \(\hat{\sigma }\)  is larger than \(\sigma \) , even if the fixed over-approximation exists, as previously we assumed the over-approximation to be valid globally not just in \(\) .
If for all \(x \in \) , \(\succeq (x) \succeq \kappa \succ 0\) , then
\( \hat{\sigma }(\hat{S}) \ge \kappa \sigma (\hat{S}).\) 
The relative smoothness, and strong-convexity can be chosen to be \(\tilde{L} = 1\) , and \(\tilde{\mu } = 1\) , respectively.
\(\hat{\sigma }(\hat{S}) & = & \min _{x\in } \min _{v \in ^d} \frac{ {v,_{\hat{S}} \left[ ^{1/2}(x)((x)_{\hat{S}})^+ (x)^{1/2} \right]v }}{{{v}_2^2}} = \min _{v \in ^d} \min _{x\in } \frac{ {v,_{\hat{S}} \left[ ^{1/2}(x)((x)_{\hat{S}})^+ (x)^{1/2} \right]v }}{{v}_2^2} \\& \ge & \min _{v \in ^d} \frac{ {v,_{\hat{S}} \kappa \left[ ^{1/2}(_{\hat{S}})^+ ^{1/2} \right]v }}{{v}_2^2} = \kappa \sigma (\hat{S})\) 

OTHER SAMPLINGS
The convergence properties of RNM with determinantal sampling depend solely on the spectral properties of \(\) . This is not true of other common samplings such as \(\tau \) -nice. Indeed we can improve or worsen the performance of \(\tau \) -nice sampling when \(\)  is transformed via spectrum preserving operation such as unitary transformation
\(\leftarrow ^\top , \text{ where } ^\top = .\) 
Suppose that we are given an eigenvalues of the matrix \(\) , for any sampling \(\hat{S}\)  is it possible to find a spectrum preserving rotation such that \(\sigma (\hat{S})\)  is at least as small as \(\sigma (\hat{S}_{})\)  which corresponds to DPP sampling with the same expected cardinality? The answer turns out to be negative, and we show counter-example.
[Counter-example]
Let \(\hat{S}_1\)  be a sampling such that \([n]\)  is sampled with \(1/2\)  probability and \(\emptyset \)  and \(1/2\)  probability. The expected size of the subset \([|\hat{S}_1|] = d/2\)  and \(\sigma (\hat{S}_1) = \frac{1}{2}\)  irrespective of the matrix \(\) .
Suppose matrix \(\)  has degenerate spectrum such that \(\lambda \)  is eigenvalue with multiplicity \(d/2\)  and \(\mu \)  is eigenvalue with \(d/2\)  multiplicity where \(\lambda < \mu \) . In order s.t. \([|S_{}|] = \frac{d}{2}\) , \(\alpha = \sqrt{\lambda \mu }\) , then \(\sigma (\hat{S}_{}) < \frac{1}{2}\) .

In what circumstances does DPP sampling perform better than a uniform sampling? First, we consider circumstances where uniform sampling is optimal.
Uniform sampling
It is important to allow for variation in the off-diagonal of \(\) . If we consider only diagonal \(\) , the optimal sampling is uniform sampling.
  Let \(\)  be diagonal. The quantity \(\sigma (\hat{S})\)  of a sampling over a power set \(P([d])\)  constrained by \([|\hat{S}|] = k\)  is maximized for uniform samplings.

[Proof of Lemma REF  ]
We want to maximize the minimum eigenvalue of a matrix \(^{1/2} [(_S)^{-1} ] ^{1/2}\) . For a diagonal \(\)  we know that \((_S)^{-1} = (^{-1})_S\) . Hence, \(^{1/2} [(_S)^{-1} ] ^{1/2} (p)\) , where \(p\)  is a vector of marginals \(p_i = P(i \in \hat{S})\) . Hence, the minimum eigenvalue is the minimum marginal probability subject to a constraint that \([|S|] = \sum _{j=1}^{d}P(j \in \hat{S}) \le k\) . This leads to an optimum where \(P(i \in \hat{S}) = P(j \in \hat{S})\)  for all \(i,j \in [d]\) . Hence the optimal sampling distribution is uniform.

Parallel Sampling
The parallel extension of the update method REF  has been considered in [8]} and [3]}. Namely, the authors consider a case, when the updates with \(c\)  machines are aggregated together to form a single update in the form \(\approx \frac{1}{b}\sum _{j=1}^{c} (_{S_j})^+\) , where \(b\)  is the aggregating parameter. It is known that for parallel disjoint samplings the convergence rate increases linearly with the number of processors. For independent samplings the aggregating parameter \(b\)  depends on the quantity,
\( \theta (\hat{S}) = \lambda _{\max } (^{1/2}[(_{\hat{S}})^+] ^{1/2} ) \) 
which in the case of DPP sampling is equal to \(\theta = \frac{\lambda _1}{\lambda _1 + \alpha }\) . The quantity \(\theta (\hat{S}) \in [\sigma (\hat{S}),1]\) , and as \(\theta \rightarrow 1\) , the aggregation operation becomes averaging \(b \rightarrow c\) . For DPP sampling, we can see an inverse relationship between increasing \(\sigma (\hat{S})\)  by increasing block size, which inherently makes the parallelization problem more difficult by increasing \(\theta (\hat{S})\) .
