Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling

Mojmir Mutny, Michal Derezinski, Andreas Krause

Abstract

We analyze the convergence rate of the Randomized Newton Method (RNM) for smooth and convex objectives, which utilizes random coordinate blocks of a Hessian-over-approximation matrix $M$. While analyzing such algorithms is typically difficult due to complex structural dependencies, we demonstrate that determinantal sampling of coordinate blocks leads to a convergence rate that depends solely on the eigenvalue distribution of $M$. We derive a new expectation formula for determinantal point processes (DPPs) that provides an analytically tractable form for the update step. Our results show that determinantal sampling allows for identifying optimal subset sizes and can yield exponential speedups for problems with rapidly decaying spectra, such as kernel methods.

Introduction: The Efficiency Trade-off

In large-scale optimization, practitioners often choose between Coordinate Descent and Newton’s Method. Coordinate Descent is computationally inexpensive per iteration but requires many steps to converge. Conversely, Newton’s Method converges rapidly but necessitates the inversion of a massive Hessian matrix, which is often computationally prohibitive.

The Randomized Newton Method (RNM) seeks a middle ground by performing Newton-like updates on randomly selected blocks of coordinates using a fixed over-approximation of the Hessian, $M$. However, determining the optimal block size and predicting performance based on data properties has remained a challenge due to the complex combinatorial nature of block selection. Until now, there was no clear way to determine the optimal block size or predict performance based on the data's properties.

Determinantal Sampling and the Spectral Connection

This work introduces Determinantal Point Processes (DPPs) to the RNM framework. Instead of uniform selection, coordinate blocks are sampled with probability proportional to the determinant of the corresponding submatrix of $M$. The core theoretical contribution is a new expectation formula: $$\mathbb{E}[(M_{\hat{S}})^+] = (\alpha I + M)^{-1}$$ where $M_{\hat{S}}$ is the sparsified matrix for the chosen block and $\alpha$ is a parameter controlling the expected block size. This formula simplifies a complex probabilistic sum into a regularized inverse of the full matrix, directly linking convergence rates to the eigenvalues of $M$.

A key insight is that for problems where eigenvalues decay quickly (e.g., Kernel Ridge Regression), a small number of coordinates can capture most of the necessary information for a high-quality update. In such cases, increasing the block size can lead to an exponential increase in the convergence rate. Furthermore, determinantal sampling inherently prefers "diverse" sets of coordinates, making it much more robust for complex, clustered datasets than uniform sampling.

Empirical Evaluation and Results

The theory was validated using synthetic data and real-world datasets, including the UCI Superconductivity dataset (linear ridge regression) and the UCI Cpusmall dataset (kernel ridge regression).

Time to convergence on real-world datasets (Superconductivity and Cpusmall) as a function of expected subset size.

As shown in Figure 3, the theory accurately predicts the "sweet spot" for block size. For the superconductivity dataset, the optimal block size aligns with the feature dimensionality, as predicted for linear kernels. Furthermore, determinantal sampling (dpp) often matches or outperforms uniform sampling (nice), particularly as the subset size increases.

Comparison of iteration count and wall-clock time between DPP and uniform (nice) sampling across different dimensions.

Figure 5 highlights the trade-off between iteration count and wall-clock time. While larger blocks reduce the number of iterations required to reach a target accuracy $\epsilon$, they also increase the per-iteration cost ($O(k^3)$). Determinantal sampling consistently requires fewer iterations than uniform sampling to achieve the same accuracy, especially in heterogeneous datasets where diversity in coordinate selection is crucial. The theory correctly identifies that if the spectrum decays fast enough, the massive reduction in iterations makes larger blocks faster in terms of total wall-clock time.

Conclusion

By leveraging the mathematical properties of DPPs, this research provides the first analytically tractable convergence analysis for RNM. The ability to link optimization performance directly to the spectral properties of the Hessian over-approximation allows for principled selection of block sizes. While the computational cost of exact DPP sampling remains a consideration, the theoretical framework established here opens new avenues for optimizing randomized second-order methods in large-scale machine learning.

Summary updated

Abstract

We analyze the convergence rate of the randomized Newton-like method introduced by Qu et. al. (2016) for smooth and convex objectives, which uses random coordinate blocks of a Hessian-over-approximation matrix M instead of the true Hessian. The convergence analysis of the algorithm is challenging because of its complex dependence on the structure of M. However, we show that when the coordinate blocks are sampled with probability proportional to their determinant, the convergence rate depends solely on the eigenvalue distribution of matrix M, and has an analytically tractable form. To do so, we derive a fundamental new expectation formula for determinantal point processes. We show that determinantal sampling allows us to reason about the optimal subset size of blocks in terms of the spectrum of M. Additionally, we provide a numerical evaluation of our analysis, demonstrating cases where determinantal sampling is superior or on par with uniform sampling.
BibTeX
@inproceedings{mutny2020convergence,
  author = {Mojmir Mutny and Michal Derezinski and Andreas Krause},
  title = {{Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=NYD4OTmd5R},
}
Figure