Rank, Trace-Norm and Max-Norm
Lecture notes in computer sciencePublished 1 January 2005
Nathan Srebro, Adi Shraibman
Citations332
SJR quartileQ2
SJR score0.35
SNIP0.55
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.
TL;DR
This work studies the rank, trace-norm and max-norm as complexity measures of matrices, focusing on the problem of fitting a matrix with matrices having low complexity, and presents generalization error bounds for predicting unobserved entries that are based on these measures.
Abstract
We study the rank, trace-norm and max-norm as complexity measures of matrices, focusing on the problem of fitting a matrix with matrices having low complexity. We present generalization error bounds for predicting unobserved entries that are based on these measures. We also consider the possible relations between these measures. We show gaps between them, and bounds on the extent of such gaps.
Keywords
Computer ScienceDecision SciencesEngineering
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.
Regional conference series in mathematicsFactorization of Linear Operators and Geometry of Banach Spaces
592 Citations1986Gilles Pisier
The Annals of StatisticsEmpirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers
468 Citations2002Vladimir Koltchinskii, Dmitry Panchenko
New probabilistic upper bounds on generalization error of complex classifiers that are combinations of simple classifier combinations, based on the methods of the theory of Gaussian and empirical processes are proved.
Machine LearningAn algorithmic theory of learning: Robust concepts and random projection
334 Citations2006Rosa I. Arriaga, Santosh Vempala
This work provides a novel algorithmic analysis via a model of robust concept learning (closely related to “margin classifiers”), and shows that a relatively small number of examples are sufficient to learn rich concept classes.
DSpace@MIT (Massachusetts Institute of Technology)Learning with matrix factorizations
218 Citations2004Nathan Srebro, Tommi Jaakkola
This thesis addresses several issues related to learning with matrix factorizations, study the asymptotic behavior and generalization ability of existing methods, suggest new optimization methods, and present a novel maximum-margin high-dimensional matrix factorization formulation.
Adaptive routing with end-to-end feedback
204 Citations2004Baruch Awerbuch, Robert Kleinberg
A second algorithm for online shortest paths is presented, which solves the shortest-path problem using a chain of online decision oracles, one at each node of the graph, which has several advantages over the online linear optimization approach.
Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices
126 Citations2004Nathan Srebro, Noga Alon +1 more
It is proved that generalization error bounds for predicting entries in a partially observed matrix are generalized by fitting the observed entries with a low-rank matrix.
Combinatorics Probability ComputingThe Expected Norm of Random Matrices
118 Citations2000Yoav Seginer
The Euclidean operator norm of a random matrix, A, obtained from a (non-random) matrix by randomizing the signs of the matrix's entries is considered, which is the best inequality possible (up to a multiplicative constant).
Geometrical realization of set systems and probabilistic communication complexity
105 Citations1985Noga Alon, Péter Frankl +1 more
It is shown that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon.
Lecture notes in computer scienceLimitations of Learning via Embeddings in Euclidean Half-Spaces
88 Citations2001Shai Ben-David, Nadav Eiron +1 more
The results indicate that any universal learning machine, which transforms data into the Euclidean space and then applies linear (or large margin) classification, cannot enjoy any meaningful generalization guarantees that are based on either VC dimension or margins considerations.
Machine LearningEstimating the Optimal Margins of Embeddings in Euclidean Half Spaces
40 Citations2003Jürgen Forster, Niels Schmitt +2 more
The singular value decomposition of this matrix is used to determine the optimal margins of embeddings of the concept classes of singletons and of half intervals in homogeneous Euclidean half spaces and to prove the corresponding best possible upper bounds on the margin.
Lecture notes in computer scienceOn the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution
6 Citations2002Jürgen Forster, Hans Ulrich Simon
The embeddability of a given concept class into a class of Euclidean half spaces of low dimension, or of arbitrarily large dimension but realizing a large margin, is studied.