Coordinate Descent Algorithm for Least Absolute Deviations Regression

Título: Algoritmo de Descida de Coordenadas para Regressão de Desvios Absolutos Mínimos (LAD)

Autores: Zehaan Naik e Debasis Kundu (IIT Kanpur, Índia)
Data: 23 de março de 2026

---

1. O Problema

A regressão por Desvios Absolutos Mínimos (LAD - Least Absolute Deviations), também conhecida como regressão de mediana, é uma alternativa robusta à clássica Regressão por Mínimos Quadrados Ordinários (OLS). Enquanto a OLS minimiza a soma dos quadrados dos resíduos (sendo sensível a outliers e ruídos de cauda pesada), a LAD minimiza a soma dos valores absolutos dos resíduos.

Apesar de suas propriedades de robustez, a adoção generalizada da LAD tem sido limitada por desafios computacionais:

• Custo Computacional: Os métodos tradicionais baseiam-se em formulações de Programação Linear (PL), resolvidas por algoritmos como o Simplex ou pontos interiores.
• Escalabilidade: Esses métodos tornam-se computacionalmente proibitivos em dimensões altas.
• Instabilidade Numérica: Em cenários de alta dimensionalidade, onde o número de preditores ($p$) é maior ou igual ao número de observações ($n$), as formulações de PL podem sofrer de má condicionamento numérico ou falhar em encontrar soluções confiáveis.
• Dependência de Software: A necessidade de solvers especializados de PL limita a facilidade de implementação.

2. Metodologia Proposta

Os autores propõem um algoritmo de Descida de Coordenadas (Coordinate Descent - CD) específico para o problema de LAD, que evita a inversão de matrizes e lida naturalmente com a não diferenciabilidade da função objetivo.

Fundamentação Teórica

O algoritmo explora a estrutura convexa do problema. Ao fixar todas as coordenadas do vetor de coeficientes $\beta$ exceto uma ($\beta_j$), o problema de otimização multivariada reduz-se a um problema univariável:
$$\min_{t \in \mathbb{R}} \sum_{i=1}^n |r_i^{(j)} - x_{ij}t|$$
onde $r_i^{(j)}$ é o resíduo parcial. A solução exata para este subproblema é dada pela mediana (se $x_{ij}=1$, caso do intercepto) ou pela mediana ponderada dos rácios $r_i^{(j)}/x_{ij}$ com pesos $|x_{ij}|$.

Algoritmo Otimizado (LAD-CD)

Para superar a ineficiência de uma implementação ingênua (que recalcula resíduos parciais a cada passo, com complexidade $O(np^2)$), os autores propõem uma versão otimizada com atualizações incrementais de resíduos:

1. Mantém-se um vetor de resíduo global $\text{res} = y - X\beta$.
2. Para cada coordenada $j$:
   • Restaura a contribuição atual de $\beta_j$ para obter o resíduo parcial.
   • Calcula a nova coordenada $\beta_j^{new}$ via mediana ponderada ($O(n \log n)$).
   • Atualiza o resíduo global in-place: $\text{res} \leftarrow \text{res} - X_{:j}(\beta_j^{new} - \beta_j)$ ($O(n)$).
3. Complexidade: A complexidade por varredura completa (uma iteração sobre todas as $p$ coordenadas) é reduzida para $O(pn \log n)$.

Estratégias de Inicialização (Warm-Start)

Como a descida de coordenadas é um método local, a escolha do ponto inicial é crucial, especialmente em problemas subdeterminados ($p \geq n$):

• Regressão Ridge: Inicializar com uma solução de Ridge (mínimos quadrados penalizados) é altamente eficaz, fornecendo estabilidade numérica e reduzindo a variância.
• Algoritmos Genéticos (GA): Usados para busca global em paisagens de perda complexas ou com ruído pesado, servindo como inicialização para o refinamento local via LAD-CD.
• Multi-start Aleatório: Estratégia simples para evitar mínimos locais em casos sem inicialização prévia.

3. Principais Contribuições

1. Algoritmo Livre de Inversão de Matriz: O método não requer a inversão de $X^TX$, tornando-o viável quando $p \geq n$ (caso onde a OLS falha e a PL é instável).
2. Convergência Global Provada: Devido à convexidade da função objetivo LAD e à exatidão de cada atualização de coordenada, o algoritmo é garantido para convergir para um minimizador global.
3. Eficiência Computacional: Redução drástica da complexidade computacional em comparação com métodos de Programação Linear, permitindo escalabilidade em regimes de alta dimensão.
4. Implementação Simples: Não requer bibliotecas de otimização especializadas, sendo fácil de implementar em qualquer linguagem de programação.

4. Resultados Experimentais

Os autores validaram o método em dados sintéticos e conjuntos de dados reais (Boston Housing, Air Quality, Concrete Compressive Strength).

• Robustez a Outliers: Em dados contaminados com 20% de outliers, o LAD-CD recuperou o sinal verdadeiro com precisão, superando significativamente a OLS e igualando a performance de solvers de PL (QuantReg).
• Regimes de Alta Dimensão ($p \geq n$):
  • Solvers de PL (QuantReg) falharam em retornar soluções quando $p > n$.
  • O LAD-CD permaneceu estável e bem definido.
  • A inicialização com Ridge seguida de refinamento LAD-CD produziu os menores erros de previsão (MAE), superando até mesmo o uso de coeficientes verdadeiros em alguns casos devido ao viés-variância (efeito de shrinkage).
• Comparação de Performance:
  • Em conjuntos de dados menores ($p < n$), o LAD-CD atingiu precisão de previsão comparável ao solver de PL (QuantReg), embora com um custo computacional ligeiramente maior devido à iteração.
  • Em cenários de alta dimensão, o LAD-CD foi a única abordagem viável e robusta.
• Convergência: O algoritmo estabilizou tipicamente em 20-50 iterações, demonstrando monotonicidade na redução da função de perda.

5. Significado e Conclusão

O trabalho apresenta uma ferramenta prática e escalável para modelagem linear robusta. A principal contribuição é democratizar o uso da regressão LAD em cenários modernos de "Big Data" e alta dimensionalidade, onde métodos tradicionais de Programação Linear são inviáveis.

• Recomendação Prática: Para problemas com $p < n$, solvers de PL ainda são rápidos. Para $p \geq n$ ou dados com ruído pesado, recomenda-se o uso do LAD-CD inicializado com Ridge.
• Impacto: O método oferece uma alternativa modular, sem dependência de solvers externos, que combina a robustez estatística da mediana com a eficiência computacional da descida de coordenadas, preenchendo uma lacuna importante na estatística robusta de alta dimensão.