Resumo Técnico: RanSOM

1. Declaração do Problema

O artigo aborda uma limitação fundamental na otimização estocástica para aprendizado profundo: o viés induzido pela curvatura em métodos de momento padrão (por exemplo, Bola Pesada de Polyak) quando aplicados a paisagens não convexas.

Em configurações estocásticas, o vetor de momento $m_t$ agrega gradientes de iterações anteriores. À medida que o otimizador se move de $x_{t-1}$ para $x_t$, a curvatura da paisagem de perda faz com que a direção do gradiente mude. Consequentemente, $m_{t-1}$ torna-se um estimador "desatualizado" do gradiente atual $\nabla f(x_t)$. Esse viés, proporcional à integral do Hessian ao longo do caminho de atualização, impede que os métodos de momento padrão alcancem a complexidade de amostra ótima $O(\epsilon^{-3})$ requerida para otimização não convexa, frequentemente limitando-os a taxas subótimas de $O(\epsilon^{-4})$.

Estratégias de correção existentes enfrentam um "gargalo viés-variância":

• Estimadores baseados em diferença (por exemplo, STORM): Requerem suavidade da amostra individual (frequentemente violada por ativações ReLU) ou sofrem com alta variância.
• Momento Determinístico de Segunda Ordem (SOM): Requer fortes suposições globais de Lipschitz no Hessian (derivadas de terceira ordem limitadas).
• SOM Estocástico (SOM-Unif): Relaxa as suposições de suavidade, mas incorre em sobrecarga computacional proibitiva ao exigir consultas auxiliares de "olho adiante" (3 passagens diretas/retroativas por iteração).

2. Metodologia: O Framework RanSOM

Os autores propõem o RanSOM (Momento de Segunda Ordem Randomizado), um framework unificado que elimina o viés induzido pela curvatura sem suposições adicionais ou sobrecarga computacional. A inovação central é substituir taxas de aprendizado determinísticas por taxas de aprendizado randomizadas extraídas de distribuições específicas.

2.1 Integração por Partes Randomizada

Em vez de uma taxa fixa $\eta_t$, a taxa de aprendizado $s_t$ é tratada como uma variável aleatória com média $\mathbb{E}[s_t] = \eta_t$. Ao alavancar identidades do tipo Stein (fórmulas de integração por partes), o método relaciona a diferença finita dos gradientes (o viés) a um único Produto Hessian-Vetor (HVP) avaliado no ponto final aleatório.

O framework utiliza duas identidades específicas:

1. Identidade Exponencial (Sem Restrições): Se $s \sim \text{Exp}(\lambda)$, então:
   $$\mathbb{E}[g(s) - g(0)] = \frac{1}{\lambda} \mathbb{E}[g'(s)]$$
   Isso permite que o viés $\nabla f(x_{t+1}) - \nabla f(x_t)$ seja estimado escalando o HVP em $x_{t+1}$ por $\eta_t$.
2. Identidade Beta (Com Restrições): Se $s \sim \text{Beta}(1, K)$, então:
   $$\mathbb{E}[g(s) - g(0)] = \mathbb{E}\left[ \frac{1-s}{K} g'(s) \right]$$
   Isso leva em conta o suporte compacto da distribuição Beta, garantindo viabilidade na otimização com restrições.

2.2 Instanciações Algorítmicas

O framework é instanciado em dois algoritmos:

• RanSOM-E (Sem Restrições): Usa passos distribuídos exponencialmente. Integra-se com um Oráculo de Minimização Linear (LMO) para unificar várias atualizações geométricas, recuperando SGD Normalizado (bola $L_2$), SignSGD (bola $L_\infty$) e atualizações espectrais no estilo Muon.
• RanSOM-B (Com Restrições): Usa passos distribuídos Beta em $[0, 1]$. Isso garante que a atualização $x_{t+1} = (1-s_t)x_t + s_t v_t$ (onde $v_t$ é a direção do LMO) permaneça estritamente dentro do conjunto viável convexo $C$, evitando operações de projeção.

2.3 Eficiência Computacional

Uma vantagem crítica do RanSOM é seu custo computacional. O termo de correção requer um HVP em $x_{t+1}$. Em frameworks modernos de diferenciação automática (por exemplo, PyTorch, JAX), esse HVP pode ser computado via truque de Pearlmutter em uma única passagem retroativa combinada junto com o cálculo padrão do gradiente.

• Custo: $2(F_c + B_c)$ (equivalente a duas passagens diretas/retroativas).
• Comparação: Isso iguala o custo de métodos padrão de redução de variância como o STORM e é significativamente mais barato que o SOM-Unif, que requer uma consulta auxiliar dedicada ($3(F_c + B_c)$).

3. Contribuições Principais

1. Framework Unificado: Um método que elimina o viés induzido pela curvatura usando taxas de aprendizado randomizadas e identidades de Stein, aplicável tanto à otimização sem restrições quanto à com restrições.
2. Taxas de Convergência Ótimas: A análise teórica prova que o RanSOM alcança a complexidade de amostra ótima $O(\epsilon^{-3})$ sob suposições padrão de ruído limitado.
3. Robustez a Caudas Pesadas: O método estende-se a configurações desafiadoras com ruído de gradiente de caudas pesadas ($p \in (1, 2]$) e $(L_0, L_1)$-suavidade generalizada (onde a norma do Hessian cresce com a norma do gradiente), sem exigir que o Hessian seja Lipschitz contínuo.
4. Sem Sobrecarga Auxiliar: Ao contrário de correções de segunda ordem anteriores, o RanSOM não requer pontos auxiliares de "olho adiante", mantendo a complexidade de consulta padrão de $2(F_c + B_c)$.
5. Sem Clipping: O método alcança taxas ótimas sem clipping explícito de gradiente, confiando na normalização intrínseca fornecida pelas atualizações do LMO e nas propriedades estatísticas dos passos randomizados.

4. Resultados Teóricos

O artigo estabelece a convergência para otimização não convexa sob as seguintes condições:

• Suposições: O objetivo é limitado inferiormente e satisfaz $(L_0, L_1)$-suavidade pontual. Gradientes estocásticos e HVPs são não tendenciosos com ruído de caudas pesadas afim (momentos $p, q \in (1, 2]$).
• Sem Restrições (RanSOM-E): Converte para um ponto estacionário com taxa:
  $$\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}[\|\nabla f(x_t)\|_*] \leq O\left( T^{-\frac{q(p-1)}{2q(p-1)+p}} \right)$$
  Para o caso padrão ($p=q=2$), isso recupera a taxa ótima $O(T^{-1/3})$.
• Com Restrições (RanSOM-B): Converte em termos do gap de Frank-Wolfe $G(x)$ com a mesma taxa ótima $O(T^{-1/3})$ para $p=q=2$.

A análise destaca um escalonamento assimétrico do parâmetro de momento $\beta$: um $\beta$ menor ajuda a suavizar gradientes de alta variância, enquanto um $\beta$ maior torna a correção de curvatura mais impactante. O $\beta$ ótimo equilibra esses efeitos.

5. Resultados Experimentais

Os autores avaliam o RanSOM em três tarefas não convexas:

1. Classificação Binária (SPLICE): O RanSOM-E (variante Muon) alcançou a maior precisão de teste (84,90%) com variância significativamente menor em comparação ao STORM (73,35% ± 10,77%).
2. Classificação de Sequências (MNIST1D): O RanSOM-E (Muon) atingiu 91,90% de precisão, superando o STORM (88,83%) e o SOM clássico, mantendo alta estabilidade (desvio padrão ±0,36 vs. ±1,38 para o STORM).
3. Completamento de Matriz com Restrições (MovieLens): O RanSOM-B convergiu para um RMSE final menor do que as bases de Frank-Wolfe Estocástico (SFW-Polyak, SFW-SOM), demonstrando eficácia na navegação de geometrias de restrições complexas.

6. Significado e Afirmações

O artigo afirma que o RanSOM resolve o "dilema" das correções de momento de segunda ordem: alcança a taxa de convergência ótima de $O(\epsilon^{-3})$ sem as suposições restritivas de Hessians Lipschitz ou suavidade de amostra individual, e sem a sobrecarga computacional de amostragem auxiliar.

Ao tratar taxas de aprendizado como variáveis aleatórias, o RanSOM permite uma correção de viés de segunda ordem robusta que é:

• Leve em Suposições: Lida com perdas individuais não suaves (por exemplo, redes ReLU) e ruído de caudas pesadas.
• Computacionalmente Eficiente: Igual ao custo do SGD padrão com momento.
• Geometricamente Flexível: Generaliza naturalmente para otimizadores normalizados e configurações com restrições via LMOs.

Os autores posicionam o RanSOM como uma solução unificada para a otimização não convexa moderna, particularmente em arquiteturas de aprendizado profundo onde as suposições padrão de suavidade falham e a eficiência computacional é primordial.