Complexidade de Rademacher

Motivação: capacidade que depende dos dados

Na teoria estatística do aprendizado, uma questão central é: por que minimizar o erro de treino frequentemente produz um modelo que funciona bem em dados não vistos? A resposta depende de controle de capacidade (capacity control): se sua classe de hipóteses for rica demais em relação à quantidade de dados, ela pode ajustar ruído (veja Sobreajuste e Regularização).

Medidas clássicas de capacidade como a dimensão VC (VC dimension) são livres de distribuição e de pior caso (veja Dimensão VC). Elas podem ser muito informativas, mas às vezes também pessimistas: dois conjuntos de dados do mesmo tamanho podem ser “fáceis” ou “difíceis” dependendo de geometria, margens, normas das características, etc., e a dimensão VC não enxerga isso.

A complexidade de Rademacher (Rademacher complexity) preenche essa lacuna ao fornecer uma medida dependente dos dados de quão bem uma classe de funções consegue correlacionar-se com ruído puro na amostra observada. Ela leva a limites uniformes de generalização (uniform generalization bounds) e é amplamente usada para analisar minimização do risco empírico (ERM, empirical risk minimization), aprendizado baseado em margem (margin-based learning), métodos de kernel (kernel methods) e preditores com normas controladas (norm-controlled predictors).

Definição central

Configuração: classes de funções em vez de “hipóteses”

A complexidade de Rademacher é tipicamente definida para uma classe de funções de valores reais [ \mathcal{F} \subseteq { f: \mathcal{X} \to \mathbb{R} }. ] Isso é conveniente porque muitos problemas de aprendizado se reduzem a limitar desvios de médias empíricas de funções.

Dada uma amostra (S = (x_1,\dots,x_n)), definimos variáveis de Rademacher (Rademacher variables) [ \sigma_1,\dots,\sigma_n \overset{i.i.d.}{\sim} \text{Unif}{-1,+1}. ]

Complexidade de Rademacher empírica

A complexidade de Rademacher empírica (empirical Rademacher complexity) de (\mathcal{F}) na amostra (S) é [ \widehat{\mathfrak{R}}{S}(\mathcal{F}) ;=; \mathbb{E}{\sigma}\left[\sup_{f\in\mathcal{F}} \frac{1}{n}\sum_{i=1}^n \sigma_i f(x_i)\right]. ]

Pontos-chave:

  • A expectativa é sobre os sinais aleatórios (\sigma), condicionando na amostra fixa (S).
  • O supremo pergunta: qual função na classe melhor se correlaciona com os sinais aleatórios?

Complexidade de Rademacher esperada (nível de distribuição)

Se a própria amostra (S) é aleatória, extraída i.i.d. de uma distribuição (D) sobre (\mathcal{X}), definimos [ \mathfrak{R}{n}(\mathcal{F}) ;=; \mathbb{E}{S\sim D^n}\left[\widehat{\mathfrak{R}}_{S}(\mathcal{F})\right]. ] Isso deixa de ser dependente dos dados, mas frequentemente é mais fácil de analisar teoricamente.

Intuição: “correlação com sinais aleatórios” como teste de ajuste a ruído

Imagine atribuir a cada ponto de dados um rótulo aleatório (\sigma_i \in {-1,+1}), como jogar uma moeda justa. Se sua classe de funções (\mathcal{F}) consegue produzir uma função (f) tal que (f(x_i)) tende a ter o mesmo sinal que (\sigma_i) (ou grande correlação positiva), então (\mathcal{F}) consegue ajustar ruído bem — sugerindo alta capacidade e risco de sobreajuste.

A quantidade [ \frac{1}{n}\sum_{i=1}^n \sigma_i f(x_i) ] é uma correlação empírica entre (f(x_i)) e o ruído aleatório (\sigma_i). Tomar o supremo sobre (f\in\mathcal{F}) mede a melhor correlação atingível, e a expectativa sobre (\sigma) faz a média sobre muitas realizações de ruído aleatório.

Assim:

  • Complexidade de Rademacher pequena: mesmo a melhor função não consegue se alinhar com sinais aleatórios → a classe é “estável” nesse conjunto de dados → melhor generalização.
  • Complexidade de Rademacher grande: a classe consegue se alinhar com sinais aleatórios → ela pode ajustar ruído → garantias de generalização mais fracas.

Limites de generalização: como ela controla a lacuna entre treino e teste

A complexidade de Rademacher é usada principalmente para limitar a diferença entre a expectativa verdadeira e a média empírica uniformemente sobre uma classe de funções.

Assuma que as funções são limitadas, por exemplo (f(x)\in[0,1]). Então, com probabilidade de pelo menos (1-\delta) sobre o sorteio de (S\sim D^n), [ \forall f\in\mathcal{F}:\quad \mathbb{E}[f(X)] ;\le; \frac{1}{n}\sum_{i=1}^n f(x_i) ;+; 2,\widehat{\mathfrak{R}}_{S}(\mathcal{F}) ;+; 3\sqrt{\frac{\log(2/\delta)}{2n}}. ]

Interpretação:

  • A média empírica é o que o ERM minimiza.
  • O termo de complexidade (2\widehat{\mathfrak{R}}_{S}(\mathcal{F})) é uma penalidade dependente dos dados.
  • O termo final é uma folga de concentração.

Limitando o risco excedente para ERM

Em aprendizado supervisionado, seja (z=(x,y)), perda (\ell(h,z)\in[0,1]), classe de hipóteses (\mathcal{H}), e defina a classe de perdas induzida [ \mathcal{L} = { z \mapsto \ell(h,z) : h\in\mathcal{H}}. ] Seja (\hat{h}) um minimizador ERM do risco empírico e (h^\star) um minimizador do risco populacional dentro de (\mathcal{H}). Então, resultados típicos baseados em Rademacher fornecem (até constantes e termos de confiança) [ R(\hat{h}) - R(h^\star) ;\lesssim; \mathfrak{R}_n(\mathcal{L}), ] isto é, o risco excedente (excess risk) é controlado pela complexidade da classe de perdas.

Essa é uma das formas mais limpas de formalizar a ideia de que o ERM funciona quando a capacidade efetiva da classe é pequena em relação a (n). Para um contexto mais amplo, veja Aprendizado PAC e Generalização e Viés/Variância.

Propriedades úteis e ferramentas padrão

A complexidade de Rademacher não é apenas uma definição — ela vem com um kit de ferramentas.

Monotonicidade

Se (\mathcal{F}\subseteq \mathcal{G}), então (\widehat{\mathfrak{R}}_S(\mathcal{F}) \le \widehat{\mathfrak{R}}_S(\mathcal{G})).

Escalonamento

Para escalar (a), (\widehat{\mathfrak{R}}_S(a\mathcal{F}) = |a|,\widehat{\mathfrak{R}}_S(\mathcal{F})).

Classes finitas: comportamento \(\log|\mathcal{F}|\)

Se (\mathcal{F}) é finita e (f(x)\in[0,1]), então [ \widehat{\mathfrak{R}}_S(\mathcal{F}) ;\lesssim; \sqrt{\frac{\log|\mathcal{F}|}{n}}. ] Assim, “espaços de hipóteses finitos” generalizam como (O(\sqrt{\log|\mathcal{F}|/n})), alinhando-se com a intuição de limites por união (union bounds).

Lema de contração (contraction lemma) (crítico em ML)

Se (\phi:\mathbb{R}\to\mathbb{R}) é (L)-Lipschitz, então (informalmente) [ \widehat{\mathfrak{R}}_S(\phi\circ\mathcal{F}) ;\le; L,\widehat{\mathfrak{R}}_S(\mathcal{F}). ] Isso permite transformar limites de complexidade em preditores (por exemplo, escores (f(x))) em limites de complexidade em perdas como logística, hinge ou quadrática (com suposições apropriadas de limitação).

Relação com dimensão VC e números de cobertura

A complexidade de Rademacher se insere em uma rede de medidas de capacidade:

Conexão com dimensão VC (classificação)

Para classificação binária, uma classe com dimensão VC (d) tipicamente tem complexidade de Rademacher escalando como [ \mathfrak{R}_n(\mathcal{F}) ;=; O!\left(\sqrt{\frac{d}{n}}\right) ] (até constantes e fatores logarítmicos, dependendo das suposições e de como a classe de funções é representada).

Assim, a dimensão VC implica limites superiores para a complexidade de Rademacher, mas Rademacher pode ser menor em amostras “fáceis” (por exemplo, grandes margens), tornando-a uma ferramenta mais precisa em muitas análises práticas.

Conexão com números de cobertura (covering numbers) (entropia métrica (metric entropy))

Números de cobertura medem quantas bolas de pequeno raio são necessárias para aproximar uma classe de funções sob uma métrica (frequentemente (L_2) empírica na amostra). Existem limites do seguinte tipo (integrais de entropia no estilo de Dudley): [ \widehat{\mathfrak{R}}{S}(\mathcal{F}) ;\lesssim; \frac{1}{\sqrt{n}} \int{0}^{\infty} \sqrt{\log \mathcal{N}(\epsilon, \mathcal{F}, |\cdot|{2,S})}; d\epsilon, ] onde (\mathcal{N}(\epsilon,\cdot)) é um número de cobertura e (|\cdot|{2,S}) é a norma (L_2) empírica na amostra.

Interpretação:

  • Se (\mathcal{F}) pode ser coberta por poucas bolas em escalas finas, ela não consegue ajustar bem sinais aleatórios.
  • Isso conecta a complexidade de Rademacher a noções clássicas de “tamanho” e suavidade de classes de funções.

Exemplos práticos (como os números se parecem)

Exemplo 1: conjunto finito de hipóteses (seleção de modelo em uma família pequena)

Suponha que (\mathcal{F}) contenha (M) preditores fixos e limitados (por exemplo, (M) regras projetadas manualmente), cada um retornando valores em ([0,1]). Então [ \widehat{\mathfrak{R}}_S(\mathcal{F}) ;\lesssim; \sqrt{\frac{\log M}{n}}. ]

Leitura prática: dobrar o número de regras candidatas só aumenta a complexidade como (\sqrt{\log 2}), o que é suave. Isso combina com a intuição por trás de selecionar a partir de um menu de modelos.

Exemplo 2: preditores lineares com restrições de norma

Seja (\mathcal{F}) o conjunto de funções lineares (f_w(x)=\langle w,x\rangle) com (|w|_2 \le B), e assuma que a amostra satisfaz (|x_i|2 \le R). Então [ \widehat{\mathfrak{R}}S(\mathcal{F}) ;\le; \frac{B}{n},\mathbb{E}\sigma\left|\sum{i=1}^n \sigma_i x_i\right|_2 ;\le; \frac{BR}{\sqrt{n}}. ]

Conclusões:

  • Normas de pesos maiores (menos regularização) aumentam a complexidade.
  • Normas de características maiores aumentam a complexidade.
  • A complexidade diminui como (1/\sqrt{n}), uma taxa típica na teoria do aprendizado.

Essa é uma das razões pelas quais a regularização (L_2) pode ser interpretada como controle de capacidade, não apenas um truque de otimização.

Exemplo 3: métodos de kernel (complexidade via norma em RKHS)

Em um espaço de Hilbert com núcleo reprodutor (RKHS, reproducing kernel Hilbert space) com mapeamento de características (feature map) (\phi(x)), considere funções (f(x)=\langle w, \phi(x)\rangle) com (|w|_{\mathcal{H}} \le B). Se (k(x,x)\le \kappa^2), então, de forma semelhante, [ \widehat{\mathfrak{R}}_S(\mathcal{F}) ;\le; \frac{B\kappa}{\sqrt{n}}. ]

Isso se alinha às análises de generalização de máquinas de vetores de suporte (SVMs, support vector machines) e regressão ridge com kernel (kernel ridge regression): a restrição da norma em RKHS é o “botão” de capacidade.

Exemplo 4: transformando limites de escores em limites de perdas (logistic / hinge)

Se você analisa um classificador por meio de um escore de valor real (f(x)) e então usa uma perda Lipschitz (\ell(y f(x))) (por exemplo, hinge, logística em domínios limitados), o lema de contração implica que a complexidade de Rademacher da classe de perdas é no máximo uma constante vezes a complexidade da classe de escores.

Implicação prática: frequentemente você pode:

  1. Limitar a complexidade das suas funções de escore (lineares, RKHS, redes com normas controladas),
  2. Multiplicar por uma constante de Lipschitz,
  3. Substituir em um limite de generalização/risco excedente.

Exemplo 5: redes neurais (capacidade baseada em norma, não na contagem de parâmetros)

Resultados modernos frequentemente limitam a complexidade de Rademacher de redes neurais em termos de produtos/somas de normas das camadas (normas espectrais, normas de Frobenius, normas de caminho), em vez de pura contagem de parâmetros. Embora os limites mais apertados e as melhores escolhas de norma ainda sejam uma área ativa de pesquisa, a mensagem de alto nível é:

  • A capacidade pode permanecer controlada mesmo com muitos parâmetros se as normas efetivas forem pequenas.
  • Medidas de complexidade dependentes dos dados ajudam a explicar por que modelos superparametrizados podem generalizar (embora dinâmicas de otimização e regularização implícita (implicit regularization) também importem; veja Estabilidade Algorítmica como uma lente complementar).

Estimando a complexidade de Rademacher empírica na prática

A definição envolve uma expectativa sobre sinais aleatórios e um supremo sobre a classe. Na prática, muitas vezes você pode aproximar (\widehat{\mathfrak{R}}_S(\mathcal{F})) via Monte Carlo:

  1. Amostre (T) vetores de sinais aleatórios (\sigma^{(t)}\in{-1,+1}^n).
  2. Para cada um, compute (ou aproxime)
    (\sup_{f\in\mathcal{F}} \frac{1}{n}\sum_i \sigma_i^{(t)} f(x_i)).
  3. Faça a média sobre (t).

Para muitas classes de hipóteses, esse “sup” é, por si só, um problema de otimização semelhante ao treinamento — às vezes exatamente ERM com rótulos/alvos randomizados.

Esboço: classe linear com restrição de norma \(L_2\)

Para \(\mathcal{F}=\{x\mapsto w^\top x: \|w\|_2\le B\}\), o supremo tem forma fechada: \[ \sup_{\|w\|\le B} \frac{1}{n}\sum_i \sigma_i w^\top x_i

\frac{B}{n}\left|\sum_i \sigma_i x_i\right|_2. ]

Assim, você pode estimá-lo diretamente:

import numpy as np

def rademacher_complexity_linear(X, B, T=200, seed=0):
    """
    X: (n, d) feature matrix
    B: L2 norm bound on w
    """
    rng = np.random.default_rng(seed)
    n, d = X.shape
    vals = []
    for _ in range(T):
        sigma = rng.choice([-1.0, 1.0], size=n)
        v = (sigma[:, None] * X).sum(axis=0)   # sum_i sigma_i x_i
        vals.append((B / n) * np.linalg.norm(v, ord=2))
    return float(np.mean(vals))

Esse tipo de estimativa às vezes é usado em protótipos de pesquisa para diagnósticos de capacidade dependentes dos dados, embora seja menos comum na prática cotidiana de ML do que proxies mais simples (curvas de validação, trajetórias de regularização, etc.).

Usos comuns em teoria e prática de ML

1) Limites de generalização para ERM

A complexidade de Rademacher é um caminho padrão para limites da forma: [ R(\hat{h}) \le \hat{R}(\hat{h}) + \text{complexity} + \text{confidence}, ] e para limites de risco excedente para ERM. Isso sustenta diretamente a base conceitual do Aprendizado PAC.

2) Minimização estrutural do risco (SRM, structural risk minimization) e comparação de modelos

Se você tem classes aninhadas (\mathcal{F}_1 \subset \mathcal{F}_2 \subset \cdots), você pode escolher a classe que minimiza [ \hat{R}(f) + \lambda_k \cdot \widehat{\mathfrak{R}}_S(\mathcal{F}_k), ] o que é um princípio de seleção com penalização por capacidade. Na prática, validação cruzada é mais comum, mas SRM fornece um “projeto” teórico.

3) Entender regularização como controle de capacidade

Muitos regularizadores (penalidades de norma, restrições de margem, parada antecipada) reduzem um limite superior da complexidade de Rademacher. Isso fornece uma explicação fundamentada para por que eles melhoram o desempenho em teste, complementando a história intuitiva em Sobreajuste e Regularização.

4) Taxas mais rápidas via *complexidade de Rademacher local (local Rademacher complexity)* (avançado)

Limites padrão frequentemente dão taxas (O(1/\sqrt{n})). Sob condições adicionais (por exemplo, baixo ruído, forte convexidade, curvatura favorável), a complexidade de Rademacher local analisa a complexidade perto da solução aprendida e pode produzir taxas mais rápidas do tipo (O(1/n)) em alguns regimes. Isso é particularmente relevante em análises refinadas de ERM e classificação baseada em margem.

Limitações e ressalvas

  • Dificuldade computacional: para classes complexas, o supremo pode ser difícil de computar exatamente (às vezes NP-difícil). Limites ou relaxações são usados em seu lugar.
  • Suposições de limitação / caudas: muitos resultados limpos assumem perdas limitadas ou comportamento subgaussiano (sub-Gaussian). Dados com caudas pesadas (heavy-tailed) exigem mais cuidado.
  • Pode ser frouxa na prática: constantes e etapas de pior caso (simetrização (symmetrization), limites por união, relaxações Lipschitz) podem tornar limites numéricos excessivamente conservadores.
  • Não captura diretamente efeitos de otimização: dois algoritmos usando a mesma classe de hipóteses podem generalizar de forma diferente devido a viés implícito ou estabilidade. A complexidade de Rademacher diz respeito à classe (ou a um subconjunto restrito), não à dinâmica completa de aprendizado — compare com Estabilidade Algorítmica.

Resumo

A complexidade de Rademacher é uma medida de capacidade dependente dos dados definida como a habilidade esperada de uma classe de funções de correlacionar-se com ruído aleatório ±1 na amostra observada. Ela desempenha um papel central na teoria moderna do aprendizado ao fornecer:

  • Limites uniformes de generalização (controle da lacuna treino–teste),
  • Limites de risco excedente para ERM via complexidade da classe de perdas,
  • Conexões com dimensão VC e números de cobertura,
  • Interpretações práticas para regularização e controle por norma em modelos lineares, kernels e (até certo ponto) redes neurais.

Ela é uma das ferramentas mais usadas para traduzir “capacidade do modelo” em garantias de generalização concretas e quantitativas, especialmente quando você quer que o limite reflita a geometria dos dados que você de fato observou, e não um conjunto de dados de pior caso.