Resumo Técnico: Bagging Aprende Robustamente Classes VC com Complexidade de Amostra Linear

Declaração do Problema

O artigo aborda o desafio fundamental de aprender preditores que sejam robustos a exemplos adversários em tempo de teste. Dado um espaço de instâncias $\mathcal{X}$, um espaço de rótulos $\mathcal{Y} = \{-1, 1\}$, e um adversário definido por um mapa de perturbação $U: \mathcal{X} \to 2^\mathcal{X}$, o objetivo é aprender um preditor $\hat{f}$ que minimize o risco robusto populacional:
$$R_U(\hat{f}; P) = \mathbb{E}_{(X,Y) \sim P} \left[ \sup_{Z \in U(X)} \mathbb{1}\{\hat{f}(Z) \neq Y\} \right]$$
onde $P$ é uma distribuição desconhecida sobre $\mathcal{X} \times \mathcal{Y}$.

O artigo foca na aprendibilidade de classes de funções $\mathcal{F}$ com dimensão Vapnik-Chervonenkis (VC) finita $d$. Trabalhos anteriores estabeleceram que, embora as classes VC sejam aprendíveis no cenário PAC padrão, o aprendizado adversariamente robusto enfrenta obstáculos significativos. Especificamente, Montasser, Hanneke e Srebro [2019] mostraram que:

1. Aprendizado próprio (restringindo a saída à classe $\mathcal{F}$) pode falhar mesmo para classes com dimensão VC 1.
2. Aprendizado impróprio é possível, mas o melhor limite conhecido para a complexidade de amostra era exponencial em $d$.
3. Algoritmos impróprios existentes são computacionalmente ineficientes, exigindo $O(nd)$ chamadas a um oráculo de Minimização do Risco Empírico Robusto (RERM) com um overhead proibitivo.

A questão central é se é possível projetar algoritmos que sejam tanto eficientes em amostras (lineares em $d$) quanto eficientes em oráculo (poucas chamadas ao RERM) para o aprendizado adversariamente robusto.

Metodologia

O autor propõe um simples algoritmo de aprendizado impróprio que combina Bagging (Bootstrap Aggregation) com Minimização do Risco Empírico Robusto (RERM).

O Algoritmo (Bagging Robust ERMs)

Dado um conjunto de treinamento $S$ de tamanho $n$, um parâmetro de confiança $\delta$ e um oráculo RERM $\hat{f}$:

1. Defina o número de amostras de bootstrap $N = O(d^\star + \log(1/\delta))$, onde $d^\star$ é a dimensão VC dual da classe $\mathcal{F}$.
2. Para cada $i \in \{1, \dots, N\}$:
   • Selecione um tamanho aleatório $t$ de um intervalo específico $J_n = \{n/4, \dots, n-1\}$.
   • Amostre um conjunto de dados de bootstrap $S'_i$ de tamanho $t$ uniformemente com reposição a partir do prefixo de $S$ de comprimento $t$.
   • Execute o oráculo RERM em $S'_i$ para obter um preditor $\hat{f}_{S'_i} \in \mathcal{F}$.
3. Retorne o voto da maioria dos $N$ preditores: $\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$.

Abordagem Teórica

A análise diverge de argumentos anteriores de compressão de amostras. Em vez disso, emprega uma análise leave-one-out adaptada ao risco robusto:

1. Distribuição sobre RERMs: O autor analisa a distribuição dos erros cometidos por RERMs treinados em subconjuntos aleatórios. Eles provam que, para um exemplo de teste aleatório $(X, Y)$ e qualquer perturbação $Z \in U(X)$, a fração de RERMs que classificam incorretamente $Z$ é pequena em expectativa ($\tilde{O}(d/n)$).
2. Limite Leave-One-Out: Ao aplicar essa expectativa a uma distribuição empírica, eles estabelecem um limite para o risco robusto do preditor de "bagging total" (uma média idealizada sobre todos os bootstraps possíveis).
3. Esparsificação: Como o preditor de bagging total é intratável, o autor utiliza uma técnica de esparsificação (Moran e Yehudayoff [2016]) para aproximar o voto agregado usando apenas $N = O(d^\star)$ amostras de bootstrap independentes. Este passo vincula a complexidade do oráculo diretamente à dimensão VC dual $d^\star$.

Contribuições Principais e Resultados

1. Limite Superior: Complexidade de Amostra Linear

O principal resultado (Teorema 1) estabelece que as classes VC são adversariamente robustamente aprendíveis com complexidade de amostra linear na dimensão VC $d$.

• Complexidade de Amostra: $O(d/\epsilon + \frac{1}{\epsilon}\log(1/\delta))$. Isso proporciona uma melhoria exponencial em relação ao limite anterior de $O(\exp(d))$.
• Complexidade de Oráculo: O algoritmo realiza $N = O(d^\star)$ chamadas ao oráculo RERM.
• Eficiência Computacional: O algoritmo é paralelizável (ao contrário das abordagens baseadas em boosting anteriores) e incorre em apenas $O(d^\star n)$ de overhead computacional.
• Cenário Agnóstico: Ao combinar este resultado realizável com uma redução do cenário agnóstico (Montasser et al. [2019]), o autor deriva um aprendiz agnóstico com complexidade de amostra $\tilde{O}(\sqrt{d/n})$ e complexidade de oráculo $O(d^\star \log n)$.

2. Limite Inferior: Necessidade da Dimensão VC Dual

O artigo prova que a dependência da dimensão VC dual $d^\star$ na complexidade do oráculo é inevitável (Teorema 2).

• Resultado: Existem classes com dimensão VC $d$ e dimensão VC dual $d^\star = 2^{d+1}-1$ tais que qualquer algoritmo que realize menos de $d^\star - 1$ chamadas a um oráculo RERM falha em aprender robustamente, independentemente do número de amostras de treinamento fornecidas.
• Implicação: Diferente do aprendizado PAC clássico onde $O(\log n)$ ou chamadas constantes de ERM são suficientes, o aprendizado adversariamente robusto requer inerentemente $\Omega(d^\star)$ consultas ao oráculo. Isso destaca uma separação fundamental entre a complexidade do aprendizado padrão e do aprendizado robusto.

3. Caracterização Técnica

Os resultados implicam que a medida de complexidade refinada $\dim(\mathcal{F}, U)$ proposta por Montasser, Hanneke e Srebro [2022] é limitada pela dimensão VC $d$, resolvendo uma conjectura de que esta medida poderia ser significativamente maior.

Significância e Alegações

O artigo afirma fornecer uma "receita" para o aprendizado PAC robusto computacionalmente eficiente. Ao demonstrar que uma simples heurística de bagging combinada com RERM alcança a complexidade de amostra ideal, o trabalho preenche a lacuna entre a robustez teórica e a eficiência algorítmica prática.

As principais alegações sobre a contribuição do artigo incluem:

• Melhoria Exponencial: Mudança de complexidade de amostra exponencial para linear em $d$.
• Eficiência de Oráculo: Redução das chamadas de oráculo de $O(nd)$ para $O(d^\star)$, tornando a abordagem viável para classes onde o RERM é computacionalmente tratável.
• Limite Fundamental: Estabelecer que a dimensão VC dual é a barreira correta para a eficiência de oráculo no aprendizado robusto, contrastando com o papel da dimensão VC no aprendizado padrão.
• Relevância Prática: A paralelizabilidade do algoritmo e sua dependência de oráculos RERM padrão (que correspondem às heurísticas de treinamento adversário usadas na prática) sugerem que essas melhorias teóricas são diretamente aplicáveis aos contextos modernos de aprendizado profundo.

O autor observa que, embora o algoritmo seja impróprio (retornando um voto da maioria em vez de uma única função em $\mathcal{F}$), isso é necessário para alcançar esses limites, espelhando a distinção entre aprendizado próprio e impróprio no cenário robusto. O trabalho unifica a eficiência algorítmica com a robustez provável, sugerindo que o aprendizado robusto eficiente é possível se aceitarmos aprendizes impróprios e aproveitarmos a dimensão VC dual.