The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries

Abstract

We consider the problem of learning convex polytopes from membership queries only, where the learner is initially provided with a single interior point. The class of polytopes learnable in this setting turns out to be those whose vertices can be efficiently enumerated given their bounding hyperplanes. It is an open question whether in general one can enumerate the vertices of a given polytope in time polynomial in the number of vertices. In fact, we show that both problems are equivalent. We also give a query-based algorithm for the related problem of piecewise linear function regression. The bit complexity of the instances in our queries and the time complexity are polynomial in the bit complexity of the coefficients of the equations defining the bounding hyperplanes. This is consistent with prior established results showing that the weights, not the size, of a neural network determine the complexity of learning. As in previous positive results on learning convex...