The Teaching Dimension of Linear Learners
This work addresses a foundational gap in learning theory for practitioners and researchers using optimization-based learners, though it is incremental as it extends existing teaching dimension concepts to new models.
The paper tackles the problem of determining the minimum training set size needed to teach a target model to modern linear learners like ridge regression, SVMs, and logistic regression, which was previously only studied for version-space learners, and presents the first known teaching dimensions and optimal training sets for these methods.
Teaching dimension is a learning theoretic quantity that specifies the minimum training set size to teach a target model to a learner. Previous studies on teaching dimension focused on version-space learners which maintain all hypotheses consistent with the training data, and cannot be applied to modern machine learners which select a specific hypothesis via optimization. This paper presents the first known teaching dimension for ridge regression, support vector machines, and logistic regression. We also exhibit optimal training sets that match these teaching dimensions. Our approach generalizes to other linear learners.