The complexity of primal-dual fixed point methods for ridge regression

Ademir Alves Ribeiro*, Peter Richtárik

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We study the ridge regression (L2 regularized least squares) problem and its dual, which is also a ridge regression problem. We observe that the optimality conditions describing the primal and dual optimal solutions can be formulated in several different but equivalent ways. The optimality conditions we identify form a linear system involving a structured matrix depending on a single relaxation parameter which we introduce for regularization purposes. This leads to the idea of studying and comparing, in theory and practice, the performance of the fixed point method applied to these reformulations. We compute the optimal relaxation parameters and uncover interesting connections between the complexity bounds of the variants of the fixed point scheme we consider. These connections follow from a close link between the spectral properties of the associated matrices. For instance, some reformulations involve purely imaginary eigenvalues; some involve real eigenvalues and others have all eigenvalues on the complex circle. We show that the deterministic Quartz method—which is a special case of the randomized dual coordinate ascent method with arbitrary sampling recently developed by Qu, Richtárik and Zhang—can be cast in our framework, and achieves the best rate in theory and in numerical experiments among the fixed point methods we study. Remarkably, the method achieves an accelerated convergence rate. Numerical experiments indicate that our main algorithm is competitive with the conjugate gradient method.

Original languageEnglish (US)
Pages (from-to)342-372
Number of pages31
JournalLinear Algebra and Its Applications
Volume556
DOIs
StatePublished - Nov 1 2018

Keywords

  • Fixed-point methods
  • Primal-dual methods
  • Ridge regression
  • Unconstrained minimization

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'The complexity of primal-dual fixed point methods for ridge regression'. Together they form a unique fingerprint.

Cite this