Spring 2017

The Polytope Learning Problem

Thursday, May 4, 2017 2:45 pm3:30 pm PDT

Add to Calendar

I will talk about the polytope learning problem: Given random samples from a polytope in the n-dimensional space with poly(n) vertices, can we efficiently find an approximation to the polytope? (Information theoretically, poly(n) many samples suffice.) I will discuss some approaches and related conjectures for this problem, and also its relation to other problems in learning theory.