# Random Separating Hyperplane Theorem and Learning Polytopes

arXiv: https://arxiv.org/abs/2307.11371 · HTML: https://mlsanity.com/paper/2307.11371/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 21 Jul 2023.

## Builds on (most cited first, 8 of 8)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Efficient Convex Optimization with Membership Oracles](https://mlsanity.com/paper/1706.07357/) (2017)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [Sparse Approximation via Generating Point Sets](https://mlsanity.com/paper/1507.02574/) (2015)
- [Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing](https://mlsanity.com/paper/1904.06738/) (2019)
- [Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier](https://mlsanity.com/paper/1507.02528/) (2015)

## Abstract (arXiv)

The Separating Hyperplane theorem is a fundamental result in Convex Geometry with myriad applications. Our first result, Random Separating Hyperplane Theorem (RSH), is a strengthening of this for polytopes. rsh asserts that if the distance between a and a polytope K with k vertices and unit diameter in Red is at least δ, where δ is a fixed constant in (0,1), then a randomly chosen hyperplane separates a and K with probability at least 1/poly(k) and margin at least Omega left(δ/√d right). An immediate consequence of our result is the first near optimal bound on the error increase in the reduction from a Separation oracle to an Optimization oracle over a polytope. RSH has algorithmic applications in learning polytopes. We consider a fundamental problem, denoted the ``Hausdorff problem'', of learning a unit diameter polytope K within Hausdorff distance δ, given an optimization oracle for K. Using RSH, we show that with polynomially many random queries to the optimization oracle, K can be approximated within error O(δ). To our knowledge this is the first provable algorithm for the Hausdorff Problem. Building on this result, we show that if the vertices of K are well-separated, then an optimization oracle can be used to generate a list of points, each within Hausdorff distance O(δ) of K, with the property that the list contains a point close to each vertex of K. Further, we show how to prune this list to generate a (unique) approximation to each vertex of the polytope. We prove that in many latent variable settings, e.g., topic modeling, LDA, optimization oracles do exist provided we project to a suitable SVD subspace. Thus, our work yields the first efficient algorithm for finding approximations to the vertices of the latent polytope under the well-separatedness assumption.