A Caltech Library Service

Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries

Kumar, Akash and Singla, Adish and Yue, Yisong and Chen, Yuxin (2020) Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We examine the task of locating a target region among those induced by intersections of n halfspaces in R^d. This generic task connects to fundamental machine learning problems, such as training a perceptron and learning a ϕ-separable dichotomy. We investigate the average teaching complexity of the task, i.e., the minimal number of samples (halfspace queries) required by a teacher to help a version-space learner in locating a randomly selected target. As our main result, we show that the average-case teaching complexity is Θ(d), which is in sharp contrast to the worst-case teaching complexity of Θ(n). If instead, we consider the average-case learning complexity, the bounds have a dependency on n as Θ(n) for i.i.d. queries and Θ(dlog(n)) for actively chosen queries by the learner. Our proof techniques are based on novel insights from computational geometry, which allow us to count the number of convex polytopes and faces in a Euclidean space depending on the arrangement of halfspaces. Our insights allow us to establish a tight bound on the average-case complexity for ϕ-separable dichotomies, which generalizes the known O(d) bound on the average number of "extreme patterns" in the classical computational geometry literature (Cover, 1965).

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2020 A. Kumar, A. Singla, Y. Yue & Y. Chen. We thank Ali Sayyadi for the helpful discussions. This work was supported in part by fundings from PIMCO and Bloomberg.
Funding AgencyGrant Number
Bloomberg Data ScienceUNSPECIFIED
Subject Keywords:Teaching dimension, homogeneous halfspaces, average-case complexity
Record Number:CaltechAUTHORS:20201111-071759033
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106601
Deposited By: Tony Diaz
Deposited On:11 Nov 2020 16:32
Last Modified:11 Nov 2020 16:32

Repository Staff Only: item control page