Proximal Projection for Doubly Sparse Regularized Models

Resumo Técnico: Projeção Proximal para Modelos Regularizados Duplamente Esparsos

Enunciado do Problema
Em configurações de regressão de alta dimensão onde o número de preditores ($p$) excede o tamanho da amostra ($n$), os Mínimos Quadrados Ordinários (MQO) padrão falham devido à singularidade e multicolinearidade. Embora métodos de regularização como LASSO (penalidade $l_1$) e Ridge (penalidade $l_2$) abordem a esparsidade e a estabilidade, eles frequentemente ignoram as relações estruturais subjacentes entre os preditores. Quando os preditores podem ser representados por um modelo gráfico gaussiano, explorar essa estrutura melhora a estimação.

Abordagens existentes, como a Regressão Esparsa Incorporando Estrutura Gráfica (SRIG) e sua extensão duplamente esparsa (DSRIG), decompõem o vetor de coeficientes $\beta$ em variáveis latentes correspondentes às contribuições dos nós e aplicam regularização nessas variáveis latentes. No entanto, o modelo DSRIG, que alcança "dupla esparsidade" (esparsidade entre grupos e dentro dos grupos), depende da duplicação de preditores para lidar com grupos sobrepostos. Essa abordagem torna-se computacionalmente proibitiva para dados de alta dimensão ou grafos densos, pois aumenta significativamente a dimensionalidade do problema de otimização. Além disso, o DSRIG requer o ajuste de dois parâmetros ($\lambda$ e $\xi$) para equilibrar a esparsidade entre grupos e dentro dos grupos, complicando a busca por soluções ótimas.

Metodologia
Os autores propõem o modelo LASSO de Grupos Sobrepostos Esparsos Incorporando Estrutura Gráfica (SGLIG). Este modelo reparametriza o framework DSRIG para manter a dupla esparsidade enquanto reduz a complexidade computacional e o número de parâmetros de ajuste.

1. Formulação do Modelo:
   O modelo SGLIG minimiza a função objetivo:
   $$\min_{\beta, V^{(1)}, \dots, V^{(p)}} \frac{1}{2n}\|Y - X\beta\|_2^2 + \lambda^* \sum_{i=1}^p \left( \alpha \tau_i \|V^{(i)}\|_2 + (1-\alpha) \frac{1}{\sqrt{d_i}} \|V^{(i)}\|_1 \right)$$
   onde $\beta = \sum V^{(i)}$, $V^{(i)}$ representa a contribuição do preditor $i$, $d_i$ é o grau do vizinhança, e $\alpha \in [0, 1]$ controla o compromisso entre as penalidades $l_2$ (grupo) e $l_1$ (dentro do grupo). Diferentemente do DSRIG, o SGLIG utiliza um único parâmetro de ajuste $\alpha$ (com $\lambda^*$ fixo como uma constante baseada em $\lambda_{max}$), simplificando a busca em grade de otimização.

2. Algoritmo Proximal Duplamente Projetado:
   Para otimizar o objetivo do SGLIG, os autores desenvolvem um Algoritmo Proximal Duplamente Projetado baseado no FISTA (Algoritmo de Encolhimento-Thresholding Iterativo Rápido).

   • Estratégia de Grupo Ativo: O algoritmo identifica um conjunto ativo de grupos $\hat{G}_m$ com base nos passos de gradiente atuais.
   • Projeção sobre a Interseção: Em vez de duplicar preditores, o algoritmo calcula o operador proximal projetando sobre a interseção de conjuntos convexos definidos por bolas de norma $l_2$ e $l_\infty$.
   • Projeção em Dois Estágios: A projeção é calculada sequencialmente: primeiro aplicando thresholding suave para esparsidade dentro do grupo ($l_1$/$l_\infty$), seguido por thresholding suave de grupo para esparsidade entre grupos ($l_2$). Isso é implementado usando uma sequência de composições (POCS) em vez do algoritmo paralelo tipo Dykstra, que os autores argumentam ser menos eficiente para sua estratégia de conjunto ativo.

3. Propriedades Teóricas:
   O artigo deriva um limite de erro de amostra finita para o estimador SGLIG sob suposições de decomposição ótima, convexidade forte restrita (RSC) e limites específicos nos pesos $\tau_i$ e graus dos nós. Adicionalmente, os autores provam a normalidade assintótica do estimador quando $n \to \infty$ com $p$ fixo, mostrando consistência com o modelo SRIG apesar da penalidade $l_1$ adicionada.

Principais Contribuições

• Inovação Algorítmica: O desenvolvimento de um algoritmo proximal duplamente projetado inovador que evita a duplicação de preditores. Este método calcula projeções sobre a interseção de conjuntos convexos iterativamente, conservando recursos computacionais para estruturas de grafos de alta dimensão e densos.
• Eficiência do Modelo: O modelo SGLIG alcança dupla esparsidade com apenas um parâmetro de ajuste ($\alpha$), reduzindo o ônus computacional da seleção de hiperparâmetros em comparação com o DSRIG de dois parâmetros.
• Garantias Teóricas: Derivação de limites de erro de amostra finita e prova de normalidade assintótica para o estimador SGLIG, estabelecendo sua validade estatística sob suposições padrão.
• Validação Empírica: Avaliação abrangente em dados simulados com cinco estruturas de grafos distintas (Duas Classes, Bipartido, Aleatório, em Blocos, Banda) e dois conjuntos de dados do mundo real (Barreira Hematoencefálica e Iniciativa de Neuroimagem da Doença de Alzheimer).

Resultados

• Estudos de Simulação:

  • Precisão: O modelo DSRIG geralmente alcançou o menor Erro Quadrático Médio (EQM) e distância $l_2$. No entanto, o modelo SGLIG performou competitivamente, frequentemente igualando a precisão do DSRIG de perto, enquanto superava significativamente o modelo SRIG de esparsidade única.
  • Eficiência: O modelo SGLIG demonstrou uma redução substancial no tempo de computação em comparação com o DSRIG. Em cenários de alta dimensão (por exemplo, 800 preditores), o DSRIG exigiu mais de 2.900 segundos, enquanto o SGLIG exigiu aproximadamente 60 segundos, e o SRIG exigiu 40 segundos. O SGLIG efetivamente preenche a lacuna entre a velocidade do SRIG e a precisão do DSRIG.
  • Sensibilidade ao Grafo: O SGLIG performou robustamente em várias topologias de grafos, com exceção do grafo "Banda", onde a esparsidade dentro do grupo foi menos benéfica devido à estrutura de conectividade linear.

• Dados do Mundo Real:

  • No conjunto de dados da Barreira Hematoencefálica, o SGLIG alcançou o menor EQM entre os três modelos, mantendo tempos de computação comparáveis ao SRIG e significativamente menores que o DSRIG.
  • A análise de seleção de variáveis mostrou que o SGLIG e o DSRIG (ambos duplamente esparsos) selecionaram variáveis relacionadas à carga da partícula, enquanto o SRIG focou mais em medidas de área de superfície, sugerindo que a dupla esparsidade captura nuances estruturais diferentes.

Significado e Alegações
O artigo alega que o modelo SGLIG oferece um compromisso prático para regressão de alta dimensão com estrutura gráfica. Ao substituir a duplicação de preditores por uma técnica de projeção proximal inovadora, os autores afirmam que seu método conserva recursos computacionais sem sacrificar os benefícios da dupla esparsidade. Os resultados sugerem que o SGLIG exibe desempenho estável em relação a outros modelos de regressão gráfica de esparsidade única ou dupla, tornando-se uma alternativa viável para cenários onde o DSRIG é computacionalmente inviável. Os autores enfatizam que sua implementação é particularmente vantajosa para dados de alta dimensão com grafos de preditores densos.