WIAS Preprint No. 2692, (2020)

Alternating minimization methods for strongly convex optimization


Authors

  • Tupitsa, Nazarii
  • Dvurechensky, Pavel
    ORCID: 0000-0003-1201-2343
  • Gasnikov, Alexander
  • Guminov, Sergey

2010 Mathematics Subject Classification

  • 90C30 90C25 68Q25

Keywords

  • Convex optimization, alternating minimization, block-coordinate method, complexity analysis

DOI

10.20347/WIAS.PREPRINT.2692

Abstract

We consider alternating minimization procedures for convex optimization problems with variable divided in many block, each block being amenable for minimization with respect to its variable with freezed other variables blocks. In the case of two blocks, we prove a linear convergence rate for alternating minimization procedure under Polyak-Łojasiewicz condition, which can be seen as a relaxation of the strong convexity assumption. Under strong convexity assumption in many-blocks setting we provide an accelerated alternating minimization procedure with linear rate depending on the square root of the condition number as opposed to condition number for the non-accelerated method.

Appeared in

Download Documents