Fast proximal algorithms for Self-concordant function minimization with application to sparse graph selection

Anastasios Kyrillidis, Volkan Cevher

Abstract

The convex ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -regularized log det divergence criterion has been shown to produce theoretically consistent graph learning. However, this objective function is challenging since the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -regularization is nonsmooth, the log det objective is not globally Lipschitz gradient function, and the problem is high-dimensional. Using the self-concordant property of the objective, we propose a new adaptive step size selection and present the (F)PS ((F)ast Proximal algorithms for Self-concordant functions) algorithmic framework which has linear convergence and exhibits superior empirical results as compared to state-of-the-art first order methods.
BibTeX
@inproceedings{kyrillidis2013fast,
  author = {Anastasios Kyrillidis and Volkan Cevher},
  title = {{Fast proximal algorithms for Self-concordant function minimization with application to sparse graph selection}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2013},
  doi = {10.1109/icassp.2013.6638935},
}

Loading related content...

Figure