Cost-sensitive spectral sampling algorithms for randomized block Kaczmarz methods

Resumo Técnico: Algoritmos de amostragem espectral sensíveis ao custo para métodos de Kaczmarz em blocos aleatórios

Enunciado do Problema
O artigo aborda o problema de design offline para métodos de Kaczmarz em blocos aleatórios utilizados para resolver sistemas lineares consistentes $Ax=b$. Embora os métodos de Kaczmarz em blocos aleatórios projetem as iterações sobre blocos de equações selecionados aleatoriamente, sua taxa de convergência certificada depende fortemente da distribuição de amostragem. Uma restrição prática crítica é que diferentes blocos de equações podem incorrer em custos computacionais vastamente distintos (por exemplo, devido ao layout de memória, overhead de comunicação ou tamanho do bloco).

Abordagens existentes frequentemente prescrevem heurísticas (proporcionais à norma, baseadas em pavimentação/paving), adaptam-se aos resíduos atuais ou otimizam quantidades livres de custo. O problema específico abordado aqui é: dada uma lista fixa e finita de blocos admissíveis com custos positivos associados, qual distribuição de probabilidade estática sobre esses blocos maximiza a taxa de convergência exponencial certificada por unidade de trabalho computacional esperado?

Metodologia e Estrutura Teórica
Os autores formalizam o problema representando cada bloco $B$ através de seu projetor ortogonal $P_B$ sobre o espaço linha do bloco e um custo $c_B$.

1. Certificado Normalizado pelo Trabalho: O certificado de convergência padrão é governado pelo menor autovalor $\mu(p)$ do projetor esperado $H_p = \sum p_B P_B$ restrito ao espaço linha de $A$. O trabalho esperado por passo é $\bar{c}(p) = \sum p_B c_B$. O objetivo é maximizar a razão $\eta(p) = \mu(p) / \bar{c}(p)$.
2. Formulação de Design Ótimo: Ao introduzir uma mudança de variáveis $w_B = p_B / \bar{c}(p)$, o problema é transformado em maximizar o menor autovalor de uma soma ponderada de projetores escalonados pelo custo $G_B/c_B$ (onde $G_B$ é o projetor restrito ao espaço linha). Isso é identificado como um problema de design E-ótimo sensível ao custo.
3. Programação Semidefinida (SDP): O problema é formulado como uma SDP:
   $$\max t \quad \text{sujeito a} \quad \sum w_B G_B \succeq t I_r, \quad \sum w_B c_B = 1, \quad w_B \ge 0$$
   onde $r = \text{rank}(A)$.
4. Certificado Dual: O artigo deriva uma formulação dual envolvendo um certificado de "direção difícil". O valor ótimo $\eta^*$ é o mínimo sobre matrizes semidefinidas positivas de traço unitário $Z$ do máximo de eficiência direcional normalizada pelo custo $\langle G_B, Z \rangle / c_B$ através do catálogo. Isso fornece um gap a posteriori rigoroso para qualquer design candidato.
5. Suporte Esparso: Um teorema baseado no teorema de Carathéodory estabelece que existe um design ótimo com suporte em no máximo $r(r+1)/2 + 1$ blocos.

Contribuições Algorítmicas
O artigo propõe dois algoritmos certificados para computar a distribuição estática ótima:

1. Método de Troca Exata (Exact Exchange Method): Um esquema de geração de colunas que mantém um pequeno conjunto ativo de blocos. Ele resolve uma SDP mestre restrita para encontrar uma distribuição candidata e um certificado dual, e então realiza um passo de "precificação" sobre o catálogo completo para identificar um novo bloco que melhore o certificado. Este método fornece gaps de otimalidade rigorosos.
2. Design Espectral do tipo Frank-Wolfe: Um método de gradiente condicional de primeira ordem aplicado ao invólucro convexo escalonado pelo custo dos projetores. Ele seleciona iterativamente o bloco com a maior eficiência direcional contra a direção eigen mais fraca atual (o supergradiente da função do menor autovalor). Este método evita a resolução de SDPs restritas e utiliza a mesma quantidade tanto para a seleção de blocos quanto para a certificação do gap.

Resultos e Testes Diagnósticos
O artigo apresenta testes numéricos diagnósticos em vez de benchmarks de larga escala para isolar mecanismos específicos:

• Redundância (Teste A): Em um catálogo com muitos blocos redundantes para algumas direções, a amostragem uniforme e baseada em norma performam mal porque desperdiçam massa de probabilidade em redundância. O design espectral concentra corretamente a massa em direções independentes, melhorando o certificado por um fator de $(N+1)/2$.
• Heterogeneidade de Custo (Teste B): Em um cenário com blocos de um único elemento (singletons) baratos e blocos grandes caros, o design espectral cego ao custo (ignorando custos) seleciona os blocos caros, alcançando um alto ganho por iteração, mas um desempenho ruim normalizado pelo trabalho. O design sensível ao custo favorece corretamente os blocos mais baratos, resultando em um trabalho total significativamente menor para atingir um erro alvo.
• Caso Não-Diagonal Esparso (Teste C): Usando uma matriz esparsa com blocos de tamanhos e custos variados (modelados por uma função de custo cúbica), o design sensível ao custo novamente supera as linhas de base de amostragem uniforme, baseada em norma e cega ao custo. O trabalho mediano empírico observado em 20 execuções aproximou-se fortemente da ordenação prevista pelo certificado teórico normalizado pelo trabalho.

Significância e Alegações
O artigo afirma fornecer uma perspectiva complementar à teoria de projeção aleatória existente. Ele não introduz um novo passo de projeção nem afirma otimizar a trajetória exata da média quadrática. Em vez disso, sua significância reside em:

• Identificação Formal: Identificar explicitamente o problema de seleção de blocos offline como um problema de design E-ótimo sensível ao custo.
• Algoritmos Certificados: Fornecer dois algoritmos com certificados a posteriori explícitos (gaps) que quantificam o quão próximo um design estático está da taxa ótima normalizada pelo trabalho.
• Insight Prático: Demonstrar que heurísticas padrão (uniforme, baseada em norma) podem ser substancialmente subótimas quando a informação do espaço linha é redundante ou os custos dos blocos são desequilibrados.
• Escopo: O método é posicionado como uma regra estática offline, mais adequada para cenários onde um catálogo de blocos é reutilizado em muitos lados direitos, ou onde os custos dos blocos variam significativamente. Não se destina a cenários de solução única onde o custo do design excede o custo da solução, nem substitui métodos adaptativos baseados em resíduos que resolvem um problema online diferente.