Randomized Fast Subspace Descent Methods

Understand

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 $\kappa_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.