Resumo Técnico: Aprendizado Focado em Decisão via Projeção no Espaço Tangente do Erro de Previsão

1. Declaração do Problema

Em pipelines de "prever-então-otimizar", um modelo preditivo estima parâmetros (por exemplo, vetores de custo) para um problema de otimização a jusante, que então calcula uma decisão final. O Aprendizado Focado em Decisão (DFL) tradicional visa treinar preditores para minimizar o arrependimento—a subotimalidade incorrida ao agir com base em parâmetros previstos em vez dos verdadeiros—em vez de simplesmente minimizar o erro de previsão (por exemplo, Erro Quadrático Médio, MSE).

No entanto, calcular o gradiente do arrependimento em relação aos parâmetros do preditor é desafiador. Abordagens existentes enfrentam limitações significativas:

• Camadas de Otimização Diferenciáveis: Métodos que diferenciam através de iterações do solucionador (por exemplo, via condições de KKT) podem ser computacionalmente caros, numericamente instáveis (devido a sistemas lineares mal condicionados) e dependentes do solucionador.
• Funções de Perda Surrogadas: Métodos que usam surrogados convexos (por exemplo, SPO+) ou estimadores perturbados frequentemente desviam-se do objetivo real de arrependimento, podem carecer de generalidade além de custos lineares ou exigir chamadas adicionais ao solucionador.

O artigo aborda a necessidade de um método que calcule gradientes reais de arrependimento de forma eficiente, sem diferenciar através de iterações do solucionador ou depender de objetivos proxy, mantendo ao mesmo tempo a estabilidade numérica.

2. Metodologia: PEAR

Os autores propõem o PEAR (Erro Projetado como Gradiente de Arrependimento), um método fundamentado na caracterização geométrica dos gradientes de arrependimento sob condições de regularidade padrão.

Fundamentação Teórica

Sob as hipóteses de convexidade estrita, Qualificação de Independência Linear das Restrições (LICQ) e Folga Complementar Estrita, o conjunto ativo de restrições na solução ótima permanece localmente estável sob pequenas perturbações. Dentro desta região, o artigo estabelece que o gradiente de arrependimento admite uma caracterização geométrica de forma fechada:
$$\nabla_{\hat{c}} R(\hat{c}; c) = P_H (\hat{c} - c) = P_H e$$
onde:

• $e = \hat{c} - c$ é o erro de previsão.
• $P_H$ é um operador de sensibilidade definido como $P_H = H^{-1} - H^{-1}J^\top(JH^{-1}J^\top)^{-1}JH^{-1}$.
• $H$ é a Hessiana da função objetivo (curvatura local).
• $J$ é a Jacobiana das restrições ativas.

Interpretação Geométrica: O gradiente de arrependimento é equivalente ao erro de previsão projetado no espaço tangente das restrições ativas, escalado pela curvatura local. Isso implica que o sinal de aprendizado filtra componentes "irrelevantes para a decisão" do erro (aqueles ortogonais à região viável) e retém apenas os componentes que influenciam a decisão.

Implementação Algorítmica

O PEAR calcula este gradiente sem formar explicitamente o operador de projeção denso $P_H$. Em vez disso, utiliza um sistema linear reduzido derivado das restrições ativas:

1. Passada Direta: Resolver o problema de otimização para obter a solução primal-dual e identificar o conjunto ativo $\mathcal{A}$ via folga complementar.
2. Passada Reversa:
   • Calcular o erro de previsão $e$.
   • Resolver um sistema linear compacto $k \times k$ (onde $k$ é o número de restrições ativas) usando uma redução de complemento de Schur: $(JH^{-1}J^\top)v = JH^{-1}e$.
   • Reconstruir o gradiente projetado: $g = H^{-1}e - H^{-1}J^\top v$.

Tratamento de Programas Lineares (PLs): Como os PLs carecem de curvatura ($H$ é singular) e possuem mapas de solução constantes por partes, o PEAR adiciona um termo de regularização quadrática pequena ($\phi(z) = \frac{\lambda}{2}\|z\|^2$) para garantir diferenciabilidade. Para evitar que o gradiente desapareça em regiões planas, o PEAR emprega injeção normal, adicionando seletivamente um componente controlado do gradiente do espaço normal à projeção tangente para estabilizar o aprendizado.

3. Contribuições Principais

1. Caracterização Geométrica: O artigo estabelece uma relação geométrica explícita entre o erro de previsão e os gradientes de arrependimento, mostrando que os gradientes de arrependimento são simplesmente gradientes de MSE filtrados para remover direções irrelevantes para a decisão.
2. Cálculo Eficiente (PEAR): O método proposto calcula gradientes de arrependimento através de um sistema linear reduzido sobre restrições ativas. Isso evita diferenciar através de iterações do solucionador, elimina a necessidade de funções de perda surrogadas e melhora a estabilidade numérica em comparação com camadas diferenciáveis existentes.
3. Desempenho Empírico: O PEAR demonstra qualidade de decisão superior e eficiência de treinamento em benchmarks sintéticos de Programação Linear (PL) e em uma tarefa real de otimização de portfólio de Programação Quadrática (PQ).

4. Resultados Experimentais

Os autores avaliaram o PEAR contra baselines incluindo MSE (duas etapas), SPO+, DBB, PFYL e LAVA.

• Benchmarks Sintéticos de PL (Caminho Mais Curto & Mochila):

  • Arrependimento: O PEAR alcançou o menor arrependimento normalizado através de vários graus polinomiais de geração de custos, superando ou igualando todas as baselines.
  • Eficiência: O PEAR foi consistentemente o mais computacionalmente eficiente, frequentemente treinando significativamente mais rápido do que camadas diferenciáveis (por exemplo, 2x mais rápido que o SPO+ no Caminho Mais Curto) e evitando tempos limite que afligiram outros métodos em instâncias complexas de Mochila.
  • Robustez: Sob ruído multiplicativo na geração de custos, o PEAR manteve o menor arrependimento, demonstrando robustez à má especificação do modelo.

• PQ do Mundo Real (Otimização de Portfólio Média-Variância):

  • Em dados do S&P 100, o PEAR alcançou o menor arrependimento normalizado e traduziu isso em desempenho de portfólio realizado superior, incluindo os maiores retornos cumulativos/anualizados, melhor razão de Sharpe e menor drawdown máximo.
  • O PEAR foi mais rápido do que camadas diferenciáveis de PQ (QPTH, CvxpyLayers) e exibiu gradientes mais estáveis, levando a um melhor desempenho fora da amostra.

• Mudanças nas Restrições:

  • O artigo testou a robustez quando as restrições no tempo de teste diferiam das de treinamento (por exemplo, alterando pares origem-destino no Caminho Mais Curto, apertando a capacidade da Mochila ou permitindo venda a descoberto em portfólios).
  • O PEAR consistentemente degradou-se o menos entre os métodos DFL e manteve o menor arrependimento, sugerindo que ele aprende estruturas de custo transferíveis em vez de memorizar caminhos ótimos específicos.

5. Significado e Alegações

O artigo alega que o PEAR fornece uma alternativa mais simples e direta às abordagens DFL existentes, revelando que os gradientes de arrependimento estão estruturalmente relacionados aos erros de previsão via projeção no espaço tangente.

• Interpretabilidade: O método esclarece por que certos componentes do erro importam para as decisões (aqueles no espaço tangente) e quais não importam (aqueles no espaço normal).
• Eficiência e Estabilidade: Ao desacoplar o solucionador direto do cálculo reverso através de um sistema linear reduzido, o PEAR evita a sobrecarga computacional e a instabilidade numérica associadas à diferenciação através de solucionadores complexos.
• Generalidade: A abordagem aplica-se a problemas de otimização com objetivos lineares ou quadráticos, oferecendo um gradiente de arrependimento determinístico sem exigir estimativa baseada em perturbação ou chamadas adicionais ao solucionador.

Os autores concluem que o PEAR alcança qualidade de decisão superior com tempo de treinamento reduzido e robustez aprimorada sob mudanças nas restrições, oferecendo um framework principiado e eficiente para Aprendizado Focado em Decisão.