Stochastic Mirror Descent under Iterate-Dependent Markov Noise: Analysis in the Asymptotic and Finite Time Regimes

Resumo Técnico: Descenso de Espelho Estocástico Sob Ruído de Markov Dependente da Iteração

Formulação do Problema
Este trabalho aborda um problema de otimização estocástica onde a distribuição de amostragem depende da variável de decisão $x$. O objetivo é minimizar:
$$\min_{x \in \mathcal{X}} f(x) := \mathbb{E}_{s \sim \mu_x}[F(x, s)] = \int_S F(x, s) d\mu_x(s)$$
onde $\mathcal{X} \subseteq \mathbb{R}^d$ é um conjunto convexo compacto. Diferentemente da otimização estocástica clássica, onde a distribuição é fixa, aqui a medida de probabilidade $\mu_x$ varia com $x$. Este cenário modela incertezas dependentes de decisão encontradas em aprendizado por reforço, processos de Markov controlados e predição performativa.

Um desafio crítico neste cenário é que a amostragem direta de $\mu_x$ não está disponível. Em vez disso, para uma decisão $x$ dada, as amostras são geradas via uma cadeia de Markov dependente da iteração com kernel de transição $\Pi(x, \cdot)$ e distribuição estacionária $\mu_x$. Isso introduz duas complicações principais:

1. Viesamento: O oráculo estocástico não é mais não viesado no sentido clássico, pois a distribuição se desloca com a iteração.
2. Dependência Temporal: A sequência de ruído é gerada por um processo de Markov, tornando as técnicas padrão para ruído independente e identicamente distribuído (i.i.d.) inaplicáveis.

Metodologia e Algoritmo
Os autores propõem e analisam o algoritmo Descenso de Espelho de Markov Estocástico (SMMD). A regra de atualização na iteração $n$ é dada por:
$$x_{n+1} = \arg\min_{x \in \mathcal{X}} \left\{ \langle g(x_n, S_n), x \rangle + \frac{1}{\alpha_n} D_R(x, x_n) \right\}$$
onde $g(x_n, S_n)$ é um subgradiente estocástico, $\alpha_n$ é o tamanho do passo e $D_R$ é a divergência de Bregman induzida por um mapa de espelho fortemente convexo $R$. O estado $S_n$ evolui de acordo com o kernel de transição $\Pi(x_n, S_n)$.

A análise depende de várias ferramentas técnicas fundamentais:

• Aproximação Estocástica com Ruído de Markov: Os autores representam as iterações discretas como um esquema de aproximação estocástica. Eles derivam uma representação equivalente da atualização envolvendo um mapa de valor conjunto $H_2$ que incorpora o subgradiente estocástico, o cone normal do conjunto de restrições e termos de erro de ordem superior.
• Abordagem de Sistemas Dinâmicos: Para estabelecer a convergência, o processo discreto é interpolado em uma trajetória de tempo contínuo. O comportamento assintótico é caracterizado pela análise de estabilidade de uma inclusão diferencial impulsionada pelo integral de Aumann do mapeamento de subgradiente de valor conjunto.
• Decomposição da Equação de Poisson: Para análise de tempo finito, o ruído de Markov é decomposto usando uma equação de Poisson associada ao kernel de Markov. Isso separa o ruído em um termo de diferença de martingale (que pode ser controlado via desigualdades de concentração) e um termo de viés que desaparece assintoticamente.

Contribuições e Resultados Principais

1. Convergência Quase Certa (Convexa e Não Convexa):
   O artigo estabelece a convergência quase certa das iterações do SMMD para o conjunto de pontos estacionários tanto para objetivos convexos quanto não convexos.

   • Regularidade: Uma contribuição significativa é que este resultado requer apenas continuidade de Lipschitz da função objetivo. A diferenciabilidade não é assumida para a prova de convergência, permitindo que o método lide com problemas não suaves.
   • Estrutura: Isso é apresentado como a primeira análise de um método baseado em gradiente estocástico no cenário de Markov dependente da iteração que lida simultaneamente com objetivos não convexos e não suaves.

2. Limites de Concentração de Tempo Finito (Objetivos Suaves):
   Para objetivos suaves, os autores derivam limites de concentração de tempo finito.

   • Cenário Convexo: A complexidade de amostra derivada corresponde à taxa clássica do descenso de espelho estocástico sob ruído i.i.d. Especificamente, o número de iterações necessário para alcançar uma solução $\epsilon$-ótima com confiança $1-p$ escala como $\tilde{O}(1/\epsilon^2)$.
   • Cenário Não Convexo: Os autores derivam um limite de complexidade de amostra em termos da norma do gradiente Riemanniano sobre o simplex de probabilidade. Esta métrica, definida via o Hessiano do mapa de espelho, é mostrada como a medida apropriada de estacionariedade para geometrias não euclidianas restritas. Até onde os autores sabem, este é o primeiro resultado de tempo finito para descenso de espelho na presença de ruído de Markov, e potencialmente o primeiro tal resultado para descenso de espelho sob ruído i.i.d. no cenário não convexo restrito usando esta norma de gradiente específica.

3. Análise Específica no Simplex de Probabilidade:
   No contexto do simplex de probabilidade (comum em otimização de políticas), os autores utilizam a entropia negativa como mapa de espelho. Eles mostram que o cone tangente torna-se um espaço linear no interior relativo, simplificando o operador de projeção. Eles provam que o mapeamento da iteração para a direção de descenso projetada é contínua de Lipschitz, o que é crucial para os limites de tempo finito.

Significância e Afirmações
O artigo afirma fornecer uma estrutura unificada de convergência para o descenso de espelho estocástico sob ruído de Markov dependente do estado. Sua significância primária reside em preencher a lacuna entre a otimização estocástica padrão (ruído i.i.d.) e cenários complexos dependentes de decisão onde a distribuição de dados evolui com as decisões do algoritmo.

Os autores enfatizam que seus resultados estendem a literatura existente de três maneiras específicas:

• Eles vão além dos kernels de transição independentes do estado (onde a distribuição estacionária é fixa) para kernels dependentes da iteração.
• Eles fornecem garantias de convergência quase certa, que são mais fortes que a convergência esperada ($L_1$ ou $L_2$) tipicamente encontrada em trabalhos anteriores sobre ruído de Markov.
• Eles abordam objetivos não suaves na análise de convergência quase certa, uma característica frequentemente ausente na literatura de ruído de Markov, que tipicamente assume suavidade.

O trabalho destaca que, embora o ruído de Markov introduza viés e dependência temporal, o algoritmo de Descenso de Espelho Estocástico permanece robusto, alcançando taxas de convergência comparáveis ao caso i.i.d. no regime convexo e fornecendo garantias rigorosas de tempo finito para problemas não convexos no simplex de probabilidade.