Resumo Técnico: Regressão Online Realizável e Aplicações para Redes ReLU

Declaração do Problema

Este artigo investiga a regressão online realizável no cenário adversarial, onde nenhuma suposição estocástica ou de margem é imposta. O problema central é determinar quando a realizabilidade (a existência de uma hipótese alvo $h^* \in \mathcal{H}$ que gera perfeitamente os rótulos) implica um limite de perda cumulativa livre de horizonte (finito), e identificar os parâmetros de complexidade que governam esse limite.

Os autores contrastam isso com a classificação online, onde mesmo classes simples como Perceptrons podem ter limites de erro infinitos sem suposições de margem. Na regressão, entretanto, a realizabilidade pode impor uma perda total finita sob funções de perda métricas, mesmo quando o problema de classificação análogo é não aprendível. O estudo foca em funções de perda $\ell$ que satisfazem uma desigualdade triangular aproximada (pseudo-métricas aproximadas), uma condição necessária para evitar cenários degenerados onde um aprendiz pode prever rótulos intermediários com perda negligenciável, apesar de grandes lacunas no espaço de hipóteses.

Metodologia

O artigo introduz um método de potencial genérico para limitar superiormente a dimensão de Littlestone escalonada ($D_{\text{onl}}$), uma dimensão abstrata introduzida por Attias et al. [2] que caracteriza a perda cumulativa minimax realizável.

O Framework do Potencial de Entropia

Em vez de computar diretamente $D_{\text{onl}}$, que pode ser difícil, os autores limitam superiormente ela usando um integral de entropia do tipo Dudley baseado nos números de cobertura da classe de hipóteses $\mathcal{H}$ sob a pseudo-métrica sup induzida $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$.

1. Definição de Potencial de Entropia: Para uma classe de hipóteses $\mathcal{H}$ com diâmetro finito, o potencial de entropia é definido como:
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   onde $N(\mathcal{H}, \varepsilon)$ é o número de cobertura $\varepsilon$ de $\mathcal{H}$ em relação a $d_\ell$.

2. Teorema Principal: Os autores provam que, para qualquer perda de pseudo-métrica $c$-aproximada, a dimensão de Littlestone escalonada é limitada pelo potencial de entropia:
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   A prova utiliza um argumento de limitação por ramificação (branch bound) em árvores de Littlestone escalonadas realizáveis. Ao analisar os espaços de versão em cada nó, eles mostram que a desigualdade triangular aproximada força qualquer cobertura $\varepsilon$ a se dividir entre os filhos de um nó com lacuna $\gamma$ quando $\varepsilon < \gamma/(2c)$. Integrar essa "divisão de cobertura" através das escalas resulta em uma queda de potencial proporcional à lacuna, limitando a lacuna total ao longo de qualquer ramificação por $\Phi(\mathcal{H})$.

3. Implicação: Se $\mathcal{H}$ possui números de cobertura polinomiais (ou seja, $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$), então $\Phi(\mathcal{H}) < \infty$, implicando um limite de perda cumulativa realizável livre de horizonte.

Contribuições Principais e Resultados

1. Regressão Lipschitz sob Perda $\ell_q$

Os autores aplicam seu framework à classe $\mathcal{H}_L$ de funções $L$-Lipschitz em $[-1, 1]^d$ sob a perda $\ell_q(y, y') = |y - y'|^q$. Eles estabelecem uma transição de fase nítida baseada na relação entre $q$ e a dimensão $d$:

• Regime Aprendível ($q > d$): O potencial de entropia é finito. A perda cumulativa minimax realizável é $\Theta_{d,q}(L^d)$. Os autores fornecem um algoritmo próprio determinístico eficiente baseado em envelopes Lipschitz (limites inferiores e superiores) que alcança este limite.
• Regime Não Aprendível ($q \leq d$): O potencial de entropia diverge.
  • Se $q < d$, a perda minimax cumulativa cresce polinomialmente com o horizonte $T$.
  • Se $q = d$, a perda cresce logaritmicamente com $T$.
  • Em ambos os casos, $D_{\text{onl}}(\mathcal{H}) = \infty$.
• Aprendibilidade Eventual: Para qualquer perda contínua $\ell$ com $\ell(y,y)=0$, os autores mostram que, para funções $L$-Lipschitz, a perda instantânea $\ell(\hat{y}_t, y_t)$ converge para 0 conforme $t \to \infty$, independentemente de a perda cumulativa total ser finita ou não.

2. Redes $k$-ReLU Limitadas

O artigo estuda a classe $\mathcal{H}_{k,d}$ de redes $k$-ReLU limitadas (somas de $k$ ReLUs com pesos limitados) sobre $[-1, 1]^d$ com perda ao quadrado.

• Separação Regressão vs. Classificação:
  • Classificação: Sob perda 0/1, a classificação online realizável é impossível para $\mathcal{H}_{2,1}$ (duas unidades ocultas, entrada 1D), pois a dimensão de Littlestone é infinita mesmo com pesos limitados.
  • Regressão: Sob perda ao quadrado, a regressão online realizável admite perda total finita.
• Limites Superiores:
  • Existe um algoritmo online (informacional-teórico) com perda cumulativa $O(k^2 \log^4 d) = \tilde{O}(k^2)$.
  • Para um único ReLU ($k=1$), há um algoritmo eficiente com $O(1)$ de perda cumulativa, independente da dimensão $d$.
• Limites Inferiores:
  • Um limite inferior de $\Omega(k^2 \log(d/k^2))$ é provado, mostrando que a dependência de $k$ e $\log d$ é necessária.
• Dificuldade Computacional:
  • Assumindo a hipótese Gap-ETH, os autores descartam a existência de um aprendiz online próprio eficiente para $k \geq 2$ que alcance perda acumulada $e^{o(d)}$ em tempo polinomial em $d$. Isso sugere que, embora a perda finita seja informacionalmente possível, computá-la eficientemente para aprendizes próprios é provavelmente difícil.

3. Generalização para Redes Profundas

Os resultados são estendidos para redes de profundidade-$L$ e largura-$k$. A perda ao quadrado minimax realizável é mostrada como $\tilde{O}(k^L)$, com um limite inferior correspondente de $\Omega(k^L \log(d/k^L))$ quando $d/k^L \to \infty$.

Significância e Alegações

O artigo afirma que a realizabilidade altera fundamentalmente o cenário do aprendizado online em comparação com o cenário agnóstico. Especificamente:

1. Entropia Métrica como Medida de Complexidade: Os autores estabelecem que, para regressão realizável sob pseudo-métricas aproximadas, a entropia métrica (via potencial de entropia $\Phi$) é um substituto suficiente e frequentemente estreito para a dimensão online $D_{\text{onl}}$. Isso fornece uma ferramenta concreta e calculável para analisar a aprendibilidade onde dimensões abstratas são intratáveis.
2. Transições de Fase em Regressão Não Paramétrica: O trabalho identifica condições precisas ($q > d$) sob as quais a regressão Lipschitz não paramétrica é livre de horizonte, contrastando fortemente com a não aprendibilidade da classificação ou regressão com $q \leq d$.
3. Aprendibilidade de Redes Neurais: O artigo destaca uma separação nítida entre classificação e regressão para redes ReLU. Enquanto redes ReLU limitadas são não aprendíveis no cenário de classificação (dimensão de Littlestone infinita), elas admitem perda cumulativa finita no cenário de regressão. No entanto, essa aprendibilidade vem com ressalvas: para $k \geq 2$, alcançar essa perda eficientemente via aprendizes próprios é provavelmente intratável computacionalmente.
4. Limitações: Os autores observam que o limite do potencial de entropia nem sempre é estreito; existem classes onde $\Phi(\mathcal{H}) = \infty$, mas $D_{\text{onl}}(\mathcal{H}) < \infty$. Assim, $\Phi$ serve como um substituto de limite superior explícito em vez de uma caracterização completa em todos os casos.

O trabalho baseia-se em avanços recentes na teoria da dimensão online [2] e adapta técnicas de processos estocásticos (integrais de Dudley) para o cenário online adversarial, evitando o chaining sequencial em favor de coberturas padrão devido à suposição de realizabilidade.