Randomized Fast Subspace Descent Methods

MaRDI QIDQ6342661zbMATH OpenFDO

Authors Long Chen, X. Hu, H. W. Wu

Publication date 11 June 2020

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25)

Abstract: Randomized Fast Subspace Descent (RFASD) Methods are developed and analyzed for smooth and non-constraint convex optimization problems. The efficiency of the method relies on a space decomposition which is stable in $A$-norm, and meanwhile, the condition number $kapp{a}_A$ measured in $A$-norm is small. At each iteration, the subspace is chosen randomly either uniformly or by a probability proportional to the local Lipschitz constants. Then in each chosen subspace, a preconditioned gradient descent method is applied. RFASD converges sublinearly for convex functions and linearly for strongly convex functions. Comparing with the randomized block coordinate descent methods, the convergence of RFASD is faster provided $kapp{a}_A$ is small and the subspace decomposition is $A$-stable. This improvement is supported by considering a multilevel space decomposition for Nesterov's `worst' problem.

This page was built for publication: Randomized Fast Subspace Descent Methods

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