### Ademir Ribeiro (Federal University of Paraná, Brazil)

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

*Joint work with Peter Richtárik.*

*Thursday 5 March 2015 at 12.00, JCMB 4352B*

##### 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 can be formulated in several different but equivalent ways, in the
form of a linear system involving a structured matrix depending on a single
"stepsize" 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 stepsize 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.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*