New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

Resumo Técnico: Nova Perspectiva sobre Redução de Variância em Limiarização Rígida de Ordem Zero

Formulação do Problema
O artigo aborda o desafio de resolver problemas de otimização com restrições $\ell_0$, que são fundamentais para alcançar aprendizado esparsificado em tarefas de aprendizado de máquina de alta dimensão. O problema específico é formulado como a minimização de um risco empírico regularizado $F(\theta) = \frac{1}{n}\sum_{i=1}^n f_i(\theta)$ sujeito a $\|\theta\|_0 \leq k$. Embora algoritmos iterativos de limiarização rígida sejam eficazes para restrições $\ell_0$, eles tradicionalmente exigem acesso a gradientes verdadeiros. Em muitos cenários modernos — como problemas de bandit, ataques adversariais de caixa preta e aprendizado por reforço — os gradientes são inacessíveis, tornando necessária a utilização de métodos de otimização de ordem zero (ZO) que dependem de avaliações de função.

O algoritmo atual de última geração para essa configuração, Limiarização Rígida Estocástica de Ordem Zero (SZOHT), sofre de uma limitação crítica. Os autores identificam um conflito inerente entre o desvio (erro) dos estimadores de gradiente de ordem zero e a expansividade (não não-expansividade) do operador de limiarização rígida. Para garantir convergência, o SZOHT impõe condições rigorosas sobre o número de direções aleatórias ($q$) utilizadas para a estimativa do gradiente e o nível de esparsidade ($k$). Essas condições são frequentemente excessivamente restritivas para aplicações práticas, limitando a utilidade do algoritmo.

Metodologia
O artigo propõe uma nova perspectiva para resolver o conflito entre gradientes de ordem zero e limiarização rígida, focando na redução de variância. Os autores argumentam que o conflito é fundamentalmente entre o operador de limiarização rígida e a variância da estimativa do gradiente, e não o erro de estimativa em si.

Para abordar isso, o artigo introduz um framework generalizado chamado pM-SZHT (Limiarização Rígida Estocástica de Ordem Zero com p-Memorização). Este framework utiliza gradientes históricos para reduzir a variância, semelhante às técnicas de redução de variância de primeira ordem como SAGA e SVRG, mas adaptado para o cenário de ordem zero. Os componentes principais incluem:

1. Expressão Iterativa Generalizada: O algoritmo segue a regra de atualização $\theta^{(r+1)} = H_k(\theta^{(r)} - \eta \hat{g}^{(r)}(\theta^{(r)}))$, onde $\hat{g}^{(r)}$ é uma estimativa de gradiente generalizada incorporando redução de variância.
2. p-Memorização: O framework emprega um mecanismo de memória onde um subconjunto aleatório de estimativas de gradiente é atualizado em cada iteração, permitindo que o algoritmo aproveite informações históricas para estabilizar as estimativas de ordem zero.
3. Algoritmos Específicos: Dentro deste framework, os autores instanciam algoritmos específicos, incluindo VR-SZHT (uma adaptação de ordem zero do SVRG) e SARAH-SZHT (uma adaptação de ordem zero do SARAH).

Análise Teórica
O artigo fornece uma análise abrangente de convergência sob suposições padrão de aprendizado esparsificado: Convexidade Forte Restrita (RSC) e Suavidade Forte Restrita (RSS).

• Mitigação do Conflito: A análise demonstra que, ao utilizar redução de variância, o algoritmo pode eliminar a dependência estrita do número de direções aleatórias ($q$) necessária para a convergência. No SZOHT, $q$ deve ser grande o suficiente para satisfazer limites específicos em relação a $k$; nos métodos propostos, a convergência é garantida para qualquer $q > 0$ (desde que outros parâmetros, como a taxa de aprendizado, sejam escolhidos corretamente).
• Taxas de Convergência: Os resultados teóricos mostram que os algoritmos propostos alcançam taxas de convergência aprimoradas em comparação com o SZOHT. Especificamente, a complexidade de consultas para o VR-SZHT é derivada como $O([n + \frac{\kappa^3}{\kappa^2+1}] \log(1/\epsilon))$, o que representa uma melhoria significativa sobre a complexidade $O((k + d/s^2)\kappa^2 \log(1/\epsilon))$ do SZOHT, particularmente quando o número de condição $\kappa$ é grande.
• Independência de $q$: Uma descoberta teórica chave é que a redução de variância desacopla a condição de convergência do número de direções aleatórias, permitindo uma seleção de parâmetros mais flexível.

Resultados Experimentais
Os autores validam seus métodos em duas tarefas principais:

1. Regressão Ridge: Utilizando dados sintéticos, os algoritmos de redução de variância propostos (VR-SZHT, SAGA-SZHT, SARAH-SZHT) superam consistentemente o SZOHT puro e o ZOHT de gradiente completo (FGZOHT). Eles alcançam valores de função mais baixos com menos operações de limiarização rígida (NHT) e chamadas competitivas de oráculo de ordem zero (IZO).
2. Ataques Adversariais de Caixa Preta: Os métodos são aplicados para gerar perturbações adversariais universais esparsas no conjunto de dados CIFAR-10 contra um classificador de caixa preta. Os resultados indicam que os métodos com redução de variância, particularmente SARAH-SZHT e SAGA-SZHT, alcançam taxas de sucesso de ataque mais altas e valores de perda mais baixos em comparação com o SZOHT. Por exemplo, o SARAH-SZHT atacou com sucesso 7 de 10 imagens na classe "avião", superando o SZOHT.

Significância e Alegações
O artigo alega fornecer uma "nova perspectiva" sobre redução de variância, enquadrando-a não apenas como um mecanismo de aceleração, mas como uma ferramenta necessária para mitigar as contradições únicas entre estimadores de ordem zero e operadores de limiarização rígida. A significância do trabalho reside em:

• Relaxamento de Restrições: Remove as restrições proibitivas sobre o número de direções aleatórias ($q$) encontradas no SZOHT, tornando a limiarização rígida de ordem zero viável para uma gama mais ampla de problemas do mundo real.
• Framework Geral: Estabelece um framework de análise geral (pM-SZHT) que abrange vários métodos de ordem zero com redução de variância, oferecendo uma compreensão teórica unificada.
• Utilidade Prática: Os resultados experimentais em ataques adversariais e regressão demonstram que esses métodos podem alcançar desempenho competitivo ou superior em comparação com algoritmos de ordem zero de última geração, mantendo restrições de esparsidade.

Os autores concluem que sua abordagem aprimora efetivamente os algoritmos existentes para otimização esparsa de ordem zero, oferecendo uma solução mais flexível e resiliente para cenários onde os gradientes são inacessíveis.