Abstract
We devise a framework for computing an approximate solution path for an important class of parameterized semidefinite problems that is guaranteed to be ε-close to the exact solution path. The problem of computing the entire regularization path for matrix factorization problems such as maximum-margin matrix factorization fits into this framework, as well as many other nuclear norm regularized convex optimization problems from machine learning. We show that the combinatorial complexity of the approximate path is independent of the size of the matrix. Furthermore, the whole solution path can be computed in near linear time in the size of the input matrix.
The framework employs an approximative semidefinite program solver for a fixed parameter value. Here we use an algorithm that has recently been introduced by Hazan. We present a refined analysis of Hazan’s algorithm that results in improved running time bounds for a single solution as well as for the whole solution path as a function of the approximation guarantee.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Hazan, E., Kale, S.: Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update Method. In: Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 339–348 (2005)
Candès, E.J., Tao, T.: The Power of Convex Relaxation: Near-Optimal Matrix Completion. IEEE Transactions on Information Theory 56(5), 2053–2080 (2010)
Clarkson, K.L.: Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. ACM Transactions on Algorithms 6(4) (2010)
d’Aspremont, A., Bach, F.R., El Ghaoui, L.: Full Regularization Path for Sparse Principal Component Analysis. In: Proceedings of the International Conference on Machine Learning (ICML), pp. 177–184 (2007)
Fazel, M., Hindi, H., Boyd, S.P.: A Rank Minimization Heuristic with Application to Minimum Order System Approximation. In: Proceedings of the American Control Conference, vol. 6, pp. 4734–4739 (2001)
Giesen, J., Jaggi, M., Laue, S.: Approximating Parameterized Convex Optimization Problems. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 524–535. Springer, Heidelberg (2010)
Giesen, J., Jaggi, M., Laue, S.: Regularization Paths with Guarantees for Convex Semidefinite Optimization. In: Proceedings International Conference on Artificial Intelligence and Statistics (AISTATS) (2012)
Hazan, E.: Sparse Approximate Solutions to Semidefinite Programs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 306–316. Springer, Heidelberg (2008)
Jaggi, M., Sulovský, M.: A Simple Algorithm for Nuclear Norm Regularized Problems. In: Proceedings of the International Conference on Machine Learning (ICML), pp. 471–478 (2010)
Koren, Y., Bell, R.M., Volinsky, C.: Matrix Factorization Techniques for Recommender Systems. IEEE Computer 42(8), 30–37 (2009)
Kuczyński, J., Woźniakowski, H.: Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start. SIAM Journal on Matrix Analysis and Applications 13(4), 1094–1122 (1992)
Mazumder, R., Hastie, T., Tibshirani, R.: Spectral Regularization Algorithms for Learning Large Incomplete Matrices. Journal of Machine Learning Research 11, 2287–2322 (2010)
Nemirovski, A.: Prox-method with Rate of Convergence O(1/T) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-concave Saddle Point Problems. SIAM Journal on Optimization 15, 229–251 (2004)
Nesterov, Y.: Smoothing Technique and its Applications in Semidefinite Optimization. Math. Program. 110(2), 245–259 (2007)
Salakhutdinov, R., Srebro, N.: Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), vol. 23 (2010)
Srebro, N., Rennie, J.D.M., Jaakkola, T.: Maximum-Margin Matrix Factorization. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), vol. 17 (2004)
Wen, Z., Goldfarb, D., Yin, W.: Alternating Direction Augmented Lagrangian Methods for Semidefinite Programming. Technical report (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Giesen, J., Jaggi, M., Laue, S. (2012). Optimizing over the Growing Spectrahedron. In: Epstein, L., Ferragina, P. (eds) Algorithms – ESA 2012. ESA 2012. Lecture Notes in Computer Science, vol 7501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33090-2_44
Download citation
DOI: https://doi.org/10.1007/978-3-642-33090-2_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33089-6
Online ISBN: 978-3-642-33090-2
eBook Packages: Computer ScienceComputer Science (R0)