PAC Learning for Complex Learning Problems with Realizable-Statistic Conditional Label Distributions
Shivani Agarwal
There has been much interest in exploring intermediate PAC learning models between the realizable and (fully) agnostic settings, that allow both for some stochasticity in the labels and for computationally efficient learning algorithms with finite sample complexity bounds. Some examples of such models include random classification noise (RCN), Massart noise, and generalized linear models (GLMs). Most of this work has focused on the binary classification problem. In this paper, we study a broad range of more complex learning problems under what we call realizable-statistic models (RSMs), wherein we allow stochastic labels but assume that some vector-valued statistic of the conditional label distribution comes from some known function class. RSMs can be viewed as generalizing GLMs to both more general function classes and more general learning problems. We give a general result showing that for a broad set of RSM learning problems, convex surrogate risk minimization algorithms designed to estimate the underlying statistic via an appropriately defined strongly proper composite surrogate loss yield computationally efficient learning algorithms with finite sample complexity bounds. We then apply this result to show that various commonly used (and in some cases, not so commonly used) convex surrogate risk minimization algorithms yield computationally efficient learning algorithms with finite sample complexity bounds for a variety of learning problems including binary classification, multiclass classification, multi-label prediction, and subset ranking. In terms of the distribution over the domain/instance space, our results are all distribution-independent. To our knowledge, these are the first such results for PAC learning with stochastic labels for such a broad set of learning problems.