Regularization Paths with Guarantees for Convex Semidefinite Optimization

Joachim Giesen, Martin Jaggi, Soeren Laue
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:432-439, 2012.

Abstract

We devise a simple algorithm for computing an approximate solution path for parameterized semidefinite convex optimization problems that is guaranteed to be epsilon-close to the exact solution path. As a consequence, we can compute the entire regularization path for many regularized matrix completion and factorization approaches, as well as nuclear norm or weighted nuclear norm regularized convex optimization problems. This also includes robust PCA and variants of sparse PCA. On the theoretical side, we show that the approximate solution path has low complexity. This implies that the whole solution path can be computed efficiently. Our experiments demonstrate the practicality of the approach for large matrix completion problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-giesen12, title = {Regularization Paths with Guarantees for Convex Semidefinite Optimization}, author = {Giesen, Joachim and Jaggi, Martin and Laue, Soeren}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {432--439}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/giesen12/giesen12.pdf}, url = {https://proceedings.mlr.press/v22/giesen12.html}, abstract = {We devise a simple algorithm for computing an approximate solution path for parameterized semidefinite convex optimization problems that is guaranteed to be epsilon-close to the exact solution path. As a consequence, we can compute the entire regularization path for many regularized matrix completion and factorization approaches, as well as nuclear norm or weighted nuclear norm regularized convex optimization problems. This also includes robust PCA and variants of sparse PCA. On the theoretical side, we show that the approximate solution path has low complexity. This implies that the whole solution path can be computed efficiently. Our experiments demonstrate the practicality of the approach for large matrix completion problems.} }
Endnote
%0 Conference Paper %T Regularization Paths with Guarantees for Convex Semidefinite Optimization %A Joachim Giesen %A Martin Jaggi %A Soeren Laue %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-giesen12 %I PMLR %P 432--439 %U https://proceedings.mlr.press/v22/giesen12.html %V 22 %X We devise a simple algorithm for computing an approximate solution path for parameterized semidefinite convex optimization problems that is guaranteed to be epsilon-close to the exact solution path. As a consequence, we can compute the entire regularization path for many regularized matrix completion and factorization approaches, as well as nuclear norm or weighted nuclear norm regularized convex optimization problems. This also includes robust PCA and variants of sparse PCA. On the theoretical side, we show that the approximate solution path has low complexity. This implies that the whole solution path can be computed efficiently. Our experiments demonstrate the practicality of the approach for large matrix completion problems.
RIS
TY - CPAPER TI - Regularization Paths with Guarantees for Convex Semidefinite Optimization AU - Joachim Giesen AU - Martin Jaggi AU - Soeren Laue BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-giesen12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 432 EP - 439 L1 - http://proceedings.mlr.press/v22/giesen12/giesen12.pdf UR - https://proceedings.mlr.press/v22/giesen12.html AB - We devise a simple algorithm for computing an approximate solution path for parameterized semidefinite convex optimization problems that is guaranteed to be epsilon-close to the exact solution path. As a consequence, we can compute the entire regularization path for many regularized matrix completion and factorization approaches, as well as nuclear norm or weighted nuclear norm regularized convex optimization problems. This also includes robust PCA and variants of sparse PCA. On the theoretical side, we show that the approximate solution path has low complexity. This implies that the whole solution path can be computed efficiently. Our experiments demonstrate the practicality of the approach for large matrix completion problems. ER -
APA
Giesen, J., Jaggi, M. & Laue, S.. (2012). Regularization Paths with Guarantees for Convex Semidefinite Optimization. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:432-439 Available from https://proceedings.mlr.press/v22/giesen12.html.

Related Material