Eastern Great Lakes Theory Workshop Talk

Density Estimation in Linear Time/Estimation of L₁ Distances Using Stochastic Integrals

Daniel Štefankovič, University of Rochester

Sunday, September 7, 10:30 am- 11:30am

ABSTRACT

I will talk about the following problem in learning theory: given a set of densities F and data, choose a density estimate from F which minimizes the L₁-distance to an unknown true distribution. I'll focus on the computational aspect of the problem, presenting a linear-time algorithm.

In the preprocessing step of the algorithm we need to solve the following problem: compute L₁-distances between every pair of densities in F. I'll show that the technique of Cauchy random projections (Indyk'06) in this context turns into stochastic integrals (of deterministic functions) with respect to Cauchy motion. I'll also show that for piecewise linear densities we can efficiently sample from these integrals using rejection sampling.

Joint work with Satyaki Mahalanabis.

Slides

Speaker Bio

Daniel Štefankovič received his undergraduate diploma (Magister degree) in computer science from Comenius University, Bratislava, Slovakia, in 1998, under Peter Ružička. He received his Ph.D. in computer science from the University of Chicago under László Babai in 2005. He joined the Computer Science faculty at the University of Rochester in July 2005.

His research area is the theory of computing; it includes computational topology, especially classical algorithmic problems on simple curves on surfaces; Markov Chain Monte Carlo sampling; extremal combinatorics; algorithmic game theory; graph drawing; algorithmic coding theory; and applications of discrete and continuous Fourier transforms, especially to lattices and diophantine approximation.

< Schedule < EaGL homepage