Large Scale Matrix Analysis and Inference

Much of Machine Learning is based on Linear Algebra. Often, the prediction is a function of a dot product between the parameter vector and the feature vector. This essentially assumes some kind of independence between the features. In contrast, matrix parameters can be used to learn interrelations between features: The (i,j)th entry of the parameter matrix represents how feature i is related to feature j.

This richer modeling has become very popular. In some applications, like PCA and collaborative filtering, the explicit goal is inference of a matrix parameter. Yet in others, like direction learning and topic modeling, the matrix parameter instead pops up in the algorithms as the natural tool to represent uncertainty.

The emergence of large matrices in many applications has brought with it a slew of new algorithms and tools. Over the past few years, matrix analysis and numerical linear algebra on large matrices has become a thriving field. Also manipulating such large matrices makes it necessary to to think about computer systems issues.

This workshop aims to bring closer researchers in large scale machine learning and large scale numerical linear algebra to foster cross-talk between the two fields. The goal is to encourage machine learning researchers to work on numerical linear algebra problems, to inform machine learning researchers about new developments on large scale matrix analysis, and to identify unique challenges and opportunities. The workshop will conclude with a session of contributed posters.

Questions of Interest

• Computational efficiency: Straight forward matrix methods rely on the eigendecomposition of the current parameter matrix during the parameter update. How can the decomposition be avoided and how can the updates be made efficient? Does randomization help?
• Theoretical analysis: What algorithms, how many examples do they need and how fast do they converge?
• How to lift vector parameter tools to the matrix case: Exponential families, regularization, entropies, probability calculus for matrices.
• How can you scale up linear algebra methods. When can you get away with approximations?
• Large matrices often have few known entries. How do you fill in the missing entries?
• What is the essential sub-matrix of a matrix and how do you find it quickly?
• How do you manipulate matrices that cannot be stored or even streamed through a single machine?
• How can cutting edge tools in distributed computing help answer linear algebraic questions in machine learning?

Goals of the Workshop

This workshop will consist of invited talks and paper submissions for a poster session. The target audience of this workshop includes industry and academic researchers interested in machine learning, large distributed systems, numerical linear algebra, and related fields.

• Submission deadline will be October 11th, 2013.
• Acceptance decisions will be mailed out on or before October 30th, 2013.
• The finalized workshop program will be available on or before October 31st, 2013.

Talks

Nathan Srebro (TTI): An overview of matrix problems. PCA, CCA, PLS, matrix regularization, main update families [slides]

Satyen Kale (Yahoo Labs): Near-Optimal Algorithms for Online Matrix Prediction [slides]

Ben Recht (Wisconsin): Large scale matrix algorithms and matrix completion [slides]

David Woodruff (IBM): Sketching as a Tool for Numerical Linear Algebra [slides]

Yiannis Koutis (Puerto Rico-Rio Piedras): Spectral sparsification of graphs: an overview of theory and practical methods [slides]

Malik Magdon-Ismail (RPI): Efficiently implementing sparsity in learning [slides]

Ashish Goel (Stanford): Primal-Dual Graph Algorithms for MapReduce [slides]

Matei Zaharia (MIT): Large-scale matrix operations using a data-flow engine [slides]

Manfred Warmuth (UCSC): Large Scale Matrix Analysis and Inference [slides]

Schedule

Accepted Papers

Linear Bandits, Matrix Completion, and Recommendation Systems [pdf]

Efficient coordinate-descent for orthogonal matrices through Givens rotations [pdf]

Improved Greedy Algorithms for Sparse Approximation of a Matrix in terms of Another Matrix [pdf]

Preconditioned Krylov solvers for kernel regression [pdf]

Probabilistic Low-Rank Matrix Completion with Adaptive Spectral Regularization Algorithms [pdf][supplementary]

Dimension Independent Matrix Square using MapReduce [pdf]