Optimistic Rates for Multiclass PAC Learning

Resumo Técnico: Taxas Otimistas para Aprendizado Multiclasse PAC

Enunciado do Problema
O artigo aborda a dificuldade estatística da classificação multiclasse no framework de aprendizado PAC. Os limites de pior caso existentes para o aprendizado multiclasse dependem de dois parâmetros de capacidade: a dimensão de Natarjan ($d_N$) e a dimensão de Daniely–Shalev-Shwartz (DS) ($d_{DS}$). Embora as taxas ótimas sejam conhecidas nos dois extremos — aprendizado realizável ($L^\star = 0$) e aprendizado totalmente agnóstico ($L^\star$ constante) — o comportamento entre eles permanece não resolvido. Especificamente, os limites atuais de pior caso agnósticos escalam como $\sqrt{d_N/n} + d_{DS}/n$, falhando em refletir o fato de que, se o melhor classificador é quase correto (pequeno risco do oráculo $L^\star$), o problema de aprendizado deveria ser mais fácil. O objetivo é estabelecer uma "taxa otimista" onde o termo de flutuação escala com $L^\star$, interpolando entre a taxa rápida realizável e a taxa lenta agnóstica.

Metodologia
Os autores propõem um aprendiz, RMC (Compressão de Menu Relativo), que alcança essa interpolação sem conhecimento prévio de $L^\star$ ou do nível de confiança $\delta$. A arquitetura da prova baseia-se em uma estratégia de divisão de amostra em três blocos, adaptando a redução "cover–menu–compression" de [CEH+26], mas introduzindo uma interface estatística inovadora.

1. Bloco 1 (Cover/Cobertura): Um compressor determinístico reduz a classe de hipóteses infinita para uma família finita $\hat{\mathcal{F}}$ de tamanho aproximadamente $d_{DS} \log^2 n$. Este passo garante que, para qualquer comparador $h$, exista uma "testemunha canônica" em $\hat{\mathcal{F}}$ que concorde com $h$ na região onde $h$ está correto.
2. Bloco 2 (Menu): Um algoritmo de pesos multiplicativos aprende um "menu" $\mu$ (um conjunto de rótulos candidatos para cada entrada) que cobre os rótulos da testemunha canônica na região correta do oráculo. Este passo controla a probabilidade de um rótulo correto estar ausente do menu, um modo de falha governado por $d_{DS}$.
3. Bloco 3 (Compression/Compressão): Uma vez fixado o menu, o problema reduz-se à classificação binária dentro do menu. O aprendiz aplica uma regra de compressão que domina empiricamente um comparador fixo.

A inovação técnica central é um Teorema de Compressão Relativa Voltado ao Comparador (Teorema 3.3). Diferente dos limites de compressão padrão que comparam o risco populacional do aprendiz com seu risco empírico (resultando em uma flutuação de $\sqrt{k/n}$), este teorema compara o risco populacional do aprendiz diretamente com o risco populacional $L(h)$ de um comparador fixo $h$. Ele estabelece que, se uma regra de compressão de tamanho $k$ não possui um perda empírica maior que $h$, então:
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
Crucialmente, o coeficiente de $L(h)$ é exatamente 1, e a flutuação escala com $\sqrt{L(h)}$. Isso é alcançado usando descrições ordenadas com índices repetidos e desigualdades de Bernstein de um lado, sem exigir suposições de estabilidade.

Principais Contribuições

1. Taxa Otimista Multiclasse Ótima: O artigo prova que, para uma classe com dimensão de Natarjan $d_N$ e dimensão DS $d_{DS}$, o excesso de risco ótimo é:
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   Este resultado é uniforme no tamanho do alfabeto. O termo $d_N$ localiza-se no risco do oráculo $L^\star$, enquanto o termo $d_{DS}$ permanece como um resto de ordem realizável.
2. Limite Inferior Correspondente: Os autores constroem uma classe de hipóteses única e uma distribuição única para qualquer $L^\star$ fixo que força ambos os termos do limite superior simultaneamente. Isso confirma que a separação de papéis — $d_{DS}$ controlando a cobertura de rótulos e $d_N$ controlando as flutuações dentro do menu — é intrínseca ao problema, não um artefato da análise.
3. Extensão para Aprendizado de Lista: A arquitetura é estendida para o aprendizado de lista (saída de $r$ rótulos). Os autores derivam taxas otimistas contra o melhor $r$-tupla de hipóteses, localizando a flutuação no risco de lista do oráculo. Isso resolve uma expectativa de [Pab26] quanto à necessidade de um termo de flutuação de Natarjan $r$-ário e melhora o limite inferior de aprendizado realizável conhecido ao remover um fator de $r$.
4. Verificação Formal: Os principais teoremas e suas provas foram verificados por máquina em Lean 4, garantindo a correção das constantes e dependências lógicas.

Resultados

• Limite Superior (Teorema 3.1): O aprendiz RMC alcança a taxa $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ com probabilidade $1-\delta$. O aprendiz é livre de parâmetros (independente de $L^\star$ e $\delta$).
• Limite Inferior (Teorema 4.1): Para qualquer $1 \leq d_N \leq d_{DS}$, existe uma classe e uma distribuição onde qualquer aprendiz incorre em um excesso de risco esperado de pelo menos $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$. A construção utiliza um produto de um cubo de Natarjan ruidoso e um pseudo-cubo (derivado de [BCD+22]) para separar as duas dimensões.
• Aprendizado de Lista (Teoremas 5.1 & 5.2): A taxa otimista estende-se aos aprendizes de lista contra o melhor $r$-tupla, com um limite inferior confirmando a necessidade do termo de flutuação. Adicionalmente, um novo limite inferior para o aprendizado de lista realizável remove o fator $r$ presente nos resultados anteriores [HMZ24].

Significância e Alegações
O artigo afirma fechar a lacuna entre as taxas conhecidas de realizável e agnóstica para multiclasse, fornecendo a primeira taxa otimista livre de distribuição e de parâmetros para aprendizado multiclasse.

• Unificação Teórica: Demonstra que o princípio de comparação de "coeficiente-um", anteriormente estabelecido para classificação binária via geometria de cubo Booleano [MQZ26], pode ser elevado para configurações multiclasse ao desacoplar a geometria dos rótulos (tratada pelo menu/cobertura) da flutuação estocástica (tratada pela compressão relativa).
• Separação Intrínseca: O limite inferior certifica que os dois parâmetros de capacidade ($d_N$ e $d_{DS}$) desempenham papéis distintos e não intercambiáveis: $d_{DS}$ dita se os rótulos corretos estão visíveis (cobertura), enquanto $d_N$ dita a dificuldade de selecionar entre os rótulos visíveis (flutuação).
• Limitações: Os autores observam que os fatores logarítmicos no limite superior não são otimizados, e o aprendiz é informacional (não necessariamente eficiente computacionalmente). Os resultados assumem um alfabeto de rótulos finito, embora o limite seja uniforme em sua cardinalidade.

O trabalho é apresentado como uma resolução para a questão da interpolação no aprendizado PAC multiclasse, estabelecendo que a dificuldade estatística de fato depende do nível de realizabilidade e fornecendo a taxa precisa na qual essa dificuldade degrada.