[AI Seminar] AI Seminar sponsored by Apple -- Hongyang Zhang -- May 01

[Adams Wei Yu]

A gentle reminder that the talk will be tomorrow (Tuesday) noon in NSH 3305.

On Sat, Apr 28, 2018 at 1:19 AM, Adams Wei Yu <weiyu at cs.cmu.edu> wrote:

> Dear faculty and students,
>
> We look forward to seeing you next Tuesday, May 01, at noon in NSH 3305 for
> AI Seminar sponsored by Apple. To learn more about the seminar series,
> please visit the AI Seminar webpage <http://www.cs.cmu.edu/~aiseminar/>.
>
> On Tuesday, Hongyang Zhang <http://www.cs.cmu.edu/~hongyanz/> will give
> the following talk:
>
> Title: Testing and Learning from Big Data, Optimally
>
> Abstract: We are now in an era of big data as well as high-dimensional
> data: data volume is almost doubling every two years. Fortunately,
> high-dimensional data are structured. Usually, they are of low rank. This
> is the basis of dimensionality reduction and compressed sensing. To extract
> efficient information from the low-rank structure without fully observing
> the matrix, there are two questions to handle: 1. what is the true rank of
> the data matrix with only small samples (testing problem)? 2. given the
> rank of the matrix, how to design computationally efficient algorithm to
> recover the matrix with only compressed observations (learning problem)?
>
> In this talk, we will focus on the testing and learning problems regarding
> the matrix rank with optimal sample complexity, which are new paradigms of
> information extraction from the big data. In the first part of the talk, we
> will see how we can test the rank of an unknown matrix via an interesting
> ladder-shaped sampling scheme. We also supplement our positive results with
> a hardness result, showing that our sampling scheme is near-optimal.
>
> In the second part of the talk, we study the matrix completion problem.
> Matrix completion is known as a non-convex problem in its most original
> form. To alleviate the computational issue, we show that strong duality
> holds for the matrix completion with nearly optimal sample complexity. For
> the hardness result, we also show that generic matrix factorization
> requires exponential time to be solved.
>
> Based on joint work with Nina Balcan (CMU), Yi Li (Nanyang Technological
> University), Yingyu Liang (Wisconsin-Madison), and David P. Woodruff (CMU).
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.srv.cs.cmu.edu/pipermail/ai-seminar-announce/attachments/20180430/8dd2751b/attachment.html>