nips nips2013 nips2013-11 nips2013-11-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Bernardino Romera-Paredes, Massimiliano Pontil
Abstract: We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable. 1
[1] A. Argyriou, R. Foygel and N. Srebro. Sparse Prediction with the k-Support Norm. Advances in Neural Information Processing Systems 25, pages 1466–1474, 2012.
[2] A. Argyriou, C.A. Micchelli, M. Pontil, L. Shen and Y. Xu. Efficient first order methods for linear composite regularizers. arXiv:1104.1436, 2011.
[3] R. Bhatia. Matrix Analysis. Springer Verlag, 1997.
[4] D.P. Bertsekas, J.N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1989.
[5] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1– 122, 2011.
[6] S. Boyd, L. Xiao, A. Mutapcic. Subgradient methods, Stanford University, 2003.
[7] P. L. Combettes and J.-C. Pesquet. Proximal splitting methods in signal processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering (H. H. Bauschke et al. Eds), pages 185–212, Springer, 2011.
[8] M. Fazel, H. Hindi, and S. Boyd. A rank minimization heuristic with application to minimum order system approximation. Proc. American Control Conference, Vol. 6, pages 4734–4739, 2001.
[9] S. Gandy, B. Recht, I. Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2), 2011.
[10] G. H. Golub, C. F. Van Loan. Matrix Computations. 3rd Edition. Johns Hopkins University Press, 1996.
[11] Z. Harchaoui, M. Douze, M. Paulin, M. Dudik, J. Malick. Large-scale image classification with tracenorm regularization. IEEE Conference on Computer Vision & Pattern Recognition (CVPR), pages 3386– 3393, 2012.
[12] J-B. Hiriart-Urruty and C. Lemar´ chal. Convex Analysis and Minimization Algorithms, Part I. Springer, e 1996.
[13] J-B. Hiriart-Urruty and C. Lemar´ chal. Convex Analysis and Minimization Algorithms, Part II. Springer, e 1993.
[14] R.A. Horn and C.R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 2005.
[15] A. Karatzoglou, X. Amatriain, L. Baltrunas, N. Oliver. Multiverse recommendation: n-dimensional tensor factorization for context-aware collaborative filtering. Proc. 4th ACM Conference on Recommender Systems, pages 79–86, 2010.
[16] T.G. Kolda and B.W. Bade. Tensor decompositions and applications. SIAM Review, 51(3):455–500, 2009.
[17] J. Liu, P. Musialski, P. Wonka, J. Ye. Tensor completion for estimating missing values in visual data. Proc. 12th International Conference on Computer Vision (ICCV), pages 2114–2121, 2009.
[18] Y. Nesterov. Gradient methods for minimizing composite objective functions. ECORE Discussion Paper, 2007/96, 2007.
[19] B. Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12:3413– 3430, 2009.
[20] B. Romera-Paredes, H. Aung, N. Bianchi-Berthouze and M. Pontil. Multilinear multitask learning. Proc. 30th International Conference on Machine Learning (ICML), pages 1444–1452, 2013.
[21] N. Z. Shor. Minimization Methods for Non-differentiable Functions. Springer, 1985.
[22] M. Signoretto, Q. Tran Dinh, L. De Lathauwer, J.A.K. Suykens. Learning with tensors: a framework based on convex optimization and spectral regularization. Machine Learning, to appear.
[23] M. Signoretto, R. Van de Plas, B. De Moor, J.A.K. Suykens. Tensor versus matrix completion: a comparison with application to spectral data. IEEE Signal Processing Letters, 18(7):403–406, 2011.
[24] N. Srebro, J. Rennie and T. Jaakkola. Maximum margin matrix factorization. Advances in Neural Information Processing Systems (NIPS) 17, pages 1329–1336, 2005.
[25] R. Tomioka, K. Hayashi, H. Kashima, J.S.T. Presto. Estimation of low-rank tensors via convex optimization. arXiv:1010.0789, 2010.
[26] R. Tomioka and T. Suzuki. Convex tensor decomposition via structured Schatten norm regularization. arXiv:1303.6370, 2013.
[27] R. Tomioka, T. Suzuki, K. Hayashi, H. Kashima. Statistical performance of convex tensor decomposition. Advances in Neural Information Processing Systems (NIPS) 24, pages 972–980, 2013. 9