A randomized coordinate descent method with volume sampling

DOI10.1137/19M125532XzbMATH Open1447.90031arXiv1904.04587OpenAlexW3042245584MaRDI QIDQ3300772FDOQ3300772

Authors: Anton Rodomanov, Dmitry Kropotov 

Publication date: 30 July 2020

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: 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. Our theoretical results show that, by increasing the size of the subsets, it is possible to accelerate the method up to the factor which depends on the spectral gap between the corresponding largest eigenvalues of the curvature matrix. Several numerical experiments confirm our theoretical conclusions.

Full work available at URL: https://arxiv.org/abs/1904.04587

Recommendations

• Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
• A flexible coordinate descent method
• Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
• On optimal probabilities in stochastic coordinate descent methods
• Efficiency of coordinate descent methods on huge-scale optimization problems

zbMATH Keywords

convex optimizationrandomized algorithmsconvergence rateunconstrained minimizationcoordinate descent methodsvolume sampling

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Smooth minimization of non-smooth functions
• Title not available (Why is that?)
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Parallel coordinate descent methods for big data optimization
• Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
• Coordinate descent algorithms
• Stochastic dual coordinate ascent methods for regularized loss minimization
• On the convergence of block coordinate descent type methods
• Smoothing and first order methods: a unified framework
• Random block coordinate descent methods for linearly constrained optimization over networks
• Matrix approximation and projective clustering via volume sampling
• An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
• Efficiency of the accelerated coordinate descent method on structured optimization problems
• Reverse iterative volume sampling for linear regression

Cited In (3)

• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
• Reverse iterative volume sampling for linear regression
• Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.

This page was built for publication: A randomized coordinate descent method with volume sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300772)