Consistency of trace norm minimization
arXiv (Cornell University)Published 15 October 2007Open access
Francis Bach
Citations183
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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
Computer ScienceMathematicsEngineering
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
Cambridge University Press eBooksConvex Optimization
31,266 Citations2004Stephen Boyd, Lieven Vandenberghe
The Annals of StatisticsLeast angle regression
9,493 Citations2004Bradley Efron, Trevor Hastie +2 more
Journal of the American Statistical AssociationThe Adaptive Lasso and Its Oracle Properties
7,633 Citations2006Hui Zou
A new version of the lasso is proposed, called the adaptive lasso, where adaptive weights are used for penalizing different coefficients in the ℓ1 penalty, and the nonnegative garotte is shown to be consistent for variable selection.
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
SIAM ReviewGuaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
3,533 Citations2010Benjamin Recht, Maryam Fazel +1 more
It is shown that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum-rank solution can be recovered by solving a convex optimization problem, namely, the minimization of the nuclear norm over the given affine space.
BiometricsMatrix Differential Calculus with Applications in Statistics and Econometrics.
2,730 Citations1988J. R. Magnus, Heinz Neudecker
On Model Selection Consistency of Lasso
2,015 Citations2006Peng Zhao, Bin Yu
It is proved that a single condition, which is called the Irrepresentable Condition, is almost necessary and sufficient for Lasso to select the true model both in the classical fixed p setting and in the large p setting as the sample size n gets large.
The MIT Press eBooksMulti-Task Feature Learning
1,369 Citations2007Andreas A. Argyriou, Theodoros Evgeniou +1 more
The Annals of StatisticsAsymptotics for lasso-type estimators
1,316 Citations2000Wenjiang Fu, Keith Knight
A rank minimization heuristic with application to minimum order system approximation
994 Citations2001Maryam Fazel, H. Hindi +1 more
It is shown that the heuristic to replace the (nonconvex) rank objective with the sum of the singular values of the matrix, which is the dual of the spectral norm, can be reduced to a semidefinite program, hence efficiently solved.
Fast maximum margin matrix factorization for collaborative prediction
968 Citations2005Jasson D. M. Rennie, Nathan Srebro
This work investigates a direct gradient-based optimization method for MMMF and finds that MMMf substantially outperforms all nine methods he tested and demonstrates it on large collaborative prediction problems.
Maximum-Margin Matrix Factorization
952 Citations2004Nathan Srebro, Jason D. M. Rennie +1 more
A novel approach to collaborative prediction is presented, using low-norm instead of low-rank factorizations, inspired by, and has strong connections to, large-margin linear discrimination.
CMS books in mathematicsConvex Analysis and Nonlinear Optimization
795 Citations2006Jonathan M. Borwein, Adrian S. Lewis
UC BerkeleyLasso-type recovery of sparse representations for high-dimensional data
751 Citations2006Meinshausen, Nicolai, Yu, Bin
arXiv (Cornell University)Consistency of the group Lasso and multiple kernel learning
704 Citations2007Francis Bach
This paper derives necessary and sufficient conditions for the consistency of group Lasso under practical assumptions, and proposes an adaptive scheme to obtain a consistent model estimate, even when the necessary condition required for the non adaptive scheme is not satisfied.
Choice Reviews OnlineNumerical optimization: theoretical and practical aspects
628 Citations2003
This book is about the theoretical foundations of optimization algorithms, and also provides practical insights on how such methods should be implemented and applied, and provides adequate examples to help the reader understand the methods better and explore possible pitfalls.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression
327 Citations2007Ming Yuan, Ali Ekici +2 more
The Annals of StatisticsOn the Asymptotics of Constrained $M$-Estimation
305 Citations1994Charles J. Geyer
Uncovering shared structures in multiclass classification
290 Citations2007Yonatan Amit, Michael Fink +2 more
This paper suggests a method for multiclass learning with many classes by simultaneously learning shared characteristics common to the classes, and predictors for the classes in terms of these characteristics.
Journal of the Royal Statistical Society Series B (Statistical Methodology)On the Non-Negative Garrotte Estimator
271 Citations2007Ming Yuan, Yi Lin
arXiv (Cornell University)A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization
213 Citations2008Jacob Abernethy, Francis Bach +2 more
This work presents a general approach for collaborative filtering using spectral regularization to learn linear operators mapping a set of "users" to aSet of possibly desired " objects", and provides novel representer theorems that are used to develop new estimation methods.
Matrix Perturbation Theory
193 Citations2005Tyler Seacrest, Weiqing Gu
arXiv (Cornell University)Low-rank matrix factorization with attributes
99 Citations2006Jacob Abernethy, Francis Bach +2 more
This work develops a new collaborative filtering method that combines both previously known users' preferences, as well as product/user attributes, i.e. standard CF, to predict a given user's interest in a particular product.
Computing regularization paths for learning multiple kernels
96 Citations2004Francis R. Bach, Romain Thibaux +1 more
Working in the setting of kernel linear regression and kernel logistic regression, it is shown empirically that the effect of the block 1-norm regularization differs notably from the (non-block) 1- norm regularization commonly used for variable selection, and that the regularization path is of particular value in the block case.
SIAM Journal on Matrix Analysis and ApplicationsTwice Differentiable Spectral Functions
90 Citations2001Adrian S. Lewis, Hristo S. Sendov
It is shown that a spectral function is twice (continuously) differentiable at a matrix if and only if the corresponding symmetric function is Twice (continuous)Differentiable at the vector of eigenvalues.
Mathematical ProgrammingConvex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression
62 Citations2010Zhaosong Lu, Renato D. C. Monteiro +1 more
It is shown that the variant of Nesterov’s smooth method generally outperforms the interior point method implemented in SDPT3 version 4.0 (beta) substantially and the former method is much more memory efficient.