Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Complexity of Primal-Dual Fixed Point Methods for Ridge Regression   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.

9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
37
The categories of this paper are: supr-con
28
The categories of this paper are: alg-geom
4
The categories of this paper are: cond-mat
14
The categories of this paper are: math-ph
34
The categories of this paper are: chem-ph
21
The categories of this paper are: adap-org
29
The categories of this paper are: funct-an
23
The categories of this paper are: solv-int
24
The categories of this paper are: dg-ga
0
The categories of this paper are: hep-ph
5
The categories of this paper are: gr-qc
10
The categories of this paper are: q-bio
35
The categories of this paper are: mtrl-th
20
The categories of this paper are: acc-phys