Random Separating Hyperplane Theorem and Learning Polytopes
# 204
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.
Amit Kumar is a faculty member in the dept. of Computer Science and Engineering at IIT Delhi. He obtained B.Tech. degree from IIT Kanpur in 1997 and Ph.D. from Cornell University in 2002. He works in the area of combinatorial optimization, with emphasis on problems arising in scheduling, graph theory and clustering. He received IBM Faculty Award in 2005, INAE (Indian National Academy of Engineering) Young Engineer Award in 2006 and INSA (Indian National Science Academy) Medal for Young Scientists in 2011. He was a Max Planck-India partner group research fellow during 2005-09. He received the prestigious Shanti Swarup Bhatnagar Award for Mathematical Sciences in 2018, and was elected Fellow of Indian Academy of Sciences in 2019, and Fellow of Indian National Academy of Engineering in 2022.