[CSDM] PU PACM COLLOQUIUM - Monday, March 4 - Shay Moran (Princeton University)

[Avi Wigderson]

A talk of possible interest

---------- Forwarded message ---------
From: *Gina M. Holland* <gholland at princeton.edu 
<mailto:gholland at princeton.edu>>
Date: Wed, 27 Feb 2019 at 11:28
Subject: NEXT: PACM COLLOQUIUM - Monday, March 4 - Shay Moran (Princeton 
University)
To: pacmdistribution at math.princeton.edu 
<mailto:pacmdistribution at math.princeton.edu> 
<pacmdistribution at math.princeton.edu 
<mailto:pacmdistribution at math.princeton.edu>>


The next PACM Colloquium will be given by *Shay Moran (Princeton 
University)***


=================
*DATE/LOCATION: Monday, March 4 2019, 4:00 – 5:00 PM / 214 Fine Hall*

SPEAKER: *Shay Moran (Princeton University)***


TITLE: *The Optimal Approximation Factor in Density Estimation*

ABSTRACT:

Consider the following problem: given arbitrary densities q1,q2 and a 
sample-access to an unknown target density p, find which of the qi's is 
closer to p in the total variation distance.

A beautiful (and simple) result due to Yatracos (1985) shows that this 
problem is tractable in the following sense: there exists an algorithm 
that uses O(epsilon^{-2}) samples from p and outputs qi such that with 
high probability, TV(qi,p) <= 3*OPT + epsilon, where OPT= 
min{TV(q1,p),TV(q2,p)}. Moreover, this result extends to any finite 
class of densities: there exists an algorithm that outputs the best 
density in Q up to a multiplicative approximation factor of 3.

We complement and extend this result by showing that: (i) the factor 3 
cannot be improved if one restricts the algorithm to output a density 
from Q, and (ii) if one allows the algorithm to output arbitrary 
densities (e.g. a mixture of densities from Q), then the approximation 
factor can be reduced to 2, which is optimal. In particular this 
demonstrates an advantage of improper learning over proper in this setup.

Our  algorithms rely on estimating carefully chosen surrogates metrics 
to the total variation, and our sample complexity bounds exploit 
techniques from Adaptive Data Analysis.

Joint work with Olivier Bousquet (Google brain) and Daniel Kane (UCSD).

//

/Shay Moran is a Postdoctoral fellow at the Computer Science Department 
in Princeton University. He graduated from the Technion in September 
’16. During 2017 he was a postdoctoral fellow at UCSD and at the Simons 
Institute in Berkeley. During 2018 he was a member at the Institute for 
Advanced Study. In October ’19 he will join the Math Department at the 
Technion as an assistant Professor. Shay’s research interests revolves 
around mathematical problems that arise in computer science, with a 
focus on combinatorial problems related to machine learning./

//

//

Macintosh HD:Users:theresa:Desktop:PACM logo:FINAL LOGO:PACM-logo.png

Macintosh 
HD:Users:theresa:Downloads:PUsig2-pkg:Links:Black-and-white:Black:PUsig2-bw-bs.pdf

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20190228/25593485/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 7866 bytes
Desc: not available
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20190228/25593485/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image004.png
Type: image/png
Size: 2027 bytes
Desc: not available
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20190228/25593485/attachment-0001.png>
-------------- next part --------------
_______________________________________________
Theory-Read mailing list
Theory-Read at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/theory-read