Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling

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 $\bM$ instead of the true Hessian. The convergence analysis of the algorithm is challenging because of its complex dependence on the structure of $\bM$. 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 $\bM$, 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 $\bM$. Additionally, we provide a numerical evaluation of our analysis, demonstrating cases where determinantal sampling is superior or on par with uniform sampling.

References in corpus (7)

• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
• Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches
• Online Variance Reduction with Mixtures

Cited by in corpus (3)

• Exact expressions for double descent and implicit regularization via surrogate random design
• Sampling from a $k$-DPP without looking at all items
• Precise expressions for random projections: Low-rank approximation and randomized Newton