[Ml-stat-talks] Fwd: [ORFE-Seminars] Princeton Optimization Seminar, Jelani Nelson, Thursday, Apr. 27, 4:30 PM, Sherrerd 101

Barbara Engelhardt bee at princeton.edu
Thu Apr 20 10:32:12 EDT 2017


Talk of interest.

*-----   **Princeton Optimization Seminar**   -----*

*DATE: *Thursday, April 27, 2017

*TIME*:  4:30PM

*LOCATION**: * Sherrerd Hall 101

*SPEAKER:*  Jelani Nelson, Harvard University

*TITLE:  *Optimality of the Johnson-Lindenstrauss Lemma

*Abstract:  *Dimensionality reduction in Euclidean space, as attainable by
the Johnson-Lindenstrauss lemma (also known as "random projections"), has
been a fundamental tool in algorithm design and machine learning. The JL
lemma states that any n points in Euclidean space can be mapped to
m-dimensional Euclidean space while preserving all pairwise distances up to
1+epsilon, where m only needs to be on the order of (log n) / epsilon^2,
independent of the original dimension. In this talk, I discuss our recent
proof that the JL lemma is optimal, in the sense that for any n there are
point sets of size n such that no embedding providing
(1+epsilon)-distortion exists into a dimension that is more than a constant
factor better than what the JL lemma guarantees. I will also discuss some
subsequent work and future directions. Joint work with Kasper Green Larsen
(Aarhus University).

*BIO:* Jelani Nelson is an Assistant Professor of Computer Science at
Harvard University. His main research interest is in algorithm design and
analysis, with recent focus on streaming algorithms, dimensionality
reduction, compressed sensing, and randomized linear algebra algorithms. He
completed his Ph.D. in computer science at MIT in 2011, receiving the
George M. Sprowls Award for best computer science doctoral dissertations at
MIT. He is the recipient of an NSF CAREER Award, ONR Young Investigator
Award, ONR Director of Research Early Career Award, Alfred P. Sloan
Research Fellowship, and Presidential Early Career Award for Scientists and
Engineers (PECASE).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20170420/ad42ab03/attachment.html>


More information about the Ml-stat-talks mailing list