Consistency of trace norm minimization

By Francis R. Bach. 2007

223 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Joint covariate selection and joint subspace selection for multiple classification problems (2010, neutral): “Shraibman (2005); Bach (2008); Recht et al.”
Optimization with Sparsity-Inducing Penalties (2011, background): “Other problems can be similarly cast (for the trace norm, see [8, 44]).”
Excess risk bounds for multitask learning with trace norm regularization (2012, background): “The foundations to a theoretical understanding of multi-task learning were laid by Baxter (2000), where covering numbers are used to expose the potential benefits of multi-task and transfer learning.”
Statistical Learning with Sparsity: The Lasso and Generalizations (2015, methodology): “Various algorithms have been developed for solving the group and overlap group lassos, as well as a variety of structured generalizations; see Bach, Jenatton, Mairal and Obozinski (2012) for a good review.”
An accelerated gradient method for trace norm minimization (2009, methodology): “It can be verified that (Bach, 2008; Recht et al., 2008a) ∂||W ||∗ = {P1P 2 + S : S ∈ Rm×n, P 1 S = 0, SP2 = 0, ||S||2 ≤ 1}, (23) where || · ||2 denotes the spectral norm of a matrix.”
Cross-Modal Similarity Learning: A Low Rank Bilinear Formulation (2014, background): “Let the SVD decomposition of an arbitrary matrix X ∈ Rm×n is X = P1ΛP2 , then the subgradient of its nuclear norm is (Bach 2008; Cai, Candès, and Shen 2010)”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, methodology): “Techniques based on nuclear norm regularization have been studied for different statistical models, including compressed sensing [37, 62], matrix completion [15, 31, 52, 61], multitask regression [4, 10, 51, 63, 77] and system identification [23, 38, 51].”
Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements (2011, background): “The work [19] then considered the asymptotics, and demonstrated consistency of the matrix Lasso estimate in the noisy case, as the number of measurements approached infinity (the matrix Lasso estimate is defined in Section I-D).”
Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing (2011, background): “The tracenorm is well-known to be a convex surrogate to the matrix rank, and has repeatedly shown good performance in practice (see for instance Srebro et al. (2004), Salakhutdinov and Mnih (2007), Bach (2008), Candès and Tao (2009)).”
Estimation of high-dimensional low-rank matrices (2009, background): “Since the Group Lasso is a special case of the nuclear norm penalized minimization on block-diagonal matrices [cf., e.g., Bach (2008)] Corollary 4 and the bounds (6.1), (6.2) imply the corresponding bounds for the Group Lasso under the low-rank assumption.”
Tensor completion for estimating missing values in visual data (2010, background): “This leads to the following convex optimization problem for matrix completion [3, 5, 14]:”
Nuclear norm penalization and optimal rates for noisy low rank matrix completion (2010, methodology): “The most popular methods are based on penalized empirical risk minimization with nuclear norm penalty [4, 2, 3, 5, 7, 8, 9, 13, 18, 23].”
Deep Canonical Correlation Analysis (2013, methodology): “To prove (15), we use the fact that for a matrix X, ∇||X|| tr = U V , where X = U DV is the singular value decomposition of X (Bach, 2008).”
Distance Metric Learning with Eigenvalue Optimization (2012, background): “Such tasks include multi-task feature learning (Argyriou et al., 2006) and low-rank matrix completion (Bach, 2008; Candes and Recht, 2008; Srebro et al., 2004).”
Restricted strong convexity and weighted matrix completion: Optimal bounds with noise (2010, background): “The nuclear norm is the sum of the singular values of a matrix [10], and has been studied in a body of past work, both on matrix completion and more general problems of low-rank matrix estimation (e.g., [9, 26, 27, 28, 23, 2, 6, 22, 11, 12, 19, 24]).”
Fixed point and Bregman iterative methods for matrix rank minimization (2009, unknown): “, [1; 4]) ∂‖X‖∗ = {UV⊤+W : U⊤W = 0,WV = 0,‖W‖ ≤ 1}.”
Estimation of (near) low-rank matrices with noise and high-dimensional scaling (2009, background): “In addition, Bach (7) has provided some consistency results for nuclear norm regularization in the classical (fixed “p”) setting, but not in the high-dimensional setting considered here.”