Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning

Resumo Técnico: Otimização de Ordem Zero Livre de Parâmetros para Métodos Baseados em LMO

Definição do Problema
O ajuste fino (fine-tuning) de Grandes Modelos de Linguagem (LLMs) é uma aplicação central da otimização moderna, mas enfrenta um gargalo crítico: o overhead de memória da retropropagação (backpropagation). Armazenar ativações intermediárias, gradientes e estados de otimizadores para modelos como o OPT-1.3B exige uma memória substancial (ex: ~25 GB), limitando a escalabilidade. A otimização de ordem zero (ZO) oferece uma alternativa eficiente em termos de memória ao substituir os cálculos de gradiente por estimativas de diferença finita derivadas de consultas de valores de função. No entanto, os métodos ZO existentes sofrem de duas limitações primárias:

1. Sensibilidade a Hiperparâmetros: O desempenho é altamente dependente do tamanho do passo (stepsize) e do parâmetro de suavização ($\tau$). Configurações ideais exigem tipicamente o conhecimento de constantes dependentes do problema (ex: constantes de Lipschitz, distância até o ótimo), que são indisponíveis na prática, necessitando de buscas de grade (grid searches) custosas e específicas para cada tarefa.
2. Desajuste Geométrico: Atualizações euclidianas padrão podem não capturar a estrutura heterogênea de blocos de parâmetros (ex: pesos com formato de matriz em LLMs). Métodos que utilizam Oráculos de Minimização Linear (LMOs) podem se adaptar a geometrias não euclidianas (como normas espectrais para matrizes), mas a combinação destes com a adaptação livre de parâmetros (PF) em um cenário ZO permanece inexplorada.

Metodologia
Os autores propõem o AdaNAGED (ADAptive Norm-Agnostic Gradient-frEe Descent), um novo algoritmo que unifica três paradigmas: otimização de ordem zero eficiente em memória, adaptação livre de parâmetros e atualizações conscientes da geometria via LMOs.

• Estimativa Livre de Parâmetros:

  • Suavidade ($L$): Em vez de exigir uma constante de Lipschitz prévia, o método estima a suavidade local iterativamente ao longo da trajetória de otimização. Ele calcula a razão entre a diferença nas aproximações de gradiente ZO e a distância entre iterantes consecutivos: $L_t = \|g_t(x_{t+1}, e_t)\|_* / \|x_{t+1} - x_t\|$. Crucialmente, a mesma direção de perturbação $e_t$ (armazenada como uma semente aleatória) é usada em ambos os pontos para manter a eficiência de memória.
  • Gap Inicial ($\Delta$): O método utiliza um limite inferior conhecido da função objetivo ($f_{min}$) para estimar o gap inicial $\Delta \leq f(x_0) - f_{min}$, evitando a necessidade de conhecer a distância até o ótimo.
  • Passo Adaptativo: O tamanho do passo $\gamma_t$ é atualizado usando uma acumulação do tipo AdaGrad-Norm das estimativas de suavidade local ($S_t = S_{t-1} + L_t$), resultando em $\gamma_t \propto 1/\sqrt{S_t}$.
  • Parâmetro de Suavização ($\tau$): Para garantir a estabilidade, $\tau_t$ é escalonado linearmente com o tamanho do passo ($\tau_t = \rho C_2 \gamma_t$), derivado dos requisitos teóricos da prova de convergência.

• Atualizações Baseadas em LMO:
  O algoritmo define atualizações via um Oráculo de Minimização Linear sobre uma bola de norma: $v_t = \text{lmo}(g_t)$. Isso permite que o método se adapte a diferentes geometrias:

  • Geometria de Vetor: Usar a norma $\ell_\infty$ resulta em uma atualização do tipo Sign-SGD.
  • Geometria de Matriz: Usar a norma espectral resulta em uma atualização do tipo Muon. Como a decomposição polar exata (SVD) é computacionalmente cara, os autores introduzem o AdaMuGED, que aproxima o operador polar usando alguns passos da iteração de Newton–Schulz (N-SS), evitando a inversão de matrizes.

Principais Contribuições

1. Nova Construção ZO Livre de Parâmetros: O artigo introduz um método para estimar a suavidade local e definir tamanhos de passo no cenário de ordem zero sem conhecimento prévio de constantes do problema. Isso preserva a eficiência de memória de ZO ao armazenar apenas as sementes geradoras para as direções de perturbação.
2. Unificação de Paradigmas: O algoritmo proposto AdaNAGED combina ZO eficiente em memória, redução de dependência de hiperparâmetros e atualizações de geometria consciente via LMOs.
3. Garantias de Convergência: Os autores estabelecem taxas de convergência para objetivos contínuos de Lipschitz, suaves e convexos. A taxa resultante é assintoticamente ótima ($O(1/\epsilon^2)$), com fatores adicionais que consideram a estimativa livre de parâmetros e a estocasticidade.
4. Variantes Práticas: A introdução do AdaMuGED estende o framework para parâmetros com valores de matriz usando iterações de Newton–Schulz, tornando-o aplicável ao ajuste fino de LLMs, onde os parâmetros são estruturados como matrizes.

Resultados Experimentais
Os métodos foram avaliados no ajuste fino do modelo OPT-1.3B na tarefa de classificação de sentimento SST-2, um benchmark para adaptação de LLM com restrição de memória.

• Baselines: Os autores compararam contra otimizadores de ordem zero ajustados: ZO-AdaMM, ZO-SignSGD e ZO-Muon.
• Desempenho:
  • AdaNAGED (tipo SignSGD-like) alcançou 0,903 de acurácia, ficando a 0,7 pontos percentuais do ZO-SignSGD ajustado (0,910).
  • AdaMuGED (tipo Muon-like) alcançou 0,908 de acurácia, reduzindo a lacuna para o ZO-SignSGD ajustado para 0,2 pontos percentuais e superando o AdaNAGED em 0,5 pontos percentuais.
  • O ZO-Muon ajustado permaneceu como o baseline mais forte com 0,921, confirmando o benefício da geometria consciente de matriz.
• Conclusão: Os métodos livres de parâmetros demonstraram desempenho competitivo contra baselines ajustados manualmente, validando que regras adaptativas podem recuperar grande parte do desempenho dos métodos ZO ajustados sem a necessidade de buscas de hiperparâmetros dispendiosas.

Significância
O artigo afirma apresentar o primeiro método operando na interseção da Otimização de Ordem Zero, Livre de Parâmetros e de Oráculo de Minimização Linear. Sua significância reside em demonstrar que:

1. Eficiência de Memória: A otimização ZO pode ser tornada prática para LLMs ao evitar a retropropagação.
2. Automação: A dependência de ajustes de hiperparâmetros custosos e específicos para tarefas pode ser eliminada através da estimativa adaptativa e livre de parâmetros de suavidade e tamanhos de passo.
3. Flexibilidade Geométrica: O framework suporta atualizações não euclidianas (via LMOs) que se alinham às propriedades estruturais dos parâmetros do modelo (ex: matrizes), melhorando o condicionamento e a estabilidade.

Os autores mantêm uma postura modesta, observando que, embora sua abordagem livre de parâmetros seja competitiva, os baselines ajustados (particularmente o ZO-Muon) ainda detêm uma leve vantagem, sugerindo que o ajuste manual continua sendo o ideal, mas que o método proposto oferece uma alternativa robusta e automatizada.