To overcome this challenge, we focus on a strategy of randomly sampling blocks of coordinates proportionally to the determinant of the corresponding submatrix of \(\) , which we call determinantal sampling. Similar sampling schemes have been analyzed in the context of stochastic optimization before [1]}, [2]}. Recently, [3]} analyzed determinantal sampling for randomized block coordinate descent, however they imposed cardinality constraints on the block size, and as a result were unable to obtain a simple expression for \([(_{\hat{S}})^+]\) .
