Abstract: The classical separating hyperplane theorem states that for a point p not in a closed convex set K, there is a hyperplane separating p and K. We give a strengthening of this result for polytopes. This result

is then used to learn the vertices of a polytope that is described by an optimization oracle, and provides a general framework for learning

polytopes arising in several hidden variable problems in machine learning which are known to admit optimization oracles. This is joint

work with Chiranjib Bhattacharyya and Ravindran Kannan.