Kruskal-Katona for convex sets, with applications
share
The well-known Kruskal-Katona theorem in combinatorics says that (under mild conditions) every monotone Boolean function f: {0,1}^n →{0,1} has a nontrivial "density increment." This means that the fraction of inputs of Hamming weight k+1 for which f=1 is significantly larger than the fraction of inputs of Hamming weight k for which f=1. We prove an analogous statement for convex sets. Informally, our main result says that (under mild conditions) every convex set K ⊂R^n has a nontrivial density increment. This means that the fraction of the radius-r sphere that lies within K is significantly larger than the fraction of the radius-r' sphere that lies within K, for r' suitably larger than r. For centrally symmetric convex sets we show that our density increment result is essentially optimal. As a consequence of our Kruskal-Katona type theorem, we obtain the first efficient weak learning algorithm for convex sets under the Gaussian distribution. We show that any convex set can be weak learned to advantage Ω(1/n) in poly(n) time under any Gaussian distribution and that any centrally symmetric convex set can be weak learned to advantage Ω(1/√(n)) in poly(n) time. We also give an information-theoretic lower bound showing that the latter advantage is essentially optimal for poly(n) time weak learning algorithms. As another consequence of our Kruskal-Katona theorem, we give the first nontrivial Gaussian noise stability bounds for convex sets at high noise rates. Our results extend the known correspondence between monotone Boolean functions over {0,1}^n and convex bodies in Gaussian space.
READ FULL TEXT