Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

Resumo Técnico: Limites de Erro, Condição PL, Crescimento Quadrático para Funções Fracamente Convexas e Convergências Lineares de Métodos de Ponto Proximal

Enunciado do Problema
Muitos problemas de otimização prática, particularmente em aprendizado de máquina e processamento de sinais, carecem de convexidade forte. Embora algoritmos de primeira ordem sejam conhecidos por alcançar convergência linear sob convexidade forte, estudos recentes mostraram que a convergência linear também pode ser garantida sob condições de regularidade mais fracas (ex: desigualdade de Polyak-Lojasiewicz, limites de erro, crescimento quadrático) para funções suaves e convexas. No entanto, as relações entre essas condições não eram bem compreendidas no contexto de funções não suaves e não convexas. Especificamente, a classe de funções fracamente convexas (funções $f$ tais que $f + \frac{\rho}{2}\|\cdot\|^2$ é convexa para algum $\rho \geq 0$) abrange muitos modelos modernos (ex: redes profundas não suaves, composições de funções convexas e suaves), mas carecia de um framework unificado conectando essas condições de regularidade. Além disso, provas existentes para a convergência linear do Método de Ponto Proximal (MPP) frequentemente dependiam de suposições restritivas (ex: minimizadores únicos, continuidade Lipschitz local do subdiferencial inverso) ou argumentos complexos.

Metodologia
O artigo emprega ferramentas da análise não suave, especificamente a noção de inclinação (slope), o princípio variacional de Ekeland e lemmas de estimativa de distância, para analisar as relações entre as condições de regularidade. Os autores definem cinco condições principais sobre um conjunto de nível $[f \leq f^\star + \nu]$:

1. Convexidade Forte (SC)
2. Desigualdade Secante Restrita (RSI)
3. Limite de Erro de Subdiferencial (EB)
4. Desigualdade de Polyak-Lojasiewicz (PL)
5. Crescimento Quadrático (QG)

Os autores utilizam a inclinação $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ (onde $\hat{\partial}f$ é o subdiferencial de Fréchet) para preencher a lacuna entre os contextos suave e não suave. Eles estabelecem implicações lógicas e equivalências entre essas condições, focando particularmente no caso onde a constante de crescimento quadrático $\mu_q$ excede o parâmetro de convexidade fraca $\rho$.

Com base nessas equivalências, o artigo analisa o Método de Ponto Proximal (MPP):
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
Os autores fornecem uma prova modular para a convergência linear tanto em contextos convexos quanto fracamente convexos. Eles também estendem a análise para o MPP Inexato (iMPP), onde os subproblemas são resolvidos aproximadamente, abordando sutilezas relativas aos critérios de parada e viabilidade (garantindo que as iteradas permaneçam dentro do domínio de $f$).

Principais Contribuições

1. Unificação das Condições de Regularidade para Funções Fracamente Convexas:
   O artigo estabelece a hierarquia e a equivalência das condições de regularidade para funções $\rho$-fracamente convexas.

   • Cadeia de Implicação Geral: $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$.
   • Equivalência sob $\mu_q > \rho$: Se uma função $\rho$-fracamente convexa satisfaz o Crescimento Quadrático com uma constante $\mu_q > \rho$, então todas as quatro condições $(RSI), (EB), (PL)$e$(QG)$ são equivalentes.
   • Os autores derivam conversões explícitas de coeficientes entre essas condições (resumidas na Tabela 1 do artigo), permitindo que profissionais traduzam constantes de uma condição para outra.

2. Provas Simplificadas de Convergência Linear para o MPP:
   O artigo apresenta uma prova simples e modular para a convergência linear do MPP para funções tanto convexas quanto fracamente convexas.

   • Caso Convexo: Sob qualquer uma das condições de regularidade equivalentes (PL, EB, RSI, QG), o MPP alcança convergência linear tanto para valores da função quanto para a distância ao conjunto de soluções. A prova relaxa suposições anteriores, removendo a exigência de um minimizador único ou de continuidade Lipschitz local do subdiferencial inverso.
   • Caso Fracamente Convexo: Os resultados são estendidos para funções $\rho$-fracamente convexas, desde que a inicialização esteja dentro de um conjunto de nível que satisfaça QG com $\mu_q > \rho$ e que os tamanhos de passo satisfaçam $1/c_k > \rho$.

3. Análise do MPP Inexato (iMPP):
   Os autores esclarecem as nuances da inexatidão e viabilidade no iMPP. Eles estabelecem a convergência linear para o iMPP sob critérios de parada padrão (critérios A e B de Rockafellar), desde que a função satisfaça QG em uma vizinhança do conjunto de soluções. A prova combina uma desigualdade chave da literatura prévia com o framework de condições de regularidade modular.

Resultados

• Teóricos: O Teorema 3.1 confirma que, para funções fracamente convexas, a equivalência das condições de regularidade ocorre se $\mu_q > \rho$. Isso generaliza resultados anteriores limitados a funções suaves ou convexas.
• Algorítmicos: Os Teoremas 4.2 e 4.3 demonstram que o MPP converge linearmente com taxas dependentes das constantes de regularidade (ex: $\omega_k = \frac{1}{1+c_k\mu_p}$). O Teorema 5.3 estende isso para o MPP inexato, mostrando que, desde que a inexatidão seja controlada (a soma dos erros seja finita), a taxa de convergência linear é preservada assintoticamente.
• Numéricos: Experimentos em problemas de SVM Linear, Lasso e Elastic-Net confirmam a convergência linear teórica do MPP. Os experimentos utilizam o pacote de modelagem YALMIP e o solver MOSEK, mostrando convergência rápida tanto nos gaps de valor de custo quanto na distância ao conjunto de soluções.

Significância e Alegações
O artigo afirma generalizar a compreensão das condições de regularidade do cenário suave/convexo para a classe mais ampla de funções não suaves fracamente convexas. Ao esclarecer as conexões entre essas condições, os autores fornecem um framework unificado que simplifica a análise de algoritmos iterativos.

Especificamente, o artigo afirma que:

• A equivalência das condições (RSI, EB, PL, QG) sob $\mu_q > \rho$ permite uma análise flexível; uma condição pode ser estabelecida para derivar resultados de convergência através das outras.
• As provas de convergência linear do MPP são mais simples e transparentes do que a literatura existente, evitando suposições restritivas como minimizadores únicos.
• Os resultados facilitam o desenvolvimento de algoritmos para otimização não suave, particularmente em aplicações de otimização conic de larga escala e aprendizado de máquina onde a convexidade fraca é prevalente.

Os autores observam que, embora a equivalência dessas condições fosse conhecida para funções suaves ou convexas, estender isso para o cenário de convexidade fraca e fornecer uma prova limpa para o MPP (incluindo versões inexatas) constitui a principal novidade. O trabalho é apresentado como uma versão estendida de um artigo de conferência, com a adição de provas detalhadas, conversões de coeficientes e análise estendida de MPP inexato.