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

Sintesi Tecnica: Discesa dello Specchio Stocastica sotto Rumore Markoviano Dipendente dall'Iterata

Formulazione del Problema
Questo lavoro affronta un problema di ottimizzazione stocastica in cui la distribuzione di campionamento dipende dalla variabile decisionale $x$. L'obiettivo è minimizzare:
$$\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)$$
dove $\mathcal{X} \subseteq \mathbb{R}^d$ è un insieme convesso compatto. A differenza dell'ottimizzazione stocastica classica in cui la distribuzione è fissa, qui la misura di probabilità $\mu_x$ varia con $x$. Questo scenario modella l'incertezza dipendente dalle decisioni, riscontrabile nell'apprendimento per rinforzo, nei processi di Markov controllati e nella previsione performativa.

Una sfida critica in questo contesto è che il campionamento diretto da $\mu_x$ non è disponibile. Invece, per una data decisione $x$, i campioni sono generati tramite una catena di Markov dipendente dall'iterata con nucleo di transizione $\Pi(x, \cdot)$ e distribuzione stazionaria $\mu_x$. Ciò introduce due complicazioni principali:

1. Bias: L'oracolo stocastico non è più inalterato nel senso classico perché la distribuzione si sposta con l'iterata.
2. Dipendenza Temporale: La sequenza di rumore è generata da un processo di Markov, rendendo inapplicabili le tecniche standard per il rumore indipendente e identicamente distribuito (i.i.d.).

Metodologia e Algoritmo
Gli autori propongono e analizzano l'algoritmo Discesa dello Specchio di Markov Stocastica (SMMD). La regola di aggiornamento all'iterazione $n$ è data da:
$$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\}$$
dove $g(x_n, S_n)$ è un subgradiente stocastico, $\alpha_n$ è il passo di apprendimento e $D_R$ è la divergenza di Bregman indotta da una mappa specchio fortemente convessa $R$. Lo stato $S_n$ evolve secondo il nucleo di transizione $\Pi(x_n, S_n)$.

L'analisi si basa su diversi strumenti tecnici chiave:

• Approssimazione Stocastica con Rumore Markoviano: Gli autori rappresentano le iterazioni discrete come uno schema di approssimazione stocastica. Derivano una rappresentazione equivalente dell'aggiornamento che coinvolge una mappa a valori insiemistici $H_2$ che incorpora il subgradiente stocastico, il cono normale dell'insieme vincolato e termini di errore di ordine superiore.
• Approccio ai Sistemi Dinamici: Per stabilire la convergenza, il processo discreto viene interpolato in una traiettoria a tempo continuo. Il comportamento asintotico è caratterizzato dall'analisi di stabilità di un'inclusione differenziale guidata dall'integrale di Aumann della mappa a valori insiemistici del subgradiente.
• Decomposizione dell'Equazione di Poisson: Per l'analisi a tempo finito, il rumore markoviano viene decomposto utilizzando un'equazione di Poisson associata al nucleo di Markov. Ciò separa il rumore in un termine di differenza martingala (che può essere controllato tramite disuguaglianze di concentrazione) e un termine di bias che svanisce asintoticamente.

Contributi e Risultati Chiave

1. Convergenza Quasi Certa (Convessa e Non Convessa):
   Il lavoro stabilisce la convergenza quasi certa delle iterazioni SMMD all'insieme dei punti stazionari sia per obiettivi convessi che non convessi.

   • Regolarità: Un contributo significativo è che questo risultato richiede solo la continuità di Lipschitz della funzione obiettivo. Non si assume la differenziabilità per la prova di convergenza, permettendo al metodo di gestire problemi non lisci.
   • Quadro: Questo è presentato come la prima analisi di un metodo basato sul gradiente stocastico nel contesto markoviano dipendente dall'iterata che gestisce simultaneamente obiettivi non convessi e non lisci.

2. Limiti di Concentrazione a Tempo Finito (Obiettivi Lisci):
   Per obiettivi lisci, gli autori derivano limiti di concentrazione a tempo finito.

   • Contesto Convesso: La complessità campionaria derivata corrisponde al tasso classico della discesa dello specchio stocastica sotto rumore i.i.d. Nello specifico, il numero di iterazioni richiesto per raggiungere una soluzione $\epsilon$-ottimale con confidenza $1-p$ scala come $\tilde{O}(1/\epsilon^2)$.
   • Contesto Non Convesso: Gli autori derivano un limite di complessità campionaria in termini della norma del gradiente Riemanniano sul semplice di probabilità. Questa metrica, definita tramite l'Hessiano della mappa specchio, si dimostra essere la misura appropriata di stazionarietà per geometrie vincolate non euclidee. A conoscenza degli autori, questo è il primo risultato a tempo finito per la discesa dello specchio in presenza di rumore markoviano, e potenzialmente il primo risultato del genere per la discesa dello specchio sotto rumore i.i.d. nel contesto non convesso vincolato utilizzando questa specifica norma del gradiente.

3. Analisi Specifica sul Simple di Probabilità:
   Nel contesto del semplice di probabilità (comune nell'ottimizzazione delle politiche), gli autori utilizzano l'entropia negativa come mappa specchio. Dimostrano che il cono tangente diventa uno spazio lineare nell'interno relativo, semplificando l'operatore di proiezione. Dimostrano che la mappatura dall'iterata alla direzione di discesa proiettata è continua di Lipschitz, il che è cruciale per i limiti a tempo finito.

Significato e Affermazioni
Il lavoro afferma di fornire un quadro unificato di convergenza per la discesa dello specchio stocastica sotto rumore markoviano dipendente dallo stato. Il suo significato principale risiede nel colmare il divario tra l'ottimizzazione stocastica standard (rumore i.i.d.) e contesti complessi dipendenti dalle decisioni in cui la distribuzione dei dati evolve con le decisioni dell'algoritmo.

Gli autori sottolineano che i loro risultati estendono la letteratura esistente in tre modi specifici:

• Si spingono oltre i nuclei di transizione indipendenti dallo stato (dove la distribuzione stazionaria è fissa) verso nuclei dipendenti dall'iterata.
• Forniscono garanzie di convergenza quasi certa, che sono più forti della convergenza attesa ($L_1$ o $L_2$) tipicamente trovata in lavori precedenti sul rumore markoviano.
• Affrontano obiettivi non lisci nell'analisi di convergenza quasi certa, una caratteristica spesso assente nella letteratura sul rumore markoviano che tipicamente assume la liscietà.

Il lavoro evidenzia che, sebbene il rumore markoviano introduca bias e dipendenza temporale, l'algoritmo di Discesa dello Specchio Stocastica rimane robusto, raggiungendo tassi di convergenza comparabili al caso i.i.d. nel regime convesso e fornendo garanzie rigorose a tempo finito per problemi non convessi sul semplice di probabilità.