Adaptive Conformal Inference through the Lens of Blackwell Approachability

Resumo Técnico: Inferência Conformal Adaptativa sob a Ótica da Aproximabilidade de Blackwell

Enunciado do Problema
A Inferência Conformal Adaptativa (ACI), introduzida por Gibbs e Candès (2021), aborda a limitação da inferência conformal padrão, que depende da suposição de permutabilidade (exchangeability), frequentemente violada em configurações sequenciais ou dependentes do tempo (ex: previsão de séries temporais). A ACI visa construir conjuntos de predição sequencialmente de modo que a cobertura empírica convirja para um nível desejado $1-\alpha$ para quaisquer sequências de dados. Embora as estratégias existentes de ACI garantam a validade (cobertura empírica $\geq 1-\alpha$), elas geralmente carecem de garantias teóricas simultâneas de eficiência (o comprimento médio dos intervalos de predição). Em cenários adversariais, não são possíveis garantias de eficiência não triviais sem suposições adicionais, enquanto em cenários de permutabilidade, os métodos existentes frequentemente produzem comprimentos de intervalo subótimos. O desafio central é projetar uma estratégia unificada que garanta validade para quaisquer sequências, enquanto adapta a eficiência ao grau de estocasticidade subjacente dos dados.

Metodologia
Os autores reformulam a ACI como um jogo finito repetido de dois jogadores com pagamentos vetoriais.

1. Ação do Aprendiz: Seleciona um nível de erro de cobertura $a_t \in A$, onde $A$ é uma grade finita derivada das estatísticas de ordem do conjunto de calibração. Isso determina o conjunto de predição $C_{1-a_t}(x_t)$.
   • Ação do Oponente: Seleciona um resultado $y_t$, que é mapeado para uma ação discreta $b_t \in B$ representando o conjunto conformal mais "justo" que contém $y_t$.
   • Vetor de Pagamento: O aprendiz recebe um vetor $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$, codificando o indicador de erro de cobertura (validade) e o comprimento do intervalo (eficiência).
2. Estrutura de Aproximabilidade:
   • O objetivo é direcionar o vetor de pagamento médio $m_T$ em direção a um conjunto alvo $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$.
   • O conjunto alvo depende de uma restrição $Q \subseteq \Delta(B)$ sobre o jogo do oponente. $Q$ representa o conjunto de distribuições que as ações do oponente seguem assintoticamente.
   • Aproximabilidade Oportunista: Os autores empregam a teoria da aproximabilidade de Blackwell e sua extensão por Bernstein et al. (2014), conhecida como aproximabilidade oportunista. Esta estrutura permite que o aprendiz se aproxime de um conjunto alvo menor e mais eficiente se o jogo do oponente for restrito a um conjunto $Q$, sem que o aprendiz precise conhecer $Q$ antecipadamente.
3. Algoritmo (BO-ACI):
   • A estratégia proposta, Inferência Conformal Adaptativa de Blackwell Oportunista (BO-ACI), utiliza um previsor calibrado auxiliar $F$.
   • Em cada rodada, $F$ prevê a distribuição da próxima ação do oponente $b_t$.
   • O aprendiz seleciona deterministicamente a ação $a_t$ que minimiza o comprimento esperado enquanto satisfaz a restrição de validade contra a distribuição prevista (via uma função de resposta $p^*$).

Contribuições Principais

1. Reformulação Teórico-Jogo: O artigo estabelece uma nova formulação da ACI como um jogo finito repetido com pagamentos vetoriais, vinculando explicitamente validade e eficiência a um problema de aproximabilidade de múltiplos objetivos.
2. Estratégia Unificada (BO-ACI): Os autores introduzem uma estratégia baseada na aproximabilidade oportunista de Blackwell que garante a validade para qualquer sequência de dados (estocástica ou adversarial) enquanto fornece garantias de eficiência que se adaptam à estocasticidade desconhecida dos dados.
3. Garantias de "Melhor de Muitos Mundos": A estratégia alcança um conjunto unificado de garantias:
   • Configuração de Permutabilidade (Exchangeable): Recupera a garantia de eficiência ótima $L(C_{1-\alpha})$, igualando o desempenho da predição conformal padrão em condições ideais.
   • Configuração Adversarial: Garante a validade, mas aceita o limite de eficiência trivial (comprimento do intervalo $2L$), consistente com os resultados de impossibilidade em configurações totalmente adversariais.
   • Configurações Intermediárias: Fornece garantias de eficiência significativas para cenários como mudanças distributivas únicas ou dados "quase-permutáveis" (ex: séries temporais com dependências fracas), onde o comprimento do intervalo se adapta ao grau de não-permutabilidade.

Resultados

• Convergência Teórica: O Teorema 19 prova que, sob a estratégia BO-ACI, o vetor de pagamento médio $m_T$ converge quase certamente para o conjunto alvo $C_{\alpha, Q}$ para qualquer conjunto convexo $Q$ que restrinja o jogo do oponente.
• Cenários Específicos:
  • Dados Permutáveis (Exchangeable): Se o oponente for restrito à distribuição uniforme $q_{unif}$, o comprimento médio do intervalo converge para $L(C_{1-\alpha})$.
  • Mudança Distributiva Única: Se os escores de teste seguirem uma distribuição $V$ diferente da distribuição de calibração $S$, a estratégia converge para o comprimento $L(C_{1-a_{S,V}})$, onde $a_{S,V}$ é o nível de erro de cobertura ótimo para a distribuição deslocada.
  • $\epsilon$-Permutável/Séries Temporais: Para dados com pequenos desvios da permutabilidade (medidos por distância de Variação Total ou Kolmogorov), a estratégia alcança comprimentos próximos ao comprimento permutável ótimo, degradando-se graciosamente conforme o desvio aumenta.
  • Adversarial: Na ausência de restrições ($Q = \Delta(B)$), a estratégia garante a validade, mas não pode garantir uma eficiência melhor que o limite trivial, confirmando a necessidade de restrições $Q$ para eficiência não trivial.
• $\epsilon$-Calibração: Os resultados são estendidos para estratégias usando previsores $\epsilon$-calibrados (Teorema 34), fornecendo limites de convergência dependentes de $\epsilon$.

Significância e Alegações
O artigo afirma fornecer um arcabouço teórico unificado para a inferência conformal adaptativa que resolve a tensão entre validade e eficiência. Ao utilizar a aproximabilidade de Blackwell, os autores demonstram que é possível projetar um único algoritmo que:

1. Garante a validade independentemente do mecanismo gerador de dados.
2. Adapta-se automaticamente ao "grau de estocasticidade" dos dados para maximizar a eficiência.
3. Recupera resultados ótimos conhecidos em casos extremos (permutáveis e adversariais) enquanto oferece novos e significativos garantias em cenários intermediários e realistas (como previsão de séries temporais) onde métodos anteriores careciam de fundamentação teórica.

Os autores posicionam este trabalho como uma solução de "melhor de muitos mundos", evitando a necessidade de ajustar hiperparâmetros com base na distribuição assumida dos dados, já que a estratégia é "desconhecedora" da restrição $Q$ específica, mas a explora caso ela exista. O trabalho também destaca as limitações do cenário totalmente adversarial, reforçando que garantias de eficiência exigem alguma suposição estrutural sobre os dados.