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

DOI10.1016/J.LAA.2018.07.017zbMATH Open1398.65128arXiv1801.06354OpenAlexW2964118231MaRDI QIDQ1669015FDOQ1669015

Authors: Ademir Alves Ribeiro, Peter Richtárik 

Publication date: 29 August 2018

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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'{a}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.

Full work available at URL: https://arxiv.org/abs/1801.06354

Recommendations

• A new accelerated algorithm for ill-conditioned ridge regression problems
• Stochastic primal dual fixed point method for composite optimization
• On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
• Variant of greedy randomized Kaczmarz for ridge regression
• Coordinate Descent Face-Off: Primal or Dual?

zbMATH Keywords

ridge regressionfixed-point methodsunconstrained minimizationprimal-dual methods

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37)

Cites Work

• Ridge Regression: Biased Estimation for Nonorthogonal Problems
• Parallel iterative methods for sparse linear systems
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Fast low-rank modifications of the thin singular value decomposition
• Title not available (Why is that?)
• Stochastic dual coordinate ascent methods for regularized loss minimization
• Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
• On the dual formulation of regularized linear systems with convex risks
• A faster algorithm for ridge regression of reduced rank data
• Solving multicollinearity problem using ridge regression models
• A new accelerated algorithm for ill-conditioned ridge regression problems

Cited In (3)

• Primal-dual fixed point methods for regularized least-squares problems
• Title not available (Why is that?)
• A new accelerated algorithm for ill-conditioned ridge regression problems

This page was built for publication: The complexity of primal-dual fixed point methods for ridge regression

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