Smooth globally PLI functions are nonlinear least-squares, and so are their gradient-dominated cousins

Resumo Técnico: Funções PŁ Suaves Globais são Mínimos Quadrados Não Lineares, e Seus Parentes de Gradiente Dominado Também São

Enunciado do Problema
O artigo aborda uma limitação na teoria estrutural da otimização suave desenvolvida por Boumal, Criscitiello e Rebjock (BCR) [1]. BCR provou que uma função suave $f$ em uma variedade de Riemann completa e contraível satisfazendo a desigualdade de Polyak–Łojasiewicz (PŁ) global, $\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f^*)$, é necessariamente da forma $f = f^* + \|\phi\|^2$ para uma submersão suave $\phi$. Isso implica que a função é um problema de "mínimos quadrados não lineares" com uma variedade de minimizadores $S$ que é uma subvariedade suave e propriamente imersa.

No entanto, a desigualdade PŁ global falha em vários problemas críticos de controle e aprendizado, notadamente na otimização de políticas de LQR (Regulador Quadrático Linear) em tempo contínuo e na regressão logística. Nesses casos, o gradiente permanece limitado enquanto a perda cresce ilimitadamente, violando o requisito de que a cota inferior do gradiente $\alpha(r)$ seja ilimitada (especificamente, $\alpha(r) \sim \sqrt{r}$ quando $r \to \infty$). Este artigo investiga se as profundas conclusões estruturais de BCR dependem da força global da desigualdade PŁ ou apenas de seu comportamento local próximo aos minimizadores e de sua uniformidade nos conjuntos de nível.

Metodologia
O autor introduz uma condição relaxada, denominada $s_{gl}$-PŁI (desigualdade PŁ semi-global), que corresponde à condição $(GD_\alpha)$ com um testemunho $\alpha$ que é positivo definido e satisfaz uma condição de crescimento quadrático local (Condição A) próximo à origem. Especificamente, o artigo substitui a desigualdade global $\|\nabla f\| \geq \sqrt{2\mu h}$ por:
$$\|\nabla f(x)\| \geq \alpha(h(x))$$
onde $\alpha$ é positivo definido e satisfaz $\alpha(s)^2 \geq 2\mu s$ para valores pequenos de $s$ (próximo ao conjunto de minimizadores $S$).

A metodologia procede em duas trilhas paralelas:

1. Prova Direta: O autor reexamina as provas em [1] para identificar exatamente quais etapas dependem da desigualdade PŁ global. Demonstra-se que os resultados estruturais (estrutura de variedade de $S$, existência de uma estrutura de fibrado, e a forma normal) dependem apenas de:

   • Comportamento Local (J1): O expoente de Łojasiewicz sendo $1/2$ próximo a $S$ (garantindo que $S$ seja uma variedade e que o Hessiano seja não degenerado em direções normais).
   • Uniformidade (J2): O gradiente ser limitado longe de zero em cada conjunto de nível $h(x) = c > 0$ (garantindo que as trajetórias não escapem para o infinito).
   • A cota quantitativa global (J3) mostra-se desnecessária para as conclusões estruturais.
     O autor constrói um "dessingularizador" $\Psi(h) = \int_0^h ds/\alpha(s)$ para limitar o comprimento das trajetórias e provar a convergência, substituando as estimativas de crescimento quadrático usadas em [1].

2. Prova por Reparametrização: Um caminho mais curto demonstra que, para qualquer função que satisfaça a condição relaxada, pode-se construir uma função companheira $g = \theta(f - f^*)$ que satisfaz a desigualdade PŁ global em relação a uma nova métrica. Aplicar os teoremas de BCR a $g$ e transportar os resultados de volta para $f$ produz as mesmas conclusões estruturais.

Principais Contribuições e Resultados

• Generalização dos Teoremas Estruturais: O artigo prova que todas as conclusções estruturais de [1] mantêm-se literalmente sob a condição $s_{gl}$-PŁI (equivalentemente, sob a condição de que $f$ é $\alpha$-dominada pelo gradiente com $\alpha$ satisfazendo a Condição A).

  • Estrutura de Variedade: O conjunto de minimizadores $S$ é uma subvariedade suave e propriamente imersa.
  • Forma Normal: Se a variedade $M$ for contraível, $f$ é globalmente difeomorfa a uma soma de quadrados: $f(x) = f^* + \|\phi(x)\|^2$, onde $\phi: M \to \mathbb{R}^k$ é uma submersão suave.
  • Estrutura de Fibrado: O mapa de ponto final do fluxo de gradiente é um fibrado de fibras sobre $S$ com fibras difeomorfas a $\mathbb{R}^k$.
  • Convexidade Oculta: Em uma variedade contraível, existe uma métrica de Riemann completa (dependente de $f$) para a qual $f$ é geodesicmente convexa e globalmente 1-PŁ.

• Nitidez e Necessidade: O artigo fornece contraexemplos elementares para mostrar que os dois componentes da hipótese são indispensáveis:

  • Remover o crescimento quadrático local (Condição A) permite minimizadores degenerados onde $S$ não é uma variedade (ex: $f(x,y)=x^2y^2$).
  • Remover a positividade uniforme do gradiente nos conjuntos de nível (permitindo que $\alpha \to 0$ no infinito) permite que as trajetórias tenham comprimento infinito ou falhem em convergir para um minimizador, mesmo que a função seja invexa.

• Perda Quantitativa: O artigo identifica explicitamente o que é perdido ao enfraquecer a hipótese: a estimativa de crescimento quadrático global ($h(x) \geq c \cdot \text{dist}(x, S)^2$). Sob $s_{gl}$-PŁI, esse crescimento é garantido apenas localmente perto de $S$. Globalmente, o crescimento pode ser subquadrático (ex: linear ou logarítmico), e a taxa de convergência do fluxo de gradiente não é mais exponencialmente global.

• Transversalidade de Robustez e Estrutura: Uma contribuição conceitual significativa é a demonstração de que "estrutura" (a forma normal) e "robustez" (Estabilidade de Entrada-Estado, ISS) são governadas por extremidades opostas da função de comparação $\alpha$.

  • A Estrutura depende de $\alpha$ próximo à origem (Condição A).
  • A Robustez (ISS/NSS) depende de $\alpha$ no infinito (ex: $\alpha \in \mathcal{K}_\infty$).
    O artigo mostra que essas propriedades são logicamente independentes; uma função pode ter uma estrutura perfeita de mínimos quadrados não lineares mas falhar em ser robusta (se $\alpha \to 0$ no infinito), ou ser robusta mas carecer de um minimizador (se $\alpha$ é grande no infinito, mas falha perto de zero).

Aplicações a Problemas Específicos
O artigo aplica estes resultados a dois problemas motivadores onde a PŁ global falha:

1. LQR em Tempo Contínuo: O artigo confirma que a perda LQR satisfaz $s_{gl}$-PŁI (e a mais forte $sat$-PŁI). Consequentemente, o conjunto de ganhos estabilizadores $D$ é difeomorfo a $\mathbb{R}^{mn}$, e a função de perda admite uma forma normal global $L = L^* + \|\phi(k)\|^2$. Isso resolve a questão topológica da forma do conjunto estabilizador sem depender da desigualdade PŁ global.
2. Regressão Logística: Para dados não linearmente separáveis, a perda de entropia cruzada satisfaz $s_{gl}$-PŁI. O artigo conclui que o cenário de perda é globalmente difeomorfo a um paraboloide padrão, reforçando que o cenário não possui obstruções topológicas "ocultas", embora o gradiente sature no infinito.

Significância e Alegações
O artigo alega que a desigualdade PŁ global em [1] é "mais forte do que o que as provas requerem". A teoria estrutural das funções de mínimos quadrados não lineares é robusta ao tamanho global do gradiente, desde que o gradiente não se anule nos conjuntos de nível e se comporte quadraticamente próximo aos minimizadores.

O autor é modesto quanto ao escopo da generalização:

• A generalização é "aparente" em um sentido geomético preciso: pelo Teorema 4.8, qualquer função nesta classe torna-se globalmente PŁ em relação a alguma métrica completa (dependente da função). Assim, a classe de conjuntos de minimizadores realizáveis (geometria) permanece inalterada; apenas a classe de funções representáveis sob uma métrica fixa é ampliada.
• O artigo não pretende melhorar as taxas de convergência ou as garantias de robustez; estas permanecem no domínio da hierarquia de funções de comparação (ex: $sat$-PŁI,$K$-PŁ) conforme estabelecido em [13, 4, 5].
• A principal contribuição é esclarecer as dependências lógicas dos teoremas estruturais em [1] e estender sua aplicabilidade a importantes problemas de controle e aprendizado que anteriormente eram excluídos pela estrita exigência da PŁ global.