Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

Resumo Técnico: Solução do Problema Min-Max Offline e Online de Funções Submodulares-Côncavas Não Suaves

Formulação do Problema
Este trabalho aborda problemas de otimização min-max e max-min de variáveis inteiras mistas da forma:
$$\max_{y \in Y} \min_{S \subset Q} f(S, y) \quad \text{e} \quad \min_{S \subset Q} \max_{y \in Y} f(S, y)$$
onde $Q = [n]$ é um conjunto base de $n$ elementos, $2^Q$ denota o conjunto das partes e $Y \subset \mathbb{R}^m$ é um conjunto convexo compacto. A função objetivo $f: 2^Q \times \mathbb{R}^m \to \mathbb{R}$ é assumida como submodular em relação à variável de conjunto $S$ e côncava em relação à variável contínua $y$. Crucialmente, a função é permitida ser não suave (não diferenciável) em relação a ambas as variáveis. Os autores visam calcular um ponto de sela $\epsilon$, definido como um par $(\bar{S}, \bar{y})$ tal que o gap de dualidade seja limitado por $\epsilon$.

Metodologia
A abordagem proposta utiliza um framework de Ordem Zero (ZO) baseado no método extragradient. A metodologia depende de duas técnicas principais para lidar com a não suavidade e a estrutura de variáveis mistas:

1. Extensão de Lovász para Submodularidade: Para lidar com o componente submodular discreto, os autores utilizam a extensão de Lovász $f^L$, que mapeia a função de conjunto submodular para uma função contínua e convexa sobre o hipercubo $[0, 1]^n$. O subgradiente de $f^L$ em relação à variável de conjunto pode ser computado usando apenas avaliações da função (via uma cadeia máxima de subconjuntos), evitando a necessidade de informações de ordem superior.
2. Suavização Gaussiana para Concavidade: Para a variável contínua côncava $y$, onde a função pode ser não suave, os autores empregam suavização gaussiana. Eles definem um oráculo aleatório usando um estimador de dois pontos para aproximar o gradiente da função suavizada. Isso permite atualizações baseadas em gradientes sem acesso explícito a derivadas.

O algoritmo resultante (Algoritmo 1, ZO-EG) opera em um loop iterativo:

• Etapa Forward: Estima-se o operador na iteração atual $z_k = (x_k, y_k)$ amostrando direções gaussianas para computar o oráculo aleatório para $y$ e calculando o subgradiente para $x$.
• Etapa de Extrapolacão: Realiza-se um passo de descida para um ponto de previsão $\hat{z}_k$.
• Etapa de Atualização: Reestima-se o operador em $\hat{z}_k$ e realiza-se um segundo passo de descida para atualizar $z_{k+1}$.

O método requer apenas consultas de valor de função (informação de ordem zero) e não assume acesso direto a gradientes ou subgradientes.

Principais Contribuições e Resultados Teóricos
O artigo fornece garantias de convergência para ambos os cenários offline e online:

• Convergência Offline: Os autores provam que o algoritmo converge, em expectativa, para um ponto de sela $\epsilon$. A complexidade total de amostragem é mostrada como $O(nm^2\epsilon^{-2})$, onde $n$ é o tamanho do conjunto base e $m$ é a dimensão da variável contínua. A dependência em $n$ surge do custo por iteração de computar subgradientes da extensão de Lovász, enquanto a contagem de iterações depende de $m$.
• Convergência Online: No cenário online, onde a função de custo $f_k$ muda ao longo do tempo, o algoritmo alcança um gap de dualidade online esperado de $O(\sqrt{N \bar{P}_N})$. Aqui, $N$ é o número de iterações e $\bar{P}_N$ é o comprimento do caminho da sequência de decisões ótimas. Este resultado alinha-se com limites de arrependimento dinâmico estabelecidos em otimização online.
• Existência de Soluções: O artigo discute condições sob as quais pontos de sela existem para o problema discreto original, relacionando-os às soluções do problema contínuo da extensão de Lovász, especificamente quando o minimizador da extensão reside em um vértice do hipercubo.

Resultados Numéricos e Aplicações
As descobertas teóricas são ilustradas através de exemplos numéricos, focando especificamente em segmentação de imagens adversariais e agrupamento semi-supervisionado:

• Segmentação Adversarial Offline: O método é aplicado a um problema min-max onde um adversário perturba os pesos de confiança de pixels semente. O algoritmo recupera com sucesso a segmentação correspondente à verdade fundamental, demonstrando robustez contra perturbações adversariais.
• Segmentação Adversarial Online: O algoritmo é testado em um fluxo de vídeo onde formas e agrupamentos se movem e rotacionam, fazendo com que a função de custo mude a cada quadro. O método realiza segmentação em tempo real (aprox. 80 fps em CPU) sem pré-treinamento.
• Comparação com Aprendizado Profundo: No cenário adversarial online, o método ZO proposto supera tanto modelos U-Net treinados de forma supervisionada quanto semi-supervisionada em termos de Interseção sobre União (IoU), precisão e recall. Notavelmente, o método ZO não requer pré-treinamento, possui uma pegada de memória significativamente menor (~0,05 MB vs. ~8 MB para U-Net) e opera efetivamente em ambientes não vistos sem acesso a grandes conjuntos de dados.

Significado e Alegações
Os autores afirmam que este é o primeiro estudo dedicado a resolver problemas de otimização min-max com funções de custo submodulares-côncavas não suaves. O significado do trabalho reside em:

1. Preenchendo uma Lacuna: Aborda uma classe de problemas min-max combinatórios que eram previamente difíceis de resolver devido à falta de suavidade e à natureza mista discreto-contínua.
2. Eficiência de Ordem Zero: Demonstra que métodos de ordem zero, tradicionalmente usados para problemas contínuos não suaves, podem ser efetivamente adaptados para otimização submodular via a extensão de Lovász.
3. Robustez e Eficiência: Os resultados numéricos sugerem que esta abordagem oferece uma alternativa viável ao aprendizado profundo para ambientes em tempo real, com restrições de recursos e adversariais, particularmente onde o pré-treinamento é inviável ou o ambiente é não estacionário.

O artigo conclui observando que trabalhos futuros poderiam explorar a relação entre essas soluções e equilíbrios de Nash de estratégias mistas, estender os resultados para funções de custo submodulares-submodulares e investigar conjuntos de restrições ilimitados.