La complexité de Rademacher est une mesure dépendant des données de la richesse d'une classe de fonctions F sur un échantillon x_1,...,x_n, définie comme l'espérance du suprémum sur F de la corrélation moyenne avec des signes de Rademacher aléatoires σ_i∈{±1} : R_n(F)=E_σ[ sup_{f∈F} (1/n)∑_{i=1}^n σ_i f(x_i) ]. Elle quantifie à quel point les fonctions de F peuvent s'ajuster à un bruit ±1 aléatoire sur l'échantillon.

Principe

Évaluer la capacité d'une classe de fonctions par sa capacité à s'aligner sur des signes aléatoires sur un échantillon donné : une grande complexité de Rademacher indique que de nombreuses fonctions peuvent corréler arbitrairement avec le bruit, suggérant un risque de surapprentissage.

Démonstration

Pour des prédicteurs linéaires à norme bornée dans R^d et un échantillon fixé, la complexité empirique de Rademacher se comporte comme la borne de la norme multipliée par la norme moyenne des caractéristiques divisée par √n ; cela conduit à des bornes de généralisation explicites pour les modèles linéarisés régularisés.

Mauvaise application

Utiliser la complexité empirique de Rademacher calculée sur l'échantillon d'entraînement comme si elle était égale à la complexité populationnelle sans arguments de concentration ; ou l'appliquer à des classes de fonctions non bornées sans tronquer ni contrôler la variance.

Conséquence

La complexité de Rademacher fournit des bornes de généralisation serrées et dépendantes des données via la symétrisation : l'écart de généralisation attendu ≤ 2·R_n(F)+termes d'ordre inférieur, permettant la sélection de modèle et le contrôle de capacité informés par les données observées.

Inversion

Contraster avec des mesures combinatoires (dimension VC) ou métriques (recouvrement/entropie) : la complexité de Rademacher dépend de l'échantillon et est aléatoire, tandis que la dimension VC est indépendante de la distribution et combinatoire ; l'inversion souligne descriptions empiriques versus uniformes de la complexité.

Limite

Dépend de l'échantillon, de la classe de fonctions et des bornes sur les valeurs de fonction ; n'a de sens que lorsque les fonctions sont mesurables et adéquatement bornées (ou sous-gaussiennes) ; ne mesure pas directement l'erreur d'approximation ou la performance au pire sur la population.

Tension sémantique

Tension avec les bornes basées sur le nombre de recouvrement et la VC : la complexité de Rademacher donne souvent des bornes plus fines et dépendantes des données mais requiert un calcul au niveau de l'échantillon et des arguments de concentration, tandis que d'autres mesures sont indépendantes de la distribution ou plus faciles à relier à des hypothèses métriques.

Synthèse

La complexité de Rademacher résume la capacité d'une classe de fonctions à ajuster des labels ±1 aléatoires sur un échantillon donné en un seul nombre dépendant des données : c'est la corrélation maximale espérée avec des signes de Rademacher et une quantité centrale dans les garanties modernes de généralisation.