Data-Driven Distributed Optimization via Aggregative Tracking and Deep-Learning

Sintesi Tecnica: Ottimizzazione Distribuita Data-Driven tramite Tracking Aggregativo e Deep-Learning (DELTA)

Formulazione del Problema
Il documento affronta la sfida dell'ottimizzazione distribuita in un framework aggregativo in cui una rete di $N$ agenti minimizza cooperativamente la somma delle proprie funzioni di costo locali. A differenza della standard ottimizzazione distribuita, il costo locale di ogni agente $f_i$ dipende non solo dalla propria variabile decisionale $x_i$, ma anche da una variabile aggregativa globale $\sigma(x)$, definita come la media dei contributi locali $\phi_i(x_i)$.

Lo scenario specifico considerato è data-driven e sconosciuto:

1. Le funzioni $f_i$ sono interamente sconosciute agli agenti.
2. Gli agenti possono ottenere solo un singolo campione di feedback del proprio costo locale per iterazione (una valutazione "1-point") in un punto scelto $(u_{x,i}, u_{\sigma,i})$.
3. Le quantità globali (la variabile aggregativa $\sigma(x)$ e la derivata del costo globale rispetto ad essa) non sono disponibili localmente.

Questa configurazione è motivata da applicazioni nella robotica cooperativa e nell'ottimizzazione personalizzata, dove le funzioni di costo possono rappresentare l'insoddisfazione dell'utente o vincoli fisici che sono difficili da modellare analiticamente ma che possono essere campionati tramite sensori o feedback dell'utente.

Metodologia: L'Algoritmo DELTA
Gli autori propongono DELTA (DEep-Learning aggregative TrAcking), un algoritmo distribuito che opera su una singola scala temporale e integra tre componenti concomitanti:

1. Modulo Orientato all'Apprendimento (Learning-Oriented Module):

   • Ogni agente $i$ impiega una rete neurale (NN) locale $\hat{f}_i(\cdot, \theta_i)$ per approssimare la funzione di costo incognita $f_i$ e i suoi gradienti.
   • Invece di addestrare la rete fino alla convergenza tra i passi di ottimizzazione (il che è computazionalmente costoso e richiede molteplici campioni), la NN viene aggiornata tramite un singolo passo di discesa del gradiente utilizzando il singolo campione di costo ottenuto in ogni iterazione.
   • Per garantire l'eccitazione persistente per l'apprendimento, l'algoritmo inietta segnali di dither ($d_{x,i}, d_{\sigma,i}$) nei punti di campionamento.
   • La NN approssima la direzione di discesa, sostituendo efficacemente la necessità di una conoscenza esplicita del gradiente.

2. Routine Orientata all'Ottimizzazione (Optimization-Oriented Routine):

   • Gli agenti eseguono un aggiornamento di tipo gradiente distribuito utilizzando i gradienti approssimati forniti dalle loro NN locali.
   • La regola di aggiornamento combina il gradiente locale stimato $\nabla_1 \hat{f}_i$ con un termine che coinvolge la derivata della funzione di aggregazione $\nabla \phi_i$ e la componente del gradiente globale stimata.

3. Meccanismo Orientato al Tracking (Tracking-Oriented Mechanism):

   • Poiché le quantità globali $\sigma(x)$ e la somma delle derivate dei gradienti locali non sono disponibili, gli agenti mantengono variabili ausiliarie ($w_i$ e $z_i$).
   • Queste variabili vengono aggiornate tramite una dinamica di consenso perturbata (utilizzando una matrice di adiacenza doppiamente stocastica) per ricostruire localmente la variabile aggregativa globale mancante e la componente del gradiente globale.

Analisi Teorica e Risultati
La stabilità e la convergenza di DELTA sono analizzate utilizzando strumenti della teoria dei sistemi, specificamente la separazione delle scale temporali (timescale separation) e la teoria dell'approssimazione a tempo discreto. L'analisi tratta l'algoritmo come un sistema a due scale temporali variabili, separando le dinamiche veloci (tracking e apprendimento) dalle dinamiche lente (ottimizzazione).

• Garanzia di Convergenza: Sotto l'ipotesi di convessità forte del costo globale e continuità Lipschitz delle funzioni e delle loro approssimazioni, gli autori dimostrano che l'algoritmo converge linearmente a un intorno della soluzione ottimale $x^*$.
• Limite di Errore: Il raggio di questo intorno dipende esplicitamente dal parametro $\epsilon$, che rappresenta l'errore massimo di ricostruzione delle reti neurali (ovvero, l'accuratezza dell'approssimazione della NN alla convergenza).
• Caso Ideale: Nel limite teorico in cui le reti neurali raggiungono una stima perfetta ($\epsilon = 0$), l'algoritmo converge esattamente alla soluzione ottimale.
• Robustezza: Il design permette all'algoritmo di adattarsi a funzioni di costo variabili nel tempo o a disturbi senza richiedere un riavvio completo dei processi di addestramento o di tracking.

Contributi Chiave

1. Integrazione Innovativa: Il documento introduce uno schema innovativo che combina l'apprendimento tramite reti neurali con l'ottimizzazione aggregativa distribuita e il gradient tracking, specificamente progettato per scenari con sole valutazioni di costo a punto singolo.
2. Superamento dei Limiti del "1-Point": I metodi standard a punto singolo di ordine zero spesso soffrono di scarse velocità di convergenza o alta varianza. DELTA affronta questo problema integrando una strategia di apprendimento dinamico (NN) che apprende la direzione di discesa nel tempo senza aumentare il numero di valutazioni del costo per iterazione.
3. Prova di Convergenza Rigorosa: Gli autori forniscono una prova formale di convergenza lineare in un intorno dell'ottimo, caratterizzando esplicitamente il compromesso tra l'accuratezza dell'approssimazione della rete neurale e l'errore di ottimizzazione finale.
4. Gestione di Ambienti Sconosciuti: Il framework è progettato per funzioni di costo completamente sconosciute, distinguendosi dai lavori precedenti in cui parti della funzione di costo erano note o in cui erano richiesti più campioni per iterazione.

Significato e Rivendicazioni
Il documento afferma che DELTA offre una soluzione pratica per l'ottimizzazione personalizzata e il controllo cooperativo in ambienti sconosciuti o non stazionari (ad esempio, collaborazione uomo-robot). Sfruttando la sinergia tra apprendimento, ottimizzazione e tracking, l'algoritmo si adatta ai cambiamenti nelle funzioni di costo in modo dinamico.

Gli autori osservano che, sebbene una versione preliminare di questo lavoro esistesse per contesti time-varying con molteplici campioni e addestramento completo della NN, il contributo attuale è tecnicamente più impegnativo: opera con singoli campioni per iterazione e addestramento NN a singolo step, richiedendo un'integrazione più complessa dell'analisi delle dinamiche di apprendimento con le dinamiche di ottimizzazione e di consenso. Simulazioni numeriche su una rete di 20 agenti validano i risultati teorici, dimostrando la convergenza verso l'intorno ottimale e la robustezza rispetto a cambiamenti improvvisi nelle funzioni di costo locali.