Resumo Técnico: Soma de Quadrados para Submodularidade

Declaração do Problema

A submodularidade é uma propriedade estrutural fundamental de funções de conjuntos, codificando a noção de retornos decrescentes. Ela é central na teoria da otimização, aparecendo na economia, aprendizado de máquina e pesquisa operacional, sendo frequentemente denominada "convexidade discreta". Embora a minimização não restrita de funções submodulares seja solucionável em tempo polinomial, e a maximização sob restrições de cardinalidade admita uma aproximação de $(1 - 1/e)$ via o algoritmo guloso, testar se uma função de conjunto geral é submodular é computacionalmente intratável. Especificamente, para funções de conjunto de grau $d \ge 4$, o problema de decisão é co-NP-completo (Crama 1989; Gallo e Simeone 1989).

Essa dificuldade motiva a necessidade de condições suficientes tratáveis para certificar a submodularidade. Abordagens existentes frequentemente dependem de heurísticas específicas de problemas ou exigem um ajuste manual extensivo. O artigo aborda a lacuna entre a estrutura discreta fundamental da submodularidade e as ferramentas da geometria algébrica real, especificamente as hierarquias de Soma de Quadrados (SOS), para fornecer um arcabouço algébrico sistemático de certificação.

Metodologia

Os autores introduzem a $t$-submodularidade por soma de quadrados ($t$-sos), uma hierarquia de condições algébricas suficientes indexadas por um inteiro $t$. A metodologia baseia-se na correspondência entre funções de conjunto e suas extensões multilineares (MLEs), que são polinômios multilineares.

Definições Principras

1. Extensão Multilinear (MLE): Uma função de conjunto $f: 2^\Omega \to \mathbb{R}$ é representada unicamente por um polinômio multilinear $F \in \mathbb{R}[x_1, \dots, x_n]$ tal que $F(\mathbf{1}_S) = f(S)$ para todo $S \subseteq \Omega$.
2. Caracterização Algébrica: A submodularidade é caracterizada pela não-positividade das derivadas parciais mistas de segunda ordem da MLE no hipercubo booleano $\{0, 1\}^n$ (ou seja, $\frac{\partial^2 F}{\partial x_i \partial x_j} \le 0$).
3. $t$-sos Submodularidade: Uma função de conjunto $f$ é $t$-sos submodular se, para todo $i \neq j$, o polinômio $-\frac{\partial^2 F}{\partial x_i \partial x_j}$ é uma soma de quadrados de polinômios de grau no máximo $t$, módulo o ideal $I_2[x_{-i,j}] = \langle x_k^2 - x_k \mid k \neq i, j \rangle$. Este ideal impõe as restrições booleanas $x_k \in \{0, 1\}$.

Estrutura Computacional

A verificação da $t$-sos submodularidade é reduzida a um Programa Semidefinido (SDP). Para um $t$ fixo e um tamanho de conjunto base $n$, a verificação envolve resolver um SDP com $n(n-1)/2$ restrições, onde o tamanho da matriz de cada restrição é polinomial em $n$ (especificamente $\sum_{k=0}^t \binom{n-2}{k}$).

O artigo estabelece várias caracterizações algébricas equivalentes da $t$-sos submodularidade correspondentes às sete definições padrão de submodularidade (ex: retornos decrescentes, desigualdades de reticulado). Embora essas caracterizações sejam algebricamente equivalentes, os autores demonstram que a formulação de segunda ordem (baseada em derivadas parciais mistas) produz a menor representação de SDP, tornando-a a mais eficiente computacionalmente.

Principais Contribuições

1. Fundamentos Teóricos

• Construção da Hierarquia: O artigo define a $t$-sos submodularidade como uma hierarquia onde qualquer função $t$-sos submodular é submodular. Inversamente, qualquer função submodular de grau $d$ é $t$-sos submodular para um $t$ suficientemente grande (especificamente $t = \lceil \frac{n+d-5}{2} \rceil$).
• Análise do Gap de Complexidade:
  • Para graus $d < 4$, a submodularidade e a $t$-sos submodularidade coincidem para pequenos valores de $t$ (ex: $t=0$ para $d=2$, $t=1$ para $d=3$). Isso se alinha ao fato de que o teste de submodularidade é polinomial para $d \le 3$.
  • Para $d=4$, o artigo constrói uma função submodular que requer $t \approx n/2$ para ser certificada como $t$-sos submodular, refletindo a dificuldade inerente do problema.
• Propriedades de Preservação: Os autores identificam operações que preservam a $t$-sos submodularidade (somas ponderadas não negativas, complementação, restrição, contração) e aquelas que não preservam (minimização parcial, convolução, monotonização), observando que estas últimas podem aumentar drasticamente o $t$ necessário.

2. Aplicações

O artigo demonstra a utilidade da $t$-sos submodularidade em três áreas distintas:

• Regressão Submodular: Os autores propõem o ajuste de polinômios $t$-sos submodulares a dados via SDP. Diferente de métodos existentes (como abordagens baseadas em redes neurais ou misturas de cascas heurísticas), esta abordagem requer mínimo ajuste manual (apenas o grau polinomial $k$ e o grau SOS $t$) e garante uma saída submodular. Resultados empíricos mostram erro de generalização superior em dados ruidosos comparado à regressão polinomial não restrita e aos métodos neurais de última geração.
• Maximização Submodular Aproximada: Para maximizar funções aproximadamente submodulares, o desempenho do algoritmo guloso depende da razão de submodularidade $\gamma^*$. Calcular $\gamma^*$ é NP-difícil. O artigo fornece um procedimento sistemático baseado em SDP para derivar limites inferiores para $\gamma^*$ usando $t$-sos submodularidade, melhorando os limites espectrais em experimentos numéricos.
• Otimização de Diferença-de-Submodulares (DS): Problemas de otimização DS ($\min g - h$) são resolvidos via Procedimento Submodular-Supermodular (SSP). A qualidade da solução depende da decomposição DS específica. Os autores propõem um SDP para encontrar uma decomposição irredutível (maximizando a curvatura do componente submodular $h$) que leva a ótimos locais significativamente melhores do que decomposições triviais, embora com maior tempo de computação.

Resultados

• Teóricos: O artigo fornece uma classificação completa de quando a submodularidade coincide com a $t$-sos submodularidade com base no grau da função de conjunto. Prova-se que, para $d \ge 4$, o gap entre os dois conceitos pode ser grande, necessitando de altos níveis da hierarquia.
• Empíricos:
  • Em tarefas de regressão, a abordagem $t$-sos supera tanto a regressão polinomial não restrita quanto o método de rede neural FlexSubNet em termos de RMSE de teste em dados sintéticos submodulares.
  • Na otimização DS, o uso da decomposição irredutível derivada de SOS reduziu o gap de otimalidade relativa médio em aproximadamente 10–15 pontos percentuais em comparação com a decomposição trivial através de vários tamanhos de problema ($n=10, 15, 20$).
  • Os limites inferiores para a razão de submodularidade baseados em SDP foram mais estreitos que os limites espectrais existentes.

Significância e Alegações

O artigo afirma construir uma nova ponte entre a otimização discreta e a geometria algébrica real. Ao conectar certificados algébricos baseados em SOS à submodularidade, os autores fornecem um arcabouço sistemático e tratável para certificar e explorar a estrutura submodular onde verificações combinatórias tradicionais falham.

A significância reside na:

1. Tratabilidade: Transformar um problema de verificação co-NP-completo em uma verificação de SDP de tempo polinomial (para um $t$ fixo).
2. Abordagem Sistemática: Substituir insights ad-hoc e específicos de problemas para derivar limites ou decomposições por um arcabouço algébrico unificado.
3. Utilidade Prática: Demonstrar que impor restrições de submodularidade algébrica melhora o desempenho em tarefas de regressão e otimização sem a instabilidade do treinamento de redes neurais não convexas.

Os autores mantêm a modéstia quanto às limitações, reconhecendo que, embora a hierarquia seja completa (qualquer função submodular é eventualmente $t$-sos submodular), o custo computacional cresce com $t$ e $n$, e o método é atualmente mais eficaz para funções de baixo grau ou quando valores moderados de $t$ são suficientes. Sugere-se como trabalho futuro a extensão destes resultados para minimização não restrita via hierarquia de Lasserre e o estabelecimento de garantias estatísticas formais para a abordagem de regressão.