Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch -- Paris Syminelakis

Reyna Marie Hulett rmhulett at
Tue Oct 23 15:55:11 PDT 2018

Hi folks,

This week's theory lunch will be given by Paris Syminelakis, on “Efficient Density Evaluation for Smooth Kernels”--see abstract below. As always, please join us Thursday from noon to 1 pm in Gates 463A!

A fundamental problem in Scientific Computing and Machine Learning is that of Interpolation: "given measurements (y_i, x_i) where y_i is a real number and x_i is a d-dimensional vector  for i \in [n], construct a continuous/smooth function f: \R^d \to \R such that f(x_i) = y_i for all i \in [n]". In order to solve such problems starting with work in Cartography in the 60's and adopted widely in Machine Learning in the 90's, scientists have used functions of the form: f(x) = \sum_{i} w_i \phi( \| x - x_i \|) by picking coefficients w_i appropriately (linear system solving/optimization). The functions \phi(r) as known as Radial Basis Functions (RBF) and the method is known as "RBF Interpolation".

In this talk, I will discuss a set of techniques that show that such functions can be approximately evaluated in *poly-logarithmic time in the number of points* but having an *exponential dependence on a smoothness parameter*. For many functions used in the literature, this smoothness parameter is small (constant), giving overall fast algorithms for evaluating such "kernel densities" in high dimensions. For decreasing and smooth kernels, we also show a black-box reduction of this problem to the problem of approximate nearest neighbor search, that might be of independent interest.

This is based on joint work with Arturs Backurs (MIT), Moses Charikar and Piotr Indyk (MIT) presented at FOCS 2018.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list