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.

本文提出了一种新的 $s$-concave 分布类别，基于凸几何工具研究了该分布类别并将其应用于学习算法中，在边缘化算子下提供了有关 $s$-concave 分布的性质和一些学习问题的收敛界限。