## [Complejidad de Rademacher](/es/node/60595) Definición La complejidad de Rademacher es una medida dependiente de los datos de la riqueza de una clase de funciones F sobre una muestra x_1,...,x_n, definida como la esperanza del supremo sobre F de la correlación media con signos de Rademacher aleatorios σ_i∈{±1}: R_n(F)=E_σ[ sup_{f∈F} (1/n)∑_{i=1}^n σ_i f(x_i) ]. Cuantifica cuánto pueden las funciones de F ajustar ruido ±1 aleatorio en la muestra. ## Principio Principio Evaluar la capacidad de la clase de funciones por su habilidad para alinearse con signos aleatorios en una muestra dada: una alta complejidad de Rademacher indica que muchas funciones pueden correlacionar arbitrariamente con el ruido, implicando riesgo de sobreajuste. ## Demostración Demostración Para predictores lineales con norma acotada en R^d y una muestra fija, la complejidad empírica de Rademacher escala como la cota de la norma multiplicada por la norma media de las características dividida por √n; esto conduce a cotas explícitas de generalización para modelos lineales regularizados. ## Aplicación incorrecta Aplicación incorrecta Usar la complejidad empírica de Rademacher calculada en el conjunto de entrenamiento como si fuera igual a la complejidad poblacional sin argumentos de concentración; o aplicarla a clases de funciones no acotadas sin truncamiento o control de varianza. ## Consecuencia Consecuencia La complejidad de Rademacher produce cotas de generalización ajustadas y dependientes de los datos mediante simetrización: brecha de generalización esperada ≤ 2·R_n(F)+términos de orden inferior, permitiendo selección de modelos y control de capacidad informados por los datos observados. ## Inversión Inversión Contrastarla con medidas combinatorias (dimensión VC) o métricas (recubrimiento/entropía): la complejidad de Rademacher depende de la muestra y es aleatoria, mientras que la dimensión VC es independiente de la distribución y combinatoria; la inversión enfatiza descripciones empíricas versus uniformes de la complejidad. ## Límite Límite Depende de la muestra, la clase de funciones y de cualquier cota sobre los valores de función; tiene sentido sólo si las funciones son medibles y adecuadamente acotadas (o subgaussianas); no mide directamente error de aproximación ni rendimiento worst-case sobre la población. ## Tensión semántica Tensión semántica Tensión con cotas basadas en números de cobertura y VC: la complejidad de Rademacher suele ofrecer cotas más ajustadas y dependientes de los datos pero requiere cálculo en la muestra y consideraciones de concentración, mientras que otras medidas son independientes de la distribución o fáciles de relacionar con supuestos métricos. ## Síntesis Síntesis La complejidad de Rademacher resume cuánto puede una clase de funciones ajustar etiquetas ±1 aleatorias en una muestra concreta en un solo número dependiente de los datos: es la correlación máxima esperada con signos de Rademacher y una cantidad central en las garantías modernas de generalización.