Dual Space Preconditioning for Gradient Descent

Understand

The conditions of relative smoothness and relative strong convexity were recently introduced for the analysis of Bregman gradient methods for convex optimization.

• We introduce a generalized left-preconditioning method for gradient descent, and show that its convergence on an essentially smooth convex objective function can be guaranteed via an application of relative smoothness in the dual space.
• Our relative smoothness assumption is between the designed preconditioner and the convex conjugate of the objective, and it generalizes the typical Lipschitz gradient assumption.
• Under dual relative strong convexity, we obtain linear convergence with a generalized condition number that is invariant under horizontal translations, distinguishing it from Bregman gradient methods.