Reviews: Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions

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.