Journal of Machine Learning Research · 2010 · 23 citations · 0 references
Artificial IntelligenceStatistical LearningEngineeringMachine LearningAlgorithmic LearningComputational ComplexityClassification MethodData ScienceData MiningPattern RecognitionLong-standing AnswerStatisticsSupervised LearningComputational Learning TheoryKnowledge DiscoveryLearning AnalyticsStatistical Learning TheoryUniform ConvergenceData ClassificationBasic QuestionStatistical InferenceClassificationMedicine
Learnability, a core question in statistical learning theory, has traditionally been equated with uniform convergence of empirical risk to population risk, especially in supervised classification and regression, implying that learnable problems are solvable via empirical risk minimization. The paper investigates the General Learning Setting, a framework encompassing most statistical learning problems. The authors analyze the General Learning Setting, a broad framework that subsumes most statistical learning problems. The study demonstrates that within the General Learning Setting, some learnable problems lack uniform convergence and fail empirical risk minimization, yet are solvable via alternative methods, establishing stability as the necessary and sufficient condition for learnability and revealing that learnability conditions are far more complex than in supervised classification and regression.
The problem of characterizing learnability is the most basic question of statistical learning theory. A fundamental and long-standing answer, at least for the case of supervised classification and regression, is that learnability is equivalent to uniform convergence of the empirical risk to the population risk, and that if a problem is learnable, it is learnable via empirical risk minimization. In this paper, we consider the General Learning Setting (introduced by Vapnik), which includes most statistical learning problems as special cases. We show that in this setting, there are non-trivial learning problems where uniform convergence does not hold, empirical risk minimization fails, and yet they are learnable using alternative mechanisms. Instead of uniform convergence, we identify stability as the key necessary and sufficient condition for learnability. Moreover, we show that the conditions for learnability in the general setting are significantly more complex than in supervised classification and regression.