Theory Lunch Seminar - Ying Feng

— 1:00pm

Location:
In Person - Gates Hillman 8102

Speaker:
YING FENG , Ph.D. Student, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
https://yinggggfeng.github.io/

A Fast Linear Map with Uniform Gaussian-Like Averages

We consider a uniform law of large numbers for random linear maps: Let $M \in R^{m \times n}$ be a random Gaussian matrix and let $f: R \rightarrow R$ be $L$-Lipschitz. As $m$ increases, the average of $\{ f ((Mx)_i) \}_{i \in [m]}$ converges to its expectation uniformly over $x \in R^n$. This concentration underlies several algorithmic uses of random Gaussian maps, but their $O(mn)$ multiplication cost limits practicality.

Recently, Cherapanamjeri and Nelson (STOC’22) constructed a faster linear map with similar uniform concentration but asymptotically slower convergence rate than Gaussians. In this work, we give a new linear map that matches the convergence rate of Gaussians while achieving an even faster runtime than Cherapanamjeri-Nelson. As applications, we obtain improved algorithms for $\ell_2 \rightarrow \ell_1$ embeddings, kernel approximation, adaptive distance estimation, etc.

For More Information:
hfleisch@andrew.cmu.edu

Add event to Google
Add event to iCal