Relative Error Tensor Low Rank Approximation by David Woodruff

Statistical Physics Methods in Machine Learning

DATE:26 December 2017 to 30 December 2017
VENUE:Ramanujan Lecture Hall, ICTS, Bengaluru

The theme of this Discussion Meeting is the analysis of distributed/networked algorithms in machine learning and theoretical computer science in the "thermodynamic" limit of large number of variables. Methods from statistical physics (eg various mean-field approaches) simplify the performance analysis of these algorithms in the limit of many variables. In particular, phase-transition like phenomena appear where the performance can undergo a discontinuous change as an underlying parameter is continuously varied. A provocative question to be explored at the meeting is whether these methods can shed theoretical light into the workings of deep networks for machine learning.

The Discussion Meeting will aim to facilitate interaction between theoretical computer scientists, statistical physicists, machine learning researchers and mathematicians interested in these questions. Examples of specific topics to be covered include (but are not limited to) problems such as phase transitions in optimization and learning algorithms, matrix approximation, mixing in large networks, sub-linear time algorithms, learning theory and non convex optimization. The meeting will allow structured and and unstructured interactions among the participants around the main theme.


CONTACT US:spmml2017 ictsresin

0:00:00 Start
0:00:11 Relative Error Tensor Low Rank Approximation
0:00:22 Motivation
0:02:45 Matrix Low Rank Approximation (More Norms)
0:05:47 Solution to Low-Rank Approximation
0:08:15 What is matrix S?
0:17:35 Caveat: Projecting the Points onto SA
0:35:17 What is Tensor?
0:36:46 Tensor Low Rank Approximation (Frobenius Norm)
0:39:41 Main Question, Tensor Low Rank Approximation
0:43:58 Tensor Rank and Border Rank
0:48:23 Main Results for 3rd Order Tensors (Frobenius Norm)
0:49:44 Main Bicriteria Algorithm Given
0:52:58 Main Rank-k Algorithm
0:53:31 Matrix CUR Decomposition Question
0:55:17 Tensor Column-based CURT Selection/Decomposition
0:57:32 Hardness - Under Exponential Time Hypothesis
1:02:07 Technical Overview
1:02:31 Iterative Existential Argument
1:13:49 Q&A