A Randomized Coordinate Descent Method with Volume Sampling

Understand

We analyze the coordinate descent method with a new coordinate selection strategy, called volume sampling.

• This strategy prescribes selecting subsets of variables of certain size proportionally to the determinants of principal submatrices of the matrix, that bounds the curvature of the objective function.
• In the particular case, when the size of the subsets equals one, volume sampling coincides with the well-known strategy of sampling coordinates proportionally to their Lipschitz constants.
• For the coordinate descent with volume sampling, we establish the convergence rates both for convex and strongly convex problems.