A Simple Algorithm for Nuclear Norm Regularized Problems
Abstract
Optimization problems with a nuclear norm regularization, such as e.g. low norm matrix factorizations, have seen many applications recently. We propose a new approximation algorithm building upon the recent sparse approximate SDP solver of (Hazan, 2008). The experimental efficiency of our method is demonstrated on large matrix completion problems such as the Netflix data set. The algorithm comes with strong convergence guarantees, and can be interpreted as a first theoretically justified variant of Simon-Funk-type SVD heuristics. The method is free of tuning parameters, and very easy to parallelize.
Cite
Text
Jaggi and Sulovský. "A Simple Algorithm for Nuclear Norm Regularized Problems." International Conference on Machine Learning, 2010.Markdown
[Jaggi and Sulovský. "A Simple Algorithm for Nuclear Norm Regularized Problems." International Conference on Machine Learning, 2010.](https://mlanthology.org/icml/2010/jaggi2010icml-simple/)BibTeX
@inproceedings{jaggi2010icml-simple,
title = {{A Simple Algorithm for Nuclear Norm Regularized Problems}},
author = {Jaggi, Martin and Sulovský, Marek},
booktitle = {International Conference on Machine Learning},
year = {2010},
pages = {471-478},
url = {https://mlanthology.org/icml/2010/jaggi2010icml-simple/}
}