A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization

Resumo Técnico: Uma História de Dois Problemas: Aprendizado Bilevel Multi-Tarefa Encontra Otimização Multi-Objetivo com Restrições de Igualdade

Declaração do Problema
O artigo aborda o desafio do Aprendizado Bilevel Multi-Tarefa (MTBL) sob Convexidade Geral no Nível Inferior (LLGC). Embora a otimização bilevel (BLO) seja amplamente utilizada em aprendizado de máquina (por exemplo, ajuste de hiperparâmetros, meta-aprendizado e alinhamento de LLMs), os frameworks teóricos e algoritmos existentes dependem predominantemente da suposição de Convexidade Forte no Nível Inferior (LLSC). Essa suposição garante uma solução única no nível inferior e um hipergradiente bem definido, mas é frequentemente violada em problemas modernos e complexos de aprendizado de máquina onde o objetivo do nível inferior é meramente convexo.

Além disso, os trabalhos existentes em MTBL estão amplamente confinados a configurações de tarefa única ou dependem de LLSC. Ao estender o MTBL para a configuração LLGC, surgem duas questões críticas:

1. O hipergradiente torna-se mal definido devido à falta de convexidade forte.
2. A presença de múltiplos objetivos no nível superior, potencialmente conflitantes, requer uma interpretação de equilíbrio de Pareto, complicando os critérios de optimalidade.

Metodologia
Os autores propõem um novo framework que reformula o problema LLGC-MTBL em um problema de Otimização Multi-Objetivo com Restrições de Igualdade (ECMO). As etapas metodológicas centrais são:

1. Reformulação para ECMO:
   Em vez de resolver diretamente o problema bilevel aninhado, os autores observam que, para uma função convexa no nível inferior $g(x, y)$, a condição de optimalidade $\nabla_y g(x, y) = 0$ é necessária e suficiente. Eles reformulam o problema MTBL como:
   $$\min_{z} F(z) = [f_1(z), \dots, f_S(z)]^\top \quad \text{s.t.} \quad h_i(z) = 0, \forall i \in [q]$$
   onde $z = [x^\top, y^\top]^\top$ e $h_i(z)$ representa a $i$-ésima componente do gradiente do nível inferior $\nabla_y g(x, y)$.

2. Caracterização da Estacionaridade de Pareto para ECMO:
   O artigo identifica que as definições padrão de estacionaridade de Pareto para otimização multi-objetivo (MOO) não restringida são insuficientes para ECMO devido às restrições de viabilidade. Os autores estabelecem um novo critério de estacionaridade de Pareto baseado em KKT. Eles aproveitam a escalarização Weighted-Chebyshev (WC) para criar uma correspondência um para um entre a frente de Pareto do problema ECMO e as soluções de um problema escalarizado. Ao analisar as condições de Karush-Kuhn-Tucker (KKT) do problema escalarizado por WC, eles definem uma métrica de convergência rigorosa baseada na norma do sistema residual de KKT.

3. Design do Algoritmo (WC-Penalty):
   Para resolver o problema ECMO, os autores propõem o algoritmo WC-Penalty. Este método:

   • Reformula o problema escalarizado por WC introduzindo variáveis de folga para lidar com a minimização da norma $\ell_\infty$.
   • Converte as restrições de igualdade (tanto as restrições originais quanto as restrições das variáveis de folga) em termos de penalidade dentro da função objetivo.
   • Resolve o problema resultante de nível único, com objetivo único e restrito, utilizando Descida de Gradiente Projetado (GD).
   • Opera em configurações determinísticas e estocásticas.

Principais Contribuições

• Extensão Teórica: Este trabalho é o primeiro a estender a otimização bilevel para a configuração multi-tarefa sob a suposição relaxada de LLGC.
• Nova Formulação de Problema: Introduz o problema ECMO como uma formulação distinta que não havia sido estudada teoricamente antes deste trabalho, abordando especificamente a falta de garantias de convergência em tempo finito na literatura existente.
• Nova Métrica de Convergência: Os autores definem uma nova métrica de estacionaridade de Pareto baseada em KKT para ECMO, resolvendo a ambiguidade das condições de optimalidade em configurações multi-objetivo restritas.
• Algoritmo e Taxa de Convergência: Eles propõem o algoritmo WC-Penalty e provam uma taxa de convergência em tempo finito de $O(S T^{-1/2})$ para a estacionaridade de Pareto baseada em KKT, onde $S$ é o número de objetivos e $T$ é o número total de iterações. Esta é a primeira garantia desse tipo para problemas ECMO.
• Exploração da Frente de Pareto: Ao variar o vetor de preferências sobre o simplex, o método explora sistematicamente toda a frente de Pareto.

Resultados Experimentais
Os autores validam sua abordagem em duas tarefas de ponderação de dados multi-objetivo:

1. Treinamento de Modelo de Recompensa RLHF: Usando o conjunto de dados HelpSteer, o algoritmo otimiza os pesos dos dados para equilibrar múltiplas métricas alinhadas com humanos (utilidade, correção, etc.). Os resultados mostram que o algoritmo WC-Penalty cobre uma porção significativamente maior da frente de Pareto em comparação com baselines como MOML, MoCo e FORUM.
2. Alinhamento Multi-Objetivo de LLM: O método é aplicado ao ajuste fino do Llama-3.2-1B-Instruct (e escalado para modelos de 3B e 8B) para minimizar múltiplas perdas de validação. O algoritmo demonstra desempenho superior em comparações de hipervolume e métrica $\epsilon$ contra baselines existentes de MTBL e bilevel.
3. Exemplos Sintéticos: Experimentos sintéticos adicionais confirmam a capacidade do algoritmo de recuperar a frente de Pareto completa nas configurações ECMO e LLGC-MTBL.

Significado e Alegações
O artigo afirma fechar o ciclo entre frameworks de otimização fundamentais, traduzindo soluções do problema ECMO diretamente de volta para o problema MTBL original. Os autores enfatizam que seu trabalho fornece a primeira garantia de convergência em tempo finito para problemas ECMO, uma lacuna anteriormente não abordada na literatura. Ao relaxar a suposição de LLSC, o framework proposto estende a aplicabilidade do aprendizado bilevel para cenários de aprendizado de máquina mais complexos e do mundo real, onde a convexidade forte não pode ser assumida. Os resultados sugerem que o método WC-Penalty oferece tanto rigor teórico quanto eficiência prática na exploração de soluções ótimas de Pareto para aprendizado bilevel multi-tarefa.