Resumo Técnico: Métodos de Viabilidade Aleatorizada para Otimização Restrita com Tamanhos de Passo Adaptativos

Formulação do Problema

O artigo aborda o problema de otimização restrita:
$$\min_{x} f(x) \quad \text{sujeito a} \quad x \in X \cap Y$$
onde $Y \subseteq \mathbb{R}^n$ é um conjunto convexo e fechado que é "fácil de projetar" (ex: bolas ou caixas), e $X$ é definido como a interseção de $m$ conjuntos de nível inferior de funções convexas:
$$X := \bigcap_{i=1}^m \{x \in \mathbb{R}^n \mid g_i(x) \leq 0\}$$
O desafio principal surge quando $m$ é grande e projetar na interseção $X$ é computacionalmente intratável. Os autores consideram dois regimes distintos para a função objetivo $f$:

1. Fortemente convexa e Lipschitz-suave: $f$ possui um minimizador único e gradientes suaves.
2. Convexa e possivelmente não suave: $f$ pode carecer de suavidade e de convexidade forte.

O objetivo é desenvolver algoritmos que minimizem $f$ garantindo a viabilidade em relação a $X$ sem exigir a projeção total sobre $X em cada iteração.

Metodologia

A abordagem proposta desacopla a minimização do objetivo da satisfação das restrições usando uma estrutura iterativa de dois passos:

1. Atualizações de Viabilidade Aleatorizada (Algoritmo 1)

Para lidar com as restrições complexas $X$, os autores empregam um algoritmo de viabilidade aleatorizada baseado nos passos de Polyak. Em vez de projetar no conjunto completo $X$, o algoritmo:

• Amostra um único índice de restrição $\omega_k$ uniformemente de $\{1, \dots, m\}$.
• Computa um subgradiente da função de violação de restrição amostrada $g^+_{\omega_k}(x) = \max\{0, g_{\omega_k}(x)\}$.
• Realiza um passo de subgradiente com um tamanho de passo de Polyak escalonado por um parâmetro $\beta \in (0, 2)$.
• Projeta o resultado de volta no conjunto "fácil" $Y$.
• Repete este processo $N_k$ vezes por iteração externa, onde $N_k$ pode ser determinístico ou aleatório.

A saída deste laço interno, $x_k$, serve como uma atualização de viabilidade que reduz a distância ao conjunto viável $X \cap Y$ geometricamente.

2. Minimização do Objetivo com Passos Adaptativos

O laço externo minimiza $f(x)$ usando a saída das atualizações de viabilidade. O artigo propõe duas estratégias específicas baseadas nas propriedades de $f$:

• Caso (i): Fortemente Convexa e Suave (Algoritmo 2)
  O método combina passos de descida de gradiente com as atualizações de viabilidade aleatorizada. Os autores introduzem um esquema de tamanho de passo adaptativo que não requer conhecimento prévio da constante de convexidade forte $\mu$ ou da constante de Lipschitz $L$. O tamanho do passo é ajustado com base na norma do gradiente e em uma tolerância alvo $\epsilon$.

• Caso (ii): Convexa e Não Suave (Algoritmos 3 & 4)
  Para objetivos não suaves, o artigo introduz um esquema totalmente livre de parâmetros baseado em Distância sobre Subgradientes Pesados (DoWS), uma variante do método DoWG.

  • Algoritmo 3 (DoWS): Assume que o conjunto viável $Y$ é limitado. Ele rastreia a distância máxima das iterações de um ponto inicial e acumula normas de subgradientes ponderados para determinar o tamanho do passo.
  • Algoritmo 4 (T-DoWS): Uma variante "domesticada" (tamed) projetada para conjuntos ilimitados (ex: $Y = \mathbb{R}^n$). Ele modifica o escalonamento do tamanho do passo para garantir que as iterações permaneçam limitadas sob uma suposição de conjunto de nível inferior de $f$, removendo a necessidade de limitação a priori de $Y$.

Principais Contribuições

1. Conexão Teórica de Limites de Erro e Multiplicadores Duais:
   Os autores estabelecem uma conexão entre limites de erro globais e multiplicadores duais sob a condição de Slater Forte. Eles provam que um limite superior uniforme para os multiplicadores duais existe sem assumir a compacidade de $Y$, um resultado derivado de trabalhos anteriores (Lewis & Pang, 1998; Bertsekas, 1999; Mangasarian, 1998), mas explicitamente vinculado aqui à estrutura específica das restrições.

2. Convergência Linear para Problemas Fortemente Convexos:
   Para objetivos fortemente convexos e suaves, o artigo prova a convergência linear em expectativa dos valores da função objetivo para qualquer tolerância prescrita $\epsilon$. Isso é alcançado usando tamanhos de passo adaptativos e uma condição específica sobre o número de amostras de viabilidade $N_k$. Diferente de trabalhos anteriores, este resultado não assume subgradientes limitados das funções de restrição a priori, mas prova que eles são limitados quase certamente.

3. Métodos Totalmente Livres de Parâmetros para Problemas Não Suaves:
   O artigo apresenta o primeiro método totalmente livre de parâmetros para resolver o problema (P) sem projeções, combinando DoWS com atualizações de viabilidade aleatorizada.

   • Alcança uma taxa de pior caso de $O(1/\sqrt{T})$ em expectativa para objetivos convexos, possivelmente não suaves.
   • Introduz o T-DoWS (Algoritmo 4), que garante iterações limitadas e taxas de convergência ótimas mesmo quando o conjunto de restrição $Y$ é ilimitado, desde que os conjuntos de nível inferior de $f$ sejam limitados.

4. Análise de Estratégias de Amostragem Aleatória:
   Os autores analisam o impacto do número de amostras de viabilidade $N_k$ por iteração. Eles mostram que a inviabilidade das iterações diminui geometricamente quase certamente. Eles fornecem orientação teórica para escolher a distribuição de $N_k$ (ex: Poisson, Binomial ou crescimento determinístico) para alcançar taxas de convergência ótimas, demonstrando que taxas ótimas podem ser alcançadas com cronogramas de crescimento de tamanho de amostra específicos.

Resultados e Avaliação Empírica

Garantias Teóricas

• Caso Fortemente Convexo: O algoritmo atinge precisão $\epsilon$ em $O(\ln(1/\epsilon))$ iterações. O gap de inviabilidade decai geometricamente com o número de amostras $N_k$.
• Caso Convexo Não Suave: As iterações médias alcançam um limite de erro esperado de $O(1/\sqrt{T})$ (até fatores logarítmicos dependendo da razão do diâmetro do conjunto em relação à estimativa inicial). O limite de inviabilidade depende da distribuição de amostragem e diminui a uma taxa de $O(1/T)$ sob condições de amostragem específicas.

Simulações

Os autores validam seus métodos em três tipos de problemas:

1. Programação Quadrática com Restrições Quadráticas (QCQP): Demonstra convergência linear para o caso fortemente convexo e desempenho competitivo para o caso não suave em comparação com Arrow-Hurwicz, Alt-GDA e ACVI.
2. Máquinas de Vetores de Suporte (SVM): Mostra que os métodos propostos livres de parâmetros convergem sem exigir validação cruzada para o ajuste do tamanho do passo, ao contrário dos métodos primal-dual que sofrem de alto overhead computacional em cenários online.
3. Regressão Logística com Restrições de Equidade de Grupo: Ilustra a capacidade de lidar com restrições de equidade complexas (modeladas como interseções de conjuntos de nível inferior) enquanto alcança violação de viabilidade zero e converge para o valor ótimo da função objetivo.

Em todas as simulações, os algoritmos propostos (Algoritmos 2, 3 e 4) demonstram eficiência computacional, particularmente em cenários com um grande número de restrições onde a projeção total é inviável. Os métodos superam ou igualam as bases de estado da arte (ACVI, Arrow-Hurwicz) enquanto evitam a necessidade de ajuste de hiperparâmetros ou resolução de subproblemas em cada iteração.

Significância e Alegações

O artigo afirma avançar o campo da otimização restrita ao fornecer algoritmos computacionalmente eficientes, teoricamente fundamentados e totalmente livres de parâmetros para problemas com um grande número de restrições.

• Novidade: Os autores afirmam que esta é a primeira vez que uma combinação de DoWG (ou sua variante domesticada) com atualizações de viabilidade aleatorizada é estudada para otimização sem projeções.
• Robustez: Os métodos não exigem conhecimento de parâmetros específicos do problema (constantes de convexidade forte, constantes de Lipschitz ou valores ótimos), tornando-os adequados para aplicações práticas onde tal informação não está disponível.
• Escalabilidade: Ao usar atualizações de viabilidade aleatorizada, os algoritmos evitam o gargalo computacional de projetar na interseção de muitas restrições, escalando efetivamente para problemas de alta dimensão com milhares de restrições.

O trabalho une a lacuna entre métodos de viabilidade aleatorizada e métodos de gradiente adaptativos, oferecendo um framework unificado que se adapta tanto a objetivos suaves quanto não suaves, garantindo a viabilidade com decaimento geomético.