Past Events

Seminar

Streaming Symmetric Norms via Measure Concentration

 

Download as iCal file

Wednesday, February 10, 2016, 11:00am

 

We characterize the streaming space complexity of every symmetric norm ℓ (a norm on Rn invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of ℓ. Specifically, we provide upper and lower bounds on the space complexity of approximating the norm of the stream, where both bounds depend on the median and maximum of ℓ(x) when x is drawn uniformly from the ℓ2 unit sphere. The same quantity governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem. The family of symmetric norms contains several well-studied norms, such as all ℓp norms, and indeed we provide a new explanation for the disparity in space complexity between p≤2 and p>2. In addition, we apply our general results to easily derive bounds for several norms were not studied before in the streaming model, including for example the top-k norm and the k-support norm, which was recently shown to be effective for machine learning tasks.

Speaker: Lin F. Yang

Bio

NULL

Location : Core A (Room 301)

Committee

Eric Allender, Pranjal Awasthi, Michael Saks and Mario Szegedy

Event Type: Seminar

Organization

Johns Hopkins University