Stochastic Adaptive Gradient Descent Without Descent

Enunciado do Problema
O artigo aborda o problema de otimização convexa estocástica:
$$\min_{x \in \mathbb{R}^d} f(x) = \min_{x \in \mathbb{R}^d} \mathbb{E}[f_\xi(x)]$$
onde $f$ é uma função convexa, diferenciável e limitada inferiormente. O objetivo é encontrar um minimizador $x^\star$ usando um oráculo de gradiente estocástico $\nabla f_{\xi_k}$ sem exigir o ajuste cuidadoso de hiperparâmetros, especificamente o passo inicial $\lambda_0$. Enquanto o Gradiente Descendente Estocástico (SGD) padrão exige o ajuste de $\lambda_0$ para equilibrar a velocidade de convergência e a estabilidade, e os métodos adaptativos existentes (como os de Malitsky e Mishchenko [2020]) frequentemente mantêm uma dependência de um parâmetro ajustável $\alpha$ no cenário estocástico, este trabalho busca uma abordagem "livre de ajuste" (tuning-free) que se adapta à geometria local da função objetivo usando apenas chamadas de oráculo de primeira ordem.

Metodologia
Os autores propõem o AdaSGD, uma adaptação estocástica do método "Adaptive Gradient Descent Without Descent" (AdaGD). A inovação central reside na regra de atualização do tamanho do passo, que evita o hiperparâmetro $\alpha$ exigido pelas adaptações estocásticas anteriores.

O algoritmo segue a recursão estocástica padrão $x_{k+1} = x_k - \lambda_k \nabla f_{\xi_k}(x_k)$. O tamanho do passo $\lambda_k$ é atualizado com base na geometria local da função. Uma distinção fundamental em relação ao AdaGD determinístico e às tentativas estocásticas anteriores é a avaliação da diferença de gradiente. Em vez de usar o lote atual $\xi_k$ para ambos os pontos (o que introduziria viés ou exigiria um segundo lote independente $\zeta_k$), o método avalia a diferença de gradiente usando a variável aleatória anterior $\xi_{k-1}$:
$$\hat{L}_{k-1} = \frac{\|\nabla f_{\xi_{k-1}}(x_k) - \nabla f_{\xi_{k-1}}(x_{k-1})\|}{\|x_k - x_{k-1}\|}$$
Isso permite que o tamanho do passo seja definido sem um parâmetro de escala externo. O artigo propõe três variantes (V-I, V-II, V-III) para $k \ge 2$:
$$\lambda_k = \min \left( \frac{c_k}{2\sqrt{2}\hat{L}_{k-1}}, \frac{\lambda_{k-1}}{\sqrt{1 + \theta_{k-1}}} \right)$$
onde $\theta_{k-1} = \lambda_{k-1}/\lambda_{k-2}$ e $c_k$ é um fator de decaimento (especificamente $c_k = 1$ para V-I, e $c_k = k^{1/2+\delta}$ para V-II e V-III com $0 < \delta < 1/2$). A V-III é recomendada por fornecer as garantias teóricas mais fortes.

Análise Teórica
A análise de convergência baseia-se na construção de uma sequência de Lyapunov $(T_k)$, inspirada em Malitsky e Mishchenko [2020], mas adaptada para o cenário estocástico. A sequência é definida como:
$$T_k = \|x_{k+1} - x^\star\|^2 + 2(\lambda_k(1+\theta_k))(f(x_k) - f^\star) + \frac{\|x_{k+1} - x_k\|^2}{2}$$
Os autores provam que, sob suposições específicas (estrutura de soma finita com gradientes Lipschitz, ou iterados limitados), a sequência $(T_k)$ converge quase certamente.

• Convergência Quase Certa: O Teorema 3.2 estabelece que, se os tamanhos de passo forem somáveis ao quadrado ($\sum \lambda_k^2 < \infty$), a sequência de Lyapunov converge. Esta condição mostra-se válida em casos de convexidade forte, regressão linear e somas de funções de ridge.
• Taxas de Convergência: Para funções fortemente convexas (Caso-1), o Teorema 3.4 deriva uma taxa de convergência de $O(1/k^{1/2+\delta})$ para o erro esperado. Crucialmente, os fatores exponenciais que governam o comportamento transiente dependem da razão $L^2/\mu^2$ (onde $L$ é a constante de suavidade e $\mu$ é o parâmetro de convexidade forte) em vez do passo inicial $\lambda_0$. Isso contrasta com o SGD comum, onde o passo inicial pode causar crescimento exponencial no limite de erro antes da convergência.

Principais Contribuições

1. Adaptação Estocástica Livre de Ajuste (Tuning-Free): O artigo introduz uma estratégia de tamanho de passo estocástica que elimina a necessidade de ajustar o parâmetro $\alpha$ (ou $\lambda_0$) exigido na versão estocástica do AdaGD de Malitsky e Mishchenko [2020].
2. Garantias Teóricas: Os autores fornecem provas de convergência rigorosas e taxas sob suposições padrão (convexidade forte, gradientes Lipschitz) sem exigir conhecimento global de $L$ ou $\mu$.
3. Robustez à Inicialização: O método é projetado de tal forma que escolher um tamanho de passo inicial pequeno é sempre seguro, evitando os problemas de sensibilidade comuns em outros métodos adaptativos.

Resultados Experimentais
Experimentos numéricos foram conduzidos em seis problemas de otimização convexa estocástica (regressão linear/ridge/logística/Poisson) usando dados sintéticos e reais (Diabetes, 2moons, w8a).

• Sensibilidade a $\lambda_0$: Os resultados demonstram que o AdaSGD é significativamente menos sensível à escolha do passo inicial $\lambda_0$ em comparação com o SGD comum, o decaying SGD, o Adagrad e o AdaGD-MM estocástico. Enquanto outros métodos exigem uma busca em grade densa para encontrar um $\lambda_0$ ideal, o AdaSGD apresenta desempenho consistente com um valor pequeno fixo (ex: $\lambda_0 = 10^{-3}$).
• Desempenho: Em termos de desempenho de minimização (gap de otimalidade), o AdaSGD (especificamente as variantes V-II e V-III) alcança resultados comparáveis aos baselines otimizados. Os autores observam que, embora a V-I às vezes sofra com oscilações devido ao ruído, o decaimento introduzido na V-II e V-III estabiliza o método.
• Custo: O método requer uma avaliação extra de gradiente estocástico por iteração (para calcular $\nabla f_{\xi_{k-1}}(x_k)$), mas os autores argumentam que esse custo é compensado pela eliminação da busca em grade necessária para o ajuste de hiperparâmetros.

Significância e Alegações
O artigo afirma que o AdaSGD transfere com sucesso os benefícios do "Adaptive Gradient Descent Without Descent" determinístico para o cenário estocástico, uma transição que tentativas anteriores falharam em realizar sem reintroduzir o ajuste de hiperparâmetros. A principal contribuição é um método que é "livre de ajuste" na prática: ele permite que os praticantes utilizem um passo inicial pequeno e fixo sem sacrificar as taxas de convergência ou a estabilidade. Os autores enfatizam que, embora o método não seja estritamente "isento de parâmetros" (pois depende de $\lambda_0$ para o valor inicial da função de Lyapunov), a dependência é fraca o suficiente para que valores pequenos sejam universalmente eficazes, tornando o método robusto e prático para otimização estocástica sem a necessidade de extensa busca de hiperparâmetros. O trabalho permanece focado em configurações convexas, sendo as extensões não convexas notadas como um desafio futuro significativo devido à dependência de desigualdades de convexidade na derivação.