Permutation Complexity Bound on Out-Sample Error
We define a data dependent permutation complexity for a hypothesis set \math{\hset}, which is similar to a Rademacher complexity or maximum discrepancy. The permutation complexity is based like the maximum discrepancy on (dependent) sampling. We prove a uniform bound on the generalization error, as well as a concentration result which means that the permutation estimate can be efficiently estimated.
Code (0)
등록된 구현이 없습니다.
Tasks
MathSimilar Papers 제목 키워드 기반
Sample Complexity of Nonparametric Semi-Supervised Learning
We study the sample complexity of semi-supervised learning (SSL) and introduce new assumptions based on the mismatch between a mixture model learned from unlabeled data and the true mixture model induced by the (unknown)…
Binary ClassificationClassificationGeneral ClassificationGraph MatchingThe Sample Complexity of Semi-Supervised Learning with Nonparametric Mixture Models
We study the sample complexity of semi-supervised learning (SSL) and introduce new assumptions based on the mismatch between a mixture model learned from unlabeled data and the true mixture model induced by the (unknown)…
Binary ClassificationClassificationGeneral ClassificationGraph MatchingOptimal Learning of Mallows Block Model
The Mallows model, introduced in the seminal paper of Mallows 1957, is one of the most fundamental ranking distribution over the symmetric group $S_m$. To analyze more complex ranking data, several studies considered the…
modelparameter estimationImproved Error Bounds Based on Worst Likely Assignments
Error bounds based on worst likely assignments use permutation tests to validate classifiers. Worst likely assignments can produce effective bounds even for data sets with 100 or fewer training examples. This paper intro…
Multiclass learnability and the ERM principle
We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist…
Binary ClassificationGeneral Classification