We study a block coordinate descent algorithm
first introduced by [1]}. In each iteration of this algorithm, we sample a block of coordinates and then solve a Newton step on the chosen coordinate subspace.
However, in place of the true Hessian, a fixed over-approximation matrix \(\)  is used for the sake of efficiency. The Newton step is computed on a sparsified version of this matrix with all but the selected coordinates set to zero, denoted \(_{\hat{S}}\)  (see Section REF  for the complete notation).
Originally, [1]} called this method Stochastic Dual Newton Ascent (SDNA), appealing to the fact that it operates in a dual ERM formulation. Later, it was also called a Stochastic Newton method [3]}, while we use the name Randomized Newton Method (RNM) following [4]}\(\endcsname \)[4]} consider a more general algorithm, relying on the novel assumptions of relative smoothness and convexity. We discuss this setting in Appendix .
.
