Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions
We provide new results for noise-tolerant and sample-efficient learning algorithms under s-concave distributions. The new class of s-concave distributions is a broad and natural generalization of log-concavity, and includes many important additional distributions, e.g., the Pareto distribution and t-distribution. This class has been studied in the context of efficient sampling, integration, and optimization, but much remains unknown about the geometry of this class of distributions and their applications in the context of learning. The challenge is that unlike the commonly used distributions in learning (uniform or more generally log-concave distributions), this broader class is not closed under the marginalization operator and many such distributions are fat-tailed. In this work, we introduce new convex geometry tools to study the properties of s-concave distributions and use these properties to provide bounds on quantities of interest to learning including the probability of disagreement between two halfspaces, disagreement outside a band, and the disagreement coefficient. We use these results to significantly generalize prior results for margin-based active learning, disagreement-based active learning, and passive learning of intersections of halfspaces. Our analysis of geometric properties of s-concave distributions might be of independent interest to optimization more broadly.
This review is adapted from my review from COLT 2017 - My feedback to this paper has not changed much since then.
This paper studies a new family of distributions, s-concave distributions, which appears in works of (Brascamp and Lieb, 1976; Bobkov, 2007, Chandrasekaran, Deshpande and Vempala, 2009). The main result is a series of upper and lower bounds regarding its probability distribution function and its measure over certain regions. These inequalities can be readily applied to (active) learning linear separators and learning the intersection of two halfspaces.
Overall this is an interesting paper, extending the family of distributions in which the problem of learning linear separators can be efficiently solved. This may spur future research on establishing new distribution-dependent conditions for (efficient) learnability.
Technical quality: on one hand, the results are impressive, since the family of admissible distributions (in the sense of Awasthi, Balcan and Long, 2014 and Klivans, Long and Tang, 2009) is broadened; on the other hand, the analysis only works when -1/(2n+3)<=s<=0. In high dimensional settings, the range of s is fairly small. 
Novelty: the result of this paper follows the reasoning in (Lovasz and Vempala, 2007); but this is definitely a non-trivial extension.
Potential Impact: this work may spur future research on distributional conditions for efficient learnability.