jmlr jmlr2008 jmlr2008-26 jmlr2008-26-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Francis R. Bach
Abstract: Regularization by the sum of singular values, also referred to as the trace norm, is a popular technique for estimating low rank rectangular matrices. In this paper, we extend some of the consistency results of the Lasso to provide necessary and sufficient conditions for rank consistency of trace norm minimization with the square loss. We also provide an adaptive version that is rank consistent even when the necessary condition for the non adaptive version is not fulfilled. Keywords: convex optimization, singular value decomposition, trace norm, consistency
J. Abernethy, F. Bach, T. Evgeniou, and J.-P. Vert. Low-rank matrix factorization with attributes. Technical Report N24/06/MM, Ecole des Mines de Paris, 2006. J. Abernethy, F. Bach, T. Evgeniou, and J.-P. Vert. A new approach to collaborative filtering: Operator estimation with spectral regularization. Technical Report HAL-00250231, HAL, 2008. Y. Amit, M. Fink, N. Srebro, and S. Ullman. Uncovering shared structures in multiclass classification. In Proceedings of the International Conference on Machine Learning, 2007. A. Argyriou, T. Evgeniou, and M. Pontil. Multi-task feature learning. In Advances in Neural Information Processing Systems 19, 2007. F. R. Bach. Consistency of the group lasso and multiple kernel learning. Journal of Machine Learning Research, 9:1179–1225, 2008. 1046 C ONSISTENCY OF T RACE N ORM M INIMIZATION F. R. Bach, R. Thibaux, and M. I. Jordan. Computing regularization paths for learning multiple kernels. In Advances in Neural Information Processing Systems 17, 2004. J. F. Bonnans, J. C. Gilbert, C. Lemar´ chal, and C. A. Sagastizbal. Numerical Optimization Theoe retical and Practical Aspects. Springer, 2003. J. M. Borwein and A. S. Lewis. Convex Analysis and Nonlinear Optimization. Number 3 in CMS Books in Mathematics. Springer-Verlag, 2000. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2003. B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Annals of Statistics, 32: 407, 2004. M. Fazel, H. Hindi, and S. P. Boyd. A rank minimization heuristic with application to minimum order system approximation. In Proceedings American Control Conference, volume 6, pages 4734–4739, 2001. W. Fu and K. Knight. Asymptotics for lasso-type estimators. Annals of Statistics, 28(5):1356–1378, 2000. C. J. Geyer. On the asymptotics of constrained m-estimation. Annals of Statistics, 22(4):1993–2010, 1994. C. J. Geyer. On the asymptotics of convex stochastic optimization. Technical report, School of Statistics, University of Minnesota, 1996. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1996. P. Hall and C. C. Heyde. Martingale Limit Theory and Its Application. Academic Press, 1980. W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. T. Kato. Perturbation Theory for Linear Operators. Springer-Verlag, 1966. A. S. Lewis and H. S. Sendov. Twice differentiable spectral functions. SIAM J. Mat. Anal. App., 23 (2):368–386, 2002. Z. Lu, R. Monteiro, and M. Yuan. Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression. Technical report, Optimization online, 2008. URL http://www.optimization-online.org/DB_HTML/2008/01/1877.html. J. R. Magnus and H. Neudecker. Matrix Differential Calculus with Applications in Statistics and Econometrics. Wiley, New York, 1998. N. Meinshausen and B. Yu. Lasso-type recovery of sparse representations for high-dimensional data. Technical Report 720, Dpt of Statistics, UC Berkeley, 2006. B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. Technical Report arXiv:0706.4138v1, arXiv, 2007. 1047 BACH J. D. M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the International Conference on Machine Learning, 2005. W. Rudin. Real and complex analysis, Third edition. McGraw-Hill, 1987. J. Shao. Mathematical Statistics. Springer, 2003. N. Srebro, J. D. M. Rennie, and T. S. Jaakkola. Maximum-margin matrix factorization. In Advances in Neural Information Processing Systems 17, 2005. G. W. Stewart and J. Sun. Matrix Perturbation Theory. Academic Press, 1990. R. Tibshirani. Regression shrinkage and selection via the lasso. Journal Royal Statististics, 58(1): 267–288, 1994. A. W. Van der Vaart. Asymptotic Statistics. Cambridge University Press, 1998. M. Yuan and Y. Lin. On the non-negative garrotte estimator. Journal of The Royal Statistical Society Series B, 69(2):143–161, 2007. M. Yuan, A. Ekici, Z. Lu, and R. D. C. Monteiro. Dimension reduction and coefficient estimation in the multivariate linear regression. Journal of the Royal Statistical Society, Series B, 69(3): 329–346, 2007. P. Zhao and B. Yu. On model selection consistency of lasso. Journal of Machine Learning Research, 7:2541–2563, 2006. H. Zou. The adaptive lasso and its oracle properties. Journal of the American Statistical Association, 101:1418–1429, December 2006. 1048